pipette
ENEnglish

Fault-tolerant cost of shallow QAOA on near-symmetric optimization problems

Jernej Rudi Fin\v{z}gar, Martin Leib, Elisabeth Wybo

Preprint

En palabras de los autores

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 , 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 clauses, the rotation angle at which QAOA succeeds shrinks as , and we show that small-angle Clifford rotation synthesis reduces the non-Clifford cost per circuit to for every clause locality . 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.

Resultado principalLimitación que admiten los autores

Apareció: jueves, 1 de octubre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: 11+3 pages, 3 figures