Concentration bounds for quantum states and limitations - Tony Metger | TQC 2023

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

We prove concentration bounds for the following classes of quantum states: (i) output states of shallow quantum circuits; (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)}} \ket{\psi_0}$ for any $n$-qubit product state $\ket{\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.

July 25, 2023
---------

TQC 2023 | 24-28 July 2023, University of Aveiro, Portugal

18th Conference on the Theory of Quantum Computation, Communication and Cryptography.

TQC is a leading annual international conference for students and researchers working in the theoretical aspects of quantum information science. The scientific objective is to bring together the theoretical quantum information science community to present and discuss the latest advances in the field.

Organisation:
Squids - Schools for Quantum Information Development
Universidade de Aveiro: Departamento de Matemática, CIDMA & Fábrica

Sponsors:
Phasecraft, UK
Google Quantum AI, USA
QuSoft, The Netherlands
Quantum for Life Centre, Denmark
Technology Innovation Institute, UAE
ML4Q, Germany
Dulwich Quantum