Top

Quantum Information Processing

Published in:

01-01-2015

A case study in programming a quantum annealer for hard operational planning problems

Authors: Eleanor G. Rieffel, Davide Venturelli, Bryan O’Gorman, Minh B. Do, Elicia M. Prystay, Vadim N. Smelyanskiy

Published in: Quantum Information Processing | Issue 1/2015

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

search-config

AI-assisted search

Off

Abstract

We report on a case study in programming an early quantum annealer to attack optimization problems related to operational planning. While a number of studies have looked at the performance of quantum annealers on problems native to their architecture, and others have examined performance of select problems stemming from an application area, ours is one of the first studies of a quantum annealer’s performance on parametrized families of hard problems from a practical domain. We explore two different general mappings of planning problems to quadratic unconstrained binary optimization (QUBO) problems, and apply them to two parametrized families of planning problems, navigation-type and scheduling-type. We also examine two more compact, but problem-type specific, mappings to QUBO, one for the navigation-type planning problems and one for the scheduling-type planning problems. We study embedding properties and parameter setting and examine their effect on the efficiency with which the quantum annealer solves these problems. From these results, we derive insights useful for the programming and design of future quantum annealers: problem choice, the mapping used, the properties of the embedding, and the annealing profile all matter, each significantly affecting the performance.

next article Experimental implementation of a nonthermalizing quantum thermometer

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

Rieffel, E.G., Polak, W.: A Gentle Introduction to Quantum Computing. MIT Press, Cambridge, MA (2011)

Nielsen, M., Chuang, I.L.: Quantum Computing and Quantum Information. Cambridge University Press, Cambridge (2001)

Farhi, E., Goldstone, J., Gutmann, S., Sipser, M.: Quantum computation by adiabatic evolution. arXiv:quant-ph/0001106 (2000)

Das, A., Chakrabarti, B.K.: Colloquium: quantum annealing and analog quantum computation. Rev. Mod. Phys. 80, 1061 (2008)ADSCrossRefMATHMathSciNet

Smelyanskiy, V.N., Rieffel, E.G., Knysh, S.I., Williams, C.P., Johnson, M.W., Thom, M.C., Macready, W.G., Pudenz, K.L.: A near-term quantum computing approach for hard computational problems in space exploration. arXiv:1204.2821 (2012)

Johnson, M., Amin, M., Gildert, S., Lanting, T., Hamze, F., Dickson, N., Harris, R., Berkley, A., Johansson, J., Bunyk, P., et al.: Quantum annealing with manufactured spins. Nature 473(7346), 194 (2011)ADSCrossRef

Boixo, S., Albash, T., Spedalieri, F.M., Chancellor, N., Lidar, D.A.: Experimental signature of programmable quantum annealing. Nat. Commun. (2013). doi:10.1038/ncomms3067

Smolin, J.A., Smith, G.: Classical signature of quantum annealing. arXiv:1305.4904 (2013)

Wang, L., Rønnow, T.F., Boixo, S., Isakov, S.V., Wang, Z., Wecker, D., Lidar, D.A., Martinis, J.M., Troyer, M.: Comment on “Classical signature of quantum annealing”. arXiv:1305.5837 (2013)

10.

Boixo, S., Rønnow, T.F., Isakov, S.V., Wang, Z., Wecker, D., Lidar, D.A., Martinis, J.M., Troyer, M.: Evidence for quantum annealing with more than one hundred qubits. Nat. Phys. 10(3), 218 (2014)CrossRef

11.

Shin, S.W., Smith, G., Smolin, J.A., Vazirani, U.: How “quantum” is the D-Wave machine? arXiv:1401.7087 (2014)

12.

Vinci, W., Albash, T., Mishra, A., Warburton, P.A., Lidar, D.A.: Distinguishing classical and quantum models for the D-Wave device. arXiv:1403.4228 (2014)

13.

Shin, S.W., Smith, G., Smolin, J.A., Vazirani, U.: Comment on “Distinguishing classical and quantum models for the D-Wave device”. arXiv:1404.6499 (2014)

14.

Rieffel, E.G., Venturelli, D., Hen, I., Do, M., Frank, J.: Parametrized families of hard planning problems from phase transitions. In: Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence (AAAI-14), pp. 2337–2343,(2014)

15.

Wang, Z., Boixo, S., Albash, T., Lidar, D.: Benchmarking the D-Wave adiabatic quantum optimizer via 2D-Ising spin glasses. APS Meeting Abstr. 1, 27005 (2013)

16.

Rønnow, T.F., Wang, Z., Job, J., Boixo, S., Isakov, S.V., Wecker,D., Martinis, J.M., Lidar, D.A., Troyer, M.: Defining and detectingquantum speedup. Science 345(6195), 420 (2014)

17.

Wang, Z., Job, J., Troyer, M., Lidar, D.A. et al.: Performance of quantum annealing on random Ising problems implemented using the D-wave two. Bull. Am. Phys. Soc. (2014)

18.

Venturelli, D., Mandra, S., Knysh, S., OGorman, B., Biswas, R., Smelyanskiy, V.: Quantum optimization of fully-connected spin glasses. arXiv:1406.7553 (2014)

19.

Kassal, I., Whitfield, J.D., Perdomo-Ortiz, A., Yung, M.H., Aspuru-Guzik, A.: Simulating chemistry using quantum computers. arXiv:1007.2648 (2010)

20.

Perdomo-Ortiz, A., Dickson, N., Drew-Brook, M., Rose, G., Aspuru-Guzik, A.: Finding low-energy conformations of lattice protein models by quantum annealing. Sci. Rep. (2012). doi:10.1038/srep00571

21.

Babbush, R., Perdomo-Ortiz, A., O’Gorman, B., Macready, W., Aspuru-Guzik, A.: Construction of energy functions for lattice heteropolymer models: a case study in constraint satisfaction programming and adiabatic quantum optimization. arXiv:1211.3422 (2012)

22.

Babbush, R., Love, P.J., Aspuru-Guzik, A.: Adiabatic quantum simulation of quantum chemistry. arXiv:1311.3967 (2013)

23.

Perdomo-Ortiz, A., Fluegemann, J., Narasimhan, S., Smelyanskiy, V., Biswas, R.: A quantum approach to diagnosis of multiple faults in electrical power systems. In: 5th IEEE International Conference on Space Mission Challenges for Information Technology. (To appear.) (2014)

24.

O’Gorman, B., Perdomo-Ortiz, A., Babbush, R., Aspuru-Guzik, A., Smelyanskiy, V.: Bayesian network structure learning using quantum annealing. Eur. Phys. J. Spec. Top. arXiv:1407.3897 (2014)

25.

Perdomo-Ortiz, A., Fluegemann, J., Narasimhan, S., Biswas, R., Smelyanskiy, V.: Programming and solving real-world applications on a quantum annealing device. arXiv:1406.7601 (2014)

26.

Fikes, R.E., Nilsson, N.J.: STRIPS: a new approach to the application of theorem proving to problem solving. Artif. Intell. 2(3), 189 (1972)

27.

Ghallab, M., Nau, D., Traverso, P.: Automated Planning: Theory and Practice. Elsevier, Amsterdam (2004)

28.

Long, D., Fox, M.: PDDL2. 1: an extension to PDDL for expressing temporal planning domains. J. Artif. Intell. Res. 20, 1 (2003)CrossRefMATH

29.

Helmert, M.: Complexity results for standard benchmark domains in planning. Artifi. Intell. J. 143(2), 219–262 (2003)

30.

Hoffmann, J.: Local search topology in planning benchmarks: an empirical analysis. J. Artif. Intell. Res. 24, 685 (2005)MATH

31.

Komlós, J., Szemerédi, E.: Limit distribution for the existence of Hamiltonian cycles in a random graph. Discrete Math. 43(1), 55 (1983)CrossRefMATHMathSciNet

32.

Cheeseman, P., Kanefsky, B., Taylor, W.M.: Where the really hard problems are. IJCAI 91, 331–337 (1991)

33.

Chien, S., Johnston, M., Frank, J., Giuliano, M., Kavelaars, A., Lenzen, C., Policella, N., Verfailie, G.: A generalized timeline representation, services, and interface for automating space mission operations. In: 12th International Conference on Space Operations (2012)

34.

Achlioptas, D., Friedgut, E.: A sharp threshold for k-colorability. Random Struct. Algorithm. 14(1), 63 (1999)CrossRefMATHMathSciNet

35.

Coja-Oghlan, A.: Upper-bounding the k-colorability threshold by counting covers. arXiv:1305.0177 (2013)

36.

Achlioptas, D., Moore, C.: Almost all graphs with average degree 4 are 3-colorable. J. Comput. Syst. Sci. 67(2), 441 (2003)CrossRefMATHMathSciNet

37.

Dubois, O., Mandler, J.: On the non-3-colourability of random graphs. arXiv:math/0209087 (2002)

38.

Culberson, J., Beacham, A., Papp, D.: Hiding our colors. In: Proceedings of the CP95 Workshop on Studying and Solving Really Hard Problems, pp. 31–42, (1995)

39.

Choi, V.: Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design. Quantum Inf. Process. 7(5), 193 (2008)CrossRefMATHMathSciNet

40.

Lucas, A.: Ising formulations of many NP problems. arXiv:1302.5843 (2013)

41.

Blum, A., Furst, M.: Fast planning through planning graph analysis. Artif. Intell. J. 90, 281 (1997)CrossRefMATH

42.

Kautz, H.: Working Notes on the Fourth International Planning Competition (IPC-2004) pp. 44–45 (2004)

43.

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

44.

Babbush, R., O’Gorman, B., Aspuru-Guzik, A.: Resource efficient gadgets for compiling adiabatic quantum optimization problems. Ann. Phys. 525(10–11), 877 (2013)CrossRefMATHMathSciNet

45.

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

46.

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

47.

Pudenz, K.L., Albash, T., Lidar, D.A.: Error-corrected quantum annealing with hundreds of qubits. Nat. Commun. (2014). doi:10.1038/ncomms4243

Title: A case study in programming a quantum annealer for hard operational planning problems
Authors: Eleanor G. Rieffel
Davide Venturelli
Bryan O’Gorman
Minh B. Do
Elicia M. Prystay
Vadim N. Smelyanskiy
Publication date: 01-01-2015
Publisher: Springer US
Published in: Quantum Information Processing / Issue 1/2015
Print ISSN: 1570-0755
Electronic ISSN: 1573-1332
DOI: https://doi.org/10.1007/s11128-014-0892-x

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 1/2015

Coherent feedback enabled distributed generation of entanglement between propagating Gaussian fields

Binary construction of pure additive quantum codes with distance five or six

Reconstruction of bipartite states via unambiguous state discrimination and mutually unbiased measurement

Experimental implementation of a nonthermalizing quantum thermometer

Quantum homomorphic signature

Entanglement witnesses generated by positive maps