Bulletin of the American Physical Society
2023 APS March Meeting
Volume 68, Number 3
Las Vegas, Nevada (March 5-10)
Virtual (March 20-22); Time Zone: Pacific Time
Session W70: Quantum Annealer Characterization
3:00 PM–5:48 PM,
Thursday, March 9, 2023
Room: Room 409
Sponsoring
Unit:
DQI
Chair: Tameem Albash, University of New Mexico
Abstract: W70.00004 : Performance and limitations of the QAOA at constant levels on different problems*
3:36 PM–3:48 PM
Presenter:
Joao Basso
(UC Berkeley)
Authors:
Joao Basso
(UC Berkeley)
David Gamarnik
(MIT)
Song Mei
(UC Berkeley)
Leo Zhou
(Caltech)
purpose quantum algorithm designed for combinatorial optimization. We
analyze its expected performance and prove concentration properties at
any constant level (number of layers) on ensembles of random
combinatorial optimization problems in the infinite size limit. These
ensembles include mixed spin models and Max-q-XORSAT on sparse random
hypergraphs. We then show that the performance of the QAOA at constant
levels for the pure q-spin model matches asymptotically the ones for
Max-q-XORSAT on random sparse Erdos-Renyi hypergraphs and every
large-girth regular hypergraph. Through this correspondence, we
establish that the average-case value produced by the QAOA at constant
levels is bounded away from optimality for pure q-spin models when q ≥
4 and is even. This limitation gives a hardness of approximation
result for quantum algorithms in a new regime where the whole graph is
seen. Furthermore, we also derive analytical expressions for the
performance of the QAOA on the spiked tensor model at low-depth and
compare it to the classical power iteration method, shedding
additional light on the comparative power of classical and quantum
algorithms for optimization.
*D.G. is supported in part by NSF grant DMS-2015517. S.M. is supported in part by NSF grant DMS-2210827.
Follow Us |
Engage
Become an APS Member |
My APS
Renew Membership |
Information for |
About APSThe American Physical Society (APS) is a non-profit membership organization working to advance the knowledge of physics. |
© 2025 American Physical Society
| All rights reserved | Terms of Use
| Contact Us
Headquarters
1 Physics Ellipse, College Park, MD 20740-3844
(301) 209-3200
Editorial Office
100 Motor Pkwy, Suite 110, Hauppauge, NY 11788
(631) 591-4000
Office of Public Affairs
529 14th St NW, Suite 1050, Washington, D.C. 20045-2001
(202) 662-8700