A paper about near-term application problems for quantum annealing on D-Wave, from the 2017 SIAM Annual Meeting minisymposium entitled “Identifying Computational Methods for Early Benefit from Quantum Computing". Paper authors are from Los Alamos National Laboratory, 1QBit, Volkswagen and D-Wave. DOWNLOAD.
Technology Information
2017
How Will Early Quantum Computing Benefit Computational Methods?
D-Wave 2000Q Technology Overview
Read the updated D-Wave 2000Q Technology Overview.
D-Wave Overview
A brief introduction to D-Wave and quantum computing. Read the D-Wave Overview
2016
IDC: Quantum Computing in the Real World
IDC recently published a Technology Spotlight on quantum computing. Download the report here.
D-Wave White Papers
2018
Synopsis: Phase transitions in a programmable quantum spin-glass simulator
Summary
In Science, July 13, 2018, researchers from D-Wave Systems Inc. report upon using a 2048-qubit quantum processing unit to experimentally study a computationally dif- cult problem known within the eld of quantum magnetism as the transverse eld Ising model. The researchers programmed 3-dimensional cubic lattices containing up to 512 quantum spins into their processor and studied the magnetic properties as a function of energy scales and intentionally induced disorder. The predicted phase tran- sitions between paramagnetic and ordered antiferromagnetic phases for low concentrations of disorder, and between paramagnetic and spin-glass phases for high con- centrations of disorder, were demonstrated as a function of the quantum mechanical energy scale.
Performance advantage in quantum Boltzmann sampling
Investigations of quantum computing were originally motivated by the possibility of efficiently simulating quantum systems. Here we approach this challenge using a D-Wave 2000Q system to estimate quantum Boltzmann statistics. We compare performance with state-of-the-art classical Monte Carlo simulations of the quantum systems, and find that, over the problems studied, the D-Wave processor realizes a performance advantage over classical methods that increases with simulated system size.
2017
Reverse Quantum Annealing for Local Refinement of Solutions
The success of classical heuristic search algorithms often depends on the balance between global search for good regions of the solution space (exploration) and local search that refones known good solutions (exploitation). While local refinement of known solutions is not available to the canonical forward quantum annealing algorithm, D-Wave has developed a reverse annealing feature that makes this possible by annealing backward from a specified state, then forward to a new state. This enables the use of quantum annealing for the refinement of classical states via local search, making it possible to use quantum annealing as a component in more sophisticated hybrid algorithms. Local quantum search has been analyzed theoretically to explore applications such as protein folding, and has natural application in molecular dynamics, quantum simulation, and quantum chemistry, but has not been available for experiments until now. In a preliminary example, we show that reverse annealing can be used to generate new global optima up to 150 times faster than forward quantum annealing.
Virtual Graphs for High-Performance Embedded Topologies
Many optimization and machine learning algorithms are commonly described as graph problems. For example, graphical models are often used to analyze the flow of traffic between cities or the transmission of information between neurons in an artificial neural network.
D-Wave quantum processing units (QPUs) solve graphifical models—specifically, Ising minimization problems on a physical working graph made up of qubits and couplers. The new virtual graphs feature of the D-Wave 2000Q system provides users with improved embedding performance wrapped in a simplified interface. We describe the key enabling processor technologies, and provide a simple example with performance results enabled by this new feature in the D-Wave 2000Q system. DOWNLOAD.
Quantum Performance Evaluation: A Short Reading List
Since the first release of D-Wave annealing-based quantum computers in 2010, scores of research papers have been published describing their physical properties, capabilities, and performance. The research domain is complex and rich, which means that the work is ongoing and will continue for many years.
This white paper gives a snapshot of recent work on quantum system performance evaluation, which considers both solution quality and computation time.
Optimization with Clause Problems
We introduce a new input class called clause problems, that can be used to study local constraint structures, which occur in inputs translated from general NP-hard problems to the D-Wave native topology. We describe a small family of clause problems that are contrived to create significant challenges for two classical competition solvers, simulated annealing (SA) and the Hamze–de Frietas–Selby solver (HFS). We identify key properties of these inputs that lead to poor performance by the classical solvers, and consider whether these properties might naturally arise in problems from real-world applications.
Computational Power Consumption and Speedup
Power consumption for computation is a serious and growing issue for the world. We rely more and more on computing in everything we do as we try to satisfy our ever-increasing thirst for mobile computing, automation, machine intelligence, cloud computing, and increasingly powerful supercomputers. Highly specialized coprocessors such as D-Wave’s quantum processing units (QPUs) show promise in significantly increasing the power effciency of computing. In a recent study, D-Wave’s 2000-qubit system was shown to be up to 100 times more energy effcient than highly specialized algorithms on state-of-the-art classical computing servers when considering pure computation time, suggesting immediate relevance to large-scale energy efficient computing.
Quantum Annealing amid Local Ruggedness and Global Frustration
We introduce a problem class with two attributes crucial to the evaluation of quantum annealing processors: local ruggedness (i.e., tall, thin energy barriers in the energy landscape) so that quantum tunneling can be harnessed as a useful resource, and global frustration so that the problems are combinatorially challenging and representative of real-world inputs. We evaluate the new 2000-qubit D-Wave quantum processing unit (QPU) on these inputs, comparing it to software solvers that include both GPU-based solvers and a CPU-based solver which is highly tailored to the D-Wave topology. The D-Wave QPU solidly outperforms the software solvers: when we consider pure annealing time, the D-Wave QPU is three to four orders of magnitude faster than software solvers in both optimization and sampling evaluations.
Boosting integer factoring performance via quantum annealing offsets
D-Wave quantum computing systems now allow a user to advance or delay the annealing path of individual qubits through the anneal offsets feature. Here we demonstrate the potential of this feature by using it in an integer factoring circuit. Offsets allow the user to homogenize dynamics of various computational elements in the circuit. This gives a remarkable improvement over baseline performance, in some cases making the computation more than 1000 times faster.
Limits on Parallel Speedup for Classical Ising Model Solvers
Why can’t we put together a million cores and make it run a million times faster? Parallel computing systems offer enormous potential for significant runtime speedups over computation by a single CPU core. However, many computational tasks cannot be effciently parallelized. We explore some practical limits to achieving parallel speedups, with reference to some classical optimization solvers that are competitors to D-Wave quantum computers.
Partitioning Optimization Problems for Hybrid Classical/Quantum Execution
In this white paper we introduce qbsolv, a tool that solves large quadratic unconstrained binary optimization (QUBO) problems by partitioning into subproblems targeted for execution on a D-Wave system. Using a classical subproblem solver rather than quantum annealing, qbsolv delivers state-of-the-art numerical results and executes almost twice as fast as the best previously known implementation. We have released qbsolv as open-source software to foster greater use and experimentation in such partitioning solvers and to establish the QUBO form as a target for higher-level optimization interfaces. The software can be acccessed on GitHub at github.com/dwavesystems/qbsolv.
2013
Programming with D-Wave: Map Coloring Problem
Quantum computing, as implemented in the D-Wave system, is described by a simple but largely unfamiliar programming model. Using a simple map coloring problem this white paper describes the entire set of transformations needed to find solutions by executing a single quantum machine instruction (QMI) within this programming model. This “direct embedding” is one of several ways to program the D-Wave quantum computer.
D-Wave Publications
2018
Observation of topological phenomena in a programmable lattice of 1,800 qubits
The work of Berezinskii, Kosterlitz and Thouless in the 1970s revealed exotic phases of matter governed by the topological properties of low-dimensional materials such as thin films of superfluids and superconductors. A hallmark of this phenomenon is the appearance and interaction of vortices and antivortices in an angular degree of freedom—typified by the classical XY model—owing to thermal fluctuations. In the two-dimensional Ising model this angular degree of freedom is absent in the classical case, but with the addition of a transverse field it can emerge from the interplay between frustration and quantum fluctuations. Consequently, a Kosterlitz–Thouless phase transition has been predicted in the quantum system—the two-dimensional transverse-field Ising model—by theory and simulation. Here we demonstrate a large- scale quantum simulation of this phenomenon in a network of 1,800 in situ programmable superconducting niobium flux qubits whose pairwise couplings are arranged in a fully frustrated square-octagonal lattice. Essential to the critical behaviour, we observe the emergence of a complex order parameter with continuous rotational symmetry, and the onset of quasi-long-range order as the system approaches a critical temperature. We describe and use a simple approach to statistical estimation with an annealing-based quantum processor that performs Monte Carlo sampling in a chain of reverse quantum annealing protocols. Observations are consistent with classical simulations across a range of Hamiltonian parameters. We anticipate that our approach of using a quantum processor as a programmable magnetic lattice will find widespread use in the simulation and development of exotic materials.
(22 Aug 2018) Nature (Vol. 560, Issue 7719, August 22, 2018)
Read the Synopsis See arXiv: https://arxiv.org/abs/1803.02047
Phase transitions in a programmable quantum spin glass simulator
Understanding magnetic phases in quantum mechanical systems is one of the essential goals in condensed matter physics, and the advent of prototype quantum simulation hardware has provided new tools for experimentally probing such systems. We report on the experimental realization of a quantum simulation of interacting Ising spins on three-dimensional cubic lattices up to dimensions 8 × 8 × 8 on a D-Wave processor (D-Wave Systems, Burnaby, Canada). The ability to control and read out the state of individual spins provides direct access to several order parameters, which we used to determine the lattice’s magnetic phases as well as critical disorder and one of its universal exponents. By tuning the degree of disorder and effective transverse magnetic field, we observed phase transitions between a paramagnetic, an antiferromagnetic, and a spin-glass phase.
(13 Jul 2018) Science Vol. 361, Issue 6398, pp. 162-165
DOI: 10.1126/science.aat2025
GumBolt: Extending Gumbel trick to Boltzmann priors
Amir H. Khoshaman, Mohammad H. Amin
Boltzmann machines (BMs) are appealing candidates for powerful priors in variational autoencoders (VAEs), as they are capable of capturing nontrivial and multi-modal distributions over discrete variables. However, indifferentiability of the discrete units prohibits using the reparameterization trick, essential for low-noise back propagation. The Gumbel trick resolves this problem in a consistent way by relaxing the variables and distributions, but it is incompatible with BM priors. Here, we propose the GumBolt, a model that extends the Gumbel trick to BM priors in VAEs. GumBolt is significantly simpler than the recently proposed methods with BM prior and outperforms them by a considerable margin. It achieves state-of-the-art performance on permutation invariant MNIST and OMNIGLOT datasets in the scope of models with only discrete latent variables. Moreover, the performance can be further improved by allowing multi-sampled (importance-weighted) estimation of log-likelihood in training, which was not possible with previous models.
(18 May 2018) https://arxiv.org/abs/1805.07349
DVAE#: Discrete Variational Autoencoders with Relaxed Boltzmann Priors
Arash Vahdat, Evgeny Andriyash, William G. Macready
Boltzmann machines are powerful distributions that have been shown to be an effective prior over binary latent variables in variational autoencoders (VAEs). However, previous methods for training discrete VAEs have used the evidence lower bound and not the tighter importance-weighted bound. We propose two approaches for relaxing Boltzmann machines to continuous distributions that permit training with importance-weighted bounds. These relaxations are based on generalized overlapping transformations and the Gaussian integral trick. Experiments on the MNIST and OMNIGLOT datasets show that these relaxations outperform previous discrete VAEs with Boltzmann priors.
(18 May 2018) https://arxiv.org/abs/1805.07445
Theory of open quantum dynamics with hybrid noise
Anatoly Yu. Smirnov, Mohammad H. Amin
We develop a theory to describe dynamics of a nonstationary open quantum system interacting with a hybrid environment, which includes high-frequency and low-frequency noise components. One part of the system-bath interaction is treated in a perturbative manner, whereas the other part is considered exactly. This approach allows us to derive a set of master equations where the relaxation rates are expressed as convolutions of the Bloch-Redfield and Marcus formulas. Our theory enables analysis of systems that have extremely small energy gaps in the presence of a realistic environment. We apply the theory to an example of the 16-qubit quantum annealing problem with dangling qubits and show qualitative agreement with experimental results.
(21 Feb 2018) https://arxiv.org/abs/1802.07715
Toward Robustness against Label Noise in Training Deep Discriminative Neural Networks
Arash Vahdat
Collecting large training datasets, annotated with high-quality labels, is costly and time-consuming. This paper proposes a novel framework for training deep convolutional neural networks from noisy labeled datasets that can be obtained cheaply. The problem is formulated using an undirected graphical model that represents the relationship between noisy and clean labels, trained in a semi-supervised setting. In our formulation, the inference over latent clean labels is tractable and is regularized during training using auxiliary sources of information. The proposed model is applied to the image labeling problem and is shown to be effective in labeling unseen images as well as reducing label noise in training on CIFAR-10 and MS COCO datasets.
(23 Feb 2018) Link to paper
Quantum Variational Autoencoder
Amir Khoshaman, Walter Vinci, Brandon Denis, Evgeny Andriyash,and Mohammad H. Amin
Variational autoencoders (VAEs) are powerful generative models with the salient ability to perform inference. Here, we introduce a quantum variational autoencoder (QVAE): a VAE whose latent generative process is implemented as a quantum Boltzmann machine (QBM). We show that our model can be trained end-to-end by maximizing a well-defined loss-function: a “quantum” lower- bound to a variational approximation of the log-likelihood. We use quantum Monte Carlo (QMC) simulations to train and evaluate the performance of QVAEs. To achieve the best performance, we first create a VAE platform with discrete latent space generated by a restricted Boltzmann machine (RBM). Our model achieves state-of-the-art performance on the MNIST dataset when compared against similar approaches that only involve discrete variables in the generative process. We consider QVAEs with a smaller number of latent units to be able to perform QMC simulations, which are computationally expensive. We show that QVAEs can be trained effectively in regimes where quantum effects are relevant despite training via the quantum bound. Our findings open the way to the use of quantum computers to train QVAEs to achieve competitive performance for generative models. Placing a QBM in the latent space of a VAE leverages the full potential of current and next-generation quantum computers as sampling devices.
(22 Feb 2018) https://arxiv.org/pdf/1802.05779.pdf
DVAE++: Discrete Variational Autoencoders with Overlapping Transformations
Arash Vahdat, William G. Macready, Zhengbing Bian, Amir Khoshaman
Training of discrete latent variable models remains challenging because passing gradient information through discrete units is difficult. We propose a new class of smoothing transformations based on a mixture of two overlapping distributions, and show that the proposed transformation can be used for training binary latent models with either directed or undirected priors. We derive a new variational bound to efficiently train with Boltzmann machine priors. Using this bound, we develop DVAE++, a generative model with a global discrete prior and a hierarchy of convolutional continuous variables. Experiments on several benchmarks show that overlapping transformations outperform other recent continuous relaxations of discrete latent variables including Gumbel-Softmax (Maddison et al., 2016; Jang et al., 2016), and discrete variational autoencoders (Rolfe, 2016).
(14 Feb 2018) https://arxiv.org/pdf/1802.04920.pdf
2017
From Near to Eternity: Spin-glass planting, tiling puzzles, and constraint satisfaction problems
Firas Hamze (D-Wave); Darryl C. Jacob, Andrew J. Ochoa (Texas A&M University); Wenlong Wang (KTH Royal Institute of Technology,Texas A&M University); and Helmut G. Katzgraber (Texas A&M University, 1QBit Technologies)
We present a methodology for generating Ising Hamiltonians of tunable complexity and with a priori known ground states based on a decomposition of the model graph into edge-disjoint subgraphs. The idea is illustrated with a spin-glass model defined on a cubic lattice, where subproblems, whose couplers are restricted to the two values {-1,+1}, are specified on unit cubes and are parametrized by their local degeneracy. The construction is shown to be equivalent to a type of three-dimensional constraint satisfaction problem known as the tiling puzzle. By varying the proportions of subproblem types, the Hamiltonian can span a dramatic range of typical computational complexity, from fairly easy to many orders of magnitude more difficult than prototypical bimodal and Gaussian spin glasses in three space dimensions. We corroborate this behavior via experiments with different algorithms and discuss generalizations and extensions to different types of graphs.
(Nov 15, 2017) https://arxiv.org/abs/1711.04083
Toward Robustness against Label Noise in Training Deep Discriminative Neural Networks
Arash Vahdat
Collecting large training datasets, annotated with high-quality labels, is costly and time-consuming. This paper proposes a novel framework for training deep convolutional neural networks from noisy labeled datasets that can be obtained cheaply. The problem is formulated using an undirected graphical model that represents the relationship between noisy and clean labels, trained in a semi- supervised setting. In our formulation, the inference over latent clean labels is tractable and is regularized during training using auxiliary sources of information. The proposed model is applied to the image labeling problem and is shown to be effective in labeling unseen images as well as reducing label noise in training on CIFAR-10 and MS COCO datasets.
(03 Nov 2017) https://arxiv.org/pdf/1706.00038.pdf
Experimental demonstration of perturbative anticrossing mitigation using nonuniform driver Hamiltonians
Trevor Lanting, Andrew D. King, Bram Evert, and Emile Hoskinson
"Perturbative anticrossings have long been identified as a potential computational bottleneck for quantum annealing. This bottleneck can appear, for example, when a uniform transverse driver Hamiltonian is applied to each qubit. Previous theoretical research sought to alleviate such anticrossings by adjusting the transverse driver Hamiltonians on individual qubits according to a perturbative approximation. Here we apply this principle to a physical implementation of quantum annealing in a D-Wave 2000Q system. We use samples from the quantum annealing hardware and per-qubit anneal offsets to produce nonuniform driver Hamiltonians. On small instances with severe perturbative anticrossings, our algorithm yields an increase in minimum eigengaps, ground-state success probabilities, and escape rates from metastable valleys. We also demonstrate that the same approach can mitigate biased sampling of degenerate ground states."
Physical Review A (16 Oct 2017) https://journals.aps.org/pra/abstract/10.1103/PhysRevA.96.042322
Experimental demonstration of perturbative anticrossing mitigation using non-uniform driver Hamiltonians
Trevor Lanting, Andrew D. King, Bram Evert, Emile Hoskinson
"Perturbative anticrossings have long been identified as a potential computational bottleneck for quantum annealing. This bottleneck can appear, for example, when a uniform transverse driver Hamiltonian is applied to each qubit. Previous theoretical research sought to alleviate such anticrossings by adjusting the transverse driver Hamiltonians on individual qubits according to a perturbative approximation. Here we apply this principle to a physical implementation of quantum annealing in a D-Wave 2000Q system. We use samples from the quantum annealing hardware and per-qubit anneal offsets to produce nonuniform driver Hamiltonians. On small instances with severe perturbative anticrossings, our algorithm yields an increase in minimum eigengaps, ground state success probabilities, and escape rates from metastable valleys. We also demonstrate that the same approach can mitigate biased sampling of degenerate ground states."
(10 Aug 2017) https://arxiv.org/abs/1708.03049
Can quantum Monte Carlo simulate quantum annealing?
Evgeny Andriyash and Mohammad H. Amin
"Recent theoretical and experimental studies have suggested that quantum Monte Carlo (QMC) simulation can behave similarly to quantum annealing (QA)...Here, we compare incoherent tunneling and QMC escape using perturbation theory, which has much wider validity than WKB approximation. We show that the two do not scale the same way when there are multiple homotopy-inequivalent paths for tunneling. We demonstrate through examples that frustration can generate an exponential number of tunneling paths, which under certain conditions can lead to an exponential advantage for incoherent tunneling over classical QMC escape. We provide analytical and numerical evidence for such an advantage and show that it holds beyond perturbation theory."
(27 Mar 2017) Link to PDF.
Quantum eigenstate tomography with qubit tunneling spectroscopy
Anatoly Yu. Smirnov and Mohammad H. Amin
"Measurement of the energy eigenvalues (spectrum) of a multi-qubit system has recently become possible by qubit tunneling spectroscopy (QTS). In the standard QTS experiments, an incoherent probe qubit is strongly coupled to one of the qubits of the system in such a way that its incoherent tunneling rate provides information about the energy eigenvalues of the original (source) system. In this paper, we generalize QTS by coupling the probe qubit to many source qubits. We show that by properly choosing the couplings, one can perform projective measurements of the source system energy eigenstates in an arbitrary basis, thus performing quantum eigenstate tomography. As a practical example of a limited tomography, we apply our scheme to probe the eigenstates of a kink in a frustrated transverse Ising chain."
(25 Feb 2017) Link to PDF.
2016
Benchmarking Quantum Hardware for Training of Fully Visible Boltzmann Machines
“Quantum annealing (QA) is a hardware-based heuristic optimization and sampling method applicable to discrete undirected graphical models. While similar to simulated annealing, QA relies on quantum, rather than thermal, effects to explore complex search spaces. For many classes of problems, QA is known to offer computational advantages over simulated annealing. Here we report on the ability of recent QA hardware to accelerate training of fully visible Boltzmann machines.”
(14 Nov 2016) https://arxiv.org/abs/1611.04528
Discrete Variational Autoencoders
“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
Global warming: Temperature estimation in annealers
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.
Mapping constrained optimization problems to quantum annealing with application to fault diagnosis
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
Quantum Boltzmann Machine
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
A frequency and sensitivity tunable microresonator array for high-speed quantum processor readout
J. D. Whittaker, L. J. Swenson, M. H. Volkmann, P. Spear, F. Altomare, A. J. Berkley, B. Bumble, P. Bunyk, P. K. Day, B. H. Eom, R. Harris, J. P. Hilton, E. Hoskinson, M. W. Johnson, A. Kleinsasser, E. Ladizinsky, T. Lanting, T. Oh, I. Perminov, E. Tolkacheva, and J. Yao
"Superconducting microresonators have been successfully utilized as detection elements for a wide variety of applications. With multiplexing factors exceeding 1000 detectors per transmission line, they are the most scalable low-temperature detector technology demonstrated to date. For high-throughput applications, fewer detectors can be coupled to a single wire but utilize a larger per-detector bandwidth. For all existing designs, fluctuations in fabrication tolerances result in a non-uniform shift in resonance frequency and sensitivity, which ultimately limits the efficiency of bandwidth utilization. Here, we present the design, implementation, and initial characterization of a superconducting microresonator readout integrating two tunable inductances per detector. We demonstrate that these tuning elements provide independent control of both the detector frequency and sensitivity, allowing us to maximize the transmission line bandwidth utilization. Finally, we discuss the integration of these detectors in a multilayer fabrication stack for high-speed readout of the D-Wave quantum processor, highlighting the use of control and routing circuitry composed of single-flux-quantum loops to minimize the number of control wires at the lowest temperature stage."
(Jan 2016) Journal of Applied Physics 119, 014506 (2016); https://doi.org/10.1063/1.4939161
2015
Degeneracy, degree, and heavy tails in quantum annealing
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.
Fast clique minor generation in Chimera qubit connectivity graphs
Tomas Boothby, Andrew D. King, Aidan Roy
(27 Oct 2015) http://link.springer.com/article/10.1007/s11128-015-1150-6?wt_mc=internal.event.1.SEM.ArticleAuthorOnlineFirst
Constructing SAT Filters with a Quantum Annealer
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."
( 27 Oct 2015) http://link.springer.com/chapter/10.1007%2F978-3-319-24318-4_9
Performance of a quantum annealer on range-limited constraint satisfaction problems
A.D.King, T.Lanting, and R.Harris
(3 Sep 2015) http://arxiv.org/pdf/1502.02098.pdf
Benchmarking a quantum annealing processor with the time-to-target metric
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
Searching for quantum speedup in quasistatic quantum annealers
Mohammad H. Amin
(13 Mar 2015) http://arxiv.org/pdf/1503.04216.pdf
Computational Role of Collective Tunneling in a Quantum Annealer
Sergio Boixo et al.
(19 Feb 2015) http://arxiv.org/pdf/1411.4036.pdf
2014
Discrete optimization using quantum annealing on sparse Ising models
Frontiers in Physics, (18 Sep 2014) http://journal.frontiersin.org/Journal/10.3389/fphy.2014.00056/abstract
A practical heuristic for finding graph minors
Jun Cai, Bill Macready, Aidan Roy
(12 Jun 2014) http://arxiv.org/pdf/1406.2741.pdf
Entanglement in a quantum annealing processor
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
Architectural considerations in the design of a superconducting quantum annealing processor
P. Bunyk et al.
Pre-print (21 Jan 2014) http://arxiv.org/pdf/1401.5504v1
2013
Evidence for temperature dependent spin-diffusion as a mechanism of intrinsic flux noise in SQUIDs
T. Lanting et al.
(23 Dec 2013) http://arxiv.org/pdf/1306.1512.pdf
Thermally assisted quantum annealing of a 16-qubit problem
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
Adiabatic quantum optimization with qudits
M.H. Amin et al.
Quant. Inf. Proc. 12, 1819-1829 (April 2013) doi:10.1007/s11128-012-0480-x/QuantInfProc12/
Tunneling spectroscopy using a probe qubit
A. J. Berkley et al.
Phys. Rev. B 87, 020502(R) (2013) doi:10.1103/PhysRevB.87.020502
2012
Algorithmic approach to adiabatic quantum optimization
N. G. Dickson et al.
Phys. Rev. A 85, 032303 (2012) doi:10.1103/PhysRevA.85.032303arXiv:1108.33031
Approximate diagonalization method for large-scale Hamiltonians
M. H. Amin et al.
Phys. Rev. A 86, 052314 (2012) doi:10.1103/PhysRevA.86.052314
2011
Probing high-frequency noise with macroscopic resonant tunneling
T. Lanting et al.
Physical Review B PhysRevB.83.180502 arXiv:1103.1931
Quantum annealing with manufactured spins
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
Importance of Explicit Vectorization for CPU and GPU Software Performance
N. Dickson et al.
Journal of Computational Physics arXiv:1004.0024
The Ising model: teaching an old problem new tricks
Z. Bian et al.
Link to PDF
Investigating the Performance of an Adiabatic Quantum Optimization Processor
K. Karimi et al.
Quantum Information Processing arXiv:1006.4147
Does adiabatic quantum optimization fail for NP-complete problems?
N. G. Dickson et al.
Phys. Rev. Lett. 106, Issue 5, 050502 arXiv:1010.0669
2010
A scalable control system for a superconducting adiabatic quantum optimization processor
M. W. Johnson et al.
Supercond. Sci. Technol. 23, 065004 arXiv:0907.3757
Experimental Demonstration of a Robust and Scalable Flux Qubit
R. Harris et al.
Physical Review B 81, 134510 (2010) arXiv:0909.4321
High-Performance Physics Simulations Using Multi-Core CPUs and GPGPUs in a Volunteer Computing Context
K. Karimi et al.
International Journal of High Performance Computing Applications, doi: 10.1177/1094342010372928arXiv:1004.0023
Robust Parameter Selection for Parallel Tempering
F. Hamze et al
International Journal of Modern Physics C, Volume 21, issue 5 (2010) arXiv:1004.2840
Experimental Investigation of an Eight Qubit Unit Cell in a Superconducting Optimization Processor
R. Harris et al.
Phys. Rev. B 82, 024511 (2010) arXiv:1004.1628
Cotunneling in pairs of coupled flux qubits
T. Lanting et al.
Phys. Rev. B 82, 060512(R) (2010) arXiv:1006.0028
A scalable readout system for a superconducting adiabatic quantum optimization system
A. J. Berkley et al.
Supercond. Sci. Technol. 23, 105014 (2010) arXiv:0905.0891
2009
Non-Markovian incoherent quantum dynamics of a two-state system
M. H. S. Amin et al.
Phys. Rev. B 80, 214302 (2009) arXiv:0907.4797
Decoherence in adiabatic quantum computation
M. H. S. Amin et al.
Phys. Rev. A 79, 022107 (2009) arXiv:0708.0384
Phys. Rev. A 79, 022107 (2009) arXiv:0708.0384
A Compound Josephson Junction Coupler for Flux Qubits With Minimal Crosstalk
R. Harris et al.
Phys. Rev. B 80, 052506 (2009) arXiv:0904.3784
Phys. Rev. B 80, 052506 (2009) arXiv:0904.3784
Landau-Zener transitions in a superconducting flux qubit
J. Johansson et al.
Phys. Rev. B 80, 012507 (2009) arXiv:0807.0797
Phys. Rev. B 80, 012507 (2009) arXiv:0807.0797
Geometrical dependence of the low-frequency noise in superconducting flux qubits
Phys. Rev. B 79, 060509 (2009) arXiv:0812.0378
Consistency of the Adiabatic Theorem
Phys. Rev. Lett. 102, 220401 (2009) arXiv:0810.4335
Landau-Zener transitions in the presence of spin environment
A. T. S. Wan et al.
Int. J. Quant. Inf. 7, 725 (2009) arXiv:cond-mat/0703085
First Order Quantum Phase Transition in Adiabatic Quantum Computation
M. H. S. Amin et al.
Phys. Rev. A 80, 062326 (2009) arXiv:0904.1387
The Role of Single Qubit Decoherence Time in Adiabatic Quantum Computation
Phys. Rev. A 80, 022303 (2009) arXiv:0803.1196
2008
Minor-Embedding in Adiabatic Quantum Computation: I. The Parameter Setting Problem
Quantum Information Processing 7, pp193-209 (2008) arXiv:0804.4884
Macroscopic Resonant Tunneling in the Presence of Low Frequency Noise
M. H. S. Amin et al.
Phys. Rev. Lett. 100, 197001 (2008) arXiv:0712.0845
Phys. Rev. Lett. 100, 197001 (2008) arXiv:0712.0845
On the construction of model Hamiltonians for adiabatic quantum computing and its application to finding low energy conformations of lattice protein models
A. Perdomo et al.
Physical Review A 78, 012320 (2008) arXiv:0801.3625
Physical Review A 78, 012320 (2008) arXiv:0801.3625
Effect of Local Minima on Adiabatic Quantum Optimization
M. H. S. Amin et al.
Phys. Rev. Lett. 100, 130503 (2008) arXiv:0709.0528
Phys. Rev. Lett. 100, 130503 (2008) arXiv:0709.0528
Thermally Assisted Adiabatic Quantum Computation
M. H. S. Amin et al.
Phys. Rev. Lett. 100, 060503 (2008) arXiv:cond-mat/0609332
Phys. Rev. Lett. 100, 060503 (2008) arXiv:cond-mat/0609332
Probing Noise in Flux Qubits via Macroscopic Resonant Tunneling
R. Harris et al.
Phys. Rev. Lett. 101, 117003 (2008) arXiv:0712.0838
Phys. Rev. Lett. 101, 117003 (2008) arXiv:0712.0838
Realizable Hamiltonians for Universal Adiabatic Quantum Computers
J. D. Biamonte et al.
Phys. Rev. A 78, 012352 (2008) aXiv:0704.1287
Phys. Rev. A 78, 012352 (2008) aXiv:0704.1287
2007
Sign- and Magnitude-Tunable Coupler for Superconducting Flux Qubits
R. Harris et al.
Phys. Rev. Lett. 98, 177001 (2007) arXiv:cond-mat/0608253
Phys. Rev. Lett. 98, 177001 (2007) arXiv:cond-mat/0608253
A Characterization of global entanglement
P. J. Love et al.
Quant. Info. Proc. 6, 187 (2007) arXiv:quant-ph/0602143
Quant. Info. Proc. 6, 187 (2007) arXiv:quant-ph/0602143
2006
Rabi oscillations in systems with small anharmonicity
M. H. S. Amin et al.
Low Temp. Phys. 32, 198 (2006) arXiv:cond-mat/0407080
Low Temp. Phys. 32, 198 (2006) arXiv:cond-mat/0407080
Four-Qubit Device with Mixed Couplings
M. Grajcar et al.
Phys. Rev. Lett. 96, 047006 (2006) arXiv:cond-mat/0509557
Phys. Rev. Lett. 96, 047006 (2006) arXiv:cond-mat/0509557
Adiabatic quantum computation with flux qubits, first experimental results
S. H. W. van der Ploeg et al.
IEEE Trans. App. Supercond. 17, 113 (2006) arXiv:cond-mat/0702580
IEEE Trans. App. Supercond. 17, 113 (2006) arXiv:cond-mat/0702580
2005
Simulated Quantum Computation of Molecular Energies
A. Aspuru-Guzik et al.
Science 309 p. 1704, (2005) arXiv:quant-ph/0604193
Science 309 p. 1704, (2005) arXiv:quant-ph/0604193
Hamiltonian for coupled flux qubits
A. M. van den Brink et al.
Phys. Rev. B, 71, 064503 (2005) arXiv:cond-mat/0310425
Phys. Rev. B, 71, 064503 (2005) arXiv:cond-mat/0310425
Quantum nondemolition charge measurement of a Josephson qubit
M. H. S. Amin et al.
Phys. Rev. B 71, 140505 (2005) arXiv:cond-mat/0412286
Phys. Rev. B 71, 140505 (2005) arXiv:cond-mat/0412286
Silent phase qubit based on d -wave Josephson junctions
M. H. S. Amin et al.
Phys. Rev. B 71, 064516 (2005) arXiv:cond-mat/0310224
Phys. Rev. B 71, 064516 (2005) arXiv:cond-mat/0310224
Flux qubit in charge-phase regime
M.H.S. Amin et al.
Phys. Rev. B 71, 024504 (2005) arXiv:cond-mat/0311220
Phys. Rev. B 71, 024504 (2005) arXiv:cond-mat/0311220
Mediated tunable coupling of flux qubits
A. M. van den Brink et al.
New J. Phys. 7 230 (2005) arXiv:cond-mat/0501148
New J. Phys. 7 230 (2005) arXiv:cond-mat/0501148
Direct Josephson coupling between superconducting flux qubits
M. Grajcar et al.
Phys. Rev. B 72, (2005) 020503(R) arXiv:cond-mat/0501085
Phys. Rev. B 72, (2005) 020503(R) arXiv:cond-mat/0501085
2004
Evidence for Entangled States of Two Coupled Flux Qubits
A. Izmalkov et al.
Phys. Rev. Lett. 93, 037003 (2004) arXiv:cond-mat/0312332
Phys. Rev. Lett. 93, 037003 (2004) arXiv:cond-mat/0312332
Low-frequency measurement of the tunneling amplitude in a flux qubit
M. Grajcar et al.
Phys. Rev. B 69, 060501 (2004) arXiv:cond-mat/0303657
Phys. Rev. B 69, 060501 (2004) arXiv:cond-mat/0303657
Quasiparticle Decoherence in d-Wave Superconducting Qubits
M. H. S. Amin et al.
Phys. Rev. Lett. 92, 017001 (2004) arXiv:cond-mat/0304255
Phys. Rev. Lett. 92, 017001 (2004) arXiv:cond-mat/0304255
Observation of macroscopic Landau-Zener tunneling in a superconducting device
A. Izmalkov et al.
Euro. Phys. Lett. 65, 844, (2004) arXiv:cond-mat/0307506
Euro. Phys. Lett. 65, 844, (2004) arXiv:cond-mat/0307506
Wigner distribution function formalism for superconductors and collisionless dynamics of the superconducting order parameter
M. H. S. Amin et al.
Low Temp. Phys. 30, 661 (2004) arXiv:cond-mat/0404401
Low Temp. Phys. 30, 661 (2004) arXiv:cond-mat/0404401
Superconducting quantum storage and processing
M. H. S. Amin et al.
IEEE International Solid State Circuit Conference (ISSCC), Tech. Dig., p296(2004)
IEEE International Solid State Circuit Conference (ISSCC), Tech. Dig., p296(2004)
2003
Anomalous current-phase relation as basis for HTS qubit
S. A. Charlebois et al.
Proceedings of the European Conference on Applied Superconductivity (EUCAS 2003)
Proceedings of the European Conference on Applied Superconductivity (EUCAS 2003)
Nonequilibrium quasiclassical theory for Josephson structures
M. H. S. Amin, et al.
Phys. Rev. B 68, 054505 (2003) arXiv:cond-mat/0207724
Phys. Rev. B 68, 054505 (2003) arXiv:cond-mat/0207724
Josephson-phase qubit without tunneling
M. H. S. Amin et al.
Phys. Rev. B 67, 100508 (2003) arXiv:cond-mat/0211638
Phys. Rev. B 67, 100508 (2003) arXiv:cond-mat/0211638
Dynamical Effects of an Unconventional Current-Phase Relation in YBCO dc SQUIDs
T. Lindstrom et al.
Phys. Rev. Lett. 90, 117002 (2003) arXiv:cond-mat/0303144
Phys. Rev. Lett. 90, 117002 (2003) arXiv:cond-mat/0303144
Quasiclassical Calculations of spontaneous current in restricted geometries
M. H. S. Amin et al.
"Towards the Controllable Quantum States" edited by H. Takayanagi and J. Nitta, World Scientific Publishing Co. (2003), arXiv:cond-mat/0207617
"Towards the Controllable Quantum States" edited by H. Takayanagi and J. Nitta, World Scientific Publishing Co. (2003), arXiv:cond-mat/0207617
Continuous Monitoring of Rabi Oscillations in a Josephson Flux Qubit
E. Il'ichev et al.
Phys. Rev. Lett. 91, 097906 (2003) arXiv:cond-mat/0303433
Phys. Rev. Lett. 91, 097906 (2003) arXiv:cond-mat/0303433
Theory of weak continuous measurements in a strongly driven quantum bit
A. Y. Smirnov, et al.
Phys. Rev. B 68, 134514 (2003) arXiv:cond-mat/0306004
Phys. Rev. B 68, 134514 (2003) arXiv:cond-mat/0306004
Tunable coupling of superconducting qubits
A. Blais et al.
Phys. Rev. Lett. 90, 127901 (2003) arXiv:cond-mat/0207112
Phys. Rev. Lett. 90, 127901 (2003) arXiv:cond-mat/0207112
2002
Multi-Terminal Superconducting Phase Qubit
M. H. S. Amin et al.
Physica C 368, 310 (2002) arXiv:cond-mat/0109382
Physica C 368, 310 (2002) arXiv:cond-mat/0109382
High Temperature PI/2-SQUID
M. H. S. Amin et al.
IEEE Tran. Appl. Supercond. 12, 1877 (2002) arXiv:cond-mat/0107370
IEEE Tran. Appl. Supercond. 12, 1877 (2002) arXiv:cond-mat/0107370
Time reversal breaking states and spontaneous current pattern in Josephson junctions of d-wave superconductors
M. H. S. Amin et al.
"New Trends in Superconductivity", edited by J.F. Annett and S. Kruchinin, Kluwer, Academic Publishers (2002).
"New Trends in Superconductivity", edited by J.F. Annett and S. Kruchinin, Kluwer, Academic Publishers (2002).
Quasiclassical theory of spontaneous currents at surfaces and interfaces of d-Wave superconductors
M. H. S. Amin et al.
Physica B 318, 162 (2002) arXiv:cond-mat/0105486
Physica B 318, 162 (2002) arXiv:cond-mat/0105486
Low-frequency characterization of quantum tunneling in flux qubits
Y. S. Greenberg et al.
Phys. Rev. B 66, 214525 (2002) arXiv:cond-mat/0208076
Phys. Rev. B 66, 214525 (2002) arXiv:cond-mat/0208076
d+is versus d+id time reversal symmetry breaking states in finite size systems
M. H. S. Amin et al.
Phys. Rev. B 66, 174515 (2002) arXiv:cond-mat/0205495
Phys. Rev. B 66, 174515 (2002) arXiv:cond-mat/0205495
DC-SQUID based on the mesoscopic multi-terminal Josephson junction
M. H. S. Amin et al.
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
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
2001
Mesoscopic multi-terminal Josephson structures. I. effects of nonlocal weak coupling
M. H. S. Amin et al.
Low Temp Phys. 27, 616 (2001) arXiv:cond-mat/0109333
Low Temp Phys. 27, 616 (2001) arXiv:cond-mat/0109333
Degenerate Ground State in a Mesoscopic YBa2Cu3O7-x Grain Boundary Josephson Junction
E. Il'ichev et al.
Phys. Rev. Lett. 86, 5369 (2001) arXiv:cond-mat/0102404
Phys. Rev. Lett. 86, 5369 (2001) arXiv:cond-mat/0102404
Mechanisms of spontaneous current generation in an inhomogeneous d-wave superconductor
M. H. S. Amin et al.
Phys. Rev. B 63, 212502 (2001) arXiv:cond-mat/0011416
Phys. Rev. B 63, 212502 (2001) arXiv:cond-mat/0011416
Third Party Publications
2018
Quantum-Assisted Cluster Analysis on a Quantum Annealing Device
Florian Neukart, David Von Dollen and Christian Seidel
"We present an algorithm for quantum-assisted cluster analysis that makes use of the topological properties of a D-Wave 2000Q quantum processing unit. Clustering is a form of unsupervised machine learning, where instances are organized into groups whose members share similarities. The assignments are, in contrast to classification, not known a priori, but generated by the algorithm. We explain how the problem can be expressed as a quadratic unconstrained binary optimization problem and show that the introduced quantum-assisted clustering algorithm is, regarding accuracy, equivalent to commonly used classical clustering algorithms."
(14 June 2018) Frontiers in Physics https://www.frontiersin.org/articles/10.3389/fphy.2018.00055/full
Quantum annealing versus classical machine learning applied to a simplified computational biology problem
Richard Y. Li, Rosa Di Felice, Remo Rohs & Daniel A. Lidar
"Transcription factors regulate gene expression, but how these proteins recognize and specifically bind to their DNA targets is still debated. Machine learning models are effective means to reveal interaction mechanisms. Here we studied the ability of a quantum machine learning approach to classify and rank binding affinities. Using simplified data sets of a small number of DNA sequences derived from actual binding affinity experiments, we trained a commercially available quantum annealer to classify and rank transcription factor binding. The results were compared to state-of-the-art classical approaches for the same simplified data sets, including simulated annealing, simulated quantum annealing, multiple linear regression, LASSO, and extreme gradient boosting..."
(21 Feb 2018) https://www.nature.com/articles/s41534-018-0060-8
Efficient Combinatorial Optimization Using Quantum Annealing
Hristo N. Djidjev, Guillaume Chapuis, Georg Hahn, Guillaume Rizk
"The recent availability of the first commercial quantum computers has provided a promising tool to tackle NP hard problems which can only be solved heuristically with present techniques. However, it is unclear if the current state of quantum computing already provides a quantum advantage over the current state of the art in classical computing. This article assesses the performance of the D-Wave 2X quantum annealer on two NP hard graph problems, in particular clique finding and graph partitioning. For this, we provide formulations as Qubo and Ising Hamiltonians suitable for the quantum annealer and compare a variety of quantum solvers (Sapi, QBSolv, QSage provided by D-Wave Sys, Inc.) to current classical algorithms (METIS, Simulated Annealing, third-party clique finding and graph splitting heuristics) on certain test sets of graphs. We demonstrate that for small graph instances, classical methods still outperform the quantum annealer in terms of computing time, even though the quality of the best solutions obtained is comparable. Nevertheless, due to the limited problem size which can be embedded on the D-Wave 2X chip, the aforementioned finding applies to most of problems of general nature solvable on the quantum annealer. For instances specifically designed to fit the D-Wave 2X architecture, we observe substantial speed-ups in computing time over classical approaches.
(Revision 2 - 30 Jan 2018) https://arxiv.org/abs/1801.08653
Leveraging Adiabatic Quantum Computation for Election Forecasting
Maxwell Henderson, John Novak, Tristan Cook
"Accurate, reliable sampling from fully-connected graphs with arbitrary correlations is a difficult problem. Such sampling requires knowledge of the probabilities of observing every possible state of a graph. As graph size grows, the number of model states becomes intractably large and efficient computation requires full sampling be replaced with heuristics and algorithms that are only approximations of full sampling. This work investigates the potential impact of adiabatic quantum computation for sampling purposes, building on recent successes training Boltzmann machines using a quantum device. We investigate the use case of quantum computation to train Boltzmann machines for predicting the 2016 Presidential election."
(30 Jan 2018) https://arxiv.org/abs/1802.00069
2017
A deceptive step towards quantum speedup detection
Salvatore Mandrà, Helmut G. Katzgraber
"There have been multiple attempts to design synthetic benchmark problems with the goal of detecting quantum speedup in current quantum annealing machines. To date, classical heuristics have consistently outperformed quantum-annealing based approaches. Here we introduce a class of problems based on frustrated cluster loops - deceptive cluster loops - for which all currently known state-of-the-art classical heuristics are outperformed by the D-Wave 2000Q quantum annealing machine. While there is a sizable constant speedup over all known classical heuristics, a noticeable improvement in the scaling remains elusive. These results represent the first steps towards a detection of potential quantum speedup, albeit without a scaling improvement and for synthetic benchmark problems."
(4 Nov 2017) https://arxiv.org/abs/1711.01368
Solving a Higgs optimization problem with quantum annealing for machine learning
Alex Mott, Joshua Job, Jean-Roch Vlimant, Daniel Lidar: (University of Southern California), and Maria Spiropulu: (California Institute of Technology)
"The discovery of Higgs-boson decays in a background of standard-model processes was assisted by machine learning methods. The classifiers used to separate signals such as these from background are trained using highly unerring but not completely perfect simulations of the physical processes involved, often resulting in incorrect labelling of background processes or signals (label noise) and systematic errors. Here we use quantum and classical, annealing (probabilistic techniques for approximating the global maximum or minimum of a given function) to solve a Higgs-signal-versus-background machine learning optimization problem, mapped to a problem of finding the ground state of a corresponding Ising spin model."
(18 Oct 2017) http://www.nature.com/nature/journal/v550/n7676/full/nature24047.html
Traffic flow optimization using a quantum annealer
Florian Neukart, David Von Dollen, Gabriele Compostella, Christian Seidel, Sheir Yarkoni, and Bob Parney (Volkswagen Group of America, San Francisco; Volkswagen Data Lab, Munich, Germany; D-Wave Systems Inc., Burnaby, Canada)
"Quantum annealing algorithms belong to the class of meta-heuristic tools, applicable for solving binary optimization problems. Hardware implementations of quantum annealing, such as the quantum processing units (QPUs) produced by D-Wave Systems, have been subject to multiple analyses in research, with the aim of characterizing the technology’s usefulness for optimization and sampling tasks. In this paper, we present a real-world application that uses quantum technologies. Specifically, we show how to map certain parts of a real-world traffic flow optimization problem to be suitable for quantum annealing. We show that time-critical optimization tasks, such as continuous redistribution of position data for cars in dense road networks, are suitable candidates for quantum computing. Due to the limited size and connectivity of current-generation D-Wave QPUs, we use a hybrid quantum and classical approach to solve the traffic flow problem."
(20 Dec 2017) Frontiers in ICT Link
Graph Partitioning using Quantum Annealing on the D-Wave System
Hayato Ushijima-Mwesigwa, Christian F. A. Negre, and Susan M. Mniszewski
"In this work, we explore graph partitioning (GP) using quantum annealing on the D-Wave 2X machine. Motivated by a recently proposed graph-based electronic structure theory applied to quantum molecular dynamics (QMD) simulations, graph partitioning is used for reducing the calculation of the density matrix into smaller subsystems rendering the calculation more computationally efficient...Results for graph partitioning using quantum and hybrid classical-quantum approaches are shown to equal or out-perform current “state of the art” methods. "
(4 May 2017) https://arxiv.org/abs/1705.03082v1
Nonnegative/binary matrix factorization with a D-Wave quantum annealer
Daniel O’Malley, Velimir V. Vesselinov, Boian S. Alexandrov, and Ludmil B. Alexandrov (Los Alamos National Laboratory)
"D-Wave quantum annealers represent a novel computational architecture and have attracted significant interest, but have been used for few real-world computations. Machine learning has been identified as an area where quantum annealing may be useful. Here, we show that the D-Wave 2X can be effectively used as part of an unsupervised machine learning method. This method can be used to analyze large datasets. The D-Wave only limits the number of features that can be extracted from the dataset. We apply this method to learn the features from a set of facial images."
(5 April 2017) https://arxiv.org/abs/1704.01605
A Study of Complex Deep Learning Networks on High Performance, Neuromorphic, and Quantum Computers
Oak Ridge National Laboratory: Thomas E. Potok, Catherine Schuman, Steven R. Young, Robert M. Patton; USC Information Sciences Institute: Federico Spedalieri, Jeremy Liu, Ke-Thia Yao; University of Tennessee: Garrett Rose, Gangotree Chakma
"Current Deep Learning approaches have been very successful using convolutional neural networks (CNN) trained on large graphical processing units (GPU)-based computers. Three limitations of this approach are: 1) they are based on a simple layered network topology, i.e., highly connected layers, without intra-layer connections; 2) the networks are manually configured to achieve optimal results, and 3) the implementation of neuron model is expensive in both cost and power. In this paper, we evaluate deep learning models using three different computing architectures to address these problems: quantum computing to train complex topologies, high performance computing (HPC) to automatically determine network topology, and neuromorphic computing for a low-power hardware implementation. We use the MNIST dataset for our experiment, due to input size limitations of current quantum computers. Our results show the feasibility of using the three architectures in tandem to address the above deep learning limitations. We show a quantum computer can find high quality values of intra-layer connections weights, in a tractable time as the complexity of the network increases; a high performance computer can find optimal layer-based topologies; and a neuromorphic computer can represent the complex topology and weights derived from the other architectures in low power memristive hardware."
(15 Mar 2017) https://arxiv.org/abs/1703.05364
2016
Not Magic…Quantum
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."
Spanning Tree Calculations on D-Wave 2 Machines
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
2015
What is the Computational Value of Finite Range Tunneling?
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
Multiple Query Optimization on the D-Wave 2X Adiabatic Quantum Computer
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
Application of quantum annealing to training of deep neural networks
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...
Solving the Optimal Trading Trajectory Problem Using a Quantum Annealer
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
Guest Column: Adiabatic Quantum Computing Challenges
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."
Benchmarking Adiabatic Quantum Optimization for Complex Network Analysis
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
Computational Role of Multiqubit Tunneling in a Quantum Annealer
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
2014
First application of quantum annealing to IMRT beamlet intensity optimization
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
Reexamining classical and quantum models for the D-Wave One processor
(12 Sep 2014) http://arxiv.org/abs/1409.3827
Quantum annealing correction for random Ising problems
(19 Aug 2014) http://arxiv.org/abs/1408.4382
A Quantum Annealing Approach for Fault Detection and Diagnosis of Graph-Based Systems
(30 Jun 2014) http://arxiv.org/abs/1406.7601
Quantum Optimization of Fully-Connected Spin Glasses
(29 Jun 2014) http://arxiv.org/abs/1406.7553
Distinguishing Classical and Quantum Models for the D-Wave Device
Walter Vinci, Tameem Albash, Anurag Mishra, Paul A. Warburton, Daniel A. Lidar
(17 Mar 2014) http://arxiv.org/abs/1403.4228
Glassy Chimeras could be blind to quantum speedup: Designing better benchmarks for quantum annealing machines
Helmut G. Katzgraber, Firas Hamze, Ruben S. Andrist
(12 Jan 2014) http://arxiv.org/pdf/1401.1546.pdf
2013
Experimental determination of Ramsey numbers
Z. Bian et al.
Phys. Rev. Lett. vol. 111, 130505 (2013) arXiv:1201.1842
Error corrected quantum annealing with hundreds of qubits
K.L. Pudenz et al.
(31 Jul 2013) arXiv:1307.8190
Hearing the shape of Ising models: on the distinguishability power of Physics
W. Vinci et al.
(3 Jul 2013) arXiv:1307.1114
Experimental signature of programmable quantum annealing
S Boxio et al.
Nature Communications, 2067 (28 June 2013) doi:10.1038/ncomms3067
MAX 2-SAT with up to 108 qubits
S. Santra
(12 Jul 2013) arXiv:1307.3931
Quantum annealing with more than one hundred qubits
S. Boxio et al.
(16 Apr 2013) arXiv:1304.4595
How Fast Can Quantum Annealers Count?
I. Hen
(21 Jan 2013) arXiv:1301.4956
Experimental Evaluation of an Adiabatic Quantum System for Combinatorial Optimization
C. C. McGeoch et al.
Download PDF
2012
Construction of Energy Functions for Lattice Heteropolymer Models: A Case Study in Constraint Satisfaction Programming and Adiabatic Quantum Optimization
R. Babbush et al.
(4 Nov 2012) arXiv:1211.3422
Solving the Graph Isomorphism Problem with a Quantum Annealer
I. Hen et al.
(6 Jul 2012) arXiv:1207.1712
Robust Classification with Adiabatic Quantum Optimization
V.S. Denchev et al.
(5 May 2012) arXiv:1205.1148
Finding low-energy conformations of lattice protein models by quantum annealing
A. Perdomo-Ortiz et al.
(24 Apr 2012) arXiv:1204.5485
A Near-Term Quantum Computing Approach for Hard Computational Problems in Space Exploration
V.N. Smelyanskiy et al.
(12 Apr 2012) arXiv:1204.2821
Quantum Speedup by Quantum Annealing
D. Nagaj et al.
Phys. Rev. Lett. 109, 050501 (2012) arXiv:1202.6257
2009
Training a Large Scale Classifier with the Quantum Adiabatic Algorithm
H. Neven, et al.
(4 Dec 2009) arXiv:0912.0779
2008
Training a Binary Classifier with the Quantum Adiabatic Algorithm
H. Neven et al.
(4 Nov 2008) arXiv:0811.0416
Image recognition with an adiabatic quantum computer I. Mapping to quadratic unconstrained binary optimization
H. Neven et al.
(28 Apr 2008) arXiv:0804.4457
