1IBM Quantum, IBM Research Europe – Zurich
2ETH Zurich
3Institute of Physics, Ecole Polytechnique Fédérale de Lausanne (EPFL)
Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.
Abstract
Quantum computers may provide good solutions to combinatorial optimization problems by leveraging the Quantum Approximate Optimization Algorithm (QAOA). The QAOA is often presented as an algorithm for noisy hardware. However, hardware constraints limit its applicability to problem instances that closely match the connectivity of the qubits. Furthermore, the QAOA must outpace classical solvers. Here, we investigate swap strategies to map dense problems into linear, grid and heavy-hex coupling maps. A line-based swap strategy works best for linear and two-dimensional grid coupling maps. Heavy-hex coupling maps require an adaptation of the line swap strategy. By contrast, three-dimensional grid coupling maps benefit from a different swap strategy. Using known entropic arguments we find that the required gate fidelity for dense problems lies deep below the fault-tolerant threshold. We also provide a methodology to reason about the execution-time of QAOA. Finally, we present a QAOA Qiskit Runtime program and execute the closed-loop optimization on cloud-based quantum computers with transpiler settings optimized for QAOA. This work highlights some obstacles to improve to make QAOA competitive, such as gate fidelity, gate speed, and the large number of shots needed. The Qiskit Runtime program gives us a tool to investigate such issues at scale on noisy superconducting qubit hardware.
Featured image: QAOA on a hardware native optimization problem with 27 decision variables executed on ibmq_mumbai with the Qiskit Runtime.
Popular summary
► BibTeX data
► References
[1] Nikolaj Moll, Panagiotis Barkoutsos, Lev S. Bishop, Jerry M. Chow, Andrew Cross, Daniel J. Egger, Stefan Filipp, Andreas Fuhrer, Jay M. Gambetta, Marc Ganzhorn, and et al. Quantum optimization using variational algorithms on near-term quantum devices. Quantum Sci. Technol., 3 (3): 030503, 2018. 10.1088/2058-9565/aab822.
https://doi.org/10.1088/2058-9565/aab822
[2] Abhinav Kandala, Kristan Temme, Antonio D. Corcoles, Antonio Mezzacapo, Jerry M. Chow, and Jay M. Gambetta. Error mitigation extends the computational reach of a noisy quantum processor. Nature, 567: 491–495, 2018. 10.1038/s41586-019-1040-7.
https://doi.org/10.1038/s41586-019-1040-7
[3] Marc Ganzhorn, Daniel J. Egger, Panagiotis Kl. Barkoutsos, Pauline Ollitrault, Gian Salis, Nikolaj Moll, Andreas Fuhrer, Peter Mueller, Stefan Woerner, Ivano Tavernelli, and Stefan Filipp. Gate-efficient simulation of molecular eigenstates on a quantum computer. Phys. Rev. Applied, 11: 044092, Apr 2019. 10.1103/PhysRevApplied.11.044092.
https://doi.org/10.1103/PhysRevApplied.11.044092
[4] Stefan Woerner and Daniel J. Egger. Quantum risk analysis. npj Quantum Inf., 5: 15, 2019. 10.1038/s41534-019-0130-6.
https://doi.org/10.1038/s41534-019-0130-6
[5] Lee Braine, Daniel J. Egger, Jennifer Glick, and Stefan Woerner. Quantum algorithms for mixed binary optimization applied to transaction settlement. IEEE Trans. on Quantum Eng., 2: 1–8, 2021. 10.1109/TQE.2021.3063635.
https://doi.org/10.1109/TQE.2021.3063635
[6] Daniel J. Egger, Claudio Gambella, Jakub Mareček, Scott McFaddin, Martin Mevissen, Rudy Raymond, Aandrea Simonetto, Sefan Woerner, and Elena Yndurain. Quantum computing for finance: State-of-the-art and future prospects. IEEE Trans. on Quantum Eng., 1: 1–24, 2020. 10.1109/TQE.2020.3030314.
https://doi.org/10.1109/TQE.2020.3030314
[7] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate optimization algorithm. 2014a. 10.48550/ARXIV.1411.4028.
https://doi.org/10.48550/ARXIV.1411.4028
[8] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate optimization algorithm applied to a bounded occurrence constraint problem. 2014b. 10.48550/ARXIV.1412.6062.
https://doi.org/10.48550/ARXIV.1412.6062
[9] Zhi-Cheng Yang, Armin Rahmani, Alireza Shabani, Hartmut Neven, and Claudio Chamon. Optimizing variational quantum algorithms using pontryagin’s minimum principle. Phys. Rev. X, 7: 021027, May 2017. 10.1103/PhysRevX.7.021027.
https://doi.org/10.1103/PhysRevX.7.021027
[10] Andrew Lucas. Ising formulations of many NP problems. Front. Phys., 2: 5, 2014. ISSN 2296-424X. 10.3389/fphy.2014.00005.
https://doi.org/10.3389/fphy.2014.00005
[11] Bas Lodewijks. Mapping NP-hard and NP-complete optimisation problems to quadratic unconstrained binary optimisation problems. arXiv:1911.08043, 2019. 10.48550/ARXIV.1911.08043.
https://doi.org/10.48550/ARXIV.1911.08043
arXiv:1911.08043
[12] IBM ILOG CPLEX Optimizer. URL https://www.ibm.com/analytics/cplex-optimizer.
https://www.ibm.com/analytics/cplex-optimizer
[13] Andrey Kardashin, Anastasiia Pervishko, Jacob Biamonte, and Dmitry Yudin. Numerical hardware-efficient variational quantum simulation of a soliton solution. Phys. Rev. A, 104: L020402, Aug 2021. 10.1103/PhysRevA.104.L020402.
https://doi.org/10.1103/PhysRevA.104.L020402
[14] Matthew P. Harrigan, Kevin J. Sung, Matthew Neeley, Kevin J. Satzinger, Frank Arute, Kunal Arya, Juan Atalaya, Joseph C. Bardin, Rami Barends, Sergio Boixo, and et al. Quantum approximate optimization of non-planar graph problems on a planar superconducting processor. Nat. Phys., 17 (3): 332–336, Mar 2021. ISSN 1745-2481. 10.1038/s41567-020-01105-y.
https://doi.org/10.1038/s41567-020-01105-y
[15] Krishanu Sankar, Artur Scherer, Satoshi Kako, Sam Reifenstein, Navid Ghadermarzy, Willem B. Krayenhoff, Yoshitaka Inui, Edwin Ng, Tatsuhiro Onodera, Pooya Ronagh, and Yoshihisa Yamamoto. Benchmark study of quantum algorithms for combinatorial optimization: Unitary versus dissipative. 2021. 10.48550/ARXIV.2105.03528.
https://doi.org/10.48550/ARXIV.2105.03528
[16] Hazel A. Chieza, Maxine T. Khumalo, Krupa Prag, and Matthew Woolway. On the computational performance of IBM quantum devices applied to combinatorial optimisation problems. In 2020 7th International Conference on Soft Computing Machine Intelligence (ISCMI), pages 260–264, 2020. 10.1109/ISCMI51676.2020.9311605.
https://doi.org/10.1109/ISCMI51676.2020.9311605
[17] Harry Markowitz. Portfolio selection. J. Finance, 7 (1): 77–91, 1952. 10.2307/2975974.
https://doi.org/10.2307/2975974
[18] Francisco Barahona, Martin Grötschel, Michael Jünger, and Gerhard Reinelt. An application of combinatorial optimization to statistical physics and circuit layout design. Oper. Res., 36 (3): 493–513, 2021/11/19/ 1988. 10.1287/opre.36.3.493.
https://doi.org/10.1287/opre.36.3.493
[19] Michel Devoret and Robert J. Schoelkopf. Superconducting circuits for quantum information: An outlook. Science, 339: 1169–1174, 2013. 10.1126/science.1231930.
https://doi.org/10.1126/science.1231930
[20] Philip Krantz, Morten Kjaergaard, Fei Yan, Terry P. Orlando, Simon Gustavsson, and William D. Oliver. A quantum engineer’s guide to superconducting qubits. Appl. Phys. Rev., 6 (2): 021318, 2019. 10.1063/1.5089550.
https://doi.org/10.1063/1.5089550
[21] Larry Isenhower, Mark Saffman, and Klaus Mølmer. Multibit CkNOT quantum gates via Rydberg blockade. Quantum Inf. Process., 10 (6): 755, Sep 2011. 10.1007/s11128-011-0292-4.
https://doi.org/10.1007/s11128-011-0292-4
[22] Guido Pagano, Aniruddha Bapat, Patrick Becker, Katherine S. Collins, Arinjoy De, Paul W. Hess, Harvey B. Kaplan, Antonis Kyprianidis, Wen Lin Tan, Christopher Baldwin, and et al. Quantum approximate optimization of the long-range Ising model with a trapped-ion quantum simulator. Proc. Natl. Acad. Sci. U.S.A., 117 (41): 25396–25401, 2020. ISSN 0027-8424. 10.1073/pnas.2006373117.
https://doi.org/10.1073/pnas.2006373117
[23] Leo Zhou, Sheng-Tao Wang, Soonwon Choi, Hannes Pichler, and Mikhail D. Lukin. Quantum approximate optimization algorithm: Performance, mechanism, and implementation on near-term devices. Phys. Rev. X, 10: 021067, Jun 2020. 10.1103/PhysRevX.10.021067.
https://doi.org/10.1103/PhysRevX.10.021067
[24] Henning Labuhn, Daniel Barredo, Sylvain Ravets, Sylvain de Léséleuc, Tommaso Macrì, Thierry Lahaye, and Antoine Browaeys. Tunable two-dimensional arrays of single rydberg atoms for realizing quantum ising models. Nature, 534 (7609): 667–670, Jun 2016. 10.1038/nature18274.
https://doi.org/10.1038/nature18274
[25] Christopher Chamberland, Guanyu Zhu, Theodore J. Yoder, Jared B. Hertzberg, and Andrew W. Cross. Topological and subsystem codes on low-degree graphs with flag qubits. Phys. Rev. X, 10: 011022, Jan 2020. 10.1103/PhysRevX.10.011022.
https://doi.org/10.1103/PhysRevX.10.011022
[26] Ron Schutjens, Fadi Abu Dagga, Daniel J. Egger, and Frank K. Wilhelm. Single-qubit gates in frequency-crowded transmon systems. Phys. Rev. A, 88: 052330, Nov 2013. 10.1103/PhysRevA.88.052330.
https://doi.org/10.1103/PhysRevA.88.052330
[27] David C. McKay, Sarah Sheldon, John A. Smolin, Jerry M. Chow, and Jay M. Gambetta. Three-qubit randomized benchmarking. Phys. Rev. Lett., 122: 200502, May 2019. 10.1103/PhysRevLett.122.200502.
https://doi.org/10.1103/PhysRevLett.122.200502
[28] Peng Zhao, Kehuan Linghu, Zhiyuan Li, Peng Xu, Ruixia Wang, Guangming Xue, Yirong Jin, and Haifeng Yu. Quantum crosstalk analysis for simultaneous gate operations on superconducting qubits. PRX Quantum, 3: 020301, Apr 2022. 10.1103/PRXQuantum.3.020301.
https://doi.org/10.1103/PRXQuantum.3.020301
[29] Alexander Cowtan, Silas Dilkes, Ross Duncan, Alexandre Krajenbrink, Will Simmons, and Seyon Sivarajah. On the Qubit Routing Problem. In Wim van Dam and Laura Mancinska, editors, 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019), volume 135 of Leibniz International Proceedings in Informatics (LIPIcs), pages 5:1–5:32, Dagstuhl, Germany, 2019. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. ISBN 978-3-95977-112-2. 10.4230/LIPIcs.TQC.2019.5.
https://doi.org/10.4230/LIPIcs.TQC.2019.5
[30] Alwin Zulehner, Alexandru Paler, and Robert Wille. An efficient methodology for mapping quantum circuits to the IBM QX architectures. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst., 38 (7): 1226–1236, 2019. 10.1109/TCAD.2018.2846658.
https://doi.org/10.1109/TCAD.2018.2846658
[31] Jens Koch, Terri M. Yu, Jay Gambetta, Andrew A. Houck, David I. Schuster, Johannes Majer, Alexandre Blais, Michel H. Devoret, Steven M. Girvin, and Robert J. Schoelkopf. Charge-insensitive qubit design derived from the cooper pair box. Phys. Rev. A, 76: 042319, Oct 2007. 10.1103/PhysRevA.76.042319.
https://doi.org/10.1103/PhysRevA.76.042319
[32] Aaron Lye, Robert Wille, and Rolf Drechsler. Determining the minimal number of swap gates for multi-dimensional nearest neighbor quantum circuits. In The 20th Asia and South Pacific Design Automation Conference, pages 178–183, 2015. 10.1109/ASPDAC.2015.7059001.
https://doi.org/10.1109/ASPDAC.2015.7059001
[33] Abhoy Kole, Kamalika Datta, and Indranil Sengupta. A heuristic for linear nearest neighbor realization of quantum circuits by swap gate insertion using $N$-gate lookahead. IEEE Trans. Emerg. Sel. Topics Circuits Syst., 6 (1): 62–72, 2016. 10.1109/JETCAS.2016.2528720.
https://doi.org/10.1109/JETCAS.2016.2528720
[34] Anirban Bhattacharjee, Chandan Bandyopadhyay, Robert Wille, Rolf Drechsler, and Hafizur Rahaman. A novel approach for nearest neighbor realization of 2D quantum circuits. In 2018 IEEE Computer Society Annual Symposium on VLSI (ISVLSI), pages 305–310, 2018. 10.1109/ISVLSI.2018.00063.
https://doi.org/10.1109/ISVLSI.2018.00063
[35] Azim Farghadan and Naser Mohammadzadeh. Mapping quantum circuits on 3D nearest-neighbor architectures. Quantum Sci. Technol., 4 (3): 035001, apr 2019. 10.1088/2058-9565/ab177a.
https://doi.org/10.1088/2058-9565/ab177a
[36] Lingling Lao and Dan E. Browne. 2QAN: A quantum compiler for 2-local qubit hamiltonian simulation algorithms. In Proceedings of the 49th Annual International Symposium on Computer Architecture, ISCA ’22, page 351–365, New York, NY, USA, 2022. Association for Computing Machinery. ISBN 9781450386104. 10.1145/3470496.3527394.
https://doi.org/10.1145/3470496.3527394
[37] Yuwei Jin, Lucent Fong, Yanhao Chen, Ari B. Hayes, Shuo Zhang, Chi Zhang, Fei Hua, Zheng, and Zhang. A structured method for compilation of QAOA circuits in quantum computing. 2021. 10.48550/ARXIV.2112.06143.
https://doi.org/10.48550/ARXIV.2112.06143
[38] Mahabubul Alam, Abdullah Ash-Saki, and Swaroop Ghosh. Circuit compilation methodologies for quantum approximate optimization algorithm. In 2020 53rd Annual IEEE/ACM International Symposium on Microarchitecture (MICRO), pages 215–228, 2020. 10.1109/MICRO50266.2020.00029.
https://doi.org/10.1109/MICRO50266.2020.00029
[39] Yuichi Hirata, Masaki Nakanishi, Shigeru Yamashita, and Yasuhiko Nakashima. An efficient method to convert arbitrary quantum circuits to ones on a linear nearest neighbor architecture. In 2009 Third International Conference on Quantum, Nano and Micro Technologies, pages 26–33, 2009. 10.1109/ICQNM.2009.25.
https://doi.org/10.1109/ICQNM.2009.25
[40] Loïc Henriet, Lucas Beguin, Adrien Signoles, Thierry Lahaye, Antoine Browaeys, Georges-Olivier Reymond, and Christophe Jurczak. Quantum computing with neutral atoms. Quantum, 4: 327, September 2020. ISSN 2521-327X. 10.22331/q-2020-09-21-327.
https://doi.org/10.22331/q-2020-09-21-327
[41] Seyon Sivarajah, Silas Dilkes, Alexander Cowtan, Will Simmons, Alec Edgington, and Ross Duncan. t$vert$ket$rangle$: a retargetable compiler for NISQ devices. Quantum Sci. Technol., 6 (1): 014003, nov 2020. 10.1088/2058-9565/ab8e92.
https://doi.org/10.1088/2058-9565/ab8e92
[42] Gushu Li, Yufei Ding, and Yuan Xie. Tackling the qubit mapping problem for NISQ-era quantum devices. In Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS ’19, pages 1001–1014, New York, NY, USA, 2019. Association for Computing Machinery. ISBN 9781450362405. 10.1145/3297858.3304023.
https://doi.org/10.1145/3297858.3304023
[43] Johan Håstad. Some optimal inapproximability results. J. ACM, 48 (4): 798–859, 2001. 10.1145/502090.502098.
https://doi.org/10.1145/502090.502098
[44] Dorit Aharonov, Michael Ben-Or, Russell Impagliazzo, and Noam Nisan. Limitations of noisy reversible computation, 1996. URL https://arxiv.org/abs/quant-ph/9611028.
arXiv:quant-ph/9611028
[45] Daniel S. França and Raul García-Patrón. Limitations of optimization algorithms on noisy quantum devices. Nat. Phys., 17 (11): 1221–1227, Nov 2021. ISSN 1745-2481. 10.1038/s41567-021-01356-3.
https://doi.org/10.1038/s41567-021-01356-3
[46] Daochen Wang, Oscar Higgott, and Stephen Brierley. Accelerated variational quantum eigensolver. Phys. Rev. Lett., 122: 140504, Apr 2019. 10.1103/PhysRevLett.122.140504.
https://doi.org/10.1103/PhysRevLett.122.140504
[47] Aram W. Harrow and John C. Napp. Low-depth gradient measurements can improve convergence in variational hybrid quantum-classical algorithms. Phys. Rev. Lett., 126: 140502, Apr 2021. 10.1103/PhysRevLett.126.140502.
https://doi.org/10.1103/PhysRevLett.126.140502
[48] Easwar Magesan, Jay M. Gambetta, and Joseph Emerson. Scalable and robust randomized benchmarking of quantum processes. Phys. Rev. Lett., 106: 180504, May 2011. 10.1103/PhysRevLett.106.180504.
https://doi.org/10.1103/PhysRevLett.106.180504
[49] Easwar Magesan, Jay M. Gambetta, and Joseph Emerson. Characterizing quantum gates via randomized benchmarking. Phys. Rev. A, 85: 042311, Apr 2012. 10.1103/PhysRevA.85.042311.
https://doi.org/10.1103/PhysRevA.85.042311
[50] Antonio D. Córcoles, Jay M. Gambetta, Jerry M. Chow, John A. Smolin, Matthew Ware, Joel Strand, Britton L. T. Plourde, and Matthias Steffen. Process verification of two-qubit quantum gates by randomized benchmarking. Phys. Rev. A, 87: 030301, Mar 2013. 10.1103/PhysRevA.87.030301.
https://doi.org/10.1103/PhysRevA.87.030301
[51] Alexander Erhard, Joel J. Wallman, Lukas Postler, Michael Meth, Roman Stricker, Esteban A. Martinez, Philipp Schindler, Thomas Monz, Joseph Emerson, and Rainer Blatt. Characterizing large-scale quantum computers via cycle benchmarking. Nat. Commun., 10 (1): 5347, Nov 2019. ISSN 2041-1723. 10.1038/s41467-019-13068-7.
https://doi.org/10.1038/s41467-019-13068-7
[52] Prakash Murali, David C. Mckay, Margaret Martonosi, and Ali Javadi-Abhari. Software mitigation of crosstalk on noisy intermediate-scale quantum computers. In Proceedings of the Twenty-Fifth International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS ’20, pages 1001–1016, New York, NY, USA, 2020. Association for Computing Machinery. ISBN 9781450371025. 10.1145/3373376.3378477.
https://doi.org/10.1145/3373376.3378477
[53] Panos Aliferis and Andrew W. Cross. Subsystem fault tolerance with the Bacon-Shor code. Phys. Rev. Lett., 98: 220502, May 2007. 10.1103/PhysRevLett.98.220502.
https://doi.org/10.1103/PhysRevLett.98.220502
[54] Austin G. Fowler, Matteo Mariantoni, John M. Martinis, and Andrew N. Cleland. Surface codes: Towards practical large-scale quantum computation. Phys. Rev. A, 86: 032324, Sep 2012. 10.1103/PhysRevA.86.032324.
https://doi.org/10.1103/PhysRevA.86.032324
[55] Andrew Wack, Hanhee Paik, Ali Javadi-Abhari, Petar Jurcevic, Ismael Faro, Jay M. Gambetta, and Blake R. Johnson. Quality, speed, and scale: three key attributes to measure the performance of near-term quantum computers. 2021. 10.48550/ARXIV.2110.14108.
https://doi.org/10.48550/ARXIV.2110.14108
[56] Daniel J. Egger, Max Werninghaus, Marc Ganzhorn, Gian Salis, Andreas Fuhrer, Peter Müller, and Stefan Filipp. Pulsed reset protocol for fixed-frequency superconducting qubits. Phys. Rev. Applied, 10: 044030, Oct 2018. 10.1103/PhysRevApplied.10.044030.
https://doi.org/10.1103/PhysRevApplied.10.044030
[57] Max Werninghaus, Daniel J. Egger, Federico Roy, Shai Machnes, Frank K. Wilhelm, and Stefan Filipp. Leakage reduction in fast superconducting qubit gates via optimal control. npj Quantum Inf., 7, 2021. 10.1038/s41534-020-00346-2.
https://doi.org/10.1038/s41534-020-00346-2
[58] Susanna Kirchhoff, Torsten Keßler, Per J. Liebermann, Elie Assémat, Shai Machnes, Felix Motzoi, and Frank K. Wilhelm. Optimized cross-resonance gate for coupled transmon systems. Phys. Rev. A, 97: 042348, Apr 2018. 10.1103/PhysRevA.97.042348.
https://doi.org/10.1103/PhysRevA.97.042348
[59] Chad Rigetti and Michel Devoret. Fully microwave-tunable universal gates in superconducting qubits with linear couplings and fixed transition frequencies. Phys. Rev. B, 81: 134507, Apr 2010. 10.1103/PhysRevB.81.134507.
https://doi.org/10.1103/PhysRevB.81.134507
[60] Sarah Sheldon, Easwar Magesan, Jerry M. Chow, and Jay M. Gambetta. Procedure for systematically tuning up cross-talk in the cross-resonance gate. Phys. Rev. A, 93: 060302, Jun 2016. 10.1103/PhysRevA.93.060302.
https://doi.org/10.1103/PhysRevA.93.060302
[61] Matthew B. Hastings. Classical and quantum bounded depth approximation algorithms. Quantum Inf. Comput., 19, 2019. 10.26421/QIC19.13-14-3.
https://doi.org/10.26421/QIC19.13-14-3
[62] Sergey Bravyi, Alexander Kliesch, Robert Koenig, and Eugene Tang. Obstacles to variational quantum optimization from symmetry protection. Phys. Rev. Lett., 125: 260505, Dec 2020. 10.1103/PhysRevLett.125.260505.
https://doi.org/10.1103/PhysRevLett.125.260505
[63] Edward Farhi, David Gamarnik, and Sam Gutmann. The quantum approximate optimization algorithm needs to see the whole graph: A typical case. 2020. 10.48550/ARXIV.2005.08747.
https://doi.org/10.48550/ARXIV.2005.08747
[64] Kurtis Geerlings, Zaki Leghtas, Ioan M. Pop, Shyam Shankar, Luigi Frunzio, Robert J. Schoelkopf, Mazyar Mirrahimi, and Michel H. Devoret. Demonstrating a driven reset protocol for a superconducting qubit. Phys. Rev. Lett., 110: 120501, Mar 2013. 10.1103/PhysRevLett.110.120501.
https://doi.org/10.1103/PhysRevLett.110.120501
[65] Antonio D. Córcoles, Maika Takita, Ken Inoue, Scott Lekuch, Zlatko K. Minev, Jerry M. Chow, and Jay M. Gambetta. Exploiting dynamic quantum circuits in a quantum algorithm with superconducting qubits. Phys. Rev. Lett., 127: 100501, Aug 2021. 10.1103/PhysRevLett.127.100501.
https://doi.org/10.1103/PhysRevLett.127.100501
[66] Ryan Sweke, Frederik Wilde, Johannes Meyer, Maria Schuld, Paul K. Faehrmann, Barthélémy Meynard-Piganeau, and Jens Eisert. Stochastic gradient descent for hybrid quantum-classical optimization. Quantum, 4: 314, aug 2020. ISSN 2521-327X. 10.22331/q-2020-08-31-314.
https://doi.org/10.22331/q-2020-08-31-314
[67] Héctor Abraham and et al. Qiskit: An open-source framework for quantum computing. 2021. 10.5281/zenodo.2573505.
https://doi.org/10.5281/zenodo.2573505
[68] Gian Giacomo Guerreschi and Mikhail Smelyanskiy. Practical optimization for hybrid quantum-classical algorithms. 2017. 10.48550/ARXIV.1701.01450.
https://doi.org/10.48550/ARXIV.1701.01450
[69] Jonathan Romero, Ryan Babbush, Jarrod R. McClean, Cornelius Hempel, Peter J. Love, and Alán Aspuru-Guzik. Strategies for quantum computing molecular energies using the unitary coupled cluster ansatz. Quantum Sci. Technol., 4 (1): 014008, oct 2018. 10.1088/2058-9565/aad3e4.
https://doi.org/10.1088/2058-9565/aad3e4
[70] Jonas M. Kübler, Andrew Arrasmith, Lukasz Cincio, and Patrick J. Coles. An adaptive optimizer for measurement-frugal variational algorithms. Quantum, 4: 263, May 2020. ISSN 2521-327X. 10.22331/q-2020-05-11-263.
https://doi.org/10.22331/q-2020-05-11-263
[71] Fernando G. S. L. Brandao, Michael Broughton, Edward Farhi, Sam Gutmann, and Hartmut Neven. For fixed control parameters the quantum approximate optimization algorithm’s objective function value concentrates for typical instances, 2018.
[72] Stefan H. Sack and Maksym Serbyn. Quantum annealing initialization of the quantum approximate optimization algorithm. Quantum, 5: 491, July 2021. ISSN 2521-327X. 10.22331/q-2021-07-01-491.
https://doi.org/10.22331/q-2021-07-01-491
[73] Gregory Quiroz, Paraj Titum, Phillip Lotshaw, Pavel Lougovski, Kevin Schultz, Eugene Dumitrescu, and Itay Hen. Quantifying the impact of precision errors on quantum approximate optimization algorithms. 2021. 10.48550/ARXIV.2109.04482.
https://doi.org/10.48550/ARXIV.2109.04482
[74] Julien Gacon, Christa Zoufal, Giuseppe Carleo, and Stefan Woerner. Simultaneous Perturbation Stochastic Approximation of the Quantum Fisher Information. Quantum, 5: 567, October 2021. ISSN 2521-327X. 10.22331/q-2021-10-20-567.
https://doi.org/10.22331/q-2021-10-20-567
[75] Kristan Temme, Sergey Bravyi, and Jay M. Gambetta. Error mitigation for short-depth quantum circuits. Phys. Rev. Lett., 119: 180509, Nov 2017. 10.1103/PhysRevLett.119.180509.
https://doi.org/10.1103/PhysRevLett.119.180509
[76] Sanjeeb Dash and Jean-François Puget. On quadratic unconstrained binary optimization problems defined on chimera graphs. OPTIMA, 98, 2015. URL http://www.mathopt.org/Optima-Issues/optima98.pdf.
http://www.mathopt.org/Optima-Issues/optima98.pdf
[77] Alain Billionnet and Sourour Elloumi. Using a mixed integer quadratic programming solver for the unconstrained quadratic 0-1 problem. Math. Program., 109 (1): 55–68, Jan 2007. ISSN 1436-4646. 10.1007/s10107-005-0637-9.
https://doi.org/10.1007/s10107-005-0637-9
[78] Vishwanathan Akshay, Daniil Rabinovich, Ernesto Campos, and Jacob Biamonte. Parameter concentrations in quantum approximate optimization. Phys. Rev. A, 104: L010401, Jul 2021. 10.1103/PhysRevA.104.L010401.
https://doi.org/10.1103/PhysRevA.104.L010401
[79] Alexey Galda, Xiaoyuan Liu, Danylo Lykov, Yuri Alexeev, and Ilya Safro. Transferability of optimal qaoa parameters between random graphs. pages 171–180, 2021. 10.1109/QCE52317.2021.00034.
https://doi.org/10.1109/QCE52317.2021.00034
[80] Michael Streif and Martin Leib. Training the quantum approximate optimization algorithm without access to a quantum processing unit. Quantum Sci. Technol., 5 (3): 034008, may 2020. 10.1088/2058-9565/ab8c2b.
https://doi.org/10.1088/2058-9565/ab8c2b
[81] Ruslan Shaydulin, Phillip C. Lotshaw, Jeffrey Larson, James Ostrowski, and Travis S. Humble. Parameter transfer for quantum approximate optimization of weighted MaxCut. 2022. 10.48550/ARXIV.2201.11785.
https://doi.org/10.48550/ARXIV.2201.11785
[82] James C. Spall. Multivariate stochastic approximation using a simultaneous perturbation gradient approximation. IEEE Trans. Autom. Control, 37 (3): 332–341, 1992. 10.1109/9.119632.
https://doi.org/10.1109/9.119632
[83] James C. Spall. Accelerated second-order stochastic optimization using only function measurements. In Proceedings of the 36th IEEE Conference on Decision and Control, volume 2, pages 1417–1424 vol.2, 1997. 10.1109/CDC.1997.657661.
https://doi.org/10.1109/CDC.1997.657661
[84] Nathan Earnest, Caroline Tornow, and Daniel J. Egger. Pulse-efficient circuit transpilation for quantum applications on cross-resonance-based hardware. Phys. Rev. Research, 3: 043088, Oct 2021. 10.1103/PhysRevResearch.3.043088.
https://doi.org/10.1103/PhysRevResearch.3.043088
[85] Panagiotis Kl. Barkoutsos, Giacomo Nannicini, Anton Robert, Ivano Tavernelli, and Stefan Woerner. Improving variational quantum optimization using CVaR. Quantum, 4: 256, Apr 2020. 10.22331/q-2020-04-20-256.
https://doi.org/10.22331/q-2020-04-20-256
[86] Sergey Bravyi, Sarah Sheldon, Abhinav Kandala, David C. McKay, and Jay M. Gambetta. Mitigating measurement errors in multiqubit experiments. Phys. Rev. A, 103: 042605, Apr 2021. 10.1103/PhysRevA.103.042605.
https://doi.org/10.1103/PhysRevA.103.042605
[87] George S. Barron and Christopher J. Wood. Measurement error mitigation for variational quantum algorithms, 2020.
[88] Michel X. Goemans and David P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM, 42 (6): 1115–1145, nov 1995. 10.1145/227683.227684.
https://doi.org/10.1145/227683.227684
[89] Mario S. Könz, Wolfgang Lechner, Helmut G. Katzgraber, and Matthias Troyer. Embedding overhead scaling of optimization problems in quantum annealing. PRX Quantum, 2: 040322, Nov 2021. 10.1103/PRXQuantum.2.040322.
https://doi.org/10.1103/PRXQuantum.2.040322
[90] Akel Hashim, Rich Rines, Victory Omole, Ravi K. Naik, John Mark Kreikebaum, David I. Santiago, Frederic T. Chong, Irfan Siddiqi, and Pranav Gokhale. Optimized swap networks with equivalent circuit averaging for qaoa. Phys. Rev. Research, 4: 033028, Jul 2022. 10.1103/PhysRevResearch.4.033028.
https://doi.org/10.1103/PhysRevResearch.4.033028
[91] Gopal Chandra Santra, Fred Jendrzejewski, Philipp Hauke, and Daniel J. Egger. Squeezing and quantum approximate optimization. 2022. 10.48550/ARXIV.2205.10383.
https://doi.org/10.48550/ARXIV.2205.10383
[92] Phillip C. Lotshaw, Thien Nguyen, Anthony Santana, Alexander McCaskey, Rebekah Herrman, James Ostrowski, George Siopsis, and Travis S. Humble. Scaling quantum approximate optimization on near-term hardware. Scientific Reports, 12 (1): 12388, Jul 2022. 10.1038/s41598-022-14767-w.
https://doi.org/10.1038/s41598-022-14767-w
[93] Thomas Alexander, Naoki Kanazawa, Daniel J. Egger, Lauren Capelluto, Christopher J. Wood, Ali Javadi-Abhari, and David C. McKay. Qiskit pulse: programming quantum computers through the cloud with pulses. Quantum Sci. Technol., 5 (4): 044006, Aug 2020. 10.1088/2058-9565/aba404.
https://doi.org/10.1088/2058-9565/aba404
[94] John P. T. Stenger, Nicholas T. Bronn, Daniel J. Egger, and David Pekker. Simulating the dynamics of braiding of majorana zero modes using an ibm quantum computer. Phys. Rev. Research, 3: 033171, Aug 2021. 10.1103/PhysRevResearch.3.033171.
https://doi.org/10.1103/PhysRevResearch.3.033171
[95] P. Chandarana, N. N. Hegade, K. Paul, F. Albarrán-Arriagada, E. Solano, A. del Campo, and Xi Chen. Digitized-counterdiabatic quantum approximate optimization algorithm. Phys. Rev. Research, 4: 013141, Feb 2022. 10.1103/PhysRevResearch.4.013141.
https://doi.org/10.1103/PhysRevResearch.4.013141
[96] Jonathan Wurtz and Peter J. Love. Counterdiabaticity and the quantum approximate optimization algorithm. Quantum, 6: 635, jan 2022. 10.22331/q-2022-01-27-635.
https://doi.org/10.22331/q-2022-01-27-635
[97] Yuval R. Sanders, Dominic W. Berry, Pedro C.S. Costa, Louis W. Tessler, Nathan Wiebe, Craig Gidney, Hartmut Neven, and Ryan Babbush. Compilation of fault-tolerant quantum heuristics for combinatorial optimization. PRX Quantum, 1: 020312, Nov 2020. 10.1103/PRXQuantum.1.020312.
https://doi.org/10.1103/PRXQuantum.1.020312
[98] David Amaro, Carlo Modica, Matthias Rosenkranz, Mattia Fiorentini, Marcello Benedetti, and Michael Lubasch. Filtering variational quantum algorithms for combinatorial optimization. Quantum Sci. Technol., 7 (1): 015021, jan 2022. 10.1088/2058-9565/ac3e54.
https://doi.org/10.1088/2058-9565/ac3e54
[99] Daniel J. Egger, Jakub Mareček, and Stefan Woerner. Warm-starting quantum optimization. Quantum, 5: 479, Jun 2021. 10.22331/q-2021-06-17-479.
https://doi.org/10.22331/q-2021-06-17-479
[100] Reuben Tate, Majid Farhadi, Creston Herold, Greg Mohler, and Swati Gupta. Bridging classical and quantum with SDP initialized warm-starts for QAOA. ACM Transactions on Quantum Computing, jun 2022. 10.1145/3549554.
https://doi.org/10.1145/3549554
[101] Reuben Tate, Bryan Gard, Greg Mohler, and Swati Gupta. Classically-inspired mixers for QAOA beat Goemans-Williamson’s Max-Cut at low circuit depths. 2021. 10.48550/ARXIV.2112.11354.
https://doi.org/10.48550/ARXIV.2112.11354
[102] Almudena Carrera Vazquez, Daniel J. Egger, David Ochsner, and Stefan Woerner. Well-conditioned multi-product formulas for hardware-friendly hamiltonian simulation. 2022. 10.48550/ARXIV.2207.11268.
https://doi.org/10.48550/ARXIV.2207.11268
[103] Youngseok Kim, Christopher J. Wood, Theodore J. Yoder, Seth T. Merkel, Jay M. Gambetta, Kristan Temme, and Abhinav Kandala. Scalable error mitigation for noisy quantum circuits produces competitive expectation values. 2021. 10.48550/ARXIV.2108.09197.
https://doi.org/10.48550/ARXIV.2108.09197
[104] Ewout van den Berg, Zlatko K. Minev, Abhinav Kandala, and Kristan Temme. Probabilistic error cancellation with sparse pauli-lindblad models on noisy quantum processors. 2022. 10.48550/ARXIV.2201.09866.
https://doi.org/10.48550/ARXIV.2201.09866
[105] Paul D. Nation, Hwajung Kang, Neereja Sundaresan, and Jay M. Gambetta. Scalable mitigation of measurement errors on quantum computers. PRX Quantum, 2: 040326, Nov 2021. 10.1103/PRXQuantum.2.040326.
https://doi.org/10.1103/PRXQuantum.2.040326
[106] Raban Iten, Romain Moyard, Tony Metger, David Sutter, and Stefan Woerner. Exact and practical pattern matching for quantum circuit optimization. ACM Transactions on Quantum Computing, 3 (1), jan 2022. ISSN 2643-6809. 10.1145/3498325.
https://doi.org/10.1145/3498325
[107] Sung-Pil Hong. Inapproximability of the max-cut problem with negative weights. Management Science and Financial Engineering, 14 (1): 87–90, 2008. URL https://koreascience.kr/article/JAKO200822179194611.page.
https://koreascience.kr/article/JAKO200822179194611.page
Cited by
[1] Almudena Carrera Vazquez, Daniel J. Egger, David Ochsner, and Stefan Woerner, “Well-conditioned multi-product formulas for hardware-friendly Hamiltonian simulation”, arXiv:2207.11268.
[2] Zheng-Hang Sun, Yong-Yi Wang, Jian Cui, and Heng Fan, “Performance of quantum approximate optimization algorithm for preparing non-trivial quantum states: dependence of translational symmetry and improvement”, arXiv:2206.02637.
[3] Maxime Dupont, Nicolas Didier, Mark J. Hodson, Joel E. Moore, and Matthew J. Reagor, “Entanglement perspective on the quantum approximate optimization algorithm”, Physical Review A 106 2, 022423 (2022).
[4] Stefan H. Sack, Raimel A. Medina, Richard Kueng, and Maksym Serbyn, “Transition states and greedy exploration of the QAOA optimization landscape”, arXiv:2209.01159.
[5] Yanzhu Chen, Linghua Zhu, Chenxu Liu, Nicholas J. Mayhall, Edwin Barnes, and Sophia E. Economou, “How Much Entanglement Do Quantum Optimization Algorithms Require?”, arXiv:2205.12283.
[6] Laurin E. Fischer, Daniel Miller, Francesco Tacchino, Panagiotis Kl. Barkoutsos, Daniel J. Egger, and Ivano Tavernelli, “Ancilla-free implementation of generalized measurements for qubits embedded in a qudit space”, Physical Review Research 4 3, 033027 (2022).
[7] Cenk Tüysüz, Giuseppe Clemente, Arianna Crippa, Tobias Hartung, Stefan Kühn, and Karl Jansen, “Classical Splitting of Parametrized Quantum Circuits”, arXiv:2206.09641.
[8] Nishant Jain, Brian Coyle, Elham Kashefi, and Niraj Kumar, “Graph neural network initialisation of quantum approximate optimisation”, arXiv:2111.03016.
[9] Maxime Dupont, Nicolas Didier, Mark J. Hodson, Joel E. Moore, and Matthew J. Reagor, “Calibrating the classical hardness of the quantum approximate optimization algorithm”, arXiv:2206.06348.
[10] André Melo, Nathan Earnest-Noble, and Francesco Tacchino, “Pulse-efficient quantum machine learning”, arXiv:2211.01383.
[11] Pranav Chandarana, Pablo S. Vieites, Narendra N. Hegade, Enrique Solano, Yue Ban, and Xi Chen, “Meta-Learning Digitized-Counterdiabatic Quantum Optimization”, arXiv:2206.09966.
[12] Phillip C. Lotshaw, Kevin D. Battles, Bryan Gard, Gilles Buchs, Travis S. Humble, and Creston D. Herold, “Modelling noise in global Molmer-Sorensen interactions applied to quantum approximate optimization”, arXiv:2211.00133.
[13] Yuwei Jin, Jason Luo, Lucent Fong, Yanhao Chen, Ari B. Hayes, Chi Zhang, Fei Hua, and Eddy Z. Zhang, “A Structured Method for Compilation of QAOA Circuits in Quantum Computing”, arXiv:2112.06143.
[14] Gopal Chandra Santra, Fred Jendrzejewski, Philipp Hauke, and Daniel J. Egger, “Squeezing and quantum approximate optimization”, arXiv:2205.10383.
[15] Christos Aravanis, Georgios Korpas, and Jakub Marecek, “Transpiling Quantum Circuits using the Pentagon Equation”, arXiv:2209.14356.
The above citations are from SAO/NASA ADS (last updated successfully 2022-12-07 13:35:20). The list may be incomplete as not all publishers provide suitable and complete citation data.
Could not fetch Crossref cited-by data during last attempt 2022-12-07 13:35:17: Could not fetch cited-by data for 10.22331/q-2022-12-07-870 from Crossref. This is normal if the DOI was registered recently.
This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.
- SEO Powered Content & PR Distribution. Get Amplified Today.
- Platoblockchain. Web3 Metaverse Intelligence. Knowledge Amplified. Access Here.
- Source: https://quantum-journal.org/papers/q-2022-12-07-870/
