IDC recently published a Technology Spotlight on quantum computing. Download the report here.
Read the new D-Wave 2X Technology Overview.
This white paper uses a simple map coloring example to explain one method of programming a D-Wave system.
A brief introduction to D-Wave and quantum computing.
Jason Tyler Rolfe
“Probabilistic models with discrete latent variables naturally capture datasets composed of discrete classes. However, they are difficult to train efficiently, since back propagation through discrete variables is generally not possible. We introduce a novel class of probabilistic models, comprising an undirected discrete component and a directed hierarchical continuous component, that can be trained efficiently using the variational autoencoder framework. The discrete component captures the distribution over the disconnected smooth manifolds induced by the continuous component. As a result, this class of models efficiently learns both the class of objects in an image, and their specific realization in pixels, from unsupervised data; and outperforms state-of-the-art methods on the permutation-invariant MNIST, OMNIGLOT, and Caltech-101 Silhouettes datasets.”
(7 Sep 2016) http://arxiv.org/abs/1609.02200
Jack Raymond, Sheir Yarkoni, Evgeny Andriyash
"Sampling from a Boltzmann distribution is NP-hard and so requires heuristic approaches. Quantum annealing is one promising candidate. The failure of annealing dynamics to equilibrate on practical time scales is a well understood limitation, but does not always prevent a heuristically useful distribution from being generated. In this paper we evaluate several methods for determining a useful operational temperature range for annealers.
(2 Jun 2016) Download PDF.
Zhengbing Bian, Fabian Chudak, Robert Israel, Brad Lackey, William G. Macready, Aidan Roy
Current quantum annealing (QA) hardware suffers from practical limitations such as finite temperature, sparse connectivity, small qubit numbers, and control error. We propose new algorithms for mapping boolean constraint satisfaction problems (CSPs) onto QA hardware mitigating these limitations. In particular we develop a new embedding algorithm for mapping a CSP onto a hardware Ising model with a fixed sparse set of interactions, and propose two new decomposition algorithms for solving problems too large to map directly into hardware.
(10 Mar 2016) http://arxiv.org/abs/1603.03111
Mohammad H. Amin, Evgeny Andriyash, Jason Rolfe, Bohdan Kulchytskyy, Roger Melko
Inspired by the success of Boltzmann Machines based on classical Boltzmann distribution, we propose a new machine learning approach based on quantum Boltzmann distribution of a transverse-field Ising Hamiltonian. Due to the non-commutative nature of quantum mechanics, the training process of the Quantum Boltzmann Machine (QBM) can become nontrivial. We circumvent the problem by introducing bounds on the quantum probabilities. This allows us to train the QBM efficiently by sampling. We show examples of QBM training with and without the bound, using exact diagonalization, and compare the results with classical Boltzmann training. We also discuss the possibility of using quantum annealing processors like D-Wave for QBM training and application.
(8 Jan 2016) http://arxiv.org/abs/1601.02036
Andrew D. King, Emile Hoskinson, Trevor Lanting, Evgeny Andriyash, Mohammad H. Amin
"Both simulated quantum annealing and physical quantum annealing have shown the emergence of "heavy tails" in their performance as optimizers: The total time needed to solve a set of random input instances is dominated by a small number of very hard instances…On similar inputs designed to suppress local degeneracy, performance of a quantum annealing processor on hard instances improves by orders of magnitude at the 512-qubit scale, while classical performance remains relatively unchanged."
(23 Dec 2015) Link to PDF.
Tomas Boothby, Andrew D. King, Aidan Roy
Adam Douglass, Andrew D. King, Jack Raymond
"Presented here is a case study of SAT filter construction with a focus on constraint satisfaction problems based on MAX-CUT clauses (Not-all-equal 3-SAT, 2-in-4-SAT, etc.) and frustrated cycles in the Ising model... Solutions are sampled using a D-Wave quantum annealer, and results are measured against classical approaches."
A.D.King, T.Lanting, and R.Harris
(3 Sep 2015) http://arxiv.org/pdf/1502.02098.pdf
James King, Sheir Yarkoni, Mayssam M. Nevisi, Jeremy P. Hilton, and Catherine C. McGeoch
In this paper we introduce the Time to Target (TTT) metric and compare the performance of the D-Wave 2X on a host of native hardware problems against highly optimized and tuned solvers.
(20 Aug, 2015) Link to PDF
Mohammad H. Amin
(13 Mar 2015) http://arxiv.org/pdf/1503.04216.pdf
Sergio Boixo et al.
(19 Feb 2015) http://arxiv.org/pdf/1411.4036.pdf
Zhengbing Bian, Fabian Chudak, Robert Israel, Brad Lackey, William G. Macready and Aidan Roy
Frontiers in Physics, (18 Sep 2014) http://journal.frontiersin.org/Journal/10.3389/fphy.2014.00056/abstract
Jun Cai, Bill Macready, Aidan Roy
(12 Jun 2014) http://arxiv.org/pdf/1406.2741.pdf
T. Lanting et. al
In this paper we present experimental evidence that, during a critical portion of QA, qubits in the D-Wave processor become entangled and entanglement persists even as these systems reach equilibrium with a thermal environment. Our results provide an encouraging sign that quantum annealing is a viable technology for large-scale quantum computing.
Physical Review X (29 May 2014) https://journals.aps.org/prx/abstract/10.1103/PhysRevX.4.021041
P. Bunyk et al.
Pre-print (21 Jan 2014) http://arxiv.org/pdf/1401.5504v1
T. Lanting et al.
(23 Dec 2013) http://arxiv.org/pdf/1306.1512.pdf
N G Dickson et al.
"Efforts to develop useful quantum computers have been blocked primarily by environmental noiseHere we examine the environment’s effect on quantum annealing using 16 qubits of a superconducting quantum processor. For a problem instance with an isolated small-gap anticrossing between the lowest two energy levels, we experimentally demonstrate that, even with annealing times eight orders of magnitude longer than the predicted single-qubit decoherence time, the probabilities of performing a successful computation are similar to those expected for a fully coherent system. Moreover, for the problem studied, we show that quantum annealing can take advantage of a thermal environment to achieve a speedup factor of up to 1,000 over a closed system."
Nature Communications, 1903 (May 21 2013) http://www.nature.com/ncomms/journal/v4/n5/full/ncomms2920.html
M.H. Amin et al.
Quant. Inf. Proc. 12, 1819-1829 (April 2013) doi:10.1007/s11128-012-0480-x/QuantInfProc12/
A. J. Berkley et al.
Phys. Rev. B 87, 020502(R) (2013) doi:10.1103/PhysRevB.87.020502
N. G. Dickson et al.
Phys. Rev. A 85, 032303 (2012) doi:10.1103/PhysRevA.85.032303arXiv:1108.33031
M. H. Amin et al.
Phys. Rev. A 86, 052314 (2012) doi:10.1103/PhysRevA.86.052314
T. Lanting et al.
Physical Review B PhysRevB.83.180502 arXiv:1103.1931
M. W. Johnson et al.
Many interesting but practically intractable problems can be reduced to that of finding the ground state of a system of interacting spins; however, finding such a ground state remains computationally difficult..Here we use quantum annealing to find the ground state of an artificial Ising spin system comprising an array of eight superconducting flux quantum bits with programmable spin–spin couplings. We observe a clear signature of quantum annealing, distinguishable from classical thermal annealing through the temperature dependence of the time at which the system dynamics freezes.
Nature 473, 194-198 (12 May 2011) http://www.nature.com/nature/journal/v473/n7346/full/nature10012.html
N. Dickson et al.
Journal of Computational Physics arXiv:1004.0024
Z. Bian et al.
Link to PDF
K. Karimi et al.
Quantum Information Processing arXiv:1006.4147
N. G. Dickson et al.
Phys. Rev. Lett. 106, Issue 5, 050502 arXiv:1010.0669
M. W. Johnson et al.
Supercond. Sci. Technol. 23, 065004 arXiv:0907.3757
R. Harris et al.
Physical Review B 81, 134510 (2010) arXiv:0909.4321
K. Karimi et al.
International Journal of High Performance Computing Applications, doi: 10.1177/1094342010372928arXiv:1004.0023
F. Hamze et al
International Journal of Modern Physics C, Volume 21, issue 5 (2010) arXiv:1004.2840
R. Harris et al.
Phys. Rev. B 82, 024511 (2010) arXiv:1004.1628
T. Lanting et al.
Phys. Rev. B 82, 060512(R) (2010) arXiv:1006.0028
A. J. Berkley et al.
Supercond. Sci. Technol. 23, 105014 (2010) arXiv:0905.0891
M. H. S. Amin et al.
Phys. Rev. B 80, 214302 (2009) arXiv:0907.4797
Phys. Rev. A 79, 022107 (2009) arXiv:0708.0384
Phys. Rev. B 80, 052506 (2009) arXiv:0904.3784
Phys. Rev. B 80, 012507 (2009) arXiv:0807.0797
Phys. Rev. Lett. 102, 220401 (2009) arXiv:0810.4335
A. T. S. Wan et al.
Int. J. Quant. Inf. 7, 725 (2009) arXiv:cond-mat/0703085
M. H. S. Amin et al.
Phys. Rev. A 80, 062326 (2009) arXiv:0904.1387
Phys. Rev. A 80, 022303 (2009) arXiv:0803.1196
Phys. Rev. Lett. 100, 197001 (2008) arXiv:0712.0845
Physical Review A 78, 012320 (2008) arXiv:0801.3625
Phys. Rev. Lett. 100, 130503 (2008) arXiv:0709.0528
Phys. Rev. Lett. 100, 060503 (2008) arXiv:cond-mat/0609332
Phys. Rev. Lett. 101, 117003 (2008) arXiv:0712.0838
Phys. Rev. A 78, 012352 (2008) aXiv:0704.1287
Phys. Rev. Lett. 98, 177001 (2007) arXiv:cond-mat/0608253
Quant. Info. Proc. 6, 187 (2007) arXiv:quant-ph/0602143
Low Temp. Phys. 32, 198 (2006) arXiv:cond-mat/0407080
Phys. Rev. Lett. 96, 047006 (2006) arXiv:cond-mat/0509557
IEEE Trans. App. Supercond. 17, 113 (2006) arXiv:cond-mat/0702580
Science 309 p. 1704, (2005) arXiv:quant-ph/0604193
Phys. Rev. B, 71, 064503 (2005) arXiv:cond-mat/0310425
Phys. Rev. B 71, 140505 (2005) arXiv:cond-mat/0412286
Phys. Rev. B 71, 064516 (2005) arXiv:cond-mat/0310224
Phys. Rev. B 71, 024504 (2005) arXiv:cond-mat/0311220
New J. Phys. 7 230 (2005) arXiv:cond-mat/0501148
Phys. Rev. B 72, (2005) 020503(R) arXiv:cond-mat/0501085
Phys. Rev. Lett. 93, 037003 (2004) arXiv:cond-mat/0312332
Phys. Rev. B 69, 060501 (2004) arXiv:cond-mat/0303657
Phys. Rev. Lett. 92, 017001 (2004) arXiv:cond-mat/0304255
Euro. Phys. Lett. 65, 844, (2004) arXiv:cond-mat/0307506
Low Temp. Phys. 30, 661 (2004) arXiv:cond-mat/0404401
IEEE International Solid State Circuit Conference (ISSCC), Tech. Dig., p296(2004)
Proceedings of the European Conference on Applied Superconductivity (EUCAS 2003)
Phys. Rev. B 68, 054505 (2003) arXiv:cond-mat/0207724
Phys. Rev. B 67, 100508 (2003) arXiv:cond-mat/0211638
Phys. Rev. Lett. 90, 117002 (2003) arXiv:cond-mat/0303144
"Towards the Controllable Quantum States" edited by H. Takayanagi and J. Nitta, World Scientific Publishing Co. (2003), arXiv:cond-mat/0207617
Phys. Rev. Lett. 91, 097906 (2003) arXiv:cond-mat/0303433
Phys. Rev. B 68, 134514 (2003) arXiv:cond-mat/0306004
Phys. Rev. Lett. 90, 127901 (2003) arXiv:cond-mat/0207112
Physica C 368, 310 (2002) arXiv:cond-mat/0109382
IEEE Tran. Appl. Supercond. 12, 1877 (2002) arXiv:cond-mat/0107370
"New Trends in Superconductivity", edited by J.F. Annett and S. Kruchinin, Kluwer, Academic Publishers (2002).
Physica B 318, 162 (2002) arXiv:cond-mat/0105486
Phys. Rev. B 66, 214525 (2002) arXiv:cond-mat/0208076
Phys. Rev. B 66, 174515 (2002) arXiv:cond-mat/0205495
Physica C 372-376P1, 184 (2002); Special issue: Proceeding of the 5th European Conference on Applied Superconductivity, Copenhagen, Denmark, (Sep. 2001) arXiv:cond-mat/0109384
Low Temp Phys. 27, 616 (2001) arXiv:cond-mat/0109333
Phys. Rev. Lett. 86, 5369 (2001) arXiv:cond-mat/0102404
Phys. Rev. B 63, 212502 (2001) arXiv:cond-mat/0011416
Third Party Publications
Los Alamos National Laboratory, 1663 Magazine, July 2016
"Quantum computers have long been on the horizon as conventional computing technologies approach their physical limits. While general-purpose quantum computers remain on the horizon for the time being, a special kind of quantum computer already exists and could be a game changer for simulation and computing tools in support of Los Alamos National Laboratory’s mission of stockpile stewardship without nuclear testing. It may also enable a slew of broader national security and computer science applications. But first, it will undoubtedly draw a vibrant community of top creative thinkers in many scientific fields to Los Alamos."
M.A. Novotny, L. Hobl, J.S. Hall, and K. Michielsen (Department of Physics and Astronomy, and Center for Computational Sciences, Mississippi State University and Institute for Advanced Simulation, Ju ̈lich Supercomputing Centre)
"Calculations on D-Wave machines are presented, both for the 500-qubit and the 1000-qubit machines. Results are presented for spanning trees on the available K4,4 Chimera graphs of both machines. Comparing trees of approximately the same size, the frequency of finding the ground state for the 1000-qubit machine is significantly improved over the 500- qubit older generation machine."
(Feb 2016) Journal of Physics Conference Series http://iopscience.iop.org/article/10.1088/1742-6596/681/1/012005/meta
Vasil S. Denchev, Sergio Boixo, Sergei V. Isakov, Nan Ding, Ryan Babbush, Vadim Smelyanskiy, John Martinis, Hartmut Neven (Google scientists)
"Quantum annealing (QA) has been proposed as a quantum enhanced optimization heuristic exploiting tunneling. Here, we demonstrate how finite range tunneling can provide considerable computational advantage. For a crafted problem designed to have tall and narrow energy barriers separating local minima, the D-Wave 2X quantum annealer achieves significant runtime advantages relative to Simulated Annealing (SA). For instances with 945 variables this results in a time-to-99%-success-probability that is ∼108 times faster than SA running on a single processor core. "
(30 Dec 2015) http://arxiv.org/abs/1512.02206
Immanuel Trummer and Christoph Koch, (E ́cole Polytechnique Federale de Lausanne scientists)
"In this paper, we tackle the problem of multiple query optimization (MQO)...While the problem sizes that can be treated are currently limited, we already find a class of problem instances where the quantum annealer is three orders of magnitude faster than other approaches."
(23 Oct 2015) http://arxiv.org/pdf/1510.06437v1.pdf
Steven H. Adachi, Maxwell P. Henderson (Lockheed Martin scientists)
"We investigated an alternative approach [to Deep Learning] that estimates model expectations of Restricted Boltzmann Machines using samples from a D-Wave quantum annealing machine...In our tests we found that the quantum sampling-based training approach achieves comparable or better accuracy with significantly fewer iterations of generative training than conventional CD-based training."
(Oct 2015) Mathpubs: http://www.mathpubs.com/detail/1510.06356v1/Application-of-Quantum-Annea...
Gili Rosenberg, Poya Haghnegahdar, Phil Goddard, Peter Carr, Kesheng Wu, Marcos López de Prado
“We solve a multi-period portfolio optimization problem using D-Wave Systems' quantum annealer. We derive a formulation of the problem, discuss several possible integer encoding schemes, and present numerical examples that show high success rates.”
(22 Aug 2015) http://arxiv.org/abs/1508.06182
ACM SIGACT News archive, Volume 46 Issue 1, March 2015, Pages 40-61 http://dl.acm.org/citation.cfm?id=2744459&dl=ACM&coll=DL&CFID=666501900&CFTOKEN=29005022
"The paper presents a brief introduction to quantum computing with focus on the adiabatic model which is illustrated with the commercial D-Wave computer. We also include new theory and experimental work done on the D-Wave computer. Finally we discuss a hybrid method of combining classical and quantum computing and a few open problems."
Ojas Parekh, Jeremy Wendt, Luke Shulenburger, Andrew Landahl, Jonathan Moussa, John Aidun (Sandia National Laboratories scientists)
"We lay the foundation for a benchmarking methodology for assessing current and future quantum computers. We pose and begin addressing fundamental questions about how to fairly compare computational devices at vastly different stages of technological maturity. We critically evaluate and offer our own contributions to current quantum benchmarking efforts, in particular those involving adiabatic quantum computation and the Adiabatic Quantum Optimizers produced by D-Wave Systems, Inc. "
(Apr 2015) Link to PDF
Sergio Boixo, Vadim N. Smelyanskiy, Alireza Shabani, Sergei V. Isakov, Mark Dykman, Vasil S. Denchev, Mohammad Amin, Anatoly Smirnov, Masoud Mohseni, Hartmut Neven (Scientists from Google, NASA Ames, and D-Wave)
Quantum tunneling, a phenomenon in which a quantum state traverses energy barriers above the energy of the state itself, has been hypothesized as an advantageous physical resource for optimization. This paper demonstrates that multiqubit tunneling plays a computational role in the D-Wave processor.
(Feb 20 2015) Nature Communications http://www.nature.com/ncomms/2016/160107/ncomms10327/full/ncomms10327.html
Daryl P Nazareth and Jason D Spaans (Roswell Park Cancer Institute)
"Optimization methods are critical to radiation therapy. A new technology, quantum annealing (QA), employs novel hardware and software techniques to address various discrete optimization problems in many fields. We report on the first application of quantum annealing to the process of beamlet intensity optimization for IMRT...This initial experiment suggests that more research into QA-based heuristics may offer significant speedup over conventional clinical optimization methods, as quantum annealing hardware scales to larger sizes."
(1 May 2015) Institute of Physics and Engineering in Medicine http://iopscience.iop.org/article/10.1088/0031-9155/60/10/4137/pdf
Tameem Albash, Troels F. Rønnow, Matthias Troyer, Daniel A. Lidar
(12 Sep 2014) http://arxiv.org/abs/1409.3827
Kristen L. Pudenz, Tameem Albash, Daniel A. Lidar
(19 Aug 2014) http://arxiv.org/abs/1408.4382
Alejandro Perdomo-Ortiz, Joseph Fluegemann, Sriram Narasimhan, Rupak Biswas, Vadim N. Smelyanskiy
(30 Jun 2014) http://arxiv.org/abs/1406.7601
Davide Venturelli, Salvatore Mandrà, Sergey Knysh, Bryan O'Gorman, Rupak Biswas, Vadim Smelyanskiy
(29 Jun 2014) http://arxiv.org/abs/1406.7553
Walter Vinci, Tameem Albash, Anurag Mishra, Paul A. Warburton, Daniel A. Lidar
(17 Mar 2014) http://arxiv.org/abs/1403.4228
Helmut G. Katzgraber, Firas Hamze, Ruben S. Andrist
(12 Jan 2014) http://arxiv.org/pdf/1401.1546.pdf
Z. Bian et al.
Phys. Rev. Lett. vol. 111, 130505 (2013) arXiv:1201.1842
K.L. Pudenz et al.
(31 Jul 2013) arXiv:1307.8190
W. Vinci et al.
(3 Jul 2013) arXiv:1307.1114
S Boxio et al.
Nature Communications, 2067 (28 June 2013) doi:10.1038/ncomms3067
(12 Jul 2013) arXiv:1307.3931
S. Boxio et al.
(16 Apr 2013) arXiv:1304.4595
(21 Jan 2013) arXiv:1301.4956
C. C. McGeoch et al.
R. Babbush et al.
(4 Nov 2012) arXiv:1211.3422
I. Hen et al.
(6 Jul 2012) arXiv:1207.1712
V.S. Denchev et al.
(5 May 2012) arXiv:1205.1148
A. Perdomo-Ortiz et al.
(24 Apr 2012) arXiv:1204.5485
V.N. Smelyanskiy et al.
(12 Apr 2012) arXiv:1204.2821
D. Nagaj et al.
Phys. Rev. Lett. 109, 050501 (2012) arXiv:1202.6257
H. Neven, et al.
(4 Dec 2009) arXiv:0912.0779
H. Neven et al.
(4 Nov 2008) arXiv:0811.0416
H. Neven et al.
(28 Apr 2008) arXiv:0804.4457