Top

Quantum Information Processing

Published in:

01-04-2019

Efficiently embedding QUBO problems on adiabatic quantum computers

Authors: Prasanna Date, Robert Patton, Catherine Schuman, Thomas Potok

Published in: Quantum Information Processing | Issue 4/2019

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Adiabatic quantum computers like the D-Wave 2000Q can approximately solve the QUBO problem, which is an NP-hard problem, and have been shown to outperform classical computers on several instances. Solving the QUBO problem literally means solving virtually any NP-hard problem like the traveling salesman problem, airline scheduling problem, protein folding problem, genotype imputation problem, thereby enabling significant scientific progress, and potentially saving millions/billions of dollars in logistics, airlines, healthcare and many other industries. However, before QUBO problems are solved on quantum computers, they must be embedded (or compiled) onto the hardware of quantum computers, which in itself is a very hard problem. In this work, we propose an efficient embedding algorithm, that lets us embed QUBO problems fast, uses less qubits and gets the objective function value close to the global minimum value. We then compare the performance of our embedding algorithm to that of D-Wave’s embedding algorithm, which is the current state of the art, and show that our embedding algorithm convincingly outperforms D-Wave’s embedding algorithm. Our embedding approach works with perfect Chimera graphs, i.e., Chimera graphs with no missing qubits.

previous article Practical integer-to-binary mapping for quantum annealers

next article Parity oblivious d-level random access codes and class of noncontextuality inequalities

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Adachi, S.H., Davenport, D.M., Henderson, M.P.: Quantum-assisted training of neural networks. US Patent App. 14/702,203 (2015)

Albash, T., Lidar, D.A.: Adiabatic quantum computation. Rev. Modern Phys. 90(1), 015002 (2018)ADSMathSciNetCrossRef

Amin, M.H.: Methods of adiabatic quantum computation. US Patent 8,504,497 (2013)

Amin, M.H., Steininger, M.F.: Adiabatic quantum computation with superconducting qubits. US Patent 7,135,701 (2006)

Applegate, D.L., Bixby, R.E., Chvatal, V., Cook, W.J.: The Traveling Salesman Problem: A Computational Study. Princeton University Press, Princeton (2006)MATH

Barends, R., Shabani, A., Lamata, L., Kelly, J., Mezzacapo, A., Las Heras, U., Babbush, R., Fowler, A.G., Campbell, B., Chen, Y., et al.: Digitized adiabatic quantum computing with a superconducting circuit. Nature 534(7606), 222 (2016)ADSCrossRef

Baruah, S., Bertogna, M., Buttazzo, G.: Multiprocessor Scheduling for Real-time Systems. Springer, Berlin (2015)MATHCrossRef

Biamonte, J.D., Berkley, A.J., Amin, M.: Physical realizations of a universal adiabatic quantum computer. US Patent 8,234,103 (2012)

Bian, Z., Chudak, F., Israel, R.B., Lackey, B., Macready, W.G., Roy, A.: Mapping constrained optimization problems to quantum annealing with application to fault diagnosis. Front. ICT 3, 14 (2016)CrossRef

10.

Bian, Z., Chudak, F., Macready, W., Roy, A., Sebastiani, R., Varotti, S.: Solving sat and maxsat with a quantum annealer: foundations and a preliminary report. In: International Symposium on Frontiers of Combining Systems, pp. 153–171. Springer, Berlin (2017)

11.

Blum, A., Rivest, R.L.: Training a 3-node neural network is NP-complete. In: Advances in Neural Information Processing Systems, pp. 494–501 (1989)

12.

Boothby, T., King, A.D., Roy, A.: Fast clique minor generation in chimera qubit connectivity graphs. Quantum Inf. Process. 15(1), 495–508 (2016)ADSMathSciNetMATHCrossRef

13.

Britt, K.A., Humble, T.S.: High-performance computing with quantum processing units. ACM J. Emerg. Technol. Comput. Syst. (JETC) 13(3), 39 (2017)

14.

Cai, J., Macready, W.G., Roy, A.: A practical heuristic for finding graph minors. Preprint (2014). arXiv:1406.2741

15.

Carrillo, H., Lipman, D.: The multiple sequence alignment problem in biology. SIAM J. Appl. Math. 48(5), 1073–1082 (1988)MathSciNetMATHCrossRef

16.

Chickering, D.M., Geiger, D., Heckerman, D., et al.: Learning Bayesian networks is NP-hard. Technical Report, Citeseer (1994)

17.

Choi, V.: Minor-embedding in adiabatic quantum computation: I. The parameter setting problem. Quantum Inf. Process. 7(5), 193–209 (2008)MathSciNetMATHCrossRef

18.

Choi, V.: Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design. Quantum Inf. Process. 10(3), 343–353 (2011)MathSciNetMATHCrossRef

19.

Cook, S.A.: The complexity of theorem-proving procedures. In: Proceedings of the 3rd Annual ACM Symposium on Theory of Computing, pp. 151–158. ACM, New York (1971)

20.

Cristianini, N., Shawe-Taylor, J., et al.: An Introduction to Support Vector Machines and Other Kernel-based Learning Methods. Cambridge University Press, Cambridge (2000)MATHCrossRef

21.

Dasgupta, S.: The hardness of \(k\)-means clustering. Department of Computer Science and Engineering, University of California, San Diego (2008)

22.

Dill, K.A., MacCallum, J.L.: The protein-folding problem, 50 years on. Science 338(6110), 1042–1046 (2012)ADSCrossRef

23.

Dubois, O., Dequen, G.: A backbone-search heuristic for efficient solving of hard 3-sat formulae. IJCAI 1, 248–253 (2001)

24.

Esteve, D., Vion, D., Devoret, M., Urbina, C., Joyez, P., Pothier, H., Orfila, P.F., Aassime, A., Cottet, A.: Superconducting quantum-bit device based on josephson junctions. US Patent 6,838,694 (2005)

25.

Etschmaier, M.M., Mathaisel, D.F.: Airline scheduling: an overview. Transp. Sci. 19(2), 127–138 (1985)CrossRef

26.

Goodrich, T.D., Sullivan, B.D., Humble, T.S.: Optimizing adiabatic quantum program compilation using a graph-theoretic framework. Quantum Inf. Process. 17(5), 118 (2018)MathSciNetMATHCrossRef

27.

Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Proceedings of the 28th Annual ACM Symposium on Theory of Computing, pp. 212–219. ACM, New York (1996)

28.

Hamilton, K.E., Humble, T.S.: Identifying the minor set cover of dense connected bipartite graphs via random matching edge sets. Quantum Inf. Process. 16(4), 94 (2017)ADSMathSciNetMATHCrossRef

29.

Huang, W., Yu, J.X.: Investigating TSP heuristics for location-based services. Data Sci. Eng. 2(1), 71–93 (2017)ADSCrossRef

30.

Imamog, A., Awschalom, D.D., Burkard, G., DiVincenzo, D.P., Loss, D., Sherwin, M., Small, A., et al.: Quantum information processing using quantum dot spins and cavity QED. Phys. Rev. Lett. 83(20), 4204 (1999)ADSCrossRef

31.

Kane, B.E.: A silicon-based nuclear spin quantum computer. Nature 393(6681), 133 (1998)ADSCrossRef

32.

Keating, T., Goyal, K., Jau, Y.Y., Biedermann, G.W., Landahl, A.J., Deutsch, I.H.: Adiabatic quantum computation with Rydberg-dressed atoms. Phys. Rev. A 87(5), 052314 (2013)ADSCrossRef

33.

King, A.D., Israel, R.B., Bunyk, P.I., Boothby, T.J., Reinhardt, S.P., Roy, A.P., King, J.A., Lanting, T.M., Evert, A.J.: Systems and methods for embedding problems into an analog processor. US Patent App. 15/487,295 (2017)

34.

Kleinberg, J., Tardos, E.: Algorithm Design. Pearson Education India, Noida (2006)

35.

Klymko, C., Sullivan, B.D., Humble, T.S.: Adiabatic quantum programming: minor embedding with hard faults. Quantum Inf. Process. 13(3), 709–729 (2014)ADSMathSciNetMATHCrossRef

36.

Landahl, A.: Adiabatic quantum computing. In: APS Four Corners Section Meeting Abstracts (2012)

37.

Lewis, M., Glover, F.: Quadratic unconstrained binary optimization problem preprocessing: theory and empirical analysis. Networks 70(2), 79–97 (2017)MathSciNetCrossRef

38.

Li, Y., Willer, C., Sanna, S., Abecasis, G.: Genotype imputation. Ann. Rev. Genom. Hum. Genet. 10, 387–406 (2009)CrossRef

39.

Macready, W., Roy, A.P.: Systems and methods that formulate problems for solving by a quantum processor using hardware graph decomposition. US Patent 9,875,215 (2018)

40.

Nielsen, M.A., Chuang, I.: Quantum Computation and Quantum Information. AAPT (2002)

41.

Papadimitriou, C.H.: Computational Complexity. Wiley, London (2003)MATH

42.

Pittman, T., Jacobs, B., Franson, J.: Probabilistic quantum logic operations using polarizing beam splitters. Phys. Rev. A 64(6), 062311 (2001)ADSCrossRef

43.

Pla, J.J., Tan, K.Y., Dehollain, J.P., Lim, W.H., Morton, J.J., Jamieson, D.N., Dzurak, A.S., Morello, A.: A single-atom electron spin qubit in silicon. Nature 489(7417), 541 (2012)ADSCrossRef

44.

Potok, T.E., Schuman, C.D., Young, S.R., Patton, R.M., Spedalieri, F., Liu, J., Yao, K.T., Rose, G., Chakma, G.: A study of complex deep learning networks on high performance, neuromorphic, and quantum computers. In: Workshop on Machine Learning in HPC Environments (MLHPC), pp. 47–55. IEEE, New York (2016)

45.

Rieffel, E.G., Venturelli, D., O’Gorman, B., Do, M.B., Prystay, E.M., Smelyanskiy, V.N.: A case study in programming a quantum annealer for hard operational planning problems. Quantum Inf. Process. 14(1), 1–36 (2015)ADSMATHCrossRef

46.

Roy, A.P.: Systems and methods that formulate embeddings of problems for solving by a quantum processor. US Patent 9,501,747 (2016)

47.

Shmygelska, A., Hoos, H.H.: An ant colony optimisation algorithm for the 2D and 3D hydrophobic polar protein folding problem. BMC Bioinformat. 6(1), 30 (2005)CrossRef

48.

Shor, P.W.: Algorithms for quantum computation: discrete logarithms and factoring. In: 1994 Proceedings., 35th Annual Symposium on Foundations of Computer Science, pp. 124–134. IEEE, New York (1994)

49.

Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Rev. 41(2), 303–332 (1999)ADSMathSciNetMATHCrossRef

50.

Thom, M.C., Roy, A.P., Chudak, F.A., Bian, Z., Macready, W.G., Israel, R.B., Boothby, T.J., Yarkoni, S., Xue, Y., Korenkevych, D., et al.: Systems and methods for analog processing of problem graphs having arbitrary size and/or connectivity. US Patent App. 15/448,361 (2017)

51.

Turing, A.M.: On computable numbers, with an application to the entscheidungsproblem. a correction. Proc. Lond. Math. Soc. 2(1), 544–546 (1938)MathSciNetMATHCrossRef

52.

Venturelli, D., Mandra, S., Knysh, S., O’Gorman, B., Biswas, R., Smelyanskiy, V.: Quantum optimization of fully connected spin glasses. Phys. Rev. X 5(3), 031040 (2015)

53.

Zagoskin, A.M.: Qubit using a josephson junction between s-wave and d-wave superconductors. US Patent 6,459,097 (2002)

54.

Zagoskin, A.M.: Quantum computing method using magnetic flux states at a Josephson junction. US Patent 6,563,311 (2003)

55.

Zaribafiyan, A., Marchand, D., REZAEI, S.S.C.: Method and system for generating an embedding pattern used for solving a quadratic binary optimization problem. US Patent App. 15/344,054 (2017)

Title: Efficiently embedding QUBO problems on adiabatic quantum computers
Authors: Prasanna Date
Robert Patton
Catherine Schuman
Thomas Potok
Publication date: 01-04-2019
Publisher: Springer US
Published in: Quantum Information Processing / Issue 4/2019
Print ISSN: 1570-0755
Electronic ISSN: 1573-1332
DOI: https://doi.org/10.1007/s11128-019-2236-3

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 4/2019

Parity oblivious d-level random access codes and class of noncontextuality inequalities

The critical detection efficiency for closing the detection loophole of some modified Bell inequalities

Controlled teleportation of an arbitrary two-qubit entanglement in noises environment

Demonstration of entanglement purification and swapping protocol to design quantum repeater in IBM quantum computer

Practical covert quantum key distribution with decoy-state method

Three-qubit separable states of length ten with unique decompositions