Classical algorithms for quantum mean values

Abstract

We consider the task of estimating the expectation value of an $n$-qubit tensor product observable $O_1\otimes O_2\otimes \cdots \otimes O_n$ in the output state of a shallow quantum circuit. This task is a cornerstone of variational quantum algorithms for optimization, machine learning, and the simulation of quantum many-body systems. Here we study its computational complexity for constant-depth quantum circuits and three types of single-qubit observables $O_j$ which are (a) close to the identity, (b) positive semidefinite, (c) arbitrary. It is shown that the mean value problem admits a classical approximation algorithm with runtime scaling as $\mathrm{poly}(n)$ and $2^{\tilde{O}(\sqrt{n})}$ in cases (a,b) respectively. In case (c) we give a linear-time algorithm for geometrically local circuits on a two-dimensional grid. The mean value is approximated with a small relative error in case (a), while in cases (b,c) we satisfy a less demanding additive error bound. The algorithms are based on (respectively) Barvinok's polynomial interpolation method, a polynomial approximation for the OR function arising from quantum query complexity, and a Monte Carlo method combined with Matrix Product State techniques. We also prove a technical lemma characterizing a zero-free region for certain polynomials associated with a quantum circuit, which may be of independent interest.

References in corpus (21)

• Quantum Computing in the NISQ era and beyond
• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• A variational eigenvalue solver on a quantum processor
• The density-matrix renormalization group in the age of matrix product states
• Hardware-efficient Variational Quantum Eigensolver for Small Molecules and Quantum Magnets
• Supervised learning with quantum enhanced feature spaces
• Efficient classical simulation of slightly entangled quantum computations
• The theory of variational hybrid quantum-classical algorithms
• Quantum machine learning in feature Hilbert spaces
• Error mitigation for short-depth quantum circuits
• Characterizing Quantum Supremacy in Near-Term Devices
• Extending the computational reach of a noisy superconducting quantum processor
• Simulating quantum computation by contracting tensor networks
• IBM Q Experience as a versatile experimental testbed for simulating open quantum systems
• Quantum Supremacy and the Complexity of Random Circuit Sampling
• Low-cost error mitigation by symmetry verification
• Establishing the Quantum Supremacy Frontier with a 281 Pflop/s Simulation
• Recovering noise-free quantum observables
• Local Hamiltonians Whose Ground States are Hard to Approximate
• Classical simulation of limited-width cluster-state quantum computation
• Approximation Algorithms for Complex-Valued Ising Models on Bounded Degree Graphs

Cited by in corpus (38)

• Noisy intermediate-scale quantum (NISQ) algorithms
• The Future of Quantum Computing with Superconducting Qubits
• Efficient classical simulation of random shallow 2D quantum circuits
• Efficient tensor network simulation of IBM's Eagle kicked Ising experiment
• Simulating Quantum Materials with Digital Quantum Computers
• Fast quantum circuit cutting with randomized measurements
• Covariant quantum kernels for data with group structure
• Efficient quantum computation of molecular forces and other energy gradients
• Boundaries of quantum supremacy via random circuit sampling
• Beating classical heuristics for the binary paint shop problem with the quantum approximate optimization algorithm
• Classical simulation of short-time quantum dynamics
• Quantum Phase Recognition via Quantum Kernel Methods
• Absence of barren plateaus in finite local-depth circuits with long-range entanglement
• Quantum algorithms with local particle number conservation: noise effects and error correction
• Quantum machine learning with adaptive linear optics
• Simulating Noisy Variational Quantum Algorithms: A Polynomial Approach
• Fourier expansion in variational quantum algorithms
• Analytical Framework for Quantum Alternating Operator Ansätze
• Looped Pipelines Enabling Effective 3D Qubit Lattices in a Strictly 2D Device
• Classically estimating observables of noiseless quantum circuits
• Group-theoretic error mitigation enabled by classical shadows and symmetries
• Fault-tolerant quantum algorithms for quantum molecular systems: A survey
• Tensor-network-assisted variational quantum algorithm
• Improved approximation algorithms for bounded-degree local Hamiltonians
• Improved Simulation of Quantum Circuits by Fewer Gaussian Eliminations
• Identification of topological phases using classically-optimized variational quantum eigensolver
• Algorithmic Cluster Expansions for Quantum Problems
• Heisenberg-limited metrology with perturbing interactions
• Reduce&chop: Shallow circuits for deeper problems
• Demonstration of long-range correlations via susceptibility measurements in a one-dimensional superconducting Josephson spin chain
• Measurement-induced entanglement and complexity in random constant-depth 2D quantum circuits
• Scalability Challenges in Variational Quantum Optimization under Stochastic Noise
• Quantum mean value approximator for hard integer value problems
• Limitations of Noisy Quantum Devices in Computational and Entangling Power
• Limits of Short-Time Evolution of Local Hamiltonians
• Measurement-induced entanglement in noisy 2D random circuits
• Sampling (noisy) quantum circuits through randomized rounding
• Classical algorithms for measurement-adaptive Gaussian circuits