Third Party Publications

Selected Papers

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
 

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

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

Not Magic…Quantum
Los Alamos National Laboratory, 1663 Magazine

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."

Link to PDF

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

 

2018

Mathematical Methods for a Quantum Annealing Computer

Richard H. Warren, Lockheed Martin Corporation-Retired

This paper describes the logic and creativity needed in order to have high probability of solving discrete optimization problems on a quantum annealing computer. Current features of quantum computing via annealing are discussed. We illustrate the logic at the forefront of this new era of computing, describe some of the work done in this field, and indicate the distinct mindset that is used when programming this type of machine. The traveling salesman problem is formulated for solving on a quantum annealing computer, which illustrates the methods for this computer.

(July 2018) Journal of Advances in Applied Mathematics, Vol. 3, No. 3, https://dx.doi.org/10.22606/jaam.2018.33002

 

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

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

2017

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

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

Guest Column: Adiabatic Quantum Computing Challenges
Cristian S. Calude, Elena Calude, Michael J. Dinneen

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."

 

 

2014

Reexamining classical and quantum models for the D-Wave One processor
Tameem Albash, Troels F. Rønnow, Matthias Troyer, Daniel A. Lidar
Quantum annealing correction for random Ising problems
Kristen L. Pudenz, Tameem Albash, Daniel A. Lidar
A Quantum Annealing Approach for Fault Detection and Diagnosis of Graph-Based Systems
Alejandro Perdomo-Ortiz, Joseph Fluegemann, Sriram Narasimhan, Rupak Biswas, Vadim N. Smelyanskiy
Quantum Optimization of Fully-Connected Spin Glasses
Davide Venturelli, Salvatore Mandrà, Sergey Knysh, Bryan O'Gorman, Rupak Biswas, Vadim Smelyanskiy
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