Abstract
Approaches to compute or estimate the output probability distributions from the quantum approximate optimization algorithm (QAOA) are needed to assess the likelihood it will obtain a quantum computational advantage. We analyze output from QAOA circuits solving 7200 random MaxCut instances, with n=14-23 qubits and depth parameter p≤12, and find that the average basis state probabilities follow approximate Boltzmann distributions: The average probabilities scale exponentially with their energy (cut value), with a peak at the optimal solution. We describe the rate of exponential scaling or effective temperature in terms of a series with a leading-order term T∼Cmin/np, with Cmin the optimal solution energy. Using this scaling, we generate approximate output distributions with up to 38 qubits and find these give accurate accounts of important performance metrics in cases we can simulate exactly.
| Original language | English |
|---|---|
| Article number | 042411 |
| Journal | Physical Review A |
| Volume | 108 |
| Issue number | 4 |
| DOIs | |
| State | Published - Oct 2023 |
Funding
P.C.L. thanks R. Bennink for interesting discussions of combinatorial optimization, feedback, and encouragement. This work was supported by the Defense Advanced Research Projects Agency program for Optimization with Noisy Intermediate-Scale Quantum devices under Award no. W911NF-20-2-0051. J.O. acknowledges the Air Force Office of Scientific Research Award No. AF-FA9550-19-1-0147. G.S. acknowledges the Army Research Office Award No. W911NF-19-1-0397. J.O. and G.S. acknowledge the National Science Foundation Award No. OMA-1937008. This research used resources of the Compute and Data Environment for Science at the Oak Ridge National Laboratory, which is supported by the Office of Science of the U.S. Department of Energy under Contract No. DE-AC05-00OR22725.