arXiv preprint ·
Fault-tolerant cost of shallow QAOA on near-symmetric optimization problems
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
Montanaro and Zhou proved that depth-one Quantum Approximate Optimization Algorithm (QAOA) finds the planted solution of certain near-symmetric constraint satisfaction problems with probability $Ω(1)$, and observed exponential runtimes for general-purpose classical solvers on explicit realizations, providing strong evidence of an empirical exponential speedup of low-depth QAOA. We ask what such a circuit costs fault-tolerantly. Although the cost Hamiltonian carries $Θ(n^\ell)$ clauses, the rotation angle at which QAOA succeeds shrinks as $n^{1-\ell}$, and we show that small-angle Clifford$+T$ rotation synthesis reduces the non-Clifford cost per circuit to $\widetilde O(n^2)$ for every clause locality $\ell$. Compiling the circuit, however, requires the explicit clause list. We find that the mechanism underlying constant QAOA success fixes the degree-one Fourier coefficients of the cost, whose signs reveal the planted solution. However, this leakage need not reveal the solution: we design families in which the quadratic non-Clifford scaling and hard exact optimization coexist.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Quantum Physics
Exponential separation in sensing continuous signals via squeezing
Complexity study of the Hartle-Hawking state in JT gravity
Polarisation-resolved identification of spontaneous four-wave mixing processes in a multimode fused tapered fibre coupler
Beyond IP = PSPACE and QIP = PSPACE: Interactive Proofs in Arbitrary Physical Theories
A Separation Between Types of Quantum Oracle Separations
Get the few papers worth your time in Quantum Physics every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.