Concentration bounds for quantum states and limitations on the QAOA from polynomial approximations

Abstract

We prove concentration bounds for the following classes of quantum states: (i) output states of shallow quantum circuits, answering an open question from [DPMRF22]; (ii) injective matrix product states; (iii) output states of dense Hamiltonian evolution, i.e. states of the form $e^{\iota H^{(p)}}\cdots e^{\iota H^{(1)}}|{\psi }_0⟩$ for any $n$-qubit product state $|{\psi }_0⟩$, where each $H^{(i)}$ can be any local commuting Hamiltonian satisfying a norm constraint, including dense Hamiltonians with interactions between any qubits. Our proofs use polynomial approximations to show that these states are close to local operators. This implies that the distribution of the Hamming weight of a computational basis measurement (and of other related observables) concentrates. An example of (iii) are the states produced by the quantum approximate optimisation algorithm (QAOA). Using our concentration results for these states, we show that for a random spin model, the QAOA can only succeed with negligible probability even at super-constant level $p=o(\log \log n)$, assuming a strengthened version of the so-called overlap gap property. This gives the first limitations on the QAOA on dense instances at super-constant level, improving upon the recent result [BGMZ22].

arXiv comment28 pages. Extended abstract in ITCS 2023, full version (v3) in Quantum

References in corpus (18)

• Matrix Product States and Projected Entangled Pair States: Concepts, Symmetries, and Theorems
• Lieb-Schultz-Mattis in Higher Dimensions
• The Thermodynamic Limit in Mean Field Spin Glass Models
• Obstacles to State Preparation and Variational Optimization from Symmetry Protection
• The Overlap Gap Property: a Geometric Barrier to Optimizing over Random Structures
• Existence of temperature on the nanoscale
• Suboptimality of local algorithms for a class of max-cut problems
• Local Hamiltonians Whose Ground States are Hard to Approximate
• An area law for 2D frustration-free spin systems
• Concentration bounds for quantum states with finite correlation length on quantum spin lattice systems
• On the local equivalence between the canonical and the microcanonical distributions for quantum spin systems
• Gaussian concentration bound and Ensemble equivalence in generic quantum many-body systems including long-range interaction
• Eigenstate thermalization from the clustering property of correlation
• Performance and limitations of the QAOA at constant levels on large sparse hypergraphs and spin glass models
• Quantum concentration inequalities
• Connecting probability distributions of different operators and generalization of the Chernoff-Hoeffding inequality
• Circuit lower bounds for low-energy states of quantum code Hamiltonians
• A construction of Combinatorial NLTS

Cited by in corpus (6)

• Quantum complexity in gravity, quantum field theory, and quantum information science
• Symmetry-informed transferability of optimal parameters in the Quantum Approximate Optimization Algorithm
• The Overlap Gap Property limits limit swapping in the QAOA
• Quantum Glassiness From Efficient Learning
• Lower bounds on the number of rounds of the quantum approximate optimization algorithm required for guaranteed approximation ratios
• Direct Gradient Computation for Barren Plateaus in Parameterized Quantum Circuits