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 EE04: V: Variational Quantum Algorithms and Adiabatic Quantum Computing
10:00 AM–12:00 PM,
Monday, March 20, 2023
Room: Virtual Room 4
Sponsoring
Unit:
DQI
Chair: Oles Shtanko, IBM Quantum
Abstract: EE04.00005 : Limitations of Local Quantum Algorithms for Random Optimization*
10:48 AM–11:00 AM
Presenter:
Juspreet Singh Sandhu
(Harvard University)
Authors:
Juspreet Singh Sandhu
(Harvard University)
Jonathan Shi
(University of California, San Diego)
Peter J Love
(Tufts University)
Chris Jones
(University of Chicago)
Kunal Marwaha
(University of Chicago)
Chi-Ning Chou
(Harvard University)
1) An efficient classical algorithm that solves typical instances of the problem under a certain solution geometry (known as full-Replica Symmetry Breaking).
2) Obstructions to large families of algorithms (now including local quantum algorithms) in the absence of this solution geometry (known as a Branching Overlap-Gap Property).
We present two recent results that contribute to this line of research and show the following:
1) Every local quantum algorithm (including the QAOA up to ~log(n) depth) is obstructed from computing arbitrarily good solutions to typical instances of random constraint satisfaction problems (random CSPs) when the problem exhibits a Branching Overlap-Gap Property. Furthermore, the exact quality of the computed solution is established by a variational principle, and is matched by a classical algorithm called Approximate-Message Passing (AMP) - This is proved by establishing strong concentration properties of local quantum algorithms on a large family of problems.
2) A large class of random CSPs possess a Branching Overlap-Gap Property - This is proved by generalizing the Guerra-Tonnineli interpolations from spin glass theory using techcniques from discrete Fourier analysis.
The two results above in conjunction with prior results in the literature immediately rule out, for example, the possibillity for quantum advantage on the canonical problem of approximating the maximum-cut of random d-regular graphs (where the degree d is a large constant)
*DARPA ONISQ program award HR001120C0068; NSF STAQ award PHY-1818914; Simons Investigator Fellowship; SF grant DMS-2134157; DARPA grant W911NF2010021; DOE grant DE-SC0022199
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. |
© 2024 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