Showing 1–50 of 78 results for author: Kueng, R

Harmoniq: Efficient Data Augmentation on a Quantum Computer Inspired by Harmonic Analysis

Authors: Kristina Kirova, Monika Doerfler, Franz Luef, Richard Kueng

Abstract: Quantum machine learning has attracted significant interest in recent years. Most existing approaches, however, are variational in nature and require extensive parameter optimization subroutines. Here, we propose a conceptually distinct quantum machine learning approach that goes beyond the variational paradigm. Harmoniq takes a recently developed data augmentation technique from quantum harmonic… ▽ More Quantum machine learning has attracted significant interest in recent years. Most existing approaches, however, are variational in nature and require extensive parameter optimization subroutines. Here, we propose a conceptually distinct quantum machine learning approach that goes beyond the variational paradigm. Harmoniq takes a recently developed data augmentation technique from quantum harmonic analysis and implements it as a stochastic mixture of n-qubit circuits with at most quadratic depth each. A key strength of Harmoniq is its modularity: viewed as a quantum process acting on density matrices, it can readily be combined with other quantum data processing and learning subroutines. A subsequent case study demonstrates this modularity by combining Harmoniq with stochastic amplitude encoding for the input density matrix and quantum PCA on the output density matrix. This results in a promising signal denoising pipeline that works particularly well in the small sample size regime. △ Less

Submitted 28 July, 2026; v1 submitted 20 April, 2026; originally announced April 2026.

Local robust shadows on a trapped ion computer -- a case study

Authors: Jadwiga Wilkens, Milena Guevara-Bertsch, Marwa Marso, Mederika Zangerl, Florian Girtler, Albert Frisch, Juris Ulmanis, Ingo Roth, Richard Kueng

Abstract: We experimentally demonstrate local robust shadows on a trapped-ion quantum computing system, a protocol developed to counteract measurement errors. We alternate between a calibration stage and the shadow estimation stage and also introduce Pauli-X-twirling before measurements in both stages to symmetrize error rates. We then demonstrate the protocol on a trapped-ion quantum computer with artifici… ▽ More We experimentally demonstrate local robust shadows on a trapped-ion quantum computing system, a protocol developed to counteract measurement errors. We alternate between a calibration stage and the shadow estimation stage and also introduce Pauli-X-twirling before measurements in both stages to symmetrize error rates. We then demonstrate the protocol on a trapped-ion quantum computer with artificially shortened measurement pulse duration. This yields faster experiments at the cost of increased error rates which are subsequently mitigated by the robust shadow protocol. We benchmark this approach on three exemplary quantum states: a local Haar random state, as well as standard and Pauli-correlation-encoded QAOA states. In all three cases, the local robust shadow protocol succeeds at mitigating the increased error rates hailing from shorter measurement pulse durations. △ Less

Submitted 26 April, 2026; v1 submitted 30 March, 2026; originally announced March 2026.

Comments: 7 pages, 2 figures

An Online Approach for Entanglement Verification Using Classical Shadows

Authors: Marwa Marso, Sabrina Herbst, Jadwiga Wilkens, Vincenzo De Maio, Ivona Brandic, Richard Kueng

Abstract: Quantum measurements are slow, while classical processors are fast, yet existing hybrid protocols never exploit this asymmetry. In this work, we propose an alternative formulation of classical estimators as online algorithms that are updated incrementally upon obtaining a new sample. Classical shadows are the natural fit for this approach: designed around the principle of measuring first and askin… ▽ More Quantum measurements are slow, while classical processors are fast, yet existing hybrid protocols never exploit this asymmetry. In this work, we propose an alternative formulation of classical estimators as online algorithms that are updated incrementally upon obtaining a new sample. Classical shadows are the natural fit for this approach: designed around the principle of measuring first and asking questions later, each snapshot is a self-contained classical description that can be processed immediately and independently. As a first demonstration, we focus on mixed state entanglement verification via PT-moments, moments of the partially transposed density matrix that provide experimentally accessible sufficient conditions for entanglement. We construct two unbiased online estimators that together characterize the fundamental challenge between memory footprint and per-shot computational cost: one scales to large systems at low moment order, the other handles high moment orders at the expense of memory exponential in system size. The online estimator certifies entanglement reliably and, by exploiting all $\binom{T}{m}$ combinations of snapshots, requires fewer samples than state-of-the-art baselines, turning entanglement detection from a purely offline diagnostic into a protocol that runs concurrently with the experiment. △ Less

Submitted 27 March, 2026; originally announced March 2026.

Comments: 20 pages, 10 figures

QuickQudits: A Framework for Efficient Simulation of Noisy Qudit Clifford Circuits via an Extended Stabilizer Tableau Formalism

Authors: Nina Brandl, Mykyta Cherniak, Johannes Kofler, Richard Kueng

Abstract: We present a comprehensive and self-contained framework for the efficient classical simulation of Clifford circuits acting on $d$-dimensional qudits, including realistic Pauli/Weyl noise via stochastic simulation. Our approach uses the stabilizer tableau formalism for qudits of arbitrary dimension and tracks both stabilizer and destabilizer generators under Clifford updates. The classical simulati… ▽ More We present a comprehensive and self-contained framework for the efficient classical simulation of Clifford circuits acting on $d$-dimensional qudits, including realistic Pauli/Weyl noise via stochastic simulation. Our approach uses the stabilizer tableau formalism for qudits of arbitrary dimension and tracks both stabilizer and destabilizer generators under Clifford updates. The classical simulation remains efficient with simple algebraic Clifford update rules over $\mathbb{Z}_d$. Computational basis measurements in prime dimensions are handled by a generalized Aaronson-Gottesman (CHP) procedure. In composite dimensions, $\mathbb{Z}_d$ is not a field and the standard tableau reduction fails, so we employ an exact Smith normal form decomposition to enable efficient sampling. Noise is modelled as probabilistic mixtures of Weyl operators that act only on the tableau's phase column. For fast simulation of noisy circuits, we support Pauli frames, respectively generalized Weyl frames, and introduce a noise-pushing technique that allows all noise processes to be consolidated into a single phase update at the end of the circuit. Using this representation, circuit fidelity can be determined entirely by the single accumulated phase-shift parameter $Δτ$, reducing fidelity estimation to a simple phase check per shot. Our codebase supports tableau simulation and conventional state-vector and density-matrix backends for qudits, and also includes circuit and tableau visualisations. Additionally, we provide tests and Jupyter notebooks for validation and illustration. This framework forms the basis for a scalable, open-source strong+weak stabilizer simulator including noise and can be found publicly available at https://github.com/QUICK-JKU/QuickQudits. △ Less

Submitted 24 March, 2026; originally announced March 2026.

Comments: 26 pages, 5 figures

Parametric Quantum State Tomography with HyperRBMs

Authors: Simon Tonner, Viet T. Tran, Richard Kueng

Abstract: Quantum state tomography (QST) is essential for validating quantum devices but suffers from exponential scaling in system size. Neural-network quantum states, such as Restricted Boltzmann Machines (RBMs), can efficiently parameterize individual many-body quantum states and have been successfully used for QST. However, existing approaches are point-wise and require retraining at every parameter val… ▽ More Quantum state tomography (QST) is essential for validating quantum devices but suffers from exponential scaling in system size. Neural-network quantum states, such as Restricted Boltzmann Machines (RBMs), can efficiently parameterize individual many-body quantum states and have been successfully used for QST. However, existing approaches are point-wise and require retraining at every parameter value in a phase diagram. We introduce a parametric QST framework based on a hypernetwork that conditions an RBM on Hamiltonian control parameters, enabling a single model to represent an entire family of quantum ground states. Applied to the transverse-field Ising model, our HyperRBM achieves high-fidelity reconstructions from local Pauli measurements on 1D and 2D lattices across both phases and through the critical region. Crucially, the model accurately reproduces the fidelity susceptibility and identifies the quantum phase transition without prior knowledge of the critical point. These results demonstrate that hypernetwork-modulated neural quantum states provide an efficient and scalable route to tomographic reconstruction across full phase diagrams. △ Less

Submitted 28 January, 2026; originally announced January 2026.

A Rigorous Quantum Framework for Inequality-Constrained and Multi-Objective Binary Optimization: Quadratic Cost Functions and Empirical Evaluations

Authors: Sebastian Egginger, Kristina Kirova, Sonja Bruckner, Stefan Hillmich, Richard Kueng

Abstract: The prospect of quantum solutions for complicated optimization problems is contingent on mapping the original problem onto a tractable quantum energy landscape, e.g. an Ising-type Hamiltonian. Subsequently, techniques like adiabatic optimization, quantum annealing, and the Quantum Approximate Optimization Algorithm (QAOA) can be used to find the ground state of this Hamiltonian. Quadratic Unconstr… ▽ More The prospect of quantum solutions for complicated optimization problems is contingent on mapping the original problem onto a tractable quantum energy landscape, e.g. an Ising-type Hamiltonian. Subsequently, techniques like adiabatic optimization, quantum annealing, and the Quantum Approximate Optimization Algorithm (QAOA) can be used to find the ground state of this Hamiltonian. Quadratic Unconstrained Binary Optimization (QUBO) is one prominent problem class for which this entire pipeline is well understood and has received considerable attention over the past years. In this work, we provide novel, tractable mappings for the maxima of multiple QUBO problems. Termed Multi-Objective Quantum Approximations, or MOQA for short, our framework allows us to recast new types of classical binary optimization problems as ground state problems of a tractable Ising-type Hamiltonian. This, in turn, opens the possibility of new quantum- and quantum-inspired solutions to a variety of problems that frequently occur in practical applications. In particular, MOQA can handle various types of routing and partitioning problems, as well as inequality-constrained binary optimization problems. △ Less

Submitted 15 October, 2025; originally announced October 2025.

A Rigorous Quantum Framework for Inequality-Constrained and Multi-Objective Binary Optimization

Authors: Sebastian Egginger, Kristina Kirova, Sonja Bruckner, Stefan Hillmich, Richard Kueng

Abstract: Encoding combinatorial optimization problems into physically meaningful Hamiltonians with tractable energy landscapes forms the foundation of quantum optimization. Numerous works have studied such efficient encodings for the class of Quadratic Unconstrained Binary Optimization (QUBO) problems. However, many real-world tasks are constrained, and handling equality and, in particular, inequality cons… ▽ More Encoding combinatorial optimization problems into physically meaningful Hamiltonians with tractable energy landscapes forms the foundation of quantum optimization. Numerous works have studied such efficient encodings for the class of Quadratic Unconstrained Binary Optimization (QUBO) problems. However, many real-world tasks are constrained, and handling equality and, in particular, inequality constraints on quantum computers remains a major challenge. In this letter, we show that including inequality constraints is equivalent to solving a multi-objective optimization. This insight motivates the Multi-Objective Quantum Approximation (MOQA) framework, which approximates the maximum via smaller $p$-norms and comes with rigorous performance guarantees. MOQA operates directly at the Hamiltonian level and is compatible with, but not restricted to, ground-state solvers such as quantum adiabatic annealing, the Quantum Approximate Optimization Algorithm (QAOA), or imaginary-time evolution. Moreover, it is not limited to quadratic functions. △ Less

Submitted 11 February, 2026; v1 submitted 15 October, 2025; originally announced October 2025.

An infinite hierarchy of multi-copy quantum learning tasks

Authors: Jan Nöller, Viet T. Tran, Mariami Gachechiladze, Richard Kueng

Abstract: Learning properties of quantum states from measurement data is a fundamental challenge in quantum information. The sample complexity of such tasks depends crucially on the measurement primitive. While shadow tomography achieves sample-efficient learning by allowing entangling measurements across many copies, it requires prohibitively deep circuits. At the other extreme, two-copy measurements alrea… ▽ More Learning properties of quantum states from measurement data is a fundamental challenge in quantum information. The sample complexity of such tasks depends crucially on the measurement primitive. While shadow tomography achieves sample-efficient learning by allowing entangling measurements across many copies, it requires prohibitively deep circuits. At the other extreme, two-copy measurements already yield exponential advantages over single-copy strategies in tasks such as Pauli tomography. In this work we show that such sharp separations extend far beyond the two-copy regime: for every prime c we construct explicit learning tasks of degree c, which are exponentially hard with (c - 1)-copy measurements but efficiently solvable with c-copy measurements. Our protocols are not only sample-efficient but also realizable with shallow circuits. Extending further, we show that such finite-degree tasks exist for all square-free integers c, pointing toward a general principle underlying their existence. Together, our results reveal an infinite hierarchy of multi-copy learning problems, uncovering new phase transitions in sample complexity and underscoring the role of reliable quantum memory as a key resource for exponential quantum advantage. △ Less

Submitted 9 October, 2025; originally announced October 2025.

Comments: 14+12 pages, 2 figures, comments are welcome

The Sound of Entanglement

Authors: Enar de Dios Rodríguez, Philipp Haslinger, Johannes Kofler, Richard Kueng, Benjamin Orthner, Alexander Ploier, Martin Ringbauer, Clemens Wenger

Abstract: The advent of quantum physics has revolutionized our understanding of the universe, replacing the deterministic framework of classical physics with a paradigm dominated by intrinsic randomness and quantum correlations. This shift has not only enabled groundbreaking technologies, such as quantum sensors, networks and computers, but has also unlocked entirely new possibilities for artistic expressio… ▽ More The advent of quantum physics has revolutionized our understanding of the universe, replacing the deterministic framework of classical physics with a paradigm dominated by intrinsic randomness and quantum correlations. This shift has not only enabled groundbreaking technologies, such as quantum sensors, networks and computers, but has also unlocked entirely new possibilities for artistic expressions. In this paper, we explore the intersection of quantum mechanics and art, focusing on the use of quantum entanglement and inherent randomness as creative tools. Specifically, we present The Sound of Entanglement, a live musical performance driven by real-time measurements of entangled photons in a Bell test. By integrating the measured quantum correlations as a central compositional element and synchronizing live visuals with experimental data, the performance offers a unique and unrepeatable audiovisual experience that relies on quantum correlations which cannot be produced by any classical device. Through this fusion of science and art, we aim to provide a deeper appreciation of quantum phenomena while expanding the boundaries of creative expression. △ Less

Submitted 10 September, 2025; originally announced September 2025.

Comments: 13 pages, 12 figures

One, Two, Three: One empirical evaluation of a two-copy shadow tomography scheme with triple efficiency

Authors: Viet T. Tran, Richard Kueng

Abstract: Shadow tomography protocols have recently emerged as powerful tools for efficient quantum state learning, aiming to reconstruct expectation values of observables with fewer resources than traditional quantum state tomography. For the particular case of estimating Pauli observables, entangling two-copy measurement schemes can offer an exponential improvement in sample complexity over any single-cop… ▽ More Shadow tomography protocols have recently emerged as powerful tools for efficient quantum state learning, aiming to reconstruct expectation values of observables with fewer resources than traditional quantum state tomography. For the particular case of estimating Pauli observables, entangling two-copy measurement schemes can offer an exponential improvement in sample complexity over any single-copy strategy conceivable [1, Huang, Kueng, Preskill, PRL(2021)]. A recent refinement of these ideas by King et al. [2, King, Gosset, Kothari, Babbush, SODA (2025)] does not only achieve polynomial sample complexity, but also maintains reasonable computational demands and utilizes joint measurements on only a small constant number of state copies. This `triple efficiency' is achievable for any subset of $n$-qubit Pauli observables, whereas single-copy strategies can only be efficient if the Pauli observables have advantageous structure. In this work, we complement existing theoretical performance guarantees with the empirical evaluation of triply efficient shadow tomography using classical, noise-free simulations. Our findings indicate that the empirical sample complexity aligns closely with theoretical predictions for stabilizer states and, notably, demonstrates slightly improved scaling for random Gibbs states compared to established theoretical bounds. In addition, we improve a central subroutine in the triply-efficient shadow protocol by leveraging insights from a refined quantum and quantum-inspired convex optimization algorithm [3, Henze et al. arXiv:2502.15426 (2025)]. To summarize, our empirical sample complexity studies of triply efficient shadow tomography not only confirm existing theoretical scaling behavior, but also showcase that the actual constants involved are comparatively benign. Hence, this protocol has the potential to also be very sample-efficient in practice. △ Less

Submitted 15 August, 2025; originally announced August 2025.

Comments: Accepted at IEEE Quantum Week (QCE) 2025. 12 pages, 4 figures, 1 table

Fast quantum measurement tomography with optimal error bounds

Authors: Leonardo Zambrano, Sergi Ramos-Calderer, Richard Kueng

Abstract: We present a two-step protocol for quantum measurement tomography that is light on classical co-processing cost and still achieves optimal sample complexity. Given measurement data from a known probe state ensemble, we first apply least-squares estimation to produce an unconstrained approximation of the POVM, and then project this estimate onto the set of valid quantum measurements. For a POVM wit… ▽ More We present a two-step protocol for quantum measurement tomography that is light on classical co-processing cost and still achieves optimal sample complexity. Given measurement data from a known probe state ensemble, we first apply least-squares estimation to produce an unconstrained approximation of the POVM, and then project this estimate onto the set of valid quantum measurements. For a POVM with $L$ outcomes acting on a $d$-dimensional system, we show that the protocol requires $\mathcal{O}\left((d^3+d^2L)/ε^2\right)$ samples to achieve error $ε$ in worst-case distance, and $\mathcal{O}(d^2 L/ε^2)$ samples in average-case distance. We further establish two matching sample complexity lower bounds of $Ω((d^3 + d^2 L) /ε^2)$ and $Ω(d^2 L/ε^2)$ for any non-adaptive, single-copy POVM tomography protocol. Hence, our projected least squares POVM tomography is sample-optimal in both the dimension and the number of outcomes for both distances. Our method admits an analytic form when using global or local 2-designs as probe ensembles and enables rigorous non-asymptotic error guarantees. Finally, we also complement our findings with empirical performance studies carried out on a noisy superconducting quantum computer with flux-tunable transmon qubits. △ Less

Submitted 9 July, 2026; v1 submitted 6 July, 2025; originally announced July 2025.

Journal ref: Quantum 10, 2162 (2026)

Quantum computing and artificial intelligence: status and perspectives

Authors: Giovanni Acampora, Andris Ambainis, Natalia Ares, Leonardo Banchi, Pallavi Bhardwaj, Daniele Binosi, G. Andrew D. Briggs, Tommaso Calarco, Vedran Dunjko, Jens Eisert, Olivier Ezratty, Paul Erker, Federico Fedele, Elies Gil-Fuster, Martin Gärttner, Mats Granath, Markus Heyl, Iordanis Kerenidis, Matthias Klusch, Anton Frisk Kockum, Richard Kueng, Mario Krenn, Jörg Lässig, Antonio Macaluso, Sabrina Maniscalco , et al. (14 additional authors not shown)

Abstract: This white paper discusses and explores the various points of intersection between quantum computing and artificial intelligence (AI). It describes how quantum computing could support the development of innovative AI solutions. It also examines use cases of classical AI that can empower research and development in quantum technologies, with a focus on quantum computing and quantum sensing. The pur… ▽ More This white paper discusses and explores the various points of intersection between quantum computing and artificial intelligence (AI). It describes how quantum computing could support the development of innovative AI solutions. It also examines use cases of classical AI that can empower research and development in quantum technologies, with a focus on quantum computing and quantum sensing. The purpose of this white paper is to provide a long-term research agenda aimed at addressing foundational questions about how AI and quantum computing interact and benefit one another. It concludes with a set of recommendations and challenges, including how to orchestrate the proposed theoretical work, align quantum AI developments with quantum hardware roadmaps, estimate both classical and quantum resources - especially with the goal of mitigating and optimizing energy consumption - advance this emerging hybrid software engineering discipline, and enhance European industrial competitiveness while considering societal implications. △ Less

Submitted 30 June, 2025; v1 submitted 29 May, 2025; originally announced May 2025.

Comments: 33 pages, 3 figures

In the shadow of the Hadamard test: Using the garbage state for good and further modifications

Authors: Paul K. Faehrmann, Jens Eisert, Richard Kueng

Abstract: The Hadamard test is naturally suited for the intermediate regime between the current era of noisy quantum devices and complete fault tolerance. Its applications use measurements of the auxiliary qubit to extract information, but disregard the system register completely. Separate advances in classical representations of quantum states via classical shadows allow the implementation of even global c… ▽ More The Hadamard test is naturally suited for the intermediate regime between the current era of noisy quantum devices and complete fault tolerance. Its applications use measurements of the auxiliary qubit to extract information, but disregard the system register completely. Separate advances in classical representations of quantum states via classical shadows allow the implementation of even global classical shadows with shallow circuits. This work combines the Hadamard test on a single auxiliary readout qubit with classical shadows on the remaining $n$-qubit work register. We argue that this combination inherits the best of both worlds and discuss statistical phase estimation as a vignette application. There, we can use the Hadamard test to estimate eigenvalues on the auxiliary qubit, while classical shadows on the remaining $n$ qubits provide access to additional features such as, (i) fidelity with certain pure quantum states, (ii) the initial state's energy and (iii) how pure and how close the initial state is to an eigenstate of the Hamiltonian. Finally, we also discuss how anti-controlled unitaries can further augment this framework. △ Less

Submitted 21 May, 2025; originally announced May 2025.

Comments: 6+3 pages, 3 figures

Journal ref: Phys. Rev. Lett. 135, 150603 (2025)

Ability of entanglement and purity to help to detect systematic experimental errors

Authors: Julia Freund, Francesco Basso Basset, Tobias M. Krieger, Alessandro Laneve, Mattia Beccaceci, Michele B. Rota, Quirin Buchinger, Saimon F. Covre da Silva, Sandra Stroj, Sven Höfling, Tobias Huber-Loyola, Richard Kueng, Armando Rastelli, Rinaldo Trotta, Otfried Gühne

Abstract: Measurements are central in all quantitative sciences, and a fundamental challenge is to make observations without systematic measurement errors. This holds in particular for quantum information processing, where other error sources, such as noise and decoherence, are unavoidable. Consequently, methods for detecting systematic errors have been developed, but the required quantum state properties a… ▽ More Measurements are central in all quantitative sciences, and a fundamental challenge is to make observations without systematic measurement errors. This holds in particular for quantum information processing, where other error sources, such as noise and decoherence, are unavoidable. Consequently, methods for detecting systematic errors have been developed, but the required quantum state properties are yet unexplored. We theoretically develop a direct and efficient method to detect systematic errors in quantum experiments and demonstrate it experimentally using quantum state tomography of photon pairs emitted from a semiconductor quantum dot. Our method can be scaled to multi-qubit systems, and we find that entanglement and quantum states with high purity can help identify systematic errors. △ Less

Submitted 2 March, 2026; v1 submitted 12 March, 2025; originally announced March 2025.

Comments: 22 pages, 10 figures

Journal ref: Phys. Rev. A 113, 022422 (2026)

Solving quadratic binary optimization problems using quantum SDP methods: Non-asymptotic running time analysis

Authors: Fabian Henze, Viet Tran, Birte Ostermann, Richard Kueng, Timo de Wolff, David Gross

Abstract: Quantum computers can solve semidefinite programs (SDPs) using resources that scale better than state-of-the-art classical methods as a function of the problem dimension. At the same time, the known quantum algorithms scale very unfavorably in the precision, which makes it non-trivial to find applications for which the quantum methods are well-suited. Arguably, precision is less crucial for SDP re… ▽ More Quantum computers can solve semidefinite programs (SDPs) using resources that scale better than state-of-the-art classical methods as a function of the problem dimension. At the same time, the known quantum algorithms scale very unfavorably in the precision, which makes it non-trivial to find applications for which the quantum methods are well-suited. Arguably, precision is less crucial for SDP relaxations of combinatorial optimization problems (such as the Goemans-Williamson algorithm), because these include a final rounding step that maps SDP solutions to binary variables. With this in mind, Brandão, França, and Kueng have proposed to use quantum SDP solvers in order to achieve an end-to-end speed-up for obtaining approximate solutions to combinatorial optimization problems. They did indeed succeed in identifying an algorithm that realizes a polynomial quantum advantage in terms of its asymptotic running time. However, asymptotic results say little about the problem sizes for which advantages manifest. Here, we present an analysis of the non-asymptotic resource requirements of this algorithm. The work consists of two parts. First, we optimize the original algorithm with a particular emphasis on performance for realistic problem instances. In particular, we formulate a version with adaptive step-sizes, an improved detection criterion for infeasible instances, and a more efficient rounding procedure. In a second step, we benchmark both the classical and the quantum version of the algorithm. The benchmarks did not identify a regime where even the optimized quantum algorithm would beat standard classical approaches for input sizes that can be realistically solved at all. In the absence of further significant improvements, these algorithms therefore fall into a category sometimes called galactic: Unbeaten in their asymptotic scaling behavior, but not practical for realistic problems. △ Less

Submitted 21 February, 2025; originally announced February 2025.

Comments: 56 pages, 6 figures

Short-time simulation of quantum dynamics by Pauli measurements

Authors: Paul K. Faehrmann, Jens Eisert, Maria Kieferova, Richard Kueng

Abstract: Simulating the dynamics of complex quantum systems is a central application of quantum devices. Here, we propose leveraging the power of measurements to simulate short-time quantum dynamics of physically prepared quantum states in classical post-processing using a truncated Taylor series approach. While limited to short simulation times, our hybrid quantum-classical method is equipped with rigorou… ▽ More Simulating the dynamics of complex quantum systems is a central application of quantum devices. Here, we propose leveraging the power of measurements to simulate short-time quantum dynamics of physically prepared quantum states in classical post-processing using a truncated Taylor series approach. While limited to short simulation times, our hybrid quantum-classical method is equipped with rigorous error bounds. It is extendable to estimate low-order Taylor approximations of smooth, time-dependent functions of tractable linear combinations of measurable operators. These insights can be made use of in the context of Hamiltonian learning and device verification, short-time imaginary time evolution, or the application of intractable operations to sub-universal quantum simulators in classical post-processing. △ Less

Submitted 15 May, 2025; v1 submitted 11 December, 2024; originally announced December 2024.

Comments: 10 pages, 1 figure

Journal ref: Phys. Rev. A 112, 012602 (2025)

Learning Properties of Quantum States Without the I.I.D. Assumption

Authors: Omar Fawzi, Richard Kueng, Damian Markham, Aadil Oufkir

Abstract: We develop a framework for learning properties of quantum states beyond the assumption of independent and identically distributed (i.i.d.) input states. We prove that, given any learning problem (under reasonable assumptions), an algorithm designed for i.i.d. input states can be adapted to handle input states of any nature, albeit at the expense of a polynomial increase in training data size (aka… ▽ More We develop a framework for learning properties of quantum states beyond the assumption of independent and identically distributed (i.i.d.) input states. We prove that, given any learning problem (under reasonable assumptions), an algorithm designed for i.i.d. input states can be adapted to handle input states of any nature, albeit at the expense of a polynomial increase in training data size (aka sample complexity). Importantly, this polynomial increase in sample complexity can be substantially improved to polylogarithmic if the learning algorithm in question only requires non-adaptive, single-copy measurements. Among other applications, this allows us to generalize the classical shadow framework to the non-i.i.d. setting while only incurring a comparatively small loss in sample efficiency. We use rigorous quantum information theory to prove our main results. In particular, we leverage permutation invariance and randomized single-copy measurements to derive a new quantum de Finetti theorem that mainly addresses measurement outcome statistics and, in turn, scales much more favorably in Hilbert space dimension. △ Less

Submitted 14 November, 2024; v1 submitted 30 January, 2024; originally announced January 2024.

Comments: 36+10 pages, 7 Figures. Close to the published version

Journal ref: Nature Communications, 15, Article number: 9677 (2024)

On the average-case complexity of learning output distributions of quantum circuits

Authors: Alexander Nietner, Marios Ioannou, Ryan Sweke, Richard Kueng, Jens Eisert, Marcel Hinsche, Jonas Haferkamp

Abstract: In this work, we show that learning the output distributions of brickwork random quantum circuits is average-case hard in the statistical query model. This learning model is widely used as an abstract computational model for most generic learning algorithms. In particular, for brickwork random quantum circuits on $n$ qubits of depth $d$, we show three main results: - At super logarithmic circuit… ▽ More In this work, we show that learning the output distributions of brickwork random quantum circuits is average-case hard in the statistical query model. This learning model is widely used as an abstract computational model for most generic learning algorithms. In particular, for brickwork random quantum circuits on $n$ qubits of depth $d$, we show three main results: - At super logarithmic circuit depth $d=ω(\log(n))$, any learning algorithm requires super polynomially many queries to achieve a constant probability of success over the randomly drawn instance. - There exists a $d=O(n)$, such that any learning algorithm requires $Ω(2^n)$ queries to achieve a $O(2^{-n})$ probability of success over the randomly drawn instance. - At infinite circuit depth $d\to\infty$, any learning algorithm requires $2^{2^{Ω(n)}}$ many queries to achieve a $2^{-2^{Ω(n)}}$ probability of success over the randomly drawn instance. As an auxiliary result of independent interest, we show that the output distribution of a brickwork random quantum circuit is constantly far from any fixed distribution in total variation distance with probability $1-O(2^{-n})$, which confirms a variant of a conjecture by Aaronson and Chen. △ Less

Submitted 9 October, 2025; v1 submitted 9 May, 2023; originally announced May 2023.

Comments: 62 pages

Journal ref: Quantum 9, 1883 (2025)

Depth-Optimal Synthesis of Clifford Circuits with SAT Solvers

Authors: Tom Peham, Nina Brandl, Richard Kueng, Robert Wille, Lukas Burgholzer

Abstract: Circuit synthesis is the task of decomposing a given logical functionality into a sequence of elementary gates. It is (depth-)optimal if it is impossible to achieve the desired functionality with even shorter circuits. Optimal synthesis is a central problem in both quantum and classical hardware design, but also plagued by complexity-theoretic obstacles. Motivated by fault-tolerant quantum computa… ▽ More Circuit synthesis is the task of decomposing a given logical functionality into a sequence of elementary gates. It is (depth-)optimal if it is impossible to achieve the desired functionality with even shorter circuits. Optimal synthesis is a central problem in both quantum and classical hardware design, but also plagued by complexity-theoretic obstacles. Motivated by fault-tolerant quantum computation, we consider the special case of synthesizing blocks of Clifford unitaries. Leveraging entangling input stimuli and the stabilizer formalism allows us to reduce the Clifford synthesis problem to a family of poly-size satisfiability (SAT) problems -- one for each target circuit depth. On a conceptual level, our result showcases that the Clifford synthesis problem is contained in the first level of the polynomial hierarchy ($\mathsf{NP}$), while the classical synthesis problem for logical circuits is known to be complete for the second level of the polynomial hierarchy ($Σ_2^{\mathsf{P}}$). Based on this theoretical reduction, we formulate a SAT encoding for depth-optimal Clifford synthesis. We then employ SAT solvers to determine a satisfying assignment or to prove that no such assignment exists. From that, the shortest depth for which synthesis is still possible (optimality) as well as the actual circuit (synthesis) can be obtained. Empirical evaluations show that the optimal synthesis approach yields a substantial depth improvement for random Clifford circuits and Clifford+T circuits for Grover search. △ Less

Submitted 2 June, 2023; v1 submitted 2 May, 2023; originally announced May 2023.

Comments: 12 pages, 2 figures, 1 table, implementation publicly available at https://github.com/cda-tum/qmap

Improved machine learning algorithm for predicting ground state properties

Authors: Laura Lewis, Hsin-Yuan Huang, Viet T. Tran, Sebastian Lehner, Richard Kueng, John Preskill

Abstract: Finding the ground state of a quantum many-body system is a fundamental problem in quantum physics. In this work, we give a classical machine learning (ML) algorithm for predicting ground state properties with an inductive bias encoding geometric locality. The proposed ML model can efficiently predict ground state properties of an $n$-qubit gapped local Hamiltonian after learning from only… ▽ More Finding the ground state of a quantum many-body system is a fundamental problem in quantum physics. In this work, we give a classical machine learning (ML) algorithm for predicting ground state properties with an inductive bias encoding geometric locality. The proposed ML model can efficiently predict ground state properties of an $n$-qubit gapped local Hamiltonian after learning from only $\mathcal{O}(\log(n))$ data about other Hamiltonians in the same quantum phase of matter. This improves substantially upon previous results that require $\mathcal{O}(n^c)$ data for a large constant $c$. Furthermore, the training and prediction time of the proposed ML model scale as $\mathcal{O}(n \log n)$ in the number of qubits $n$. Numerical experiments on physical systems with up to 45 qubits confirm the favorable scaling in predicting ground state properties using a small training dataset. △ Less

Submitted 30 January, 2023; originally announced January 2023.

Comments: 8 pages, 5 figures + 32-page appendix

Journal ref: Nat. Commun. 15, 895 (2024)

Entanglement barrier and its symmetry resolution: theory and experiment

Authors: Aniket Rath, Vittorio Vitale, Sara Murciano, Matteo Votto, Jérôme Dubail, Richard Kueng, Cyril Branciard, Pasquale Calabrese, Benoît Vermersch

Abstract: The operator entanglement (OE) is a key quantifier of the complexity of a reduced density matrix. In out-of-equilibrium situations, e.g. after a quantum quench of a product state, it is expected to exhibit an entanglement barrier. The OE of a reduced density matrix initially grows linearly as entanglement builds up between the local degrees of freedom, it then reaches a maximum, and ultimately dec… ▽ More The operator entanglement (OE) is a key quantifier of the complexity of a reduced density matrix. In out-of-equilibrium situations, e.g. after a quantum quench of a product state, it is expected to exhibit an entanglement barrier. The OE of a reduced density matrix initially grows linearly as entanglement builds up between the local degrees of freedom, it then reaches a maximum, and ultimately decays to a small finite value as the reduced density matrix converges to a simple stationary state through standard thermalization mechanisms. Here, by performing a new data analysis of the published experimental results of [Brydges et al., Science 364, 260 (2019)], we obtain the first experimental measurement of the OE of a subsystem reduced density matrix in a quantum many-body system. We employ the randomized measurements toolbox and we introduce and develop a new efficient method to post-process experimental data in order to extract higher-order density matrix functionals and access the OE. The OE thus obtained displays the expected barrier as long as the experimental system is large enough. For smaller systems, we observe a barrier with a double-peak structure, whose origin can be interpreted in terms of pairs of quasi-particles being reflected at the boundary of the qubit chain. As $U(1)$ symmetry plays a key role in our analysis, we introduce the notion of symmetry resolved operator entanglement (SROE), in addition to the total OE. To gain further insights into the SROE, we provide a thorough theoretical analysis of this new quantity in chains of non-interacting fermions, which, in spite of their simplicity, capture most of the main features of OE and SROE. In particular, we uncover three main physical effects: the presence of a barrier in any charge sector, a time delay for the onset of the growth of SROE, and an effective equipartition between charge sectors. △ Less

Submitted 9 September, 2022; originally announced September 2022.

Comments: 13 + 24 pages with 3 + 7 figures

Journal ref: Phys. Rev. X Quantum 4, 010318 (2023)

Recursive greedy initialization of the quantum approximate optimization algorithm with guaranteed improvement

Authors: Stefan H. Sack, Raimel A. Medina, Richard Kueng, Maksym Serbyn

Abstract: The quantum approximate optimization algorithm (QAOA) is a variational quantum algorithm, where a quantum computer implements a variational ansatz consisting of $p$ layers of alternating unitary operators and a classical computer is used to optimize the variational parameters. For a random initialization, the optimization typically leads to local minima with poor performance, motivating the search… ▽ More The quantum approximate optimization algorithm (QAOA) is a variational quantum algorithm, where a quantum computer implements a variational ansatz consisting of $p$ layers of alternating unitary operators and a classical computer is used to optimize the variational parameters. For a random initialization, the optimization typically leads to local minima with poor performance, motivating the search for initialization strategies of QAOA variational parameters. Although numerous heuristic initializations exist, an analytical understanding and performance guarantees for large $p$ remain evasive. We introduce a greedy initialization of QAOA which guarantees improving performance with an increasing number of layers. Our main result is an analytic construction of $2p+1$ transition states - saddle points with a unique negative curvature direction - for QAOA with $p+1$ layers that use the local minimum of QAOA with $p$ layers. Transition states connect to new local minima, which are guaranteed to lower the energy compared to the minimum found for $p$ layers. We use the GREEDY procedure to navigate the exponentially increasing with $p$ number of local minima resulting from the recursive application of our analytic construction. The performance of the GREEDY procedure matches available initialization strategies while providing a guarantee for the minimal energy to decrease with an increasing number of layers $p$. △ Less

Submitted 6 June, 2023; v1 submitted 2 September, 2022; originally announced September 2022.

Comments: 15 pages, 9 figures, updated to be close to published version

Journal ref: Phys. Rev. A 107, 062404 (2023)

Quantum mean states are nicer than you think: fast algorithms to compute states maximizing average fidelity

Authors: A. Afham, Richard Kueng, Chris Ferrie

Abstract: Fidelity is arguably the most popular figure of merit in quantum sciences. However, many of its properties are still unknown. In this work, we resolve the open problem of maximizing average fidelity over arbitrary finite ensembles of quantum states and derive new upper bounds. We first construct a semidefinite program whose optimal value is the maximum average fidelity and then derive fixed-point… ▽ More Fidelity is arguably the most popular figure of merit in quantum sciences. However, many of its properties are still unknown. In this work, we resolve the open problem of maximizing average fidelity over arbitrary finite ensembles of quantum states and derive new upper bounds. We first construct a semidefinite program whose optimal value is the maximum average fidelity and then derive fixed-point algorithms that converge to the optimal state. The fixed-point algorithms outperform the semidefinite program in terms of numerical runtime. We also derive expressions for near-optimal states that are easier to compute and upper and lower bounds for maximum average fidelity that are exact when all the states in the ensemble commute. Finally, we discuss how our results solve some open problems in Bayesian quantum tomography. △ Less

Submitted 16 June, 2022; originally announced June 2022.

Comments: 24 + 1 pages and 5 figures. Code available at https://github.com/afhamash/optimal-average-fidelity

Experimental single-setting quantum state tomography

Authors: Roman Stricker, Michael Meth, Lukas Postler, Claire Edmunds, Chris Ferrie, Rainer Blatt, Philipp Schindler, Thomas Monz, Richard Kueng, Martin Ringbauer

Abstract: Quantum computers solve ever more complex tasks using steadily growing system sizes. Characterizing these quantum systems is vital, yet becoming increasingly challenging. The gold-standard is quantum state tomography (QST), capable of fully reconstructing a quantum state without prior knowledge. Measurement and classical computing costs, however, increase exponentially in the system size - a bottl… ▽ More Quantum computers solve ever more complex tasks using steadily growing system sizes. Characterizing these quantum systems is vital, yet becoming increasingly challenging. The gold-standard is quantum state tomography (QST), capable of fully reconstructing a quantum state without prior knowledge. Measurement and classical computing costs, however, increase exponentially in the system size - a bottleneck given the scale of existing and near-term quantum devices. Here, we demonstrate a scalable and practical QST approach that uses a single measurement setting, namely symmetric informationally complete (SIC) positive operator-valued measures (POVM). We implement these nonorthogonal measurements on an ion trap device by utilizing more energy levels in each ion - without ancilla qubits. More precisely, we locally map the SIC POVM to orthogonal states embedded in a higher-dimensional system, which we read out using repeated in-sequence detections, providing full tomographic information in every shot. Combining this SIC tomography with the recently developed randomized measurement toolbox ("classical shadows") proves to be a powerful combination. SIC tomography alleviates the need for choosing measurement settings at random ("derandomization"), while classical shadows enable the estimation of arbitrary polynomial functions of the density matrix orders of magnitudes faster than standard methods. The latter enables in-depth entanglement studies, which we experimentally showcase on a 5-qubit absolutely maximally entangled (AME) state. Moreover, the fact that the full tomography information is available in every shot enables online QST in real time. We demonstrate this on an 8-qubit entangled state, as well as for fast state identification. All in all, these features single out SIC-based classical shadow estimation as a highly scalable and convenient tool for quantum state characterization. △ Less

Submitted 31 May, 2022; originally announced June 2022.

Comments: 34 pages, 15 figures

Journal ref: PRX Quantum 3, 040310 (2022)

The randomized measurement toolbox

Authors: Andreas Elben, Steven T. Flammia, Hsin-Yuan Huang, Richard Kueng, John Preskill, Benoît Vermersch, Peter Zoller

Abstract: Increasingly sophisticated programmable quantum simulators and quantum computers are opening unprecedented opportunities for exploring and exploiting the properties of highly entangled complex quantum systems. The complexity of large quantum systems is the source of their power, but also makes them difficult to control precisely or characterize accurately using measured classical data. We review r… ▽ More Increasingly sophisticated programmable quantum simulators and quantum computers are opening unprecedented opportunities for exploring and exploiting the properties of highly entangled complex quantum systems. The complexity of large quantum systems is the source of their power, but also makes them difficult to control precisely or characterize accurately using measured classical data. We review recently developed protocols for probing the properties of complex many-qubit systems using measurement schemes that are practical using today's quantum platforms. In all these protocols, a quantum state is repeatedly prepared and measured in a randomly chosen basis; then a classical computer processes the measurement outcomes to estimate the desired property. The randomization of the measurement procedure has distinct advantages; for example, a single data set can be employed multiple times to pursue a variety of applications, and imperfections in the measurements are mapped to a simplified noise model that can more easily be mitigated. We discuss a range of use cases that have already been realized in quantum devices, including Hamiltonian simulation tasks, probes of quantum chaos, measurements of nonlocal order parameters, and comparison of quantum states produced in distantly separated laboratories. By providing a workable method for translating a complex quantum state into a succinct classical representation that preserves a rich variety of relevant physical properties, the randomized measurement toolbox strengthens our ability to grasp and control the quantum world. △ Less

Submitted 21 March, 2022; originally announced March 2022.

Journal ref: Nature Review Physics (2022)

Avoiding barren plateaus using classical shadows

Authors: Stefan H. Sack, Raimel A. Medina, Alexios A. Michailidis, Richard Kueng, Maksym Serbyn

Abstract: Variational quantum algorithms are promising algorithms for achieving quantum advantage on near-term devices. The quantum hardware is used to implement a variational wave function and measure observables, whereas the classical computer is used to store and update the variational parameters. The optimization landscape of expressive variational ansätze is however dominated by large regions in parame… ▽ More Variational quantum algorithms are promising algorithms for achieving quantum advantage on near-term devices. The quantum hardware is used to implement a variational wave function and measure observables, whereas the classical computer is used to store and update the variational parameters. The optimization landscape of expressive variational ansätze is however dominated by large regions in parameter space, known as barren plateaus, with vanishing gradients which prevents efficient optimization. In this work we propose a general algorithm to avoid barren plateaus in the initialization and throughout the optimization. To this end we define a notion of weak barren plateaus (WBP) based on the entropies of local reduced density matrices. The presence of WBPs can be efficiently quantified using recently introduced shadow tomography of the quantum state with a classical computer. We demonstrate that avoidance of WBPs suffices to ensure sizable gradients in the initialization. In addition, we demonstrate that decreasing the gradient step size, guided by the entropies allows to avoid WBPs during the optimization process. This paves the way for efficient barren plateau free optimization on near-term devices. △ Less

Submitted 30 June, 2022; v1 submitted 20 January, 2022; originally announced January 2022.

Comments: 9 pages, 4 figures, comments are welcome; v2: improved readability, added new section and data, added more citations

Journal ref: PRX Quantum 3, 020365 (2022)

Quantum advantage in learning from experiments

Authors: Hsin-Yuan Huang, Michael Broughton, Jordan Cotler, Sitan Chen, Jerry Li, Masoud Mohseni, Hartmut Neven, Ryan Babbush, Richard Kueng, John Preskill, Jarrod R. McClean

Abstract: Quantum technology has the potential to revolutionize how we acquire and process experimental data to learn about the physical world. An experimental setup that transduces data from a physical system to a stable quantum memory, and processes that data using a quantum computer, could have significant advantages over conventional experiments in which the physical system is measured and the outcomes… ▽ More Quantum technology has the potential to revolutionize how we acquire and process experimental data to learn about the physical world. An experimental setup that transduces data from a physical system to a stable quantum memory, and processes that data using a quantum computer, could have significant advantages over conventional experiments in which the physical system is measured and the outcomes are processed using a classical computer. We prove that, in various tasks, quantum machines can learn from exponentially fewer experiments than those required in conventional experiments. The exponential advantage holds in predicting properties of physical systems, performing quantum principal component analysis on noisy states, and learning approximate models of physical dynamics. In some tasks, the quantum processing needed to achieve the exponential advantage can be modest; for example, one can simultaneously learn about many noncommuting observables by processing only two copies of the system. Conducting experiments with up to 40 superconducting qubits and 1300 quantum gates, we demonstrate that a substantial quantum advantage can be realized using today's relatively noisy quantum processors. Our results highlight how quantum technology can enable powerful new strategies to learn about nature. △ Less

Submitted 1 December, 2021; originally announced December 2021.

Comments: 6 pages, 17 figures + 46 page appendix; open-source code available at https://github.com/quantumlib/ReCirq/tree/master/recirq/qml_lfe

Report number: Science 376, 1182--1186 (2022)

Projected Least-Squares Quantum Process Tomography

Authors: Trystan Surawy-Stepney, Jonas Kahn, Richard Kueng, Madalin Guta

Abstract: We propose and investigate a new method of quantum process tomography (QPT) which we call projected least squares (PLS). In short, PLS consists of first computing the least-squares estimator of the Choi matrix of an unknown channel, and subsequently projecting it onto the convex set of Choi matrices. We consider four experimental setups including direct QPT with Pauli eigenvectors as input and Pau… ▽ More We propose and investigate a new method of quantum process tomography (QPT) which we call projected least squares (PLS). In short, PLS consists of first computing the least-squares estimator of the Choi matrix of an unknown channel, and subsequently projecting it onto the convex set of Choi matrices. We consider four experimental setups including direct QPT with Pauli eigenvectors as input and Pauli measurements, and ancilla-assisted QPT with mutually unbiased bases (MUB) measurements. In each case, we provide a closed form solution for the least-squares estimator of the Choi matrix. We propose a novel, two-step method for projecting these estimators onto the set of matrices representing physical quantum channels, and a fast numerical implementation in the form of the hyperplane intersection projection algorithm. We provide rigorous, non-asymptotic concentration bounds, sampling complexities and confidence regions for the Frobenius and trace-norm error of the estimators. For the Frobenius error, the bounds are linear in the rank of the Choi matrix, and for low ranks, they improve the error rates of the least squares estimator by a factor $d^2$, where $d$ is the system dimension. We illustrate the method with numerical experiments involving channels on systems with up to 7 qubits, and find that PLS has highly competitive accuracy and computational tractability. △ Less

Submitted 18 October, 2022; v1 submitted 2 July, 2021; originally announced July 2021.

Comments: 13+9 pages, 8 figures

MSC Class: Primary: 81P47. Secondary: 62P35

Journal ref: Quantum 6, 844 (2022)

Provably efficient machine learning for quantum many-body problems

Authors: Hsin-Yuan Huang, Richard Kueng, Giacomo Torlai, Victor V. Albert, John Preskill

Abstract: Classical machine learning (ML) provides a potentially powerful approach to solving challenging quantum many-body problems in physics and chemistry. However, the advantages of ML over more traditional methods have not been firmly established. In this work, we prove that classical ML algorithms can efficiently predict ground state properties of gapped Hamiltonians in finite spatial dimensions, afte… ▽ More Classical machine learning (ML) provides a potentially powerful approach to solving challenging quantum many-body problems in physics and chemistry. However, the advantages of ML over more traditional methods have not been firmly established. In this work, we prove that classical ML algorithms can efficiently predict ground state properties of gapped Hamiltonians in finite spatial dimensions, after learning from data obtained by measuring other Hamiltonians in the same quantum phase of matter. In contrast, under widely accepted complexity theory assumptions, classical algorithms that do not learn from data cannot achieve the same guarantee. We also prove that classical ML algorithms can efficiently classify a wide range of quantum phases of matter. Our arguments are based on the concept of a classical shadow, a succinct classical description of a many-body quantum state that can be constructed in feasible quantum experiments and be used to predict many properties of the state. Extensive numerical experiments corroborate our theoretical results in a variety of scenarios, including Rydberg atom systems, 2D random Heisenberg models, symmetry-protected topological phases, and topologically ordered phases. △ Less

Submitted 26 September, 2022; v1 submitted 23 June, 2021; originally announced June 2021.

Comments: 10 pages, 13 figures + 60-page appendix; v4: Fixed a minor formatting issue; open-source code available at https://github.com/hsinyuan-huang/provable-ml-quantum

Journal ref: Science Vol 377, Issue 6613 (2022)

Proof methods for robust low-rank matrix recovery

Authors: Tim Fuchs, David Gross, Peter Jung, Felix Krahmer, Richard Kueng, Dominik Stöger

Abstract: Low-rank matrix recovery problems arise naturally as mathematical formulations of various inverse problems, such as matrix completion, blind deconvolution, and phase retrieval. Over the last two decades, a number of works have rigorously analyzed the reconstruction performance for such scenarios, giving rise to a rather general understanding of the potential and the limitations of low-rank matrix… ▽ More Low-rank matrix recovery problems arise naturally as mathematical formulations of various inverse problems, such as matrix completion, blind deconvolution, and phase retrieval. Over the last two decades, a number of works have rigorously analyzed the reconstruction performance for such scenarios, giving rise to a rather general understanding of the potential and the limitations of low-rank matrix models in sensing problems. In this article, we compare the two main proof techniques that have been paving the way to a rigorous analysis, discuss their potential and limitations, and survey their successful applications. On the one hand, we review approaches based on descent cone analysis, showing that they often lead to strong guarantees even in the presence of adversarial noise, but face limitations when it comes to structured observations. On the other hand, we discuss techniques using approximate dual certificates and the golfing scheme, which are often better suited to deal with practical measurement structures, but sometimes lead to weaker guarantees. Lastly, we review recent progress towards analyzing descent cones also for structured scenarios -- exploiting the idea of splitting the cones into multiple parts that are analyzed via different techniques. △ Less

Submitted 8 June, 2021; originally announced June 2021.

Comments: 39 pages, 6 figures

Sketching with Kerdock's crayons: Fast sparsifying transforms for arbitrary linear maps

Authors: Tim Fuchs, David Gross, Felix Krahmer, Richard Kueng, Dustin G. Mixon

Abstract: Given an arbitrary matrix $A\in\mathbb{R}^{n\times n}$, we consider the fundamental problem of computing $Ax$ for any $x\in\mathbb{R}^n$ such that $Ax$ is $s$-sparse. While fast algorithms exist for particular choices of $A$, such as the discrete Fourier transform, there is currently no $o(n^2)$ algorithm that treats the unstructured case. In this paper, we devise a randomized approach to tackle t… ▽ More Given an arbitrary matrix $A\in\mathbb{R}^{n\times n}$, we consider the fundamental problem of computing $Ax$ for any $x\in\mathbb{R}^n$ such that $Ax$ is $s$-sparse. While fast algorithms exist for particular choices of $A$, such as the discrete Fourier transform, there is currently no $o(n^2)$ algorithm that treats the unstructured case. In this paper, we devise a randomized approach to tackle the unstructured case. Our method relies on a representation of $A$ in terms of certain real-valued mutually unbiased bases derived from Kerdock sets. In the preprocessing phase of our algorithm, we compute this representation of $A$ in $O(n^3\log n)$ operations. Next, given any unit vector $x\in\mathbb{R}^n$ such that $Ax$ is $s$-sparse, our randomized fast transform uses this representation of $A$ to compute the entrywise $ε$-hard threshold of $Ax$ with high probability in only $O(sn + ε^{-2}\|A\|_{2\to\infty}^2n\log n)$ operations. In addition to a performance guarantee, we provide numerical results that demonstrate the plausibility of real-world implementation of our algorithm. △ Less

Submitted 12 May, 2021; originally announced May 2021.

The lens SW05 J143454.4+522850: a fossil group at redshift 0.6?

Authors: Philipp Denzel, Onur Çatmabacak, Jonathan P. Coles, Claude Cornen, Robert Feldmann, Ignacio Ferreras, Xanthe Gwyn Palmer, Rafael Küng, Dominik Leier, Prasenjit Saha, Aprajita Verma

Abstract: Fossil groups are considered the end product of natural galaxy group evolution in which group members sink towards the centre of the gravitational potential due to dynamical friction, merging into a single, massive, and X-ray bright elliptical. Since gravitational lensing depends on the mass of a foreground object, its mass concentration, and distance to the observer, we can expect lensing effects… ▽ More Fossil groups are considered the end product of natural galaxy group evolution in which group members sink towards the centre of the gravitational potential due to dynamical friction, merging into a single, massive, and X-ray bright elliptical. Since gravitational lensing depends on the mass of a foreground object, its mass concentration, and distance to the observer, we can expect lensing effects of such fossil groups to be particularly strong. This paper explores the exceptional system $\mathrm{J}143454.4+522850$. We combine gravitational lensing with stellar population-synthesis to separate the total mass of the lens into stars and dark matter. The enclosed mass profiles are contrasted with state-of-the-art galaxy formation simulations, to conclude that SW05 is likely a fossil group with a high stellar to dark matter mass fraction $0.027\pm0.003$ with respect to expectations from abundance matching $0.012\pm0.004$, indicative of a more efficient conversion of gas into stars in fossil groups. △ Less

Submitted 7 April, 2021; originally announced April 2021.

Comments: 8 pages, 9 figures, submitted to MNRAS

Efficient estimation of Pauli observables by derandomization

Authors: Hsin-Yuan Huang, Richard Kueng, John Preskill

Abstract: We consider the problem of jointly estimating expectation values of many Pauli observables, a crucial subroutine in variational quantum algorithms. Starting with randomized measurements, we propose an efficient derandomization procedure that iteratively replaces random single-qubit measurements with fixed Pauli measurements; the resulting deterministic measurement procedure is guaranteed to perfor… ▽ More We consider the problem of jointly estimating expectation values of many Pauli observables, a crucial subroutine in variational quantum algorithms. Starting with randomized measurements, we propose an efficient derandomization procedure that iteratively replaces random single-qubit measurements with fixed Pauli measurements; the resulting deterministic measurement procedure is guaranteed to perform at least as well as the randomized one. In particular, for estimating any $L$ low-weight Pauli observables, a deterministic measurement on only of order $\log(L)$ copies of a quantum state suffices. In some cases, for example when some of the Pauli observables have a high weight, the derandomized procedure is substantially better than the randomized one. Specifically, numerical experiments highlight the advantages of our derandomized protocol over various previous methods for estimating the ground-state energies of small molecules. △ Less

Submitted 12 March, 2021; originally announced March 2021.

Comments: 12 pages, 2 figures, 1 table; open-source code available at https://github.com/momohuang/predicting-quantum-properties

Journal ref: Phys. Rev. Lett. 127, 030503 (2021)

Symmetry-resolved entanglement detection using partial transpose moments

Authors: Antoine Neven, Jose Carrasco, Vittorio Vitale, Christian Kokail, Andreas Elben, Marcello Dalmonte, Pasquale Calabrese, Peter Zoller, Benoît Vermersch, Richard Kueng, Barbara Kraus

Abstract: We propose an ordered set of experimentally accessible conditions for detecting entanglement in mixed states. The $k$-th condition involves comparing moments of the partially transposed density operator up to order $k$. Remarkably, the union of all moment inequalities reproduces the Peres-Horodecki criterion for detecting entanglement. Our empirical studies highlight that the first four conditions… ▽ More We propose an ordered set of experimentally accessible conditions for detecting entanglement in mixed states. The $k$-th condition involves comparing moments of the partially transposed density operator up to order $k$. Remarkably, the union of all moment inequalities reproduces the Peres-Horodecki criterion for detecting entanglement. Our empirical studies highlight that the first four conditions already detect mixed state entanglement reliably in a variety of quantum architectures. Exploiting symmetries can help to further improve their detection capabilities. We also show how to estimate moment inequalities based on local random measurements of single state copies (classical shadows) and derive statistically sound confidence intervals as a function of the number of performed measurements. Our analysis includes the experimentally relevant situation of drifting sources, i.e. non-identical, but independent, state copies. △ Less

Submitted 12 March, 2021; originally announced March 2021.

Comments: 11+11 pages, 6 figures

Journal ref: Npj Quantum Inf. 7, 152 (2021)

Symmetry-resolved dynamical purification in synthetic quantum matter

Authors: Vittorio Vitale, Andreas Elben, Richard Kueng, Antoine Neven, Jose Carrasco, Barbara Kraus, Peter Zoller, Pasquale Calabrese, Benoit Vermersch, Marcello Dalmonte

Abstract: When a quantum system initialized in a product state is subjected to either coherent or incoherent dynamics, the entropy of any of its connected partitions generically increases as a function of time, signalling the inevitable spreading of (quantum) information throughout the system. Here, we show that, in the presence of continuous symmetries and under ubiquitous experimental conditions, symmetry… ▽ More When a quantum system initialized in a product state is subjected to either coherent or incoherent dynamics, the entropy of any of its connected partitions generically increases as a function of time, signalling the inevitable spreading of (quantum) information throughout the system. Here, we show that, in the presence of continuous symmetries and under ubiquitous experimental conditions, symmetry-resolved information spreading is inhibited due to the competition of coherent and incoherent dynamics: in given quantum number sectors, entropy decreases as a function of time, signalling dynamical purification. Such dynamical purification bridges between two distinct short and intermediate time regimes, characterized by a log-volume and log-area entropy law, respectively. It is generic to symmetric quantum evolution, and as such occurs for different partition geometry and topology, and classes of (local) Liouville dynamics. We then develop a protocol to measure symmetry-resolved entropies and negativities in synthetic quantum systems based on the random unitary toolbox, and demonstrate the generality of dynamical purification using experimental data from trapped ion experiments [Brydges et al., Science 364, 260 (2019)]. Our work shows that symmetry plays a key role as a magnifying glass to characterize many-body dynamics in open quantum systems, and, in particular, in noisy-intermediate scale quantum devices. △ Less

Submitted 11 February, 2022; v1 submitted 19 January, 2021; originally announced January 2021.

Comments: 41 pages, 11 figures

Journal ref: SciPost Phys. 12, 106 (2022)

Randomizing multi-product formulas for Hamiltonian simulation

Authors: Paul K. Faehrmann, Mark Steudtner, Richard Kueng, Maria Kieferova, Jens Eisert

Abstract: Quantum simulation, the simulation of quantum processes on quantum computers, suggests a path forward for the efficient simulation of problems in condensed-matter physics, quantum chemistry, and materials science. While the majority of quantum simulation algorithms are deterministic, a recent surge of ideas has shown that randomization can greatly benefit algorithmic performance. In this work, we… ▽ More Quantum simulation, the simulation of quantum processes on quantum computers, suggests a path forward for the efficient simulation of problems in condensed-matter physics, quantum chemistry, and materials science. While the majority of quantum simulation algorithms are deterministic, a recent surge of ideas has shown that randomization can greatly benefit algorithmic performance. In this work, we introduce a scheme for quantum simulation that unites the advantages of randomized compiling on the one hand and higher-order multi-product formulas, as they are used for example in linear-combination-of-unitaries (LCU) algorithms or quantum error mitigation, on the other hand. In doing so, we propose a framework of randomized sampling that is expected to be useful for programmable quantum simulators and present two new multi-product formula algorithms tailored to it. Our framework reduces the circuit depth by circumventing the need for oblivious amplitude amplification required by the implementation of multi-product formulas using standard LCU methods, rendering it especially useful for early quantum computers used to estimate the dynamics of quantum systems instead of performing full-fledged quantum phase estimation. Our algorithms achieve a simulation error that shrinks exponentially with the circuit depth. To corroborate their functioning, we prove rigorous performance bounds as well as the concentration of the randomized sampling procedure. We demonstrate the functioning of the approach for several physically meaningful examples of Hamiltonians, including fermionic systems and the Sachdev-Ye-Kitaev model, for which the method provides a favorable scaling in the effort. △ Less

Submitted 30 September, 2022; v1 submitted 19 January, 2021; originally announced January 2021.

Comments: 24 pages, 6 figures

Journal ref: Quantum 6, 806 (2022)

Information-theoretic bounds on quantum advantage in machine learning

Authors: Hsin-Yuan Huang, Richard Kueng, John Preskill

Abstract: We study the performance of classical and quantum machine learning (ML) models in predicting outcomes of physical experiments. The experiments depend on an input parameter $x$ and involve execution of a (possibly unknown) quantum process $\mathcal{E}$. Our figure of merit is the number of runs of $\mathcal{E}$ required to achieve a desired prediction performance. We consider classical ML models th… ▽ More We study the performance of classical and quantum machine learning (ML) models in predicting outcomes of physical experiments. The experiments depend on an input parameter $x$ and involve execution of a (possibly unknown) quantum process $\mathcal{E}$. Our figure of merit is the number of runs of $\mathcal{E}$ required to achieve a desired prediction performance. We consider classical ML models that perform a measurement and record the classical outcome after each run of $\mathcal{E}$, and quantum ML models that can access $\mathcal{E}$ coherently to acquire quantum data; the classical or quantum data is then used to predict outcomes of future experiments. We prove that for any input distribution $\mathcal{D}(x)$, a classical ML model can provide accurate predictions on average by accessing $\mathcal{E}$ a number of times comparable to the optimal quantum ML model. In contrast, for achieving accurate prediction on all inputs, we prove that exponential quantum advantage is possible. For example, to predict expectations of all Pauli observables in an $n$-qubit system $ρ$, classical ML models require $2^{Ω(n)}$ copies of $ρ$, but we present a quantum ML model using only $\mathcal{O}(n)$ copies. Our results clarify where quantum advantage is possible and highlight the potential for classical ML models to address challenging quantum problems in physics and chemistry. △ Less

Submitted 1 April, 2021; v1 submitted 7 January, 2021; originally announced January 2021.

Comments: 6 pages, 2 figures + 28-page appendix

Journal ref: Phys. Rev. Lett. 126, 190505 (2021)

Stochastic Quantum Circuit Simulation Using Decision Diagrams

Authors: Thomas Grurl, Richard Kueng, Jürgen Fuß, Robert Wille

Abstract: Recent years have seen unprecedented advance in the design and control of quantum computers. Nonetheless, their applicability is still restricted and access remains expensive. Therefore, a substantial amount of quantum algorithms research still relies on simulating quantum circuits on classical hardware. However, due to the sheer complexity of simulating real quantum computers, many simulators unr… ▽ More Recent years have seen unprecedented advance in the design and control of quantum computers. Nonetheless, their applicability is still restricted and access remains expensive. Therefore, a substantial amount of quantum algorithms research still relies on simulating quantum circuits on classical hardware. However, due to the sheer complexity of simulating real quantum computers, many simulators unrealistically simplify the problem and instead simulate perfect quantum hardware, i.e., they do not consider errors caused by the fragile nature of quantum systems. Stochastic quantum simulation provides a conceptually suitable solution to this problem: physically motivated errors are applied in a probabilistic fashion throughout the simulation. In this work, we propose to use decision diagrams, as well as concurrent executions, to substantially reduce resource-requirements-which are still daunting-for stochastic quantum circuit simulation. Backed up by rigorous theory, empirical studies show that this approach allows for a substantially faster and much more scalable simulation for certain quantum circuits. △ Less

Submitted 10 December, 2020; originally announced December 2020.

Comments: 6 pages, 1 figure, 1 table

As Accurate as Needed, as Efficient as Possible: Approximations in DD-based Quantum Circuit Simulation

Authors: Stefan Hillmich, Richard Kueng, Igor L. Markov, Robert Wille

Abstract: Quantum computers promise to solve important problems faster than conventional computers. However, unleashing this power has been challenging. In particular, design automation runs into (1) the probabilistic nature of quantum computation and (2) exponential requirements for computational resources on non-quantum hardware. In quantum circuit simulation, Decision Diagrams (DDs) have previously shown… ▽ More Quantum computers promise to solve important problems faster than conventional computers. However, unleashing this power has been challenging. In particular, design automation runs into (1) the probabilistic nature of quantum computation and (2) exponential requirements for computational resources on non-quantum hardware. In quantum circuit simulation, Decision Diagrams (DDs) have previously shown to reduce the required memory in many important cases by exploiting redundancies in the quantum state. In this paper, we show that this reduction can be amplified by exploiting the probabilistic nature of quantum computers to achieve even more compact representations. Specifically, we propose two new DD-based simulation strategies that approximate the quantum states to attain more compact representations, while, at the same time, allowing the user to control the resulting degradation in accuracy. We also analytically prove the effect of multiple approximations on the attained accuracy and empirically show that the resulting simulation scheme enables speed-ups up to several orders of magnitudes. △ Less

Submitted 10 December, 2020; originally announced December 2020.

Comments: 6 pages, 2 figures, to be published at Design, Automation, and Test in Europe 2021

Characteristics of Reversible Circuits for Error Detection

Authors: Lukas Burgholzer, Robert Wille, Richard Kueng

Abstract: In this work, we consider error detection via simulation for reversible circuit architectures. We rigorously prove that reversibility augments the performance of this simple error detection protocol to a considerable degree. A single randomly generated input is guaranteed to unveil a single error with a probability that only depends on the size of the error, not the size of the circuit itself. Emp… ▽ More In this work, we consider error detection via simulation for reversible circuit architectures. We rigorously prove that reversibility augments the performance of this simple error detection protocol to a considerable degree. A single randomly generated input is guaranteed to unveil a single error with a probability that only depends on the size of the error, not the size of the circuit itself. Empirical studies confirm that this behavior typically extends to multiple errors as well. In conclusion, reversible circuits offer characteristics that reduce masking effects -- a desirable feature that is in stark contrast to irreversible circuit architectures. △ Less

Submitted 3 December, 2020; originally announced December 2020.

Comments: 6 pages, 9 figures

Random Stimuli Generation for the Verification of Quantum Circuits

Authors: Lukas Burgholzer, Richard Kueng, Robert Wille

Abstract: Verification of quantum circuits is essential for guaranteeing correctness of quantum algorithms and/or quantum descriptions across various levels of abstraction. In this work, we show that there are promising ways to check the correctness of quantum circuits using simulative verification and random stimuli. To this end, we investigate how to properly generate stimuli for efficiently checking the… ▽ More Verification of quantum circuits is essential for guaranteeing correctness of quantum algorithms and/or quantum descriptions across various levels of abstraction. In this work, we show that there are promising ways to check the correctness of quantum circuits using simulative verification and random stimuli. To this end, we investigate how to properly generate stimuli for efficiently checking the correctness of a quantum circuit. More precisely, we introduce, illustrate, and analyze three schemes for quantum stimuli generation---offering a trade-off between the error detection rate (as well as the required number of stimuli) and efficiency. In contrast to the verification in the classical realm, we show (both, theoretically and empirically) that even if only a few randomly-chosen stimuli (generated from the proposed schemes) are considered, high error detection rates can be achieved for quantum circuits. The results of these conceptual and theoretical considerations have also been empirically confirmed---with a grand total of approximately $10^6$ simulations conducted across 50 000 benchmark instances. △ Less

Submitted 14 November, 2020; originally announced November 2020.

Comments: 6 pages, in Asia and South Pacific Design Automation Conference (ASP-DAC) 2021

Rapid characterisation of linear-optical networks via PhaseLift

Authors: Daniel Suess, Nicola Maraviglia, Richard Kueng, Alexandre Maïnos, Chris Sparrow, Toshikazu Hashimoto, Nobuyuki Matsuda, David Gross, Anthony Laing

Abstract: Linear-optical circuits are elementary building blocks for classical and quantum information processing with light. In particular, due to its monolithic structure, integrated photonics offers great phase-stability and can rely on the large scale manufacturability provided by the semiconductor industry. New devices, based on such optical circuits, hold the promise of faster and energy-efficient com… ▽ More Linear-optical circuits are elementary building blocks for classical and quantum information processing with light. In particular, due to its monolithic structure, integrated photonics offers great phase-stability and can rely on the large scale manufacturability provided by the semiconductor industry. New devices, based on such optical circuits, hold the promise of faster and energy-efficient computations in machine learning applications and even implementing quantum algorithms intractable for classical computers. However, this technological revolution requires accurate and scalable certification protocols for devices that can be comprised of thousands of optical modes. Here, we present a novel technique to reconstruct the transfer matrix of linear optical networks that is based on the recent advances in low-rank matrix recovery and convex optimisation problems known as PhaseLift algorithms. Conveniently, our characterisation protocol can be performed with a coherent classical light source and photodiodes. We prove that this method is robust to noise and scales efficiently with the number of modes. We experimentally tested the proposed characterisation protocol on a programmable integrated interferometer designed for quantum information processing. We compared the transfer matrix reconstruction obtained with our method against the one provided by a more demanding reconstruction scheme based on two-photon quantum interference. For 5-dimensional random unitaries, the average circuit fidelity between the matrices obtained from the two reconstructions is 0.993. △ Less

Submitted 1 October, 2020; originally announced October 2020.

Comments: main document: 11 pages with 4 figures, appendix section: 15 pages

Fast and robust quantum state tomography from few basis measurements

Authors: Fernando G. S. L. Brandão, Richard Kueng, Daniel Stilck França

Abstract: Quantum state tomography is a powerful, but resource-intensive, general solution for numerous quantum information processing tasks. This motivates the design of robust tomography procedures that use relevant resources as sparingly as possible. Important cost factors include the number of state copies and measurement settings, as well as classical postprocessing time and memory. In this work, we pr… ▽ More Quantum state tomography is a powerful, but resource-intensive, general solution for numerous quantum information processing tasks. This motivates the design of robust tomography procedures that use relevant resources as sparingly as possible. Important cost factors include the number of state copies and measurement settings, as well as classical postprocessing time and memory. In this work, we present and analyze an online tomography algorithm designed to optimize all the aforementioned resources at the cost of a worse dependence on accuracy. The protocol is the first to give provably optimal performance in terms of rank and dimension for state copies, measurement settings and memory. Classical runtime is also reduced substantially and numerical experiments demonstrate a favorable comparison with other state-of-the-art techniques. Further improvements are possible by executing the algorithm on a quantum computer, giving a quantum speedup for quantum state tomography. △ Less

Submitted 16 March, 2021; v1 submitted 17 September, 2020; originally announced September 2020.

Comments: Corrected typos and added numerical examples

Journal ref: 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC), 2021

Concentration for random product formulas

Authors: Chi-Fang Chen, Hsin-Yuan Huang, Richard Kueng, Joel A. Tropp

Abstract: Quantum simulation has wide applications in quantum chemistry and physics. Recently, scientists have begun exploring the use of randomized methods for accelerating quantum simulation. Among them, a simple and powerful technique, called qDRIFT, is known to generate random product formulas for which the average quantum channel approximates the ideal evolution. qDRIFT achieves a gate count that does… ▽ More Quantum simulation has wide applications in quantum chemistry and physics. Recently, scientists have begun exploring the use of randomized methods for accelerating quantum simulation. Among them, a simple and powerful technique, called qDRIFT, is known to generate random product formulas for which the average quantum channel approximates the ideal evolution. qDRIFT achieves a gate count that does not explicitly depend on the number of terms in the Hamiltonian, which contrasts with Suzuki formulas. This work aims to understand the origin of this speed-up by comprehensively analyzing a single realization of the random product formula produced by qDRIFT. The main results prove that a typical realization of the randomized product formula approximates the ideal unitary evolution up to a small diamond-norm error. The gate complexity is already independent of the number of terms in the Hamiltonian, but it depends on the system size and the sum of the interaction strengths in the Hamiltonian. Remarkably, the same random evolution starting from an arbitrary, but fixed, input state yields a much shorter circuit suitable for that input state. In contrast, in deterministic settings, such an improvement usually requires initial state knowledge. The proofs depend on concentration inequalities for vector and matrix martingales, and the framework is applicable to other randomized product formulas. Our bounds are saturated by certain commuting Hamiltonians. △ Less

Submitted 25 March, 2026; v1 submitted 26 August, 2020; originally announced August 2020.

Comments: 27 pages, 6 figures

Journal ref: PRX Quantum 2, 040305 (2021)

Mixed-state entanglement from local randomized measurements

Authors: Andreas Elben, Richard Kueng, Hsin-Yuan Huang, Rick van Bijnen, Christian Kokail, Marcello Dalmonte, Pasquale Calabrese, Barbara Kraus, John Preskill, Peter Zoller, Benoît Vermersch

Abstract: We propose a method for detecting bipartite entanglement in a many-body mixed state based on estimating moments of the partially transposed density matrix. The estimates are obtained by performing local random measurements on the state, followed by post-processing using the classical shadows framework. Our method can be applied to any quantum system with single-qubit control. We provide a detailed… ▽ More We propose a method for detecting bipartite entanglement in a many-body mixed state based on estimating moments of the partially transposed density matrix. The estimates are obtained by performing local random measurements on the state, followed by post-processing using the classical shadows framework. Our method can be applied to any quantum system with single-qubit control. We provide a detailed analysis of the required number of experimental runs, and demonstrate the protocol using existing experimental data [Brydges et al, Science 364, 260 (2019)]. △ Less

Submitted 13 November, 2020; v1 submitted 13 July, 2020; originally announced July 2020.

Comments: 5+10 pages, 7 figures

Journal ref: Phys. Rev. Lett. 125, 200501 (2020)

Predicting Many Properties of a Quantum System from Very Few Measurements

Authors: Hsin-Yuan Huang, Richard Kueng, John Preskill

Abstract: Predicting properties of complex, large-scale quantum systems is essential for developing quantum technologies. We present an efficient method for constructing an approximate classical description of a quantum state using very few measurements of the state. This description, called a classical shadow, can be used to predict many different properties: order $\log M$ measurements suffice to accurate… ▽ More Predicting properties of complex, large-scale quantum systems is essential for developing quantum technologies. We present an efficient method for constructing an approximate classical description of a quantum state using very few measurements of the state. This description, called a classical shadow, can be used to predict many different properties: order $\log M$ measurements suffice to accurately predict $M$ different functions of the state with high success probability. The number of measurements is independent of the system size, and saturates information-theoretic lower bounds. Moreover, target properties to predict can be selected after the measurements are completed. We support our theoretical findings with extensive numerical experiments. We apply classical shadows to predict quantum fidelities, entanglement entropies, two-point correlation functions, expectation values of local observables, and the energy variance of many-body local Hamiltonians. The numerical results highlight the advantages of classical shadows relative to previously known methods. △ Less

Submitted 21 April, 2020; v1 submitted 18 February, 2020; originally announced February 2020.

Comments: 10 pages, 9 figures + 30 page appendix; supersedes arXiv:1908.08909; open source code available at https://github.com/momohuang/predicting-quantum-properties

Journal ref: Nature Physics 16, 1050--1057 (2020)

Variational-Correlations Approach to Quantum Many-body Problems

Authors: Arbel Haim, Richard Kueng, Gil Refael

Abstract: We investigate an approach for studying the ground state of a quantum many-body Hamiltonian that is based on treating the correlation functions as variational parameters. In this approach, the challenge set by the exponentially-large Hilbert space is circumvented by approximating the positivity of the density matrix, order-by-order, in a way that keeps track of a limited set of correlation functio… ▽ More We investigate an approach for studying the ground state of a quantum many-body Hamiltonian that is based on treating the correlation functions as variational parameters. In this approach, the challenge set by the exponentially-large Hilbert space is circumvented by approximating the positivity of the density matrix, order-by-order, in a way that keeps track of a limited set of correlation functions. In particular, the density-matrix description is replaced by a correlation matrix whose dimension is kept linear in system size, to all orders of the approximation. Unlike the conventional variational principle which provides an upper bound on the ground-state energy, in this approach one obtains a lower bound instead. By treating several one-dimensional spin $1/2$ Hamiltonians, we demonstrate the ability of this approach to produce long-range correlations, and a ground-state energy that converges to the exact result. Possible extensions, including to higher-excited states are discussed. △ Less

Submitted 17 January, 2020; originally announced January 2020.

Comments: 8 pages, 6 figures

Models of quantum complexity growth

Authors: Fernando G. S. L. Brandão, Wissam Chemissany, Nicholas Hunter-Jones, Richard Kueng, John Preskill

Abstract: The concept of quantum complexity has far-reaching implications spanning theoretical computer science, quantum many-body physics, and high energy physics. The quantum complexity of a unitary transformation or quantum state is defined as the size of the shortest quantum computation that executes the unitary or prepares the state. It is reasonable to expect that the complexity of a quantum state gov… ▽ More The concept of quantum complexity has far-reaching implications spanning theoretical computer science, quantum many-body physics, and high energy physics. The quantum complexity of a unitary transformation or quantum state is defined as the size of the shortest quantum computation that executes the unitary or prepares the state. It is reasonable to expect that the complexity of a quantum state governed by a chaotic many-body Hamiltonian grows linearly with time for a time that is exponential in the system size; however, because it is hard to rule out a short-cut that improves the efficiency of a computation, it is notoriously difficult to derive lower bounds on quantum complexity for particular unitaries or states without making additional assumptions. To go further, one may study more generic models of complexity growth. We provide a rigorous connection between complexity growth and unitary $k$-designs, ensembles which capture the randomness of the unitary group. This connection allows us to leverage existing results about design growth to draw conclusions about the growth of complexity. We prove that local random quantum circuits generate unitary transformations whose complexity grows linearly for a long time, mirroring the behavior one expects in chaotic quantum systems and verifying conjectures by Brown and Susskind. Moreover, our results apply under a strong definition of quantum complexity based on optimal distinguishing measurements. △ Less

Submitted 9 December, 2019; originally announced December 2019.

Comments: 64 pages, 4 figures, many diagrams

Journal ref: PRX Quantum 2, 030316 (2021)

Faster quantum and classical SDP approximations for quadratic binary optimization

Authors: Fernando G. S L. Brandão, Richard Kueng, Daniel Stilck França

Abstract: We give a quantum speedup for solving the canonical semidefinite programming relaxation for binary quadratic optimization. This class of relaxations for combinatorial optimization has so far eluded quantum speedups. Our methods combine ideas from quantum Gibbs sampling and matrix exponent updates. A de-quantization of the algorithm also leads to a faster classical solver. For generic instances, ou… ▽ More We give a quantum speedup for solving the canonical semidefinite programming relaxation for binary quadratic optimization. This class of relaxations for combinatorial optimization has so far eluded quantum speedups. Our methods combine ideas from quantum Gibbs sampling and matrix exponent updates. A de-quantization of the algorithm also leads to a faster classical solver. For generic instances, our quantum solver gives a nearly quadratic speedup over state-of-the-art algorithms. Such instances include approximating the ground state of spin glasses and MaxCut on Erdös-Rényi graphs. We also provide an efficient randomized rounding procedure that converts approximately optimal SDP solutions into approximations of the original quadratic optimization problem. △ Less

Submitted 10 January, 2022; v1 submitted 10 September, 2019; originally announced September 2019.

Comments: 42 pages, one figure. Corrected several typos and added a more thorough discussion on speedups for random instances. Accepted for publication in Quantum

Journal ref: Quantum 6, 625 (2022)

Predicting Features of Quantum Systems from Very Few Measurements

Authors: Hsin-Yuan Huang, Richard Kueng

Abstract: Predicting features of complex, large-scale quantum systems is essential to the characterization and engineering of quantum architectures. We present an efficient approach for constructing an approximate classical description, called the classical shadow, of a quantum system from very few quantum measurements that can later be used to predict a large collection of features. This approach is guaran… ▽ More Predicting features of complex, large-scale quantum systems is essential to the characterization and engineering of quantum architectures. We present an efficient approach for constructing an approximate classical description, called the classical shadow, of a quantum system from very few quantum measurements that can later be used to predict a large collection of features. This approach is guaranteed to accurately predict M linear functions with bounded Hilbert-Schmidt norm from only order of log(M) measurements. This is completely independent of the system size and saturates fundamental lower bounds from information theory. We support our theoretical findings with numerical experiments over a wide range of problem sizes (2 to 162 qubits). These highlight advantages compared to existing machine learning approaches. △ Less

Submitted 24 November, 2019; v1 submitted 23 August, 2019; originally announced August 2019.

Comments: 8 pages, 6 figures + 10 page appendix and one reference to Norse mythology