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].

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

References in corpus (6)

• The Overlap Gap Property: a Geometric Barrier to Optimizing over Random Structures
• Existence of temperature on the nanoscale
• An area law for 2D frustration-free spin systems
• Performance and limitations of the QAOA at constant levels on large sparse hypergraphs and spin glass models
• Quantum concentration inequalities
• 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