Encoding trade-offs and design toolkits in quantum algorithms for discrete optimization: coloring, routing, scheduling, and other problems

Nicolas PD Sawaya1, Albert T Schmitz2, and Stuart Hadfield3,4

1Intel Labs, Intel Corporation, Santa Clara, California 95054, USA [nicolas.sawaya@intel.com]
2Intel Labs, Intel Corporation, Hillsboro, Oregon 97124, USA
3Quantum Artificial Intelligence Laboratory, NASA Ames Research Center, Moffett Field, California 94035, USA
4USRA Research Institute for Advanced Computer Science, Mountain View, California, 94043, USA

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.


Challenging combinatorial optimization problems are ubiquitous in science and engineering. Several quantum methods for optimization have recently been developed, in different settings including both exact and approximate solvers. Addressing this field of research, this manuscript has three distinct purposes. First, we present an intuitive method for synthesizing and analyzing discrete ($i.e.,$ integer-based) optimization problems, wherein the problem and corresponding algorithmic primitives are expressed using a discrete quantum intermediate representation (DQIR) that is encoding-independent. This compact representation often allows for more efficient problem compilation, automated analyses of different encoding choices, easier interpretability, more complex runtime procedures, and richer programmability, as compared to previous approaches, which we demonstrate with a number of examples. Second, we perform numerical studies comparing several qubit encodings; the results exhibit a number of preliminary trends that help guide the choice of encoding for a particular set of hardware and a particular problem and algorithm. Our study includes problems related to graph coloring, the traveling salesperson problem, factory/machine scheduling, financial portfolio rebalancing, and integer linear programming. Third, we design low-depth graph-derived partial mixers (GDPMs) up to 16-level quantum variables, demonstrating that compact (binary) encodings are more amenable to QAOA than previously understood. We expect this toolkit of programming abstractions and low-level building blocks to aid in designing quantum algorithms for discrete combinatorial problems.

► BibTeX data

► References

[1] Christos H Papadimitriou and Kenneth Steiglitz. Combinatorial optimization: algorithms and complexity. Courier Corporation, 1998.

[2] Lov K Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pages 212–219, 1996. https:/​/​doi.org/​10.1145/​237814.237866.

[3] Tad Hogg and Dmitriy Portnov. Quantum optimization. Information Sciences, 128(3-4):181–197, 2000. https:/​/​doi.org/​10.1016/​s0020-0255(00)00052-9.

[4] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate optimization algorithm. arXiv preprint arXiv:1411.4028, 2014. https:/​/​doi.org/​10.48550/​arXiv.1411.4028.

[5] Matthew B Hastings. A short path quantum algorithm for exact optimization. Quantum, 2:78, 2018. https:/​/​doi.org/​10.22331/​q-2018-07-26-78.

[6] Tameem Albash and Daniel A Lidar. Adiabatic quantum computation. Reviews of Modern Physics, 90(1):015002, 2018. https:/​/​doi.org/​10.1103/​revmodphys.90.015002.

[7] Stuart Hadfield, Zhihui Wang, Bryan O'Gorman, Eleanor Rieffel, Davide Venturelli, and Rupak Biswas. From the quantum approximate optimization algorithm to a quantum alternating operator ansatz. Algorithms, 12(2):34, 2019. https:/​/​doi.org/​10.3390/​a12020034.

[8] Philipp Hauke, Helmut G Katzgraber, Wolfgang Lechner, Hidetoshi Nishimori, and William D Oliver. Perspectives of quantum annealing: Methods and implementations. Reports on Progress in Physics, 83(5):054401, 2020. https:/​/​doi.org/​10.1088/​1361-6633/​ab85b8.

[9] K.M. Svore, A.V. Aho, A.W. Cross, I. Chuang, and I.L. Markov. A layered software architecture for quantum computing design tools. Computer, 39(1):74–83, jan 2006. https:/​/​doi.org/​10.1109/​MC.2006.4.

[10] David Ittah, Thomas Häner, Vadym Kliuchnikov, and Torsten Hoefler. Enabling dataflow optimization for quantum programs. arXiv preprint arXiv:2101.11030, 2021. https:/​/​doi.org/​10.48550/​arXiv.2101.11030.

[11] Ruslan Shaydulin, Kunal Marwaha, Jonathan Wurtz, and Phillip C Lotshaw. Qaoakit: A toolkit for reproducible study, application, and verification of the qaoa. In 2021 IEEE/​ACM Second International Workshop on Quantum Computing Software (QCS), pages 64–71. IEEE, 2021. https:/​/​doi.org/​10.1109/​qcs54837.2021.00011.

[12] Nicolas P. D. Sawaya, Tim Menke, Thi Ha Kyaw, Sonika Johri, Alán Aspuru-Guzik, and Gian Giacomo Guerreschi. Resource-efficient digital quantum simulation of d-level systems for photonic, vibrational, and spin-s hamiltonians. npj Quantum Information, 6(1), jun 2020. https:/​/​doi.org/​10.1038/​s41534-020-0278-0.

[13] Stuart Hadfield. On the representation of Boolean and real functions as Hamiltonians for quantum computing. ACM Transactions on Quantum Computing, 2(4):1–21, 2021. https:/​/​doi.org/​10.1145/​3478519.

[14] Kesha Hietala, Robert Rand, Shih-Han Hung, Xiaodi Wu, and Michael Hicks. Verified optimization in a quantum intermediate representation. CoRR, abs/​1904.06319, 2019. https:/​/​doi.org/​10.48550/​arXiv.1904.06319.

[15] Thien Nguyen and Alexander McCaskey. Retargetable optimizing compilers for quantum accelerators via a multilevel intermediate representation. IEEE Micro, 42(5):17–33, 2022. https:/​/​doi.org/​10.1109/​mm.2022.3179654.

[16] Alexander McCaskey and Thien Nguyen. A MLIR dialect for quantum assembly languages. In 2021 IEEE International Conference on Quantum Computing and Engineering (QCE), pages 255–264. IEEE, 2021. https:/​/​doi.org/​10.1109/​qce52317.2021.00043.

[17] Andrew W Cross, Lev S Bishop, John A Smolin, and Jay M Gambetta. Open quantum assembly language. arXiv preprint arXiv:1707.03429, 2017. https:/​/​doi.org/​10.48550/​arXiv.1707.03429.

[18] Nicolas P. D. Sawaya, Gian Giacomo Guerreschi, and Adam Holmes. On connectivity-dependent resource requirements for digital quantum simulation of d-level particles. In 2020 IEEE International Conference on Quantum Computing and Engineering (QCE). IEEE, 2020. https:/​/​doi.org/​10.1109/​qce49297.2020.00031.

[19] Alexandru Macridin, Panagiotis Spentzouris, James Amundson, and Roni Harnik. Electron-phonon systems on a universal quantum computer. Phys. Rev. Lett., 121:110504, 2018. https:/​/​doi.org/​10.1103/​PhysRevLett.121.110504.

[20] Sam McArdle, Alexander Mayorov, Xiao Shan, Simon Benjamin, and Xiao Yuan. Digital quantum simulation of molecular vibrations. Chem. Sci., 10(22):5725–5735, 2019. https:/​/​doi.org/​10.1039/​c9sc01313j.

[21] Pauline J. Ollitrault, Alberto Baiardi, Markus Reiher, and Ivano Tavernelli. Hardware efficient quantum algorithms for vibrational structure calculations. Chem. Sci., 11(26):6842–6855, 2020. https:/​/​doi.org/​10.1039/​d0sc01908a.

[22] Nicolas PD Sawaya, Francesco Paesani, and Daniel P Tabor. Near-and long-term quantum algorithmic approaches for vibrational spectroscopy. Physical Review A, 104(6):062419, 2021. https:/​/​doi.org/​10.1103/​physreva.104.062419.

[23] Jakob S Kottmann, Mario Krenn, Thi Ha Kyaw, Sumner Alperin-Lea, and Alán Aspuru-Guzik. Quantum computer-aided design of quantum optics hardware. Quantum Science and Technology, 6(3):035010, 2021. https:/​/​doi.org/​10.1088/​2058-9565/​abfc94.

[24] R Lora-Serrano, Daniel Julio Garcia, D Betancourth, RP Amaral, NS Camilo, E Estévez-Rams, LA Ortellado GZ, and PG Pagliuso. Dilution effects in spin 7/​2 systems. the case of the antiferromagnet GdRhIn5. Journal of Magnetism and Magnetic Materials, 405:304–310, 2016. https:/​/​doi.org/​10.1016/​j.jmmm.2015.12.093.

[25] Jarrod R McClean, Jonathan Romero, Ryan Babbush, and Alán Aspuru-Guzik. The theory of variational hybrid quantum-classical algorithms. New Journal of Physics, 18(2):023023, 2016. https:/​/​doi.org/​10.1088/​1367-2630/​18/​2/​023023.

[26] Vladyslav Verteletskyi, Tzu-Ching Yen, and Artur F Izmaylov. Measurement optimization in the variational quantum eigensolver using a minimum clique cover. The Journal of chemical physics, 152(12):124114, 2020. https:/​/​doi.org/​10.1063/​1.5141458.

[27] Marco Cerezo, Andrew Arrasmith, Ryan Babbush, Simon C Benjamin, Suguru Endo, Keisuke Fujii, Jarrod R McClean, Kosuke Mitarai, Xiao Yuan, Lukasz Cincio, et al. Variational quantum algorithms. Nature Reviews Physics, 3(9):625–644, 2021. https:/​/​doi.org/​10.1038/​s42254-021-00348-9.

[28] Dmitry A Fedorov, Bo Peng, Niranjan Govind, and Yuri Alexeev. VQE method: A short survey and recent developments. Materials Theory, 6(1):1–21, 2022. https:/​/​doi.org/​10.1186/​s41313-021-00032-6.

[29] Andrew Lucas. Ising formulations of many NP problems. Frontiers in physics, 2:5, 2014. https:/​/​doi.org/​10.3389/​fphy.2014.00005.

[30] Young-Hyun Oh, Hamed Mohammadbagherpoor, Patrick Dreher, Anand Singh, Xianqing Yu, and Andy J. Rindos. Solving multi-coloring combinatorial optimization problems using hybrid quantum algorithms. arXiv preprint arXiv:1911.00595, 2019. https:/​/​doi.org/​10.48550/​arXiv.1911.00595.

[31] Zhihui Wang, Nicholas C. Rubin, Jason M. Dominy, and Eleanor G. Rieffel. XY mixers: Analytical and numerical results for the quantum alternating operator ansatz. Phys. Rev. A, 101:012320, Jan 2020. https:/​/​doi.org/​10.1103/​PhysRevA.101.012320.

[32] Zsolt Tabi, Kareem H. El-Safty, Zsofia Kallus, Peter Haga, Tamas Kozsik, Adam Glos, and Zoltan Zimboras. Quantum optimization for the graph coloring problem with space-efficient embedding. In 2020 IEEE International Conference on Quantum Computing and Engineering (QCE). IEEE, oct 2020. https:/​/​doi.org/​10.1109/​qce49297.2020.00018.

[33] Franz G Fuchs, Herman Oie Kolden, Niels Henrik Aase, and Giorgio Sartor. Efficient encoding of the weighted MAX k-CUT on a quantum computer using qaoa. SN Computer Science, 2(2):89, 2021. https:/​/​doi.org/​10.1007/​s42979-020-00437-z.

[34] Bryan O'Gorman, Eleanor Gilbert Rieffel, Minh Do, Davide Venturelli, and Jeremy Frank. Comparing planning problem compilation approaches for quantum annealing. The Knowledge Engineering Review, 31(5):465–474, 2016. https:/​/​doi.org/​10.1017/​S0269888916000278.

[35] Tobias Stollenwerk, Stuart Hadfield, and Zhihui Wang. Toward quantum gate-model heuristics for real-world planning problems. IEEE Transactions on Quantum Engineering, 1:1–16, 2020. https:/​/​doi.org/​10.1109/​TQE.2020.3030609.

[36] Tobias Stollenwerk, Bryan OGorman, Davide Venturelli, Salvatore Mandra, Olga Rodionova, Hokkwan Ng, Banavar Sridhar, Eleanor Gilbert Rieffel, and Rupak Biswas. Quantum annealing applied to de-conflicting optimal trajectories for air traffic management. IEEE Transactions on Intelligent Transportation Systems, 21(1):285–297, jan 2020. https:/​/​doi.org/​10.1109/​tits.2019.2891235.

[37] Alan Crispin and Alex Syrichas. Quantum annealing algorithm for vehicle scheduling. In 2013 IEEE International Conference on Systems, Man, and Cybernetics. IEEE, 2013. https:/​/​doi.org/​10.1109/​smc.2013.601.

[38] Davide Venturelli, Dominic J. J. Marchand, and Galo Rojo. Quantum annealing implementation of job-shop scheduling. arXiv preprint arXiv:1506.08479, 2015. https:/​/​doi.org/​10.48550/​arXiv.1506.08479.

[39] Tony T. Tran, Minh Do, Eleanor G. Rieffel, Jeremy Frank, Zhihui Wang, Bryan O'Gorman, Davide Venturelli, and J. Christopher Beck. A hybrid quantum-classical approach to solving scheduling problems. In Ninth Annual Symposium on Combinatorial Search. AAAI, 2016. https:/​/​doi.org/​10.1609/​socs.v7i1.18390.

[40] Krzysztof Domino, Mátyás Koniorczyk, Krzysztof Krawiec, Konrad Jałowiecki, and Bartłomiej Gardas. Quantum computing approach to railway dispatching and conflict management optimization on single-track railway lines. arXiv preprint arXiv:2010.08227, 2020. https:/​/​doi.org/​10.48550/​arXiv.2010.08227.

[41] Constantin Dalyac, Loïc Henriet, Emmanuel Jeandel, Wolfgang Lechner, Simon Perdrix, Marc Porcheron, and Margarita Veshchezerova. Qualifying quantum approaches for hard industrial optimization problems. A case study in the field of smart-charging of electric vehicles. EPJ Quantum Technology, 8(1), 2021. https:/​/​doi.org/​10.1140/​epjqt/​s40507-021-00100-3.

[42] David Amaro, Matthias Rosenkranz, Nathan Fitzpatrick, Koji Hirano, and Mattia Fiorentini. A case study of variational quantum algorithms for a job shop scheduling problem. EPJ Quantum Technology, 9(1):5, 2022. https:/​/​doi.org/​10.1140/​epjqt/​s40507-022-00123-4.

[43] Julia Plewa, Joanna Sieńko, and Katarzyna Rycerz. Variational algorithms for workflow scheduling problem in gate-based quantum devices. Computing & Informatics, 40(4), 2021. https:/​/​doi.org/​10.31577/​cai_2021_4_897.

[44] Adam Glos, Aleksandra Krawiec, and Zoltán Zimborás. Space-efficient binary optimization for variational quantum computing. npj Quantum Information, 8(1):39, 2022. https:/​/​doi.org/​10.1038/​s41534-022-00546-y.

[45] Özlem Salehi, Adam Glos, and Jarosław Adam Miszczak. Unconstrained binary models of the travelling salesman problem variants for quantum optimization. Quantum Information Processing, 21(2):67, 2022. https:/​/​doi.org/​10.1007/​s11128-021-03405-5.

[46] David E. Bernal, Sridhar Tayur, and Davide Venturelli. Quantum integer programming (QuIP) 47-779: Lecture notes. arXiv preprint arXiv:2012.11382, 2020. https:/​/​doi.org/​10.48550/​arXiv.2012.11382.

[47] Mark Hodson, Brendan Ruck, Hugh Ong, David Garvin, and Stefan Dulman. Portfolio rebalancing experiments using the quantum alternating operator ansatz. arXiv preprint arXiv:1911.05296, 2019. https:/​/​doi.org/​10.48550/​arXiv.1911.05296.

[48] Sergi Ramos-Calderer, Adrián Pérez-Salinas, Diego García-Martín, Carlos Bravo-Prieto, Jorge Cortada, Jordi Planagumà, and José I. Latorre. Quantum unary approach to option pricing. Phys. Rev. A, 103:032414, 2021. https:/​/​doi.org/​10.1103/​PhysRevA.103.032414.

[49] Kensuke Tamura, Tatsuhiko Shirai, Hosho Katsura, Shu Tanaka, and Nozomu Togawa. Performance comparison of typical binary-integer encodings in an ising machine. IEEE Access, 9:81032–81039, 2021. https:/​/​doi.org/​10.1109/​ACCESS.2021.3081685.

[50] Ludmila Botelho, Adam Glos, Akash Kundu, Jarosław Adam Miszczak, Özlem Salehi, and Zoltán Zimborás. Error mitigation for variational quantum algorithms through mid-circuit measurements. Physical Review A, 105(2):022441, 2022. https:/​/​doi.org/​10.1103/​physreva.105.022441.

[51] Zhihui Wang, Stuart Hadfield, Zhang Jiang, and Eleanor G Rieffel. Quantum approximate optimization algorithm for maxcut: A fermionic view. Physical Review A, 97(2):022304, 2018. https:/​/​doi.org/​10.1103/​physreva.97.022304.

[52] Stuart Andrew Hadfield. Quantum algorithms for scientific computing and approximate optimization. Columbia University, 2018. https:/​/​doi.org/​10.48550/​arXiv.1805.03265.

[53] Matthew B. Hastings. Classical and quantum bounded depth approximation algorithms. quantum Information and Computation, 19(13&14):1116–1140, 2019. https:/​/​doi.org/​10.26421/​QIC19.13-14-3.

[54] Sergey Bravyi, Alexander Kliesch, Robert Koenig, and Eugene Tang. Obstacles to variational quantum optimization from symmetry protection. Physical Review Letters, 125(26):260505, 2020. https:/​/​doi.org/​10.1103/​physrevlett.125.260505.

[55] Alexander M Dalzell, Aram W Harrow, Dax Enshan Koh, and Rolando L La Placa. How many qubits are needed for quantum computational supremacy? Quantum, 4:264, 2020. https:/​/​doi.org/​10.22331/​q-2020-05-11-264.

[56] Daniel Stilck França and Raul Garcia-Patron. Limitations of optimization algorithms on noisy quantum devices. Nature Physics, 17(11):1221–1227, 2021. https:/​/​doi.org/​10.1038/​s41567-021-01356-3.

[57] 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. Physical Review X, 10(2):021067, 2020. https:/​/​doi.org/​10.1103/​physrevx.10.021067.

[58] Boaz Barak and Kunal Marwaha. Classical Algorithms and Quantum Limitations for Maximum Cut on High-Girth Graphs. In Mark Braverman, editor, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022), volume 215 of Leibniz International Proceedings in Informatics (LIPIcs), pages 14:1–14:21, Dagstuhl, Germany, 2022. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. https:/​/​doi.org/​10.4230/​LIPIcs.ITCS.2022.14.

[59] Lennart Bittel and Martin Kliesch. Training variational quantum algorithms is NP-hard. Physical Review Letters, 127(12):120502, 2021. https:/​/​doi.org/​10.1103/​PhysRevLett.127.120502.

[60] Kunal Marwaha and Stuart Hadfield. Bounds on approximating Max $k$ XOR with quantum and classical local algorithms. Quantum, 6:757, 2022. https:/​/​doi.org/​10.22331/​q-2022-07-07-757.

[61] A Barış Özgüler and Davide Venturelli. Numerical gate synthesis for quantum heuristics on bosonic quantum processors. Frontiers in Physics, page 724, 2022. https:/​/​doi.org/​10.3389/​fphy.2022.900612.

[62] Yannick Deller, Sebastian Schmitt, Maciej Lewenstein, Steve Lenk, Marika Federer, Fred Jendrzejewski, Philipp Hauke, and Valentin Kasper. Quantum approximate optimization algorithm for qudit systems with long-range interactions. arXiv preprint arXiv:2204.00340, 2022. https:/​/​doi.org/​10.1103/​physreva.107.062410.

[63] Stuart Hadfield, Zhihui Wang, Eleanor G Rieffel, Bryan O'Gorman, Davide Venturelli, and Rupak Biswas. Quantum approximate optimization with hard and soft constraints. In Proceedings of the Second International Workshop on Post Moores Era Supercomputing, pages 15–21, 2017. https:/​/​doi.org/​10.1145/​3149526.3149530.

[64] Nikolaj Moll, Panagiotis Barkoutsos, Lev S Bishop, Jerry M Chow, Andrew Cross, Daniel J Egger, Stefan Filipp, Andreas Fuhrer, Jay M Gambetta, Marc Ganzhorn, et al. Quantum optimization using variational algorithms on near-term quantum devices. Quantum Science and Technology, 3(3):030503, 2018. https:/​/​doi.org/​10.1088/​2058-9565/​aab822.

[65] Sam McArdle, Tyson Jones, Suguru Endo, Ying Li, Simon C Benjamin, and Xiao Yuan. Variational ansatz-based quantum simulation of imaginary time evolution. npj Quantum Information, 5(1):1–6, 2019. https:/​/​doi.org/​10.1038/​s41534-019-0187-2.

[66] Mario Motta, Chong Sun, Adrian T. K. Tan, Matthew J. O'Rourke, Erika Ye, Austin J. Minnich, Fernando G. S. L. Brandão, and Garnet Kin-Lic Chan. Determining eigenstates and thermal states on a quantum computer using quantum imaginary time evolution. Nature Physics, 16(2):205–210, 2019. https:/​/​doi.org/​10.1038/​s41567-019-0704-4.

[67] Ryan O'Donnell. Analysis of Boolean functions. Cambridge University Press, 2014.

[68] Kyle E. C. Booth, Bryan O'Gorman, Jeffrey Marshall, Stuart Hadfield, and Eleanor Rieffel. Quantum-accelerated constraint programming. Quantum, 5:550, September 2021. https:/​/​doi.org/​10.22331/​q-2021-09-28-550.

[69] Adriano Barenco, Charles H Bennett, Richard Cleve, David P DiVincenzo, Norman Margolus, Peter Shor, Tycho Sleator, John A Smolin, and Harald Weinfurter. Elementary gates for quantum computation. Physical review A, 52(5):3457, 1995. https:/​/​doi.org/​10.1103/​PhysRevA.52.3457.

[70] V.V. Shende and I.L. Markov. On the CNOT cost of TOFFOLI gates. Quantum Information and Computation, 9(5&6):461–486, 2009. https:/​/​doi.org/​10.26421/​qic8.5-6-8.

[71] Mehdi Saeedi and Igor L Markov. Synthesis and optimization of reversible circuits—a survey. ACM Computing Surveys (CSUR), 45(2):1–34, 2013. https:/​/​doi.org/​10.1145/​2431211.2431220.

[72] Gian Giacomo Guerreschi. Solving quadratic unconstrained binary optimization with divide-and-conquer and quantum algorithms. arXiv preprint arXiv:2101.07813, 2021. https:/​/​doi.org/​10.48550/​arXiv.2101.07813.

[73] Zain H. Saleem, Teague Tomesh, Michael A. Perlin, Pranav Gokhale, and Martin Suchara. Quantum divide and conquer for combinatorial optimization and distributed computing. arXiv preprint arXiv:2107.07532, 2021. https:/​/​doi.org/​10.48550/​arXiv.2107.07532.

[74] Daniel A Lidar and Todd A Brun. Quantum error correction. Cambridge university press, 2013.

[75] Nicholas Chancellor. Domain wall encoding of discrete variables for quantum annealing and qaoa. Quantum Science and Technology, 4(4):045004, 2019. https:/​/​doi.org/​10.1088/​2058-9565/​ab33c2.

[76] Jesse Berwald, Nicholas Chancellor, and Raouf Dridi. Understanding domain-wall encoding theoretically and experimentally. Philosophical Transactions of the Royal Society A, 381(2241):20210410, 2023. https:/​/​doi.org/​10.1098/​rsta.2021.0410.

[77] Jie Chen, Tobias Stollenwerk, and Nicholas Chancellor. Performance of domain-wall encoding for quantum annealing. IEEE Transactions on Quantum Engineering, 2:1–14, 2021. https:/​/​doi.org/​10.1109/​tqe.2021.3094280.

[78] Mark W Johnson, Mohammad HS Amin, Suzanne Gildert, Trevor Lanting, Firas Hamze, Neil Dickson, Richard Harris, Andrew J Berkley, Jan Johansson, Paul Bunyk, et al. Quantum annealing with manufactured spins. Nature, 473(7346):194–198, 2011. https:/​/​doi.org/​10.1038/​nature10012.

[79] Zoe Gonzalez Izquierdo, Shon Grabbe, Stuart Hadfield, Jeffrey Marshall, Zhihui Wang, and Eleanor Rieffel. Ferromagnetically shifting the power of pausing. Physical Review Applied, 15(4):044013, 2021. https:/​/​doi.org/​10.1103/​physrevapplied.15.044013.

[80] Davide Venturelli and Alexei Kondratyev. Reverse quantum annealing approach to portfolio optimization problems. Quantum Machine Intelligence, 1(1):17–30, 2019. https:/​/​doi.org/​10.1007/​s42484-019-00001-w.

[81] Nike Dattani, Szilard Szalay, and Nick Chancellor. Pegasus: The second connectivity graph for large-scale quantum annealing hardware. arXiv preprint arXiv:1901.07636, 2019. https:/​/​doi.org/​10.48550/​arXiv.1901.07636.

[82] Wolfgang Lechner, Philipp Hauke, and Peter Zoller. A quantum annealing architecture with all-to-all connectivity from local interactions. Science advances, 1(9):e1500838, 2015. https:/​/​doi.org/​10.1126/​sciadv.1500838.

[83] MS Sarandy and DA Lidar. Adiabatic quantum computation in open systems. Physical review letters, 95(25):250503, 2005. https:/​/​doi.org/​10.1103/​physrevlett.95.250503.

[84] MHS Amin, Peter J Love, and CJS Truncik. Thermally assisted adiabatic quantum computation. Physical review letters, 100(6):060503, 2008. https:/​/​doi.org/​10.1103/​physrevlett.100.060503.

[85] Sergio Boixo, Tameem Albash, Federico M Spedalieri, Nicholas Chancellor, and Daniel A Lidar. Experimental signature of programmable quantum annealing. Nature communications, 4(1):2067, 2013. https:/​/​doi.org/​10.1038/​ncomms3067.

[86] Kostyantyn Kechedzhi and Vadim N Smelyanskiy. Open-system quantum annealing in mean-field models with exponential degeneracy. Physical Review X, 6(2):021028, 2016. https:/​/​doi.org/​10.1103/​physrevx.6.021028.

[87] Gianluca Passarelli, Ka-Wa Yip, Daniel A Lidar, and Procolo Lucignano. Standard quantum annealing outperforms adiabatic reverse annealing with decoherence. Physical Review A, 105(3):032431, 2022. https:/​/​doi.org/​10.1103/​physreva.105.032431.

[88] Stefanie Zbinden, Andreas Bärtschi, Hristo Djidjev, and Stephan Eidenbenz. Embedding algorithms for quantum annealers with chimera and pegasus connection topologies. In International Conference on High Performance Computing, pages 187–206. Springer, 2020. https:/​/​doi.org/​10.1007/​978-3-030-50743-5_10.

[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(4):040322, 2021. https:/​/​doi.org/​10.1103/​prxquantum.2.040322.

[90] Aniruddha Bapat and Stephen Jordan. Bang-bang control as a design principle for classical and quantum optimization algorithms. arXiv preprint arXiv:1812.02746, 2018. https:/​/​doi.org/​10.26421/​qic19.5-6-4.

[91] Ruslan Shaydulin, Stuart Hadfield, Tad Hogg, and Ilya Safro. Classical symmetries and the quantum approximate optimization algorithm. Quantum Information Processing, 20(11):1–28, 2021. https:/​/​doi.org/​10.48550/​arXiv.2012.04713.

[92] Vishwanathan Akshay, Daniil Rabinovich, Ernesto Campos, and Jacob Biamonte. Parameter concentrations in quantum approximate optimization. Physical Review A, 104(1):L010401, 2021. https:/​/​doi.org/​10.1103/​physreva.104.l010401.

[93] Michael Streif and Martin Leib. Training the quantum approximate optimization algorithm without access to a quantum processing unit. Quantum Science and Technology, 5(3):034008, 2020. https:/​/​doi.org/​10.1088/​2058-9565/​ab8c2b.

[94] Guillaume Verdon, Michael Broughton, Jarrod R McClean, Kevin J Sung, Ryan Babbush, Zhang Jiang, Hartmut Neven, and Masoud Mohseni. Learning to learn with quantum neural networks via classical neural networks. arXiv preprint arXiv:1907.05415, 2019. https:/​/​doi.org/​10.48550/​arXiv.1907.05415.

[95] Max Wilson, Rachel Stromswold, Filip Wudarski, Stuart Hadfield, Norm M Tubman, and Eleanor G Rieffel. Optimizing quantum heuristics with meta-learning. Quantum Machine Intelligence, 3(1):1–14, 2021. https:/​/​doi.org/​10.1007/​s42484-020-00022-w.

[96] Alicia B Magann, Kenneth M Rudinger, Matthew D Grace, and Mohan Sarovar. Feedback-based quantum optimization. Physical Review Letters, 129(25):250502, 2022. https:/​/​doi.org/​10.1103/​physrevlett.129.250502.

[97] Lucas T Brady, Christopher L Baldwin, Aniruddha Bapat, Yaroslav Kharkov, and Alexey V Gorshkov. Optimal protocols in quantum annealing and quantum approximate optimization algorithm problems. Physical Review Letters, 126(7):070505, 2021. https:/​/​doi.org/​10.1103/​physrevlett.126.070505.

[98] Jonathan Wurtz and Peter J Love. Counterdiabaticity and the quantum approximate optimization algorithm. Quantum, 6:635, 2022. https:/​/​doi.org/​10.22331/​q-2022-01-27-635.

[99] Andreas Bärtschi and Stephan Eidenbenz. Grover mixers for QAOA: Shifting complexity from mixer design to state preparation. In 2020 IEEE International Conference on Quantum Computing and Engineering (QCE), pages 72–82. IEEE, 2020. https:/​/​doi.org/​10.1109/​qce49297.2020.00020.

[100] Daniel J Egger, Jakub Mareček, and Stefan Woerner. Warm-starting quantum optimization. Quantum, 5:479, 2021. https:/​/​doi.org/​10.22331/​q-2021-06-17-479.

[101] Jonathan Wurtz and Peter J Love. Classically optimal variational quantum algorithms. IEEE Transactions on Quantum Engineering, 2:1–7, 2021. https:/​/​doi.org/​10.1109/​tqe.2021.3122568.

[102] Xiaoyuan Liu, Anthony Angone, Ruslan Shaydulin, Ilya Safro, Yuri Alexeev, and Lukasz Cincio. Layer VQE: A variational approach for combinatorial optimization on noisy quantum computers. IEEE Transactions on Quantum Engineering, 3:1–20, 2022. https:/​/​doi.org/​10.1109/​tqe.2021.3140190.

[103] Jarrod R McClean, Sergio Boixo, Vadim N Smelyanskiy, Ryan Babbush, and Hartmut Neven. Barren plateaus in quantum neural network training landscapes. Nature communications, 9(1):1–6, 2018. https:/​/​doi.org/​10.1038/​s41467-018-07090-4.

[104] Linghua Zhu, Ho Lun Tang, George S Barron, FA Calderon-Vargas, Nicholas J Mayhall, Edwin Barnes, and Sophia E Economou. Adaptive quantum approximate optimization algorithm for solving combinatorial problems on a quantum computer. Physical Review Research, 4(3):033029, 2022. https:/​/​doi.org/​10.1103/​physrevresearch.4.033029.

[105] Bence Bakó, Adam Glos, Özlem Salehi, and Zoltán Zimborás. Near-optimal circuit design for variational quantum optimization. arXiv preprint arXiv:2209.03386, 2022. https:/​/​doi.org/​10.48550/​arXiv.2209.03386.

[106] Itay Hen and Marcelo S Sarandy. Driver hamiltonians for constrained optimization in quantum annealing. Physical Review A, 93(6):062312, 2016. https:/​/​doi.org/​10.1103/​physreva.93.062312.

[107] Itay Hen and Federico M Spedalieri. Quantum annealing for constrained optimization. Physical Review Applied, 5(3):034007, 2016. https:/​/​doi.org/​10.1103/​PhysRevApplied.5.034007.

[108] Yue Ruan, Samuel Marsh, Xilin Xue, Xi Li, Zhihao Liu, and Jingbo Wang. Quantum approximate algorithm for NP optimization problems with constraints. arXiv preprint arXiv:2002.00943, 2020. https:/​/​doi.org/​10.48550/​arXiv.2002.00943.

[109] Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press, New York, NY, USA, 10th edition, 2011.

[110] Masuo Suzuki. Decomposition formulas of exponential operators and Lie exponentials with some applications to quantum mechanics and statistical physics. Journal of mathematical physics, 26(4):601–612, 1985. https:/​/​doi.org/​10.1063/​1.526596.

[111] Michael Streif, Martin Leib, Filip Wudarski, Eleanor Rieffel, and Zhihui Wang. Quantum algorithms with local particle-number conservation: Noise effects and error correction. Physical Review A, 103(4):042412, 2021. https:/​/​doi.org/​10.1103/​physreva.103.042412.

[112] Vishwanathan Akshay, Hariphan Philathong, Mauro ES Morales, and Jacob D Biamonte. Reachability deficits in quantum approximate optimization. Physical review letters, 124(9):090504, 2020. https:/​/​doi.org/​10.22331/​q-2021-08-30-532.

[113] Franz Georg Fuchs, Kjetil Olsen Lye, Halvor Møll Nilsen, Alexander Johannes Stasik, and Giorgio Sartor. Constraint preserving mixers for the quantum approximate optimization algorithm. Algorithms, 15(6):202, 2022. https:/​/​doi.org/​10.3390/​a15060202.

[114] Vandana Shukla, O. P. Singh, G. R. Mishra, and R. K. Tiwari. Application of CSMT gate for efficient reversible realization of binary to gray code converter circuit. In 2015 IEEE UP Section Conference on Electrical Computer and Electronics (UPCON). IEEE, dec 2015. https:/​/​doi.org/​10.1109/​UPCON.2015.7456731.

[115] Alexander Slepoy. Quantum gate decomposition algorithms. Technical report, Sandia National Laboratories, 2006. https:/​/​doi.org/​10.2172/​889415.

[116] Bryan T. Gard, Linghua Zhu, George S. Barron, Nicholas J. Mayhall, Sophia E. Economou, and Edwin Barnes. Efficient symmetry-preserving state preparation circuits for the variational quantum eigensolver algorithm. npj Quantum Information, 6(1), 2020. https:/​/​doi.org/​10.1038/​s41534-019-0240-1.

[117] D.P. DiVincenzo and J. Smolin. Results on two-bit gate design for quantum computers. In Proceedings Workshop on Physics and Computation. PhysComp 94. IEEE Comput. Soc. Press, 1994. https:/​/​doi.org/​10.48550/​arXiv.cond-mat/​9409111.

[118] David Joseph, Adam Callison, Cong Ling, and Florian Mintert. Two quantum ising algorithms for the shortest-vector problem. Physical Review A, 103(3):032433, 2021. https:/​/​doi.org/​10.1103/​PhysRevA.103.032433.

[119] Peter Brucker. Scheduling Algorithms. Springer-Verlag Berlin Heidelberg, 2004.

[120] AMA Hariri and Chris N Potts. Single machine scheduling with batch set-up times to minimize maximum lateness. Annals of Operations Research, 70:75–92, 1997. https:/​/​doi.org/​10.1023/​A:1018903027868.

[121] Xiaoqiang Cai, Liming Wang, and Xian Zhou. Single-machine scheduling to stochastically minimize maximum lateness. Journal of Scheduling, 10(4):293–301, 2007. https:/​/​doi.org/​10.1007/​s10951-007-0026-8.

[122] Derya Eren Akyol and G Mirac Bayhan. Multi-machine earliness and tardiness scheduling problem: an interconnected neural network approach. The International Journal of Advanced Manufacturing Technology, 37(5):576–588, 2008. https:/​/​doi.org/​10.1007/​s00170-007-0993-0.

[123] Michele Conforti, Gérard Cornuéjols, Giacomo Zambelli, et al. Integer programming, volume 271. Springer, 2014.

[124] Hannes Leipold and Federico M Spedalieri. Constructing driver hamiltonians for optimization problems with linear constraints. Quantum Science and Technology, 7(1):015013, 2021. https:/​/​doi.org/​10.1088/​2058-9565/​ac16b8.

[125] Masuo Suzuki. Generalized Trotter's formula and systematic approximants of exponential operators and inner derivations with applications to many-body problems. Communications in Mathematical Physics, 51(2):183–190, 1976. https:/​/​doi.org/​10.1007/​BF01609348.

[126] Dominic W. Berry and Andrew M. Childs. Black-box hamiltonian simulation and unitary implementation. Quantum Info. Comput., 12(1–2):29–62, 2012. https:/​/​doi.org/​10.26421/​qic12.1-2-4.

[127] D. W. Berry, A. M. Childs, and R. Kothari. Hamiltonian simulation with nearly optimal dependence on all parameters. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 792–809, 2015. https:/​/​doi.org/​10.1109/​FOCS.2015.54.

[128] Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, and Rolando D. Somma. Simulating Hamiltonian dynamics with a truncated Taylor series. Physical Review Letters, 114(9):090502, 2015. https:/​/​doi.org/​10.1103/​PhysRevLett.114.090502.

[129] Guang Hao Low and Isaac L. Chuang. Optimal hamiltonian simulation by quantum signal processing. Phys. Rev. Lett., 118:010501, 2017. https:/​/​doi.org/​10.1103/​PhysRevLett.118.010501.

[130] Guang Hao Low and Isaac L. Chuang. Hamiltonian simulation by qubitization. Quantum, 3:163, 2019. https:/​/​doi.org/​10.22331/​q-2019-07-12-163.

[131] Andrew M. Childs, Aaron Ostrander, and Yuan Su. Faster quantum simulation by randomization. Quantum, 3:182, 2019. https:/​/​doi.org/​10.22331/​q-2019-09-02-182.

[132] Earl Campbell. Random Compiler for Fast Hamiltonian Simulation. Physical Review Letters, 123(7):070503, 2019. https:/​/​doi.org/​10.1103/​PhysRevLett.123.070503.

[133] Andrew M. Childs, Yuan Su, Minh C. Tran, Nathan Wiebe, and Shuchen Zhu. Theory of trotter error with commutator scaling. Phys. Rev. X, 11:011020, 2021. https:/​/​doi.org/​10.1103/​PhysRevX.11.011020.

[134] Albert T Schmitz, Nicolas PD Sawaya, Sonika Johri, and AY Matsuura. Graph optimization perspective for low-depth trotter-suzuki decomposition. arXiv preprint arXiv:2103.08602, 2021. https:/​/​doi.org/​10.48550/​arXiv.2103.08602.

[135] Nicolas PD Sawaya. mat2qubit: A lightweight pythonic package for qubit encodings of vibrational, bosonic, graph coloring, routing, scheduling, and general matrix problems. arXiv preprint arXiv:2205.09776, 2022. https:/​/​doi.org/​10.48550/​arXiv.2205.09776.

[136] Pauli Virtanen, Ralf Gommers, Travis E. Oliphant, Matt Haberland, Tyler Reddy, David Cournapeau, Evgeni Burovski, Pearu Peterson, Warren Weckesser, Jonathan Bright, Stéfan J. van der Walt, Matthew Brett, Joshua Wilson, K. Jarrod Millman, Nikolay Mayorov, Andrew R. J. Nelson, Eric Jones, Robert Kern, Eric Larson, C J Carey, İlhan Polat, Yu Feng, Eric W. Moore, Jake VanderPlas, Denis Laxalde, Josef Perktold, Robert Cimrman, Ian Henriksen, E. A. Quintero, Charles R. Harris, Anne M. Archibald, Antônio H. Ribeiro, Fabian Pedregosa, Paul van Mulbregt, and SciPy 1.0 Contributors. SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python. Nature Methods, 17:261–272, 2020. https:/​/​doi.org/​10.1038/​s41592-019-0686-2.

[137] Jarrod R McClean, Nicholas C Rubin, Kevin J Sung, Ian D Kivlichan, Xavier Bonet-Monroig, Yudong Cao, Chengyu Dai, E Schuyler Fried, Craig Gidney, Brendan Gimby, et al. Openfermion: the electronic structure package for quantum computers. Quantum Science and Technology, 5(3):034014, 2020. https:/​/​doi.org/​10.1088/​2058-9565/​ab8ebc.

[138] Aaron Meurer, Christopher P Smith, Mateusz Paprocki, Ondřej Čertík, Sergey B Kirpichev, Matthew Rocklin, AMiT Kumar, Sergiu Ivanov, Jason K Moore, Sartaj Singh, et al. Sympy: symbolic computing in Python. PeerJ Computer Science, 3:e103, 2017. https:/​/​doi.org/​10.7717/​peerj-cs.103.

[139] Pradnya Khalate, Xin-Chuan Wu, Shavindra Premaratne, Justin Hogaboam, Adam Holmes, Albert Schmitz, Gian Giacomo Guerreschi, Xiang Zou, and AY Matsuura. An LLVM-based C++ compiler toolchain for variational hybrid quantum-classical algorithms and quantum accelerators. arXiv preprint arXiv:2202.11142, 2022. https:/​/​doi.org/​10.48550/​arXiv.2202.11142.

[140] C. A. Ryan, C. Negrevergne, M. Laforest, E. Knill, and R. Laflamme. Liquid-state nuclear magnetic resonance as a testbed for developing quantum control methods. Phys. Rev. A, 78:012328, Jul 2008. https:/​/​doi.org/​10.1103/​PhysRevA.78.012328.

[141] Richard Versluis, Stefano Poletto, Nader Khammassi, Brian Tarasinski, Nadia Haider, David J Michalak, Alessandro Bruno, Koen Bertels, and Leonardo DiCarlo. Scalable quantum circuit and control for a superconducting surface code. Physical Review Applied, 8(3):034021, 2017. https:/​/​doi.org/​10.1103/​physrevapplied.8.034021.

[142] Bjoern Lekitsch, Sebastian Weidt, Austin G Fowler, Klaus Mølmer, Simon J Devitt, Christof Wunderlich, and Winfried K Hensinger. Blueprint for a microwave trapped ion quantum computer. Science Advances, 3(2):e1601540, 2017. https:/​/​doi.org/​10.1126/​sciadv.1601540.

Cited by

[1] Nicolas PD Sawaya, Daniel Marti-Dafcik, Yang Ho, Daniel P Tabor, David Bernal, Alicia B Magann, Shavindra Premaratne, Pradeep Dubey, Anne Matsuura, Nathan Bishop, Wibe A de Jong, Simon Benjamin, Ojas D Parekh, Norm Tubman, Katherine Klymko, and Daan Camps, "HamLib: A library of Hamiltonians for benchmarking quantum algorithms and hardware", arXiv:2306.13126, (2023).

[2] Federico Dominguez, Josua Unger, Matthias Traube, Barry Mant, Christian Ertler, and Wolfgang Lechner, "Encoding-Independent Optimization Problem Formulation for Quantum Computing", arXiv:2302.03711, (2023).

[3] Ioannis D. Leonidas, Alexander Dukakis, Benjamin Tan, and Dimitris G. Angelakis, "Qubit efficient quantum algorithms for the vehicle routing problem on NISQ processors", arXiv:2306.08507, (2023).

[4] Nicolas PD Sawaya and Joonsuk Huh, "Improved resource-tunable near-term quantum algorithms for transition probabilities, with applications in physics and variational quantum linear algebra", arXiv:2206.14213, (2022).

The above citations are from SAO/NASA ADS (last updated successfully 2023-09-22 13:23:52). The list may be incomplete as not all publishers provide suitable and complete citation data.

On Crossref's cited-by service no data on citing works was found (last attempt 2023-09-22 13:23:50).