Abstract
Although quantum computing hardware has evolved significantly in recent years, spurred by increasing industrial and government interest, the size limitation of current generation quantum computers remains an obstacle when applying these devices to relevant, real-world problems. In order to effectively exploit the potential benefits of quantum computing, heterogeneous approaches that combine both classical and quantum computing techniques are needed. In this work, we explore multiple heterogeneous algorithms for solving a variety of industry-relevant benchmark problems in order to understand how best to leverage quantum computers given current constraints. Our results indicate the following: (1) that solver performance is highly dependent on the structure (size and edge density) of the problem graph; (2) that reusing a single fixed problem embedding, as opposed to dynamically searching for problem embeddings, is key to avoiding computational bottlenecks; (3) that solutions of better quality are produced by algorithms that iteratively propagate the influence that solving an individual sub-problem has to the remainder of the larger problem; and (4) that the Qbsolv algorithm (which implements the aforementioned techniques) is, at this time, the state-of-the-art in producing quality solutions, in a timely fashion, to a variety of theoretical and real-world problems too large to directly embed onto a quantum annealing device.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Ajagekar A, Humble T, You F (2020) Quantum computing based hybrid solution strategies for large-scale discrete-continuous optimization problems. Comput Chem Eng 132(607):1–50. ISSN 00981354. https://doi.org/10.1016/j.compchemeng.2019.106630
Arute F et al (2019) Quantum supremacy using a programmable superconducting processor. Nature 574(7779):505–510. ISSN 14764687. https://doi.org/10.1038/s41586-019-1666-5
Bass G, Tomlin C, Kumar V, Rihaczek P, Dulny J (2018) Heterogeneous quantum computing for satellite constellation optimization: solving the weighted k-clique problem. Quantum Sci Technol 3 (2):24010. ISSN 2058-9565. https://doi.org/10.1088/2058-9565/aaadc2
Bian Z, Chudak F, Israel R, Lackey B, Macready WG, Roy A (2014) Discrete optimization using quantum annealing on sparse Ising models. Front Phys 2:56. ISSN 2296-424X. https://doi.org/10.3389/fphy.2014.00056
Bian Z, Chudak F, Israel R, Lackey B, Macready WG, Roy A (2016) Mapping constrained optimization problems to quantum annealing with application to fault diagnosis. http://arxiv.org/1603.03111
Booth M, Reinhardt SP, Roy A (2017) Partitioning optimization problems for hybrid classical/quantum execution. www.dwavesys.com
Brooke J, Bitko D, Rosenbaum T~F, Aeppli G (1999) Quantum annealing of a disordered magnet. Science 284:779. https://doi.org/10.1126/science.284.5415.779
Cai J, Macready W~G, Roy A (2014) A practical heuristic for finding graph minors. ArXiv e-prints
Chapuis G, Djidjev H, Hahn G, Rizk G (2019) Finding maximum cliques on the D-wave quantum annealer. J Signal Process Syst 91(3-4):363–377. ISSN 1939-8018. https://doi.org/10.1007/s11265-018-1357-8
D-Wave (2018) The D-Wave 2000Q System
Djidjev HN, Chapuis G, Hahn G, Rizk G (2018) Efficient combinatorial optimization using quantum annealing. pp 1–25, http://arxiv.org/abs/1801.08653
Djidjev HN, Hahn G, Mniszewski SM, Negre CFA, Niklasson AMN, Sardeshmukh VB (2016) Graph partitioning methods for fast parallel quantum molecular dynamics. http://arxiv.org/abs/1605.01118
Farhi E, Goldstone J, Gutmann S, Lapan J, Lundgren A, Preda D (2001) A quantum adiabatic evolution algorithm applied to random instances of an NP-Complete problem. Science 292(5516):472. http://science.sciencemag.org/content/292/5516/472.abstract
Finnila A~B, Gomez M~A, Sebenik C, Stenson C, Doll J~D (1994) Quantum annealing: a new method for minimizing multidimensional functions, vol 219
Fruchterman TMJ, Reingold EM (1991) Graph drawing by force-directed placement. Software: Practice and Experience 21(11):1129–1164. ISSN 0038-0644. https://doi.org/10.1002/spe.4380211102
Garey MR, Johnson DS (1990) Computers and intractability; a guide to the theory of NP-completeness. W. H. Freeman & Co., New York. ISBN 0716710455
Goldberg DE, Holland JH (1988) Genetic algorithms and machine learning. Mach Learn 3(2):95–99. ISSN 1573-0565. https://doi.org/10.1023/A:1022602019183
Hagberg AA, Schult DAS, Swart PJ (2008) Exploring network structure, dynamics, and function using NetworkX. In: Proceedings of the 7th python in science conference (SciPy2008)
Henderson M, Novak J, Cook T (2019) Leveraging quantum annealing for election forecasting. J Phys Soc Japan 88(6):061009. https://doi.org/10.7566/JPSJ.88.061009
Holland JH (1992) Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence, 2nd edn. MIT Press, Cambridge
Job Joshua, Adachi Steve (2020)
Kadowaki T, Nishimori H (1998) Quantum annealing in the transverse Ising model. Phys Rev E 58:5355–5363. https://doi.org/10.1103/PhysRevE.58.5355
Lucas A (2014) Ising formulations of many NP problems. Front Phys 2:5. https://doi.org/10.3389/fphy.2014.00005
Neven H, Denchev VS, Rose G, Macready WG (2012) Qboost: Large scale classifier training with adiabatic quantum optimization. In: Hoi SCH, Buntine W (eds) Proceedings of the Asian conference on machine learning, vol 25 of proceedings of machine learning research. PMLR. http://proceedings.mlr.press/v25/neven12.html. Singapore Management University, Singapore, pp 333–348
Noori M, Vedaie SS, Singh I, Crawford D, Oberoi JS, Sanders BC, Zahedinejad E (2020) Analog-quantum feature mapping for machine-learning applications. Phys Rev Appl 14:034034. https://doi.org/10.1103/PhysRevApplied.14.034034
Preskill J (2018) Quantum Computing in the NISQ era and beyond. https://doi.org/10.22331/q-2018-08-06-79. arXiv:1801.00862
Reinelt G (1995) Tsplib 95. interdisziplinäres Zentrum für Wissenschaftliches Rechnen (IWR). Heidelberg 338:1–16
Salakhutdinov R, Hinton G (2009) Deep Boltzmann machines. Aistats 1(3):448–455. ISSN 1063-6919. https://doi.org/10.1109/CVPRW.2009.5206577
Santoro G~E, Marto\v nák R , Tosatti E, Car R (2002) Theory of quantum annealing of an Ising spin glass. Science 295:2427–2430. https://doi.org/10.1126/science.1068774
Santoro GE, Tosatti E (2006) Optimization using quantum mechanics: quantum annealing through adiabatic evolution. J Phys A: Math Gen 39(36):R393. http://stacks.iop.org/0305-4470/39/i=36/a=R01
Squires RR, Hoffman KL (2014) A military maintenance planning and scheduling problem. Optim Lett 9(8):1675–1688. ISSN 18624480. https://doi.org/10.1007/s11590-014-0814-y
Acknowledgements
The authors would like to acknowledge the support of the Universities Space Research Association, Quantum AI Lab Research Opportunity Program, Cycle 2, for providing us with remote access to a D-Wave 2000Q device. Additionally, the thoughtful reviews and suggestions from Duncan Fletcher are acknowledged.
We would also like to thank the anonymous reviewers for the helpful comments and suggestions which have significantly improved the manuscript.
Funding
This work was funded through the Air Force Research Laboratory, Contract No. FA8750-18-C-0167.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher’s note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Bass, G., Henderson, M., Heath, J. et al. Optimizing the optimizer: decomposition techniques for quantum annealing. Quantum Mach. Intell. 3, 10 (2021). https://doi.org/10.1007/s42484-021-00039-9
Received:
Accepted:
Published:
DOI: https://doi.org/10.1007/s42484-021-00039-9