Top

Published in:

2018 | OriginalPaper | Chapter

A Survey of Programming Tools for D-Wave Quantum-Annealing Processors

Authors : Scott Pakin, Steven P. Reinhardt

Published in: High Performance Computing

Publisher: Springer International Publishing

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

search-config

AI-assisted search

Off

Abstract

The rapid growth in the realized performance of D-Wave Systems’ annealing-based quantum processing units (QPUs) has sparked a surge in tools development to deliver the anticipated performance to application developers. In this survey we describe the tools that are available, their goals (e.g., performance or ease of use), the programming abstractions they expose, and their use for application development. The existing tools confirm the need for interfaces at a variety of points on the continuum between complexity and simplicity in using the QPU. Most of the current tools abstract the hardware’s native topology but generally not using existing interfaces that are familiar to typical programmers. To date, only a small number of applications have been implemented for QPUs. Our survey finds that tools provide potentially great leverage to enable more applications as long as the tools expose the appropriate abstractions and deliver the anticipated performance.

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

previous chapter Classifying Jobs and Predicting Applications in HPC Systems

next chapter Compiler-Assisted Source-to-Source Skeletonization of Application Models for System Simulation

Note the possibility of confusion between this definition of unconstrained BQP and the definition of BQP as bounded-error quantum polynomial time [4], a computational complexity class. To avoid this confusion, we refer to the problem as a QUBO throughout this paper.

Chain strength is the relative strength of couplings between qubits corresponding to the same problem variable to couplings between qubits corresponding to different problem variables.

A chain is considered broken if its qubits, which correspond to the same problem variable, are assigned different values.

Section 2 mentions the difference between the Ising-model Hamiltonian and the QUBO. For consistency with the rest of this paper we use QUBO terminology here.

Lockheed Martin Corporation: Quantum, August 2011. http://www.lockheedmartin.com/us/what-we-do/emerging/quantum.html

Denchev, V.S., Boixo, S., Isakov, S.V., Ding, N., Babbush, R., Smelyanskiy, V., Martinis, J., Neven, H.: What is the computational value of finite-range tunneling? Phys. Rev. X 6(3), 031015 (2016)

King, A.D., Hoskinson, E., Lanting, T., Andriyash, E., Amin, M.H.: Degeneracy, degree, and heavy tails in quantum annealing. Phys. Rev. A 93(5), 052320 (2016)CrossRef

Wikipedia: BQP, August 2017. https://en.wikipedia.org/wiki/BQP

Bunyk, P.I., Hoskinson, E.M., Johnson, M.W., Tolkacheva, E., Altomare, F., Berkley, A.J., Harris, R., Hilton, J.P., Lanting, T., Przybysz, A.J., Whittaker, J.: Architectural considerations in the design of a superconducting quantum annealing processor. IEEE Trans. Appl. Supercond. 24(4), 1–10 (2014)CrossRef

Anthony, A.: Has the age of quantum computing arrived?, December 2016. https://www.theguardian.com/technology/2016/may/22/age-of-quantum-computing-d-wave

NASA Quantum Artificial Intelligence Laboratory (QuAIL), December 2016. https://ti.arc.nasa.gov/tech/dash/physics/quail/

Grant, E.: D-Wave adiabatic quantum computer, October 2016. http://web.eecs.utk.edu/courses/fall2016/cosc594/presentations/D-Wave.pdf

Boothby, K.: D-Wave improved heuristic embedder, October 2017. https://github.com/dwavesystems/minorminer

10.

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

11.

Boothby, K.: D-Wave clique embedder, October 2017. https://github.com/dwavesystems/chimera-embedding

12.

Goodrich, T.D., Sullivan, B.D., Humble, T.S.: Optimizing adiabatic quantum program compilation using a graph-theoretic framework. arXiv preprint arXiv:1704.01996 (2017)

13.

Goodrich, T.D.: AQC virtual embedding, October 2017. https://github.com/TheoryInPractice/aqc-virtual-embedding

14.

D-Wave Systems Inc.: Burnaby, British Columbia, Canada: Developer Guide for C (2017)

15.

Andriyash, E., Bian, Z., Chudak, F., Drew-Brook, M., King, A.D., Macready, W.G., Roy, A.: Boosting integer factoring performance via quantum annealing offsets, December 2016. https://www.dwavesys.com/sites/default/files/14-1002A_B_tr_Boosting_integer_factorization_via_quantum_annealing_offsets.pdf

16.

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)CrossRef

17.

Stollenwerk, T., Basermann, A.: Experiences with scheduling problems on adiabatic quantum computers. In: Proceedings of the 1st International Workshop on Post-Moore Era Supercomputing (PMES), Future Technologies Group Technical report FTGTR-2016-11, pp. 45–46 (2016)

18.

Trummer, I., Koch, C.: Multiple query optimization on the D-Wave 2X adiabatic quantum computer. Proc. VLDB Endow. 9(9), 648–659 (2016)CrossRef

19.

Adachi, S.H., Henderson, M.P.: Application of quantum annealing to training of deep neural networks. arXiv preprint arXiv:1510.06356 (2015)

20.

Perdomo-Ortiz, A., Fluegemann, J., Narasimhan, S., Biswas, R., Smelyanskiy, V.N.: A quantum annealing approach for fault detection and diagnosis of graph-based systems. Eur. Phys. J. Spec. Topics 224(1), 131–148 (2015)CrossRef

21.

Douglass, A., King, A.D., Raymond, J.: Constructing SAT filters with a quantum annealer. In: Heule, M., Weaver, S. (eds.) SAT 2015. LNCS, vol. 9340, pp. 104–120. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-24318-4_9CrossRefMATH

22.

Douglass, A.: dwave-cloud-client, March 2017. https://github.com/dwavesystems/dwave-cloud-client

23.

Booth, M., Dahl, E., Furtney, M., Reinhardt, S.P.: Abstractions considered helpful: a tools architecture for quantum annealers. In: 2016 IEEE High Performance Extreme Computing Conference (HPEC), pp. 1–2. IEEE (2016)

24.

Ramey, C.: Bash, the Bourne-again shell. In: Proceedings of The Romanian Open Systems Conference & Exhibition (ROSE 1994), The Romanian UNIX User’s Group (GURU), 3–5 November 1994

25.

QC Ware: QC Ware Platform, October 2017. https://platform.qcware.com

26.

Rosenberg, G., Haghnegahdar, P., Goddard, P., Carr, P., Wu, K., de Prado, M.L.: Solving the optimal trading trajectory problem using a quantum annealer. IEEE J. Sel. Topics Sig. Process. 10(6), 1053–1060 (2016)CrossRef

27.

Accenture: Biogen, 1QBit and Accenture: Pioneering Quantum Computing in R&D, August 2016. https://www.accenture.com/us-en/success-biogen-quantum-computing-advance-drug-discovery

28.

1QBit: 1QBit Quantum Development Kit, October 2017. https://qdk.1qbit.com

29.

Hodson, M., Fletcher, D., Padilha, D., Cook, T.: Rapid prototyping with symbolic computation: fast development of quantum annealing solutions. In: 2016 IEEE High Performance Extreme Computing Conference (HPEC), pp. 1–5. IEEE (2016)

30.

McCaskey, A.: XACC–eXtreme-scale ACCelerator programming framework, October 2016. https://github.com/ORNL-QCI/xacc

31.

Munshi, A.: The OpenCL specification. In: 2009 IEEE Hot Chips 21 Symposium (HCS), pp. 1–314. IEEE (2009)

32.

Smith, R.S., Curtis, M.J., Zeng, W.J.: A practical quantum instruction set architecture. arXiv preprint arXiv:1608.03355 (2016)

33.

JavadiAbhari, A., Patil, S., Kudrow, D., Heckey, J., Lvov, A., Chong, F.T., Martonosi, M.: ScaffCC: scalable compilation and analysis of quantum programs. Parallel Comput. 45, 2–17 (2015)CrossRef

34.

Elsokkary, N., Khan, F.S., La Torre, D., Humble, T.S., Gottlieb, J.: Financial portfolio management using adiabatic quantum optimization: the case of Abu Dhabi securities exchange. In: 2017 IEEE High Performance Extreme Computing Conference (HPEC), pp. 1–4. IEEE (2017)

35.

McCaskey, A.: Eclipse XACC: Hardware Agnostic Quantum Programming, May 2018. https://github.com/eclipse/xacc

36.

Coffrin, C., Nagarajan, H., Bent, R.: Ising processing units: potential and challenges for discrete optimization. arXiv preprint arXiv:1707.00355 (2017)

37.

Coffrin, C.: BQPSOLVERS, BQPJSON, and DWIG, May 2018. https://github.com/lanl-ansi/bqpsolvers, https://github.com/lanl-ansi/bqpjson, https://github.com/lanl-ansi/dwig

38.

Pakin, S.: A quantum macro assembler. In: Proceedings of the 20th Annual IEEE High Performance Extreme Computing Conference (HPEC 2016), Waltham, Massachusetts, USA, IEEE, 13–15 September 2016

39.

Pakin, S.: Quantum macro assembler (QMASM), October 2017. https://github.com/lanl/qmasm

40.

Booth, M., Reinhardt, S.P., Roy, A.: Partitioning optimization problems for hybrid classical/quantum execution, August 2017. https://github.com/dwavesystems/qbsolv/blob/master/qbsolv_techReport.pdf

41.

Glover, F.: Tabu search-part I. ORSA J. Comput. 1(3), 190–206 (1989)CrossRef

42.

Mniszewski, S.M., Negre, C.F., Ushijima-Mwesigwa, H.M.: Graph partitioning using the D-Wave for electronic structure problems. Technical report LA-UR-16-27873, Los Alamos National Laboratory (2016)

43.

O’Malley, D., Vesselinov, V.V., Alexandrov, B.S., Alexandrov, L.B.: Nonnegative/binary matrix factorization with a D-Wave quantum annealer. arXiv preprint arXiv:1704.01605 (2017)

44.

Ushijima-Mwesigwa, H., Negre, C.F.A., Mniszewski, S.M.: Graph partitioning using quantum annealing on the D-Wave system. arXiv preprint arXiv:1705.03082 (2017)

45.

Neukart, F., Compostella, G., Seidel, C., Von Dollen, D., Yarkoni, S., Parney, B.: Optimizing traffic flow using quantum annealing and classical machine learning. arXiv preprint arXiv:1708.01625 (2017)

46.

Ossorio-Castillo, J.: Solving energy-related scheduling problems with column generation and an adiabatic quantum computer, Tokyo, Japan, 26–29 July 2017

47.

Dulny, J.S.: Quantum annealing enabled cluster analysis, Tokyo, Japan, 26–29 July 2017

48.

Booth, M., Douglass, A., et al.: QUBO solver (qbsolv), October 2017. https://github.com/dwavesystems/qbsolv

49.

O’Malley, D., Vesselinov, V.V.: ToQ.jl: a high-level programming language for D-Wave machines based on Julia. In: 2016 IEEE High Performance Extreme Computing Conference (HPEC), pp. 1–7. IEEE (2016)

50.

Bezanson, J., Edelman, A., Karpinski, S., Shah, V.B.: Julia: a fresh approach to numerical computing. SIAM Rev. 59(1), 65–98 (2017)MathSciNetCrossRef

51.

Lubin, M., Dunning, I.: Computing in operations research using Julia. INFORMS J. Comput. 27(2), 238–248 (2015)MathSciNetCrossRef

52.

O’Malley, D.: ThreeQ, October 2017. https://github.com/lanl/ThreeQ.jl

53.

Condello, A.: D-Wave NetworkX, October 2017. https://github.com/dwavesystems/dwave_networkx

54.

Hagberg, A.A., Schult, D.A., Swart, P.J.: Exploring network structure, dynamics, and function using NetworkX. In: Proceedings of the 7th Python in Science Conference (SciPy 2008), Pasadena, California, USA, pp. 11–15, August 2008

55.

Ambrosiano, J.J., Roberts, R.M., Sims, B.H.: Using the D-Wave 2X quantum computer to explore the formation of global terrorist networks. Technical report LA-UR-17-23946, Los Alamos National Laboratory (2017)

56.

Condello, A.: Structural imbalance demo, December 2017. https://github.com/dwavesystems/structural-imbalance-demo

57.

Pakin, S.: edif2qmasm–run hardware descriptions on a quantum annealer, August 2017. https://github.com/lanl/edif2qmasm

58.

Thomas, D., Moorby, P.: The Verilog\(\textregistered \) Hardware Description Language. Springer Science & Business Media, New York (2008). https://doi.org/10.1007/978-0-387-85344-4CrossRefMATH

59.

Ecker, W.: Using VHDL for HW/SW co-specification. In: Proceedings EURO-DAC 1993 European Design Automation Conference, 1993, with EURO-VHDL 1993, pp. 500–505. IEEE (1993)

60.

Crawford, J.D.: EDIF: a mechanism for the exchange of design information. IEEE Des. Test Comput. 2(1), 63–69 (1985)CrossRef

61.

Wolf, C., Glaser, J., Kepler, J.: Yosys–a free Verilog synthesis suite. In: Proceedings of the 21st Austrian Workshop on Microelectronics (Austrochip) (2013)

62.

Fourer, R., Gay, D.M., Kernighan, B.W.: A modeling language for mathematical programming. Manag. Sci. 36(5), 519–554 (1990)CrossRef

63.

Bussieck, M.R., Meeraus, A.: General Algebraic Modeling System (GAMS). Appl. Optim. 88, 137–158 (2004)CrossRef

64.

Nethercote, N., Stuckey, P.J., Becket, R., Brand, S., Duck, G.J., Tack, G.: MiniZinc: towards a standard CP modelling language. In: Bessière, C. (ed.) CP 2007. LNCS, vol. 4741, pp. 529–543. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-74970-7_38CrossRef

65.

Hart, W.E., Watson, J.P., Woodruff, D.L.: Pyomo: modeling and solving mathematical programs in Python. Math. Program. Comput. 3(3), 219–260 (2011)MathSciNetCrossRef

66.

Pakin, S.: Navigating a maze using a quantum annealer. In: Proceedings of the 2nd International Workshop on Post Moore’s Era Supercomputing, Denver, Colorado, USA, pp. 30–36. ACM, 13 November 2017

67.

Gould, S.J.: Wonderful Life: The Burgess Shale and the Nature of History. W. W. Norton & Company, New York (1990)

Title: A Survey of Programming Tools for D-Wave Quantum-Annealing Processors
Authors: Scott Pakin
Steven P. Reinhardt
Publisher: Springer International Publishing
Book: High Performance Computing
Print ISBN: 978-3-319-92039-9

Electronic ISBN: 978-3-319-92040-5

Copyright Year: 2018
DOI: https://doi.org/10.1007/978-3-319-92040-5_6

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"