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

• URL: http://arxiv.org/abs/2209.02715v3
• Date: Sun, 30 Apr 2023 16:38:26 GMT
• Title: Concentration bounds for quantum states and limitations on the QAOA from polynomial approximations
• Authors: Anurag Anshu, Tony Metger
• Abstract summary: We prove concentration 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, answering an open question from [DPMRF22]; (iii) output states of dense Hamiltonian evolution, i.e. states of the form $eiota H(p) cdots eiota H(1) |psirangle for any $n$-qubit product state $|psirangle$, where each $H(
• Score: 17.209060627291315
• License: http://creativecommons.org/licenses/by/4.0/
• 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\rangle$ for any $n$-qubit product state $|\psi_0\rangle$, 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].

Related papers

• Optimizing random local Hamiltonians by dissipation [44.99833362998488]
  We prove that a simplified quantum Gibbs sampling algorithm achieves a $Omega(frac1k)$-fraction approximation of the optimum. Our results suggest that finding low-energy states for sparsified (quasi)local spin and fermionic models is quantumly easy but classically nontrivial.
  arXiv  Detail & Related papers  (2024-11-04T20:21:16Z)
• Quasi-quantum states and the quasi-quantum PCP theorem [0.21485350418225244]
  We show that solving the $k$-local Hamiltonian over the quasi-quantum states is equivalent to optimizing a distribution of assignment over a classical $k$-local CSP. Our main result is a PCP theorem for the $k$-local Hamiltonian over the quasi-quantum states in the form of a hardness-of-approximation result.
  arXiv  Detail & Related papers  (2024-10-17T13:43:18Z)
• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
  We study the power of unentangled quantum proofs with non-negative amplitudes, a class which we denote $textQMA+(2)$. In particular, we design global protocols for small set expansion, unique games, and PCP verification. We show that QMA(2) is equal to $textQMA+(2)$ provided the gap of the latter is a sufficiently large constant.
  arXiv  Detail & Related papers  (2024-02-29T01:35:46Z)
• The role of shared randomness in quantum state certification with unentangled measurements [36.19846254657676]
  We study quantum state certification using unentangled quantum measurements. $Theta(d2/varepsilon2)$ copies are necessary and sufficient for state certification. We develop a unified lower bound framework for both fixed and randomized measurements.
  arXiv  Detail & Related papers  (2024-01-17T23:44:52Z)
• Analysis of sum-of-squares relaxations for the quantum rotor model [0.0]
  The noncommutative sum-of-squares hierarchy was introduced by Navascu'es-Pironio-Ac'i as a sequence of semidefinite programming relaxations for approximating quantum values of nonlocal games. Recent work has started to analyze the hierarchy for approximating ground energies of local Hamiltonians.
  arXiv  Detail & Related papers  (2023-11-15T14:53:22Z)
• Guidable Local Hamiltonian Problems with Implications to Heuristic Ansätze State Preparation and the Quantum PCP Conjecture [0.0]
  We study 'Merlinized' versions of the recently defined Guided Local Hamiltonian problem. These problems do not have a guiding state provided as a part of the input, but merely come with the promise that one exists. We show that guidable local Hamiltonian problems for both classes of guiding states are $mathsfQCMA$-complete in the inverse-polynomial precision setting.
  arXiv  Detail & Related papers  (2023-02-22T19:00:00Z)
• Sparse random Hamiltonians are quantumly easy [105.6788971265845]
  A candidate application for quantum computers is to simulate the low-temperature properties of quantum systems. This paper shows that, for most random Hamiltonians, the maximally mixed state is a sufficiently good trial state. Phase estimation efficiently prepares states with energy arbitrarily close to the ground energy.
  arXiv  Detail & Related papers  (2023-02-07T10:57:36Z)
• Average-case Speedup for Product Formulas [69.68937033275746]
  Product formulas, or Trotterization, are the oldest and still remain an appealing method to simulate quantum systems. We prove that the Trotter error exhibits a qualitatively better scaling for the vast majority of input states. Our results open doors to the study of quantum algorithms in the average case.
  arXiv  Detail & Related papers  (2021-11-09T18:49:48Z)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  We present an efficient read-out protocol that yields the classical vector form of the generated state. Our protocol suits the case that the output state lies in the row space of the input matrix. One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
  arXiv  Detail & Related papers  (2020-04-14T11:05:26Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.