Quantum Bridge Analytics I: a tutorial on formulating and using QUBO models | 4OR Skip to main content
Springer Nature Link
Log in

Quantum Bridge Analytics I: a tutorial on formulating and using QUBO models

  • Invited Survey
  • Published:
4OR Aims and scope Submit manuscript

Abstract

Quantum Bridge Analytics relates generally to methods and systems for hybrid classical-quantum computing, and more particularly is devoted to developing tools for bridging classical and quantum computing to gain the benefits of their alliance in the present and enable enhanced practical application of quantum computing in the future. This is the first of a two-part tutorial that surveys key elements of Quantum Bridge Analytics and its applications, with an emphasis on supplementing models with numerical illustrations. In Part 1 (the present paper) we focus on the Quadratic Unconstrained Binary Optimization model which is presently the most widely applied optimization model in the quantum computing area, and which unifies a rich variety of combinatorial optimization problems.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

Notes

  1. This adds a constant to the QUBO model, which is irrelevant for optimization.

  2. Reference to quantum computing would not be complete without mentioning Google’s recent claim to achieving ‘quantum supremacy.’ This outcome has no bearing on the computational considerations discussed here. See, for example Preskill (2019).

References

  • Ailon N, Charikar M, Newman A (2008) Aggregating inconsistent information: ranking and clustering. J ACM (JACM) 55(5):23

    Article  Google Scholar 

  • Aimone JB, Hamilton KE, Mniszewsk S, Reeder L, Schuman CD, Severa WM (2018) Non-neural network applications for spiking neuromorphic hardware. In: PMES workshop

  • Albash T, Lidar DA (2015) Decoherence in adiabatic quantum computation. Phys Rev A 91: 062320. arXiv:1503.08767v2

  • Albash T, Hen I, Spedalieri FM, Lidar DA (2015) Reexamination of the evidence for entanglement in the D-Wave processor. Phys Rev A 92:62328. arXiv:1506.03539v2

  • Aliadee B, Glover F, Kochenberger G, Rego C (2005) A new modeling and solution approach for the number partitioning problem. Appl Math Decis Sci 9(2):135–145

    Google Scholar 

  • Alidaee B, Kochenberger G, Lewis K, Lewis M, Wang H (2008) A new approach for modeling and solving set packing problems. Eur J Oper Res 186(2):504–512

    Article  Google Scholar 

  • Aloise D, Cafieri S, Caporossi G, Hansen P, Perron S, Liberti L (2010) Column generation algorithms for exact modularity maximization in networks. Phys Rev E 82(4):046112

    Article  Google Scholar 

  • Alom MZ, Van Essen B, Moody AT, Widemann DP, Taha TM (2017) Quadratic unconstrained binary optimization (QUBO) on neuromorphic computing system. In: IEEE 2017 international joint conference on neural networks (IJCNN). https://doi.org/10.1109/ijcnn.2017.7966350

  • Alpha-QUBO (2019). http://meta-analytics.net/Home/AlphaQUBO

  • Amin MHS, Truncik CJS, Averin DV (2008) Role of single qubit decoherence time in adiabatic quantum computation. Phys Rev A 80: 022303. arXiv:0803.1196v2

  • Anthony M, Boros E, Crama Y, Gruber A (2017) Quadratic reformulations of nonlinear binary optimization problems. Math Program 162(1–2):115–144

    Article  Google Scholar 

  • Aramon M, Rosenberger G, Valiante E, Miyazawa T, Tamura H, Katzgraber HG (2019) Physics-inspired optimization for quadratic unconstrained problems using a digital annealer. Front Phys 7:48

    Article  Google Scholar 

  • Berwald JJ, Gottlieb JM, Munch E (2018) Computing Wasserstein distance for persistence diagrams on a quantum computer. arXiv:1809.06433

  • Boixo S, Rønnow TF, Isakov SV, Wang Z, Wecker D, Lidar DA, Martinis JM, Troyer M (2014) Evidence for quantum annealing with more than one hundred qubits. Nat Phys 10:218–224

    Article  Google Scholar 

  • Boros E, Hammer P (1991) The max-cut problem and quadratic 0–1 optimization: polyhedral aspects, relaxations and bounds. Ann Oper Res 33(3):151–180

    Article  Google Scholar 

  • Boros E, Hammer P (2002) Pseudo-boolean optimization. Discrete Appl Math 123(1):155–225

    Article  Google Scholar 

  • Boros E, Hammer PL, Sun R, Tavares G (2008) A max-flow approach to improved lower bounds for quadratic unconstrained binary optimization (QUBO). Discrete Optim 5(2):501–529

    Article  Google Scholar 

  • Chapuis G, Djidjev H, Hahn G, Rizk G (2018) Finding maximum cliques on the D-wave quantum annealer. J Signal Process Syst. https://doi.org/10.1007/s11265-018-1357-8

    Article  Google Scholar 

  • Clark J, West T, Zammit J, Guo X, Mason L, Russell D (2019) Towards real time multi-robot routing using quantum computing technologies. In: HPC Asia 2019 proceedings of the international conference on high performance computing in Asia-Pacific region, pp 111–119

  • Date P, Patton R, Schuman C, Potok T (2019) Efficiently embedding QUBO problems on adiabatic quantum computers. Quantum Inf Process 18:117. https://doi.org/10.1007/s11128-019-2236-3

    Article  Google Scholar 

  • Debenedictis EP (2019) A future with quantum machine learning. IEEE Comput Edge 5(3):24–27

    Google Scholar 

  • Elsokkary N, Khan FS, Humble TS, Torre DL, Gottlieb J (2017) Financial portfolio management using D-wave, quantum optimizer: the case of abu dhabi securities exchange. In: 2017 IEEE high-performance extreme computing (HPEC)

  • Farhi E, Goldstone J (2014) A quantum approximate optimization algorithm. arXiv:1411.4028

  • Feld S, Roch C, Gabor T, Seidel C, Neukart F, Galter I, Mauerer W, Linnhoff-Popien C (2018) A hybrid solution method for the capacitated vehicle routing problem using a quantum annealer. arXiv:1811.07403

  • Glover F (1996) Tabu search and adaptive memory programming–advances, applications and challenges. In: Barr RS, Helgason RV, Kennington JL (eds) Interfaces in computer science and operations research. Kluwer Academic Publishers, Springer, pp 1–75

    Google Scholar 

  • Glover F (1997) A template for scatter search and path relinking, in artificial evolution. In: Hao JK, Lutton E, Ronald E, Schoenauer M, Snyers D (eds) Lecture notes in computer science, vol 1363. Springer, pp 13–54

  • Glover F, Kochenberger G (2019) Quantum bridge analytics & QUBO 2.0. In: Quantum insight conference 2019, invited presentation 10/04/19, LHOFT—Luxembourg House of Financial Technology, 9, rue du Laboratoire, Luxembourg

  • Glover F, Laguna M (1997) Tabu search. Kluwer Academic Publishers, Boston

    Book  Google Scholar 

  • Glover F, Mulvey J, Bai D, Tapia M (1998) Integrative population analysis for better solutions to large-scale mathematical programs. In: Yu G (ed) Industrial applications of combinatorial optimization. Kluwer Academic Publishers, Boston, pp 212–237

    Chapter  Google Scholar 

  • Glover F, Kochenberger G, Alidaee B, Amini M (2002) Solving quadratic knapsack problems by reformulation and tabu search. In: Pardalos PM, Megados A, Burkard R (eds) Combinatorial and global optimization. World Scientific Publishing Co., Singapore, pp 272–287

    Google Scholar 

  • Glover F, Kochenberger G, Wang Y (2018a) A new QUBO model for unsupervised machine learning. Res Prog (work in progress)

  • Glover F, Lewis M, Kochenberger G (2018b) Logical and inequality implications for reducing the size and difficulty of unconstrained binary optimization problems. Eur J Oper Res 265(2018):829–842

    Article  Google Scholar 

  • Hahn G, Djidjev H (2017) Reducing binary quadratic forms for more scalable quantum annealing. In: 2017 IEEE international conference on rebooting computing. https://doi.org/10.1109/ICRC.2017.8123654

  • Hamilton K, Schuman CD, Young SR, Imam N, Humble TS (2018) Neural networks and graph alogrithms with next-generation processors. In: 2018 IEEE international parallel and distributed processing symposium workshops (IPDPSW). https://doi.org/10.1109/IPDPSW.2018.00184

  • Hoos HH (2012) Programming by optimization. Commun ACM 55(2):70–80

    Article  Google Scholar 

  • Kalra A, Qureshi F, Tisi M (2018) Portfolio asset identification using graph algorithms on a quantum annealer. http://www.henryyuen.net/fall2018/projects/qfinance.pdf

  • Kerberos (2019) The network authentication protocol. https://web.mit.edu/kerberos/

  • Kochenberger G, Glover F (2006) A unified framework for modeling and solving combinatorial optimization problems: a tutorial. In: Hager W, Huang SJ, Pardalos P, Prokopyev O (eds) Multiscale optimization methods and applications. Springer, Berlin, pp 101–124

    Chapter  Google Scholar 

  • Kochenberger G, Glover F, Alidaee B, Lewis K (2005a) Using the unconstrained quadratic program to model and solve Max 2-Sat problems. Int J OR 1(1):89–100

    Google Scholar 

  • Kochenberger G, Glover F, Alidaee B, Rego C (2005b) An unconstrained quadratic binary programming approach to the vertex coloring problem. Ann OR 139(1–4):229–241

    Article  Google Scholar 

  • Kochenberger G, Hao J-K, Lu S, Wang H, Glover F (2013) Solving large scale max cut problems via tabu search. J Heuristics 19(4):565–571

    Article  Google Scholar 

  • Kochenberger G, Hao J-K, Glover F, Lewis M, Lu Z, Wang H, Wang Y (2014) The unconstrained binary quadratic programming problem: a survey. J Comb Optim 28(1):58–81

    Article  Google Scholar 

  • Kochenberger G, Badgett A, Chawla R, Glover F, Wang Y, Du Y (2019) Comparison of QAOA and alpha QUBO algorithms (work in progress)

  • Lanting AJ, Przybysz A, Smirnov Y, Spedalieri FM, Amin MH, Berkley AJ, Harris R, Altomare F, Boixo S, Bunyk P, Dickson N, Enderud C, Hilton JP, Hoskinson E, Johnson MW, Ladizinsky E, Ladizinsky N, Neufeld R, Oh T, Perminov I, Rich C, Thom MC, Tolkacheva E, Uchaikin S, Wilson AB, Rose G (2014) Entanglement in a quantum annealing processor. Phys Rev X 4:021041. arXiv:1401.3500v1

  • Lewis M (2008) A new modeling and solution approach for the set partitioning problem. Comput OR 35(3):807–813

    Article  Google Scholar 

  • Lucas A (2014) Ising formulations of many NP problems. Front Phys 5:2. arXiv:1302.5843

  • Mniszewski S, Negre C, Ushijima-Mwesigwa H (2016) Graph partitioning using the D-wave for electronic structure problems. LA-UR-16-27873, pp 1–21

  • Mniszewski SM, Negre CFA, Ushijima-Mwesigwa (2018) Graph clustering approaches using near term quantum computing. In: Argonne quantum computing workshop

  • Negre CFA, Ushijima-Mwesigwa H, Mniszewsk SM (2019) Detecting multiple communities using quantum annealing on the D-wave system. arXiv:1901.09756

  • Neukart F, Compostella G, Seidel C, Dollen D, Yarkoni S, Parney B (2017) Traffic flow optimization using a quantum annealer. arXiv:1708.01625

  • Ohzeki M, Miki A, Miyama MJ, Terabe M (2018) Control of automated guided vehicles without collision by quantum annealer and digital devices. arXiv:1812.01532

  • Oliveira NMD, Silva RMDA, Oliveira WRD (2018) QUBO formulation for the contact map overlap problem. Int J Quantum Inf 16(8):1840007

    Article  Google Scholar 

  • O’Malley D, Vesselinov VV, Alexandrov BS, Alexandrov LB (2018) Nonnegative/binary matrix factorization with a D-Wave quantum annealer. PLoS ONE 13(12):e0206653. https://doi.org/10.1371/journal.pone.0206653

    Article  Google Scholar 

  • Pakin S (2017) Navigating a maze using a quantum annealer. In: Proceedings of the second international workshop on post Moores era supercomputing, pp 30–36

  • Pakin S (2018) QMASM–quantum macro assembler. https://ccsweb.lanl.gov/~pakin/software/; https://github.com/lanl/qmasm

  • Pardalos P, Xue J (1999) The maximum clique problem. J Glob Optim 4(3):301–328

    Article  Google Scholar 

  • Pelofske E, Hahn G, Djidjev H (2019) Solving large Maximum Clique problems on a quantum annealer. arXiv:1901.07657

    Chapter  Google Scholar 

  • Preskill J (2019) Why i called it “quantum supremacy, quanta magazine. https://www.quantamagazine.org/john-preskill-explains-quantum-supremacy-20191002/

  • Pudenz KL, Lidar DA (2013) Quantum adiabatic machine learning. Quantum Inf Process 12(5):2027–2070

    Article  Google Scholar 

  • Qbsolv (2017) D-Wave initiates open quantum software environment. www.dwavesys.com/press-releases/d-wave-initiates-open-quantum-software-environment

  • Reedy C (2017) When will quantum computers be consumer products? Futurism. https://futurism.com/when-will-quantum-computers-be-consumer-products

  • Reinhardt S (2018) Detecting lateral movement with a compute-intense graph kernel. http://www.clsac.org/uploads/5/0/6/3/50633811/reinhardt-clsac-2018.pdf

  • Rodriguez-Heck E (2018) Linear ad quadratic reformulations of nonlinear optimization problems in binary variables. Ph.D. Dissertation, Liege University

  • Rosenberg I (1975) Reduction of bivalent maximization to the quadratic case. Cahiers du Centre d’Etudes de Recherche Operationnelle 17:71–74

    Google Scholar 

  • Sahner D (2018) A potential role for quantum annealing in the enhancement of patient outcomes?. https://www.dwavesys.com/sites/default/files/Sahner.2018.pdf

  • Samorani M, Wang Y, Wang Y, Lv Z, Glover F (2019) Clustering-Driven evolutionary algorithms: an application of path relinking to the quadratic unconstrained binary optimization problem. J Heuristics 25(4–5):629–642

    Article  Google Scholar 

  • Schneidman E, Berry MJ, Segev R, Bialek W (2006) Weak pairwise correlations imply strongly correlated network states in a neural population. Nature 440(7087):1007–1012

    Article  Google Scholar 

  • Shaydulin R, Ushijima-Mwesigwa H, Safro I, Mniszewski S, Alexeev Y (2018) Community detection across emerging quantum architectures. In: PMES workshop

  • The National Academies of Sciences, Engineering and Medicine Consensus Study Report (2019) Quantum computing: progress and prospects. https://www.nap.edu/catalog/25196/quantum-computing-progress-and-prospects

  • Ushijima-Mwesigwa H, Negre CFA, Mniszewsk SM (2017) Graph partitioning using quantum annealing on the D-wave system. arXiv:1705.03082

  • Verma A, Lewis M (2019) Optimal quadratic reformulations of fourth degree Pseudo-Boolean functions. Optim Lett. https://doi.org/10.1007/s11590-019-01460-7

    Article  Google Scholar 

  • Vyskocil T, Pakin S, Djidjev HN (2019) Embedding inequality constraints for quantum annealling optimization, quantum technology and optimization problems. QTOP 2019. Lecture notes in computer science, vol 11413. Springer

  • Wang Q, Abdullah T (2018) An introduction to quantum optimization approximation algorithm. https://www.cs.umd.edu/class/fall2018/cmsc657/projects/group_16.pdf

  • Wang Y, Lu Z, Glover F, Hao J-K (2012) Path relinking for unconstrained binary quadratic programming. Eur J Oper Res 223(3):595–604

    Article  Google Scholar 

  • Wang Y, Lu Z, Glover F, Hao J-K (2013) Backbone guided tabu search for solving the UBQP problem. J Heuristics 19(4):679–695

    Article  Google Scholar 

  • Wang H, Wang Y, Resende M, Kochenberger G (2016) A QUBO approach to solving QAP problems (unpublished manuscript)

  • Yu H, Huang Y, Wu B (2018) Exact equivalence between quantum adiabatic algorithm and quantum circuit algorithm. arXiv: 1706.07646v3 [quant-ph], https://doi.org/10.1088/0256-307X/35/11/110303

    Article  Google Scholar 

  • Zhou L, Wang S, Choi S, Pichler H, Lukin MD (2018) Quantum approximate optimization algorithm: performance, mechanism, and implementation on near-term devices. arXiv:1812.01041

Download references

Acknowledgements

This tutorial was influenced by our collaborations on many papers over recent years with several colleagues to whom we owe a major debt of gratitude. These co-workers, listed in alphabetical order, are: Bahram Alidaee, Dick Barr, Andy Badgett, Rajesh Chawla, Yu Du, Jin-Kao Hao, Mark Lewis, Karen Lewis, Zhipeng Lu, Abraham Punnen, Cesar Rego, Yang Wang, Haibo Wang and Qinghua Wu. Other collaborators whose work has inspired us are too numerous to mention. Their names may be found listed as our coauthors on our home pages.

Author information

Authors and Affiliations

  1. ECEE, College of Engineering and Applied Science, University of Colorado, Boulder, CO, 80302, USA

    Fred Glover

  2. Business School, University of Colorado at Denver, Denver, CO, 80217, USA

    Gary Kochenberger & Yu Du

Authors
  1. Fred Glover
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Gary Kochenberger
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Yu Du
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Fred Glover.

Ethics declarations

Conflict of interest

The authors declare that they have no conflict of interest.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Glover, F., Kochenberger, G. & Du, Y. Quantum Bridge Analytics I: a tutorial on formulating and using QUBO models. 4OR-Q J Oper Res 17, 335–371 (2019). https://doi.org/10.1007/s10288-019-00424-y

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10288-019-00424-y

Keywords

Mathematics Subject Classification

Search

Navigation