Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor
Matthew P. Harrigan,1, ⇤ . Sung,1, 2 ,1 . Satzinger,1 ,1 ,1 ,1 . Bardin,1, 3 ,1 ,1 ,1 . Buckley,1 . Buell,1 ,1 ,1 ,1 ,1 ,1, 4 ,1 ,1 ,1 ,1 ,1 ,1 Brooks Foxen,1 ,1 Marissa Giustina,1 ↵,1 ,1 ,1 ,1 ,1 L. B. Io↵e,1 Sergei V. Isakov,1 ↵rey,1 ,1 ,1 ,1 ,1 ,1 ,1 . Klimov,1 . Korotkov,1, 5 ,1 ,1 ,1 ,1 ,6 ,1 . Martinis,1, 4 Jarrod R. McClean,1 Ewen,1, 4 ,1 ,1 ,1 ,1 Josh Mutus,1 ,1 ,1 ,6 Niu,1 . O’Brien,1 ’Gorman,7, 8 ,1 ,1 ,1 ,1 ,1 . Rubin,1 ,1 ,6, 9 ,1 Doug Strain,1 ,6, 10 ,1 ,1 ,1 Z. ,1 Ping Yeh,1 ,1
,1, 11 ,1 ,1 ,1 ,1 and 1, † 1Google Quantum AI
2Department of Electrical Engineering and Computer Science, University of Michigan, , MI 3Department of Electrical and Computer Engineering, University of Massachusetts, Amherst, MA 4Department of Physics, University of California, Santa Barbara, CA
Copyright By PowCoder代写 加微信 powcoder
5Department of Electrical and Computer Engineering, University of California, Riverside, CA
6Volkswagen Data:Lab
7NASA Ames Research Center, Mo↵ett Field, CA
8Department of Electrical Engineering and Computer Sciences, University of California, Berkeley, CA
9Leiden University, Leiden, Netherlands
10Friedrich- Erlangen-Nu ̈rnberg, Department of Physics, Erlangen, Germany 11Department of Physics, Harvard University, Cambridge, MA
(Dated: February 2, 2021)
We demonstrate the application of the Google Sycamore superconducting qubit quantum pro- cessor to combinatorial optimization problems with the quantum approximate optimization algo- rithm (QAOA). Like past QAOA experiments, we study performance for problems defined on the (planar) connectivity graph of our hardware; however, we also apply the QAOA to the Sherrington- Kirkpatrick model and MaxCut, both high dimensional graph problems for which the QAOA requires significant compilation. Experimental scans of the QAOA energy landscape show good agreement with theory across even the largest instances studied (23 qubits) and we are able to perform varia- tional optimization successfully. For problems defined on our hardware graph we obtain an approx- imation ratio that is independent of problem size and observe, for the first time, that performance increases with circuit depth. For problems requiring compilation, performance decreases with prob- lem size but still provides an advantage over random guessing for circuits involving several thousand gates. This behavior highlights the challenge of using near-term quantum computers to optimize problems on graphs di↵ering from hardware connectivity. As these graphs are more representative of real world instances, our results advocate for more emphasis on such problems in the developing tradition of using the QAOA as a holistic, device-level benchmark of quantum processors.
I. INTRODUCTION
The Google Sycamore superconducting qubit platform has been used to demonstrate computational capabili- ties surpassing those of classical supercomputers for cer- tain sampling tasks [1]. However, it remains to be seen whether such processors will be able to achieve a similar computational advantage for problems of practical inter-
⇤ Corresponding author (M. Harrigan): † Corresponding author (R. Babbush):
est. Along with quantum chemistry [2, 3], machine learn- ing [4], and simulation of physical systems [5], discrete optimization has been widely anticipated as a promising area of application for quantum computers.
Beginning with a focus on quantum annealing [6] and adiabatic quantum computing [7], the possibility of quan- tum enhanced optimization has driven much interest in quantum technologies over the years. This is because faster optimization could prove transformative for di- verse areas such as logistics, finance, machine learning, and more. Such discrete optimization problems can be expressed as the minimization of a quadratic function of binary variables [8, 9], and one can visualize these
arXiv:2004.04197v3 [quant-ph] 30 Jan 2021
cost functions as graphs with binary variables as nodes and (weighted) edges connecting bits whose (weighted) products sum to the total cost function value. For most industrially-relevant problems, these graphs are non-planar and many ancilla would be required to em- bed them in (quasi-)planar graphs matching the qubit connectivity of most hardware platforms [10]. This lim- its the applicability of scalable architectures for quantum annealing [11] and corresponds to increased circuit com- plexity in digital quantum algorithms for optimization such as QAOA.
The quantum approximate optimization algorithm (QAOA) is the most studied gate model approach for optimization using near-term devices [12]. While the prospects for achieving quantum advantage with QAOA remain unclear, QAOA prescribes a simple paradigm for optimization which makes it amenable to both analytical results and implementation on current processors [13– 21]. For these reasons, QAOA has also become popu- lar as a system-level benchmark of quantum hardware. This work builds on prior experimental demonstrations of QAOA on superconducting qubits [22–25], ion traps [26], and photonics systems [27]. We compare results from these past experiments in Appendix B.
We are able to experimentally resolve, for the first time, increased performance with greater QAOA depth and apply QAOA to cost functions on graphs that de- viate significantly from our hardware connectivity. Ow- ing to the low error rates of the Sycamore platform, the trade-o↵ between the theoretical increase in quality of so- lutions with increasing QAOA depth and additional noise is apparent for hardware-native problems. We also apply the algorithm to non-native graph problems with their necessary compilation overhead and study the scaling of solution quality and problem size. Our results reveal that the performance of QAOA is qualitatively di↵erent when applied to hardware native graphs versus more complex graphs, highlighting the challenge of scaling QAOA to problems of industrial importance.
For this study, we used a “Sycamore” quantum pro- cessor which consists of a two-dimensional array of 54 transmon qubits [1]. Each qubit is tunably coupled to four nearest neighbors in a rectangular lattice. In this case, all device calibration was fully automated and data was collected using a cloud interface to the platform pro- grammed using Cirq [28]. Our experiment was restricted to 23 physical qubits of the larger Sycamore device, ar- ranged in a topology depicted in Figure 1a.
The combinatorial optimization problems we study in this work are defined through a cost function C(z) with a corresponding quantum operator C given by
C = XwjkZjZk (1) j