Scientific Publications

Thomas Lubinski, Carleton Coffrin, Catherine McGeoch, Pratik Sathe, Joshua Apanavicius, David Bernal Neira, Quantum Economic Development Consortium(QED-C) Collaboration

ACM Transactions on Quantum Computing, Volume 5, Issue 3

Abhishek Awasthi∗, Nico Kraus†, Florian Krellner‡, David Zambrano† ∗BASF Digital Solutions GmbH, Ludwigshafen am Rhein, Germany †Aqarios GmbH, Munich, Germany
‡SAP SE, Walldorf, Germany

This work is a benchmark study for quantum- classical computing method with a real-world optimization problem from industry. The problem involves scheduling and balancing jobs on different machines, with a non-linear objective function. We first present the motivation and the problem description, along with different modeling techniques for classical and quantum computing. The modeling for classical solvers has been done as a mixed-integer convex program, while for the quantum-classical solver we model the problem as a binary quadratic program, which is best suited to the D-Wave Leap’s Hybrid Solver. This ensures that all the solvers we use are fetched with dedicated and most suitable model(s). Henceforth, we carry out benchmarking and comparisons between classical and quantum-classical methods, on problem sizes ranging till approximately 150, 000 variables. We utilize an industry grade classical solver and compare its results with D-Wave Leap’s Hybrid Solver. The results we obtain from D-Wave are highly competitive and sometimes offer speedups, compared to the classical solver.

Pérez Armas, L.F., Creemers, S. & Deleplanque, S. Solving the resource constrained project scheduling problem with quantum annealing. Scientific Reports14, 16784 (2024). 

Quantum annealing emerges as a promising approach for tackling complex scheduling problems such as the resource-constrained project scheduling problem (RCPSP). This study represents the first application of quantum annealing to solve the RCPSP, analyzing 12 well-known mixed integer linear programming (MILP) formulations and converting the most qubit-efficient one into a quadratic unconstrained binary optimization (QUBO) model. We then solve this model using the D-wave advantage 6.3 quantum annealer, comparing its performance against classical computer solvers. Our results indicate significant potential, particularly for small to medium-sized instances. Further, we introduce time-to-target and Atos Q-score metrics to evaluate the effectiveness of quantum annealing and reverse quantum annealing. The paper also explores advanced quantum optimization techniques, such as customized anneal schedules, enhancing our understanding and application of quantum computing in operations researc

N. Nikmehr, P. Zhang, H. Zheng, T. -C. Wei, G. He and Y. A. Shamash, "Quantum Annealing-Infused Microgrids Formation: Distribution System Restoration and Resilience Enhancement," in IEEE Transactions on Power Systems, DOI: 10.1109/TPWRS.2024.3399122

In this paper, the use of quantum computing is explored to solve a crucial optimization problem in the formation of microgrids (MGs), which can enhance the resilience of distribution networks against natural disasters or faults. The study focuses on developing a quantum-inspired optimization model for critical load restoration via MGs formation, leveraging the power of quantum annealing to solve complex combinatorial problems that classical methods struggle with. The Constrained Quadratic Model (CQM) solver from D-Wave is used to merge classical and quantum optimization approaches, delivering improved solutions to complex optimization problems. The solver has been optimized to take advantage of quantum computing's parallelism to provide high-performance solutions. The study compares outcomes from the D-Wave hybrid quantum-classical solver and the classical Gurobi solver, underscoring the effectiveness of quantum computing in addressing resilience-oriented optimization challenges. This assessment is validated through two case studies: the IEEE 37-bus system and the IEEE 240-bus distribution system.

Pelofske, E., Bärtschi, A. & Eidenbenz, S. Short-depth QAOA circuits and quantum annealing on higher-order ising models. npj Quantum Information 10, 30 (2024). 

We present a direct comparison between QAOA (Quantum Alternating Operator Ansatz), and QA (Quantum Annealing) on 127 qubit problem instances. QAOA with p = 1, 2 rounds is executed on the 127 qubit heavy-hex graph gate-model quantum computer ibm_washington, using on-device grid-searches for angle finding, and QA is executed on two Pegasus-chip D-Wave quantum annealers. The problems are random Ising models whose connectivity matches heavy-hex graphs and the Pegasus graph connectivity, and optionally include hardware-compatible cubic terms (ZZZ terms). The QAOA circuits are heavily optimized and of extremely short depth, with a CNOT depth of 6 per round, which allows whole chip usage of the heavy-hex lattice. QAOA and QA are both compared against simulated annealing and the optimal solutions are computed exactly using CPLEX. The noiseless mean QAOA expectation values for p = 1, 2 are computed using classical light-cone based simulations. We find QA outperforms QAOA on the evaluated devices.

Anders Irbäck, Lucas Knuthson, Sandipan Mohanty, and Carsten Peterson, Using quantum annealing to design lattice proteins, Phys. Rev. Research 6, 013162 

Quantum annealing has shown promise for finding solutions to difficult optimization problems, including protein folding. Recently, we used the D-Wave Advantage quantum annealer to explore the folding problem in a coarse-grained lattice model, the HP model, in which amino acids are classified into two broad groups: hydrophobic (H) and polar (P). Using a set of 22 HP sequences with up to 64 amino acids, we demonstrated the fast and consistent identification of the correct HP model ground states using the D-Wave hybrid quantum-classical solver. An equally relevant biophysical challenge, called the protein design problem, is the inverse of the above, where the task is to predict protein sequences that fold to a given structure. Here, we approach the design problem by a two-step procedure implemented and executed on a D-Wave machine. In the first step, we perform a pure sequence-space search by varying the type of amino acid at each sequence position, and seek sequences which minimize the HP-model energy of the target structure. After mapping this task onto an Ising spin-glass representation, we employ a hybrid quantum-classical solver to deliver energy-optimal sequences for structures with 30–64 amino acids, with a 100% success rate. In the second step, we filter the optimized sequences from the first step according to their ability to fold to the intended structure. In addition, we try solving the sequence optimization problem using only the quantum processing unit (QPU), which confines us to sizes ≤20, due to exponentially decreasing success rates. To shed light on the pure QPU results, we investigate the effects of control errors caused by an imperfect implementation of the intended Hamiltonian on the QPU, by numerically analyzing the Schrödinger equation. We find that the simulated success rates in the presence of control noise semiquantitatively reproduce the modest pure QPU results for larger chains.

Humberto Munoz Bauza, Daniel A. Lidar, Scaling Advantage in Approximate Optimization with Quantum Annealing, arXiv:2401.07184 

Quantum annealing is a heuristic optimization algorithm that exploits quantum evolution to approximately find lowest energy states. Quantum annealers have scaled up in recent years to tackle increasingly larger and more highly connected discrete optimization and quantum simulation problems. Nevertheless, despite numerous attempts, a computational quantum advantage in exact optimization using quantum annealing hardware has so far remained elusive. Here, we present evidence for a quantum annealing scaling advantage in approximate optimization. The advantage is relative to the top classical heuristic algorithm: parallel tempering with isoenergetic cluster moves (PT-ICM). The setting is a family of 2D spin-glass problems with high-precision spin-spin interactions. To achieve this advantage, we implement quantum annealing correction (QAC): an embedding of a bit-flip error-correcting code with energy penalties that leverages the properties of the D-Wave Advantage quantum annealer to yield over 1,300 error-suppressed logical qubits on a degree-5 interaction graph. We generate random spin-glass instances on this graph and benchmark their time-to-epsilon, a generalization of the time-to-solution metric for low-energy states. We demonstrate that with QAC, quantum annealing exhibits a scaling advantage over PT-ICM at sampling low energy states with an optimality gap of at least 1.0%. This amounts to the first demonstration of an algorithmic quantum speedup in approximate optimization.

Pokharel, B., Izquierdo, Z.G., Lott, P.A. et al. Inter-generational comparison of quantum annealers in solving hard scheduling problems. Quantum Inf Process 22, 364 (2023). 

We compare the performance of four quantum annealers, the D-Wave Two, 2X, 2000Q, and Advantage in solving an identical ensemble of a parametrized family of scheduling problems. These problems are NP-complete and, in fact, equivalent to vertex coloring problems. They are also practically motivated and closely connected to planning problems from artificial intelligence. We examine factors contributing to the performance differences while separating the contributions from hardware upgrades, support for shorter anneal times, and possible optimization of ferromagnetic couplings. While shorter anneal times can improve the time to solution (TTS) at any given problem size, the scaling of TTS with respect to the problem size worsens for shorter anneal times. In contrast, optimizing the ferromagnetic coupling improves both the absolute TTS and the scaling. There is a statistically significant improvement in performance between D-Wave Two and 2X and from all older generation annealers to Advantage, even when operated under identical anneal time and ferromagnetic couplings. However, the performance improvement from 2X to 2000Q requires the anneal time and ferromagnetic couplings to be optimized. Overall, owing to these inter-generational hardware improvements and optimizations, the scaling exponent reduces from 1.01 ± 0.01 on Two to 0.259 ± 0.008 on Advantage.

S. Arai et al., Effectiveness of quantum annealing for continuous-variable optimization, Physical Review A, 108, 042403 (2023)

The application of quantum annealing to the optimization of continuous-variable functions is a relatively unexplored area of research. We test the performance of quantum annealing applied to a one-dimensional continuous-variable function with a rugged energy landscape. After domain-wall encoding to map a continuous variable to discrete Ising variables, we first benchmark the performance of the real hardware, the D-Wave 2000Q, against several state-of-the-art classical optimization algorithms designed for continuous-variable problems to find that the D-Wave 2000Q matches the classical algorithms in a limited domain of computation time. Beyond this domain, classical global optimization algorithms outperform the quantum device. Next we examine several optimization algorithms that are applicable to the Ising formulation of the problem, such as the time-evolving block decimation (TEBD) to simulate ideal coherent quantum annealing, simulated annealing, simulated quantum annealing, and spin-vector Monte Carlo. The data show that TEBD's coherent quantum annealing achieves far better results than the other approaches, demonstrating the effectiveness of coherent tunneling. From these two types of benchmarks, we conclude that the hardware realization of quantum annealing has the potential to significantly outperform the best classical algorithms if thermal noise and other imperfections are sufficiently suppressed and the device operates coherently, as demonstrated in recent short-time quantum simulations

R. Sandt and R. Spatschek, Efficient low temperature Monte Carlo sampling using quantum annealing, Nature Scientific Reports, 13, Article number 6754 (2023)

Quantum annealing is an efficient technology to determine ground state configurations of discrete binary optimization problems, described through Ising Hamiltonians. Here we show that—at very low computational cost—finite temperature properties can be calculated. The approach is most efficient at low temperatures, where conventional approaches like Metropolis Monte Carlo sampling suffer from high rejection rates and therefore large statistical noise. To demonstrate the general approach, we apply it to spin glasses and Ising chains.

E.  Pelofske, Comparing three generations of D-Wave quantum annealers for minor embedded combinatorial optimization problems, arXiv:2301.03009 

Quantum annealing is a novel type of analog computation that aims to use quantum mechanical fluctuations to search for optimal solutions of Ising problems. Quantum annealing in the Transverse Ising model, implemented on D-Wave QPUs, are available as cloud computing resources. In this article we report concise benchmarks across three generations of D-Wave quantum annealers, consisting of four different devices, for the NP-Hard combinatorial optimization problems unweighted maximum clique and unweighted maximum cut on random graphs. The Ising, or equivalently QUBO, formulation of these problems do not require auxiliary variables for order reduction, and their overall structure and weights are not highly complex, which makes these problems simple test cases to understand the sampling capability of current D-Wave quantum annealers. All-to-all minor embeddings of size 52, with relatively uniform chain lengths, are used for a direct comparison across the Chimera, Pegasus, and Zephyr device topologies. A grid search over annealing times and the minor embedding chain strengths is performed in order to determine the level of reasonable performance for each device and problem type. Experiment metrics that are reported are approximation ratios for non-broken chain samples and chain break proportions. How fairly the quantum annealers sample optimal maximum cliques, for instances which contain multiple maximum cliques, is also quantified using entropy of the measured ground state distributions. The newest generation of quantum annealing hardware, which has a Zephyr hardware connectivity, performed the best overall with respect to approximation ratios and chain break frequencies.

On the Emerging Potential of Quantum Annealing Hardware for Combinatorial Optimization

Byron Tasseff (Los Alamos), Tameem Albash (New Mexico U.), Zachary Morrell (Los Alamos), Marc Vuffray (Los Alamos), Andrey Y. Lokhov (Los Alamos) et al.

e-Print: 2210.04291 [math.OC]

A. Braida et al., On constant-time quantum annealing and guaranteed approximations for graph optimization problems, Quantum Science and Technology, 7, 4, 045030  (2022)

Quantum annealing (QA) is a computational framework where a quantum system's continuous evolution is used to find the global minimum of an objective function over an unstructured search space. It can be seen as a general metaheuristic for optimization problems, including NP-hard ones if we allow an exponentially large running time. While QA is widely studied from a heuristic point of view, little is known about theoretical guarantees on the quality of the solutions obtained in polynomial time. In this paper, we use a technique borrowed from theoretical physics, the Lieb–Robinson (LR) bound, and develop new tools proving that short, constant-time QA guarantees constant factor approximations ratios for some optimization problems when restricted to bounded degree graphs. Informally, on bounded degree graphs the LR bound allows us to retrieve a (relaxed) locality argument, through which the approximation ratio can be deduced by studying subgraphs of bounded radius. We illustrate our tools on problems MaxCut and maximum independent set for cubic graphs, providing explicit approximation ratios and the runtimes needed to obtain them. Our results are of similar flavor to the well-known ones obtained in the different but related QAOA (quantum optimization algorithms) framework.

D. Von Dollen et al., Quantum-enhanced selection operators for evolutionary algorithms,  Proceedings of GECCO’22,  pp. 463-466 arXiv:2206.10743 

Genetic algorithms have unique properties which are useful when applied to black box optimization. Using selection, crossover, and mutation operators, candidate solutions may be obtained without the need to calculate a gradient. In this work, we study results obtained from using quantum-enhanced operators within the selection mechanism of a genetic algorithm. Our approach frames the selection process as a minimization of a binary quadratic model with which we encode fitness and distance between members of a population, and we leverage a quantum annealing system to sample low energy solutions for the selection mechanism. We benchmark these quantum-enhanced algorithms against classical algorithms over various black-box objective functions, including the OneMax function, and functions from the IOHProfiler library for black-box optimization. We observe a performance gain in average number of generations to convergence for the quantum-enhanced elitist selection operator in comparison to classical on the OneMax function. We also find that the quantum-enhanced selection operator with non-elitist selection outperform benchmarks on functions with fitness perturbation from the IOHProfiler library. Additionally, we find that in the case of elitist selection, the quantum-enhanced operators outperform classical benchmarks on functions with varying degrees of dummy variables and neutrality.

Pelofske et al., Quantum annealing algorithms for Boolean tensor networks, Nature Scientific Reports, 12, 8539 (2022).

Quantum annealers manufactured by D-Wave Systems, Inc., are computational devices capable of finding high-quality heuristic solutions of NP-hard problems. In this contribution, we explore the potential and effectiveness of such quantum annealers for computing Boolean tensor networks. Tensors offer a natural way to model high-dimensional data commonplace in many scientific fields, and representing a binary tensor as a Boolean tensor network is the task of expressing a tensor containing categorical (i.e., {0,1}" role="presentation" style="box-sizing: inherit; display: inline-block; font-style: normal; font-weight: normal; line-height: normal; font-size: 18px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;">) values as a product of low dimensional binary tensors. A Boolean tensor network is computed by Boolean tensor decomposition, and it is usually not exact. The aim of such decomposition is to minimize the given distance measure between the high-dimensional input tensor and the product of lower-dimensional (usually three-dimensional) tensors and matrices representing the tensor network. In this paper, we introduce and analyze three general algorithms for Boolean tensor networks: Tucker, Tensor Train, and Hierarchical Tucker networks. The computation of a Boolean tensor network is reduced to a sequence of Boolean matrix factorizations, which we show can be expressed as a quadratic unconstrained binary optimization problem suitable for solving on a quantum annealer. By using a novel method we introduce called parallel quantum annealing, we demonstrate that Boolean tensor’s with up to millions of elements can be decomposed efficiently using a DWave 2000Q quantum annealer.

Nelson et al., High quality thermal Gibbs sampling with quantum annealing hardware, Physical Review Applied, 17, 044046 (2022) 

Quantum annealing (QA) was originally intended for accelerating the solution of combinatorial optimization tasks that have natural encodings as Ising models. However, recent experiments on QA-hardware platforms have demonstrated that, in the operating regime corresponding to weak interactions, the QA hardware behaves like a noisy Gibbs sampler at a hardware-specific effective temperature. This work builds on those insights and identifies a class of small hardware-native Ising models that are robust to noise effects and proposes a procedure for executing these models on QA hardware to maximize Gibbs-sampling performance. The experimental results indicate that the proposed protocol results in high-quality Gibbs samples from a hardware-specific effective temperature. Furthermore, we show that this effective temperature can be adjusted by modulating the annealing time and energy scale. The procedure proposed in this work provides an approach to using QA hardware for Ising-model sampling presenting potential opportunities for applications in machine learning and physics simulation.

Willsch et al., Benchmarking Advantage and D-Wave 2000Q quantum annealers with exact cover problems, Quantum Information Processing, Vol 21, No 141 (2022)

We benchmark the quantum processing units of the largest quantum annealers to date, the 5000+ qubit quantum annealer Advantage and its 2000+ qubit predecessor D-Wave 2000Q, using tail assignment and exact cover problems from aircraft scheduling scenarios. The benchmark set contains small, intermediate, and large problems with both sparsely connected and almost fully connected instances. We find that Advantage outperforms D-Wave 2000Q for almost all problems, with a notable increase in success rate and problem size. In particular, Advantage is also able to solve the largest problems with 120 logical qubits that D-Wave 2000Q cannot solve anymore. Furthermore, problems that can still be solved by D-Wave 2000Q are solved faster by Advantage. We find, however, that D-Wave 2000Q can achieve better success rates for sparsely connected problems that do not require the many new couplers present on Advantage, so improving the connectivity of a quantum annealer does not per se improve its performance.

Pelofske, E., Hahn, G. & Djidjev, H.N. Parallel quantum annealing. Scientific Reports 12, 4499 (2022).

The application of quantum annealing to the optimization of continuous-variable functions is a relatively unexplored area of research. We test the performance of quantum annealing applied to a one-dimensional continuous-variable function with a rugged energy landscape. After domain-wall encoding to map a continuous variable to discrete Ising variables, we first benchmark the performance of the real hardware, the D-Wave 2000Q, against several state-of-the-art classical optimization algorithms designed for continuous-variable problems to find that the D-Wave 2000Q matches the classical algorithms in a limited domain of computation time. Beyond this domain, classical global optimization algorithms outperform the quantum device. Next we examine several optimization algorithms that are applicable to the Ising formulation of the problem, such as the time-evolving block decimation (TEBD) to simulate ideal coherent quantum annealing, simulated annealing, simulated quantum annealing, and spin-vector Monte Carlo. The data show that TEBD's coherent quantum annealing achieves far better results than the other approaches, demonstrating the effectiveness of coherent tunneling. From these two types of benchmarks, we conclude that the hardware realization of quantum annealing has the potential to significantly outperform the best classical algorithms if thermal noise and other imperfections are sufficiently suppressed and the device operates coherently, as demonstrated in recent short-time quantum simulations. 

R. Zielewski and H. Takizawa, A method for reducing time-to-solution in quantum annealing through pausing,  Proc. Int. Conf. HPC in Asia-Pacific Region pp. 137-145 (2023)

Recent research has shown that alternative annealing schedules provide the means for improving performance in modern quantum annealing devices. One such type of schedule is forward annealing with a pause, in which there is a period of time when system evolution is paused. While the results from using this type of schedule have been promising, effectively using a pause is not a trivial task. One challenge associated with introducing a pause into the schedule is determining the point in the anneal at which the pause will start. Additionally, tuning the schedule in real-time requires a significant amount of time. A second challenge is that while a pause may increase the number of correct solutions returned from the annealer, the time-to-solution, a standard metric for measuring performance in quantum annealing, will not necessarily be improved. We propose a method for constructing annealing schedules containing a pause that avoids the costly process of determining the optimal pause location in an online manner. We also evaluate our method on the subset sum problem, a problem of practical significance, and show that our method is able to achieve a 70% reduction in time-to-solution from a standard schedule containing no pause.

Marina Fernández-Campoamor, et al.

With the increase of intermittent renewable generation resources feeding into the electrical grid, Distribution System Operators (DSOs) must find ways to incorporate these new actors and adapt the grid to ensure stability and enable flexibility. Dividing the grid into logical clusters entails several organizational and technical benefits, helping overcome these challenges. However, finding the optimal grid partitioning remains a challenging task due to its complexity. At the same time, new technology has gained traction in the last decades for its promising speed-up potential in solving non-trivial combinatorial optimization problems: quantum computing. This work explores its application in Graph Partitioning using electrical modularity. We benchmarked several quantum annealing and hybrid methods on IEEE well-known test cases. The results obtained for the IEEE 14-bus test case show that quantum annealing DWaveSampler brings equal solutions or, for the optimal number partitions, a 1% improvement. For the more significant test cases, hybrid quantum annealing shows a relative error of less than 0.02% compared to the classical benchmark and for IEEE 118-bus test case shows time performance speed-up. The increment in performance would enable real-time planning and operations of electrical grids in real-time. This work intends to be the first step to showcase the potentials of quantum computing towards the modernization and adaption of electrical grids to the decentralized future of energy systems.

Ramin Ayanzadeh, et al.

We present multi-qubit correction (MQC) as a novel postprocessing method for quantum annealers that views the evolution in an open-system as a Gibbs sampler and reduces a set of excited states to a new synthetic state with lower energy value. After sampling from the ground state of a given (Ising) Hamiltonian, MQC compares pairs of excited states to recognize virtual tunnels—i.e., a group of qubits that changing their states simultaneously can result in a new state with lower energy value—and successively converges to the ground state. Experimental results using D-Wave 2000Q quantum annealers demonstrate that MQC finds samples with notably lower energy values and improves the reproducibility of results when compared to recent hardware/software advances in the realm of quantum annealing, such as spin-reversal transforms, classical postprocessing techniques, and increased inter-sample delay between successive measurements.

Sarmed A Rahman, Randy Lewis, Emanuele Mendicelli, and Sarah Powell, SU(2) lattice gauge theory on a quantum annealer, Physical Review D 104, 034501

Lattice gauge theory is an essential tool for strongly interacting non-Abelian fields, such as those in quantum chromodynamics where lattice results have been of central importance for several decades. Recent studies suggest that quantum computers could extend the reach of lattice gauge theory in dramatic ways, but the usefulness of quantum annealing hardware for lattice gauge theory has not yet been explored. In this work, we implement SU(2) pure gauge theory on a quantum annealer for lattices comprising a few plaquettes in a row with a periodic boundary condition. These plaquettes are in two spatial dimensions and calculations use the Hamiltonian formulation where time is not discretized. Numerical results are obtained from calculations on D-Wave Advantage hardware for eigenvalues, eigenvectors, vacuum expectation values, and time evolution. The success of this initial exploration indicates that the quantum annealer might become a useful hardware platform for some aspects of lattice gauge theories.

Alexander Teplukhin, et al.

The possibility of using quantum computers for electronic structure calculations has opened up a promising avenue for computational chemistry. Towards this direction, numerous algorithmic advances have been made in the last five years. The potential of quantum annealers, which are the prototypes of adiabatic quantum computers, is yet to be fully explored. In this work, we demonstrate the use of a D-Wave quantum annealer for the calculation of excited electronic states of molecular systems. These simulations play an important role in a number of areas, such as photovoltaics, semiconductor technology and nanoscience. The excited states are treated using two methods, time-dependent Hartree-Fock (TDHF) and time-dependent density-functional theory (TDDFT), both within a commonly used Tamm-Dancoff approximation (TDA). The resulting TDA eigenvalue equations are solved on a D-Wave quantum annealer using the Quantum Annealer Eigensolver (QAE), developed previously. The method is shown to reproduce a typical basis set convergence on the example H2 molecule and is also applied to several other molecular species.

Addressing the world’s climate emergency is an uphill battle, requiring a multifaceted approach including optimal deployment of green-energy alternatives. Such undertakings often involve computationally-expensive optimization of black-box models in continuous parameter space. We observe good performance on the DW-2000Q QPU - even using default settings - and higher sensitivity of performance to a number of samples and annealing time for the Advantage QPU. These results are promising and potentially justify further investment in hardware, software, and optimization research, in particular, in the area of solvers for dense QUBOs.

Elizabeth Crosson¹, Tameem Albash^1,2, Itay Hen^3,4, and A. P. Young⁵

Quantum 4, 334 (2020) https://doi.org/10.22331/q-2020-09-24-334

Quantum fluctuations driven by non-stoquastic Hamiltonians have been conjectured to be an important and perhaps essential missing ingredient for achieving a quantum advantage with adiabatic optimization. We introduce a transformation that maps every non-stoquastic adiabatic path ending in a classical Hamiltonian to a corresponding stoquastic adiabatic path by appropriately adjusting the phase of each matrix entry in the computational basis. We compare the spectral gaps of these adiabatic paths and find both theoretically and numerically that the paths based on non-stoquastic Hamiltonians have generically smaller spectral gaps between the ground and first excited states, suggesting they are less useful than stoquastic Hamiltonians for quantum adiabatic optimization. These results apply to any adiabatic algorithm which interpolates to a final Hamiltonian that is diagonal in the computational basis.

¹Center for Quantum Information and Control (CQuIC), Department of Physics and Astronomy , University of New Mexico, Albuquerque, NM 87131, USA
²Electrical and Computer Engineering, University of New Mexico, Albuquerque, NM 87131, USA
³Information Sciences Institute, University of Southern California, Marina del Rey, California 90292, USA
⁴Department of Physics and Astronomy and Center for Quantum Information Science & Technology, University of Southern California, Los Angeles, California 90089, USA
⁵Department of Physics, University of California, Santa Cruz, California 95064, USA

Nicholas Chancellor, et al.

A finite length ferromagnetic chain with opposite spin polarisation imposed at its two ends is one of the simplest frustrated spin models. In the clean classical limit, the domain wall inserted on account of the boundary conditions resides with equal probability on any one of the bonds, and the degeneracy is precisely equal to the number of bonds. If quantum mechanics is introduced via a transverse field, the domain wall will behave as a particle in a box, and prefer to be nearer the middle of the chain rather than the ends. A simple characteristic of a real quantum annealer is therefore which of these limits obtains in practice. Here we have used the ferromagnetic chain with antiparallel boundary spins to test a real flux qubit quantum annealer and discover that contrary to both expectations, the domain walls found are non-uniformly distributed on account of effective random longitudinal fields present notwithstanding tuning carried out to zero out such fields when the couplings between qubits are nominally zero. We present a simple derivation of the form of the distribution function for the domain walls and show also how the effect we have discovered can be used to determine the strength of the effective random fields (noise) characterizing the annealer. The noise measured in this fashion is smaller than what is seen during the single-qubit tuning process, but nonetheless qualitatively affects the outcome of the simulation performed by the annealer.

Richard H. Warren, et al.

This paper describes the logic and creativity needed in order to have a 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.

Florian Neukart, et al.

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.

Richard Y. Li, et al.

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. Despite technological limitations, we find a slight advantage in classification performance and nearly equal ranking performance using the quantum annealer for these fairly small training data sets. Thus, we propose that quantum annealing might be an effective method to implement machine learning for certain computational biology problems.

Maxwell Henderson, et al.

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.

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.

Florian Neukart, et al. 

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.

Salvatore Mandrà, et al.

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 overall known classical heuristics, a noticeable improvement in the scaling remains elusive. These results represent the first steps towards detection of potential quantum speedup, albeit without a scaling improvement and for synthetic benchmark problems.

Alex Mott, et al.

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 the background are trained using highly unerring but not completely perfect simulations of the physical processes involved, often resulting in incorrect labeling 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.

Hayato Ushijima-Mwesigwa, et al.

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.

Daniel O’Malley, et al.

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.

Thomas E. Potok, et al.

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 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 low-power hardware implementation. We use the MNIST dataset for our experiment, due to the 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.

Eleanor Hutterer

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, et al.

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.

Tameem Albash, et al.

Recently the question of whether the D-Wave processors exhibit large-scale quantum behavior or can be described by a classical model has attracted significant interest. In this work, we address this question by studying a 503 qubit D-Wave Two device in the "black box" model, i.e., by studying its input-output behavior. Our work generalizes an approach introduced in Boixo et al. [Nat. Commun. 4, 2067 (2013)], and uses groups of up to 20 qubits to realize a transverse Ising model evolution with a ground-state degeneracy whose distribution acts as a sensitive probe that distinguishes classical and quantum models for the D-Wave device. Our findings rule out all classical models proposed to date for the device and provide evidence that an open system quantum dynamical description of the device that starts from a quantized energy level structure is well justified, even in the presence of relevant thermal excitations and a small value of the ratio of the single-qubit decoherence time to the annealing time.

Helmut G. Katzgraber, et al.

Recently, a programmable quantum annealing machine has been built that minimizes the cost function of hard optimization problems by, in principle, adiabatically quenching quantum fluctuations. Tests performed by different research teams have shown that, indeed, the machine seems to exploit quantum effects. However, experiments on a class of random-bond instances have not yet demonstrated an advantage over classical optimization algorithms on traditional computer hardware. Here we present evidence as to why this might be the case. These engineered quantum annealing machines effectively operate coupled to a decohering thermal bath. Therefore, we study the finite-temperature critical behavior of the standard benchmark problem used to assess the computational capabilities of these complex machines. We simulate both random-bond Ising models and spin glasses with bimodal and Gaussian disorder on the D-Wave Chimera topology. Our results show that while the worst-case complexity of finding a ground state of an Ising spin glass on the Chimera graph is not polynomial, the finite-temperature phase space is likely rather simple because spin glasses on Chimera have only a zero-temperature transition. This means that benchmarking optimization methods using spin glasses on the Chimera graph might not be the best benchmark problems to test quantum speedup. We propose alternative benchmarks by embedding potentially harder problems on the Chimera topology. Finally, we also study the (reentrant) disorder-temperature phase diagram of the random-bond Ising model on the Chimera graph and show that a finite-temperature ferromagnetic phase is stable up to 19.85(15)% antiferromagnetic bonds. Beyond this threshold, the system only displays a zero-temperature spin-glass phase. Our results, therefore, show that a careful design of the hardware architecture and benchmark problems is key when building quantum annealing machines.

Z. Bian, et al.

Ramsey theory is a highly active research area in mathematics that studies the emergence of order in large disordered structures. Ramsey numbers mark the threshold at which order first appears and are extremely difficult to calculate due to their explosive rate of growth. Recently, an algorithm that can be implemented using adiabatic quantum evolution has been proposed that calculates the two-color Ramsey numbers R(m,n). Here we present results of an experimental implementation of this algorithm and show that it correctly determines the Ramsey numbers R(3,3) and R(m,2) for 4≤m≤8. The R(8,2) computation used 84 qubits of which 28 were computational qubits. This computation is the largest experimental implementation of a scientifically meaningful adiabatic evolution algorithm that has been done to date.

K.L. Pudenz, et al.

Quantum information processing offers dramatic speedups, yet is famously susceptible to decoherence, the process whereby quantum superpositions decay into mutually exclusive classical alternatives, thus robbing quantum computers of their power. This has made the development of quantum error correction an essential and inescapable aspect of both theoretical and experimental quantum computing. So far little is known about protection against decoherence in the context of quantum annealing, a computational paradigm that aims to exploit ground state quantum dynamics to solve optimization problems more rapidly than is possible classically. Here we develop error correction for quantum annealing and provide an experimental demonstration using up to 344 superconducting flux qubits in processors which have recently been shown to physically implement programmable quantum annealing. We demonstrate a substantial improvement over the performance of the processors in the absence of error correction. These results pave a path toward large-scale noise-protected adiabatic quantum optimization devices.

S. Santra, et al.

We experimentally study the performance of a programmable quantum annealing processor, the D-Wave One (DW1) with up to 108 qubits, on maximum satisfiability problem with 2 variables per clause (MAX 2-SAT) problems. We consider ensembles of random problems characterized by a fixed clause density, an order parameter that we tune through its critical value in our experiments. We demonstrate that the DW1 is sensitive to the critical value of the clause density. The DW1 results are verified and compared with akmaxsat, an exact, state-of-the-art algorithm. We study the relative performance of the two solvers and how they correlate in terms of problem hardness. We find that the DW1 performance scales more favorably with problem size and that problem hardness correlation is essentially non-existent. We discuss the relevance and limitations of such a comparison.

W. Vinci, et al.

Two objects can be distinguished if they have different measurable properties. Thus, distinguishability depends on the Physics of the objects. In considering graphs, we revisit the Ising model as a framework to define physically meaningful spectral invariants. In this context, we introduce a family of refinements of the classical spectrum and consider the quantum partition function. We demonstrate that the energy spectrum of the quantum Ising Hamiltonian is a stronger invariant than the classical one without refinements. For the purpose of implementing the related physical systems, we perform experiments on a programmable annealer with superconducting flux technology. Departing from the paradigm of adiabatic computation, we take advantage of a noisy evolution of the device to generate statistics of low energy states. The graphs considered in the experiments have the same classical partition functions, but different quantum spectra. The data obtained from the annealer distinguish non-isomorphic graphs via information contained in the classical refinements of the functions but not via the differences in the quantum spectra.

S. Boxio, et al. 

Quantum annealing is a general strategy for solving difficult optimization problems with the aid of quantum adiabatic evolution. Both analytical and numerical evidence suggests that under idealized, closed system conditions, quantum annealing can outperform classical thermalization-based algorithms such as simulated annealing. Current engineered quantum annealing devices have a decoherence timescale which is orders of magnitude shorter than the adiabatic evolution time. Do they effectively perform classical thermalization when coupled to a decohering thermal environment? Here we present an experimental signature that is consistent with quantum annealing, and at the same time inconsistent with classical thermalization. Our experiment uses groups of eight superconducting flux qubits with programmable spin-spin couplings, embedded on a commercially available chip with >100 functional qubits. This suggests that programmable quantum devices, scalable with current superconducting technology, implement quantum annealing with surprising robustness against noise and imperfections.

Sergio Boixo, et al.

Quantum technology is maturing to the point where quantum devices, such as quantum communication systems, quantum random number generators, and quantum simulators, may be built with capabilities exceeding classical computers. A quantum annealer, in particular, solves hard optimization problems by evolving a known initial configuration at non-zero temperature towards the ground state of a Hamiltonian encoding a given problem. Here, we present results from experiments on a 108 qubit D-Wave One device based on superconducting flux qubits. The strong correlations between the device and a simulated quantum annealer, in contrast with weak correlations between the device and classical annealing or classical spin dynamics, demonstrate that the device performs quantum annealing. We find additional evidence for quantum annealing in the form of small-gap avoided level crossings characterizing the hard problems. To assess the computational power of the device we compare it to optimized classical algorithms.

Italy Hen

We outline an algorithm for the Quantum Counting problem using Adiabatic Quantum Computation (AQC). We show that using local adiabatic evolution, a process in which the adiabatic procedure is performed at a variable rate, the problem is solved with the same complexity as the analogous circuit-based algorithm, i.e., quadratically faster than the corresponding classical algorithm. The above algorithm provides further evidence for the potentially powerful capabilities of AQC as a paradigm for more efficient problem solving on a quantum computer and may be used as the basis for solving more sophisticated

Ryan Babbush, et al.

Optimization problems associated with the interaction of linked particles are at the heart of polymer science, protein folding, and other important problems in the physical sciences. In this review, we explain how to recast these problems as constraint satisfaction problems such as linear programming, maximum satisfiability, and pseudo-boolean optimization. By encoding problems this way, one can leverage substantial insight and powerful solvers from the computer science community which studies constraint programming for diverse applications such as logistics, scheduling, artificial intelligence, and circuit design. We demonstrate how to constrain and embed lattice heteropolymer problems using several strategies. Each strikes a unique balance between a number of constraints, the complexity of constraints, and a number of variables. Finally, we show how to reduce the locality of couplings in these energy functions so they can be realized as Hamiltonians on existing quantum annealing machines. We intend that this review be used as a case study for encoding related combinatorial optimization problems in a form suitable for adiabatic quantum optimization.

We propose a novel method using a quantum annealer -- an analog quantum computer based on the principles of quantum adiabatic evolution -- to solve the Graph Isomorphism problem, in which one has to determine whether two graphs are isomorphic (i.e., can be transformed into each other simply by a relabeling of the vertices). We demonstrate the capabilities of the method by analyzing several types of graph families, focusing on graphs with particularly high symmetry called strongly regular graphs (SRG's). We also show that our method is applicable, within certain limitations, to currently available quantum hardware such as "D-Wave One".

V.N. Smelyanskiy, et al.

In this article, we show how to map a sampling of the hardest artificial intelligence problems in space exploration onto equivalent Ising models that then can be attacked using quantum annealing implemented in the D-Wave machine. We overview the existing results as well as propose new Ising model implementations for quantum annealing. We review supervised and unsupervised learning algorithms for classification and clustering with applications to feature identification and anomaly detection. We introduce algorithms for data fusion and image matching for remote sensing applications. We overview planning problems for space exploration mission applications and algorithms for diagnostics and recovery with applications to deep space missions. We describe combinatorial optimization algorithms for task assignment in the context of autonomous unmanned exploration. Finally, we discuss the ways to circumvent the limitation of the Ising mapping using a "black box" approach based on ideas from probabilistic computing. In this article, we describe the architecture of the D-Wave One machine and report its benchmarks. Results on a random ensemble of problems in the range of up to 96 qubits show improved scaling for median core quantum annealing time compared with classical algorithms; whether this scaling persists for larger problem sizes is an open question. We also review previous results of D-Wave One benchmarking studies for solving binary classification problems with a quantum boosting algorithm which is shown to outperform AdaBoost. We review quantum algorithms for structured learning for multi-label classification and introduce a hybrid classical/quantum approach for learning the weights. Results of D-Wave One benchmarking studies for learning structured labels on four different data sets show better performance compared with an independent Support Vector Machine approach with linear kernel.

D. Nagaj, et al.

We study the glued-trees problem of Childs et. al. in the adiabatic model of quantum computing and provide an annealing schedule to solve an oracular problem exponentially faster than classically possible. The Hamiltonians involved in quantum annealing do not suffer from the so-called sign problem. Unlike the typical scenario, our schedule is efficient even though the minimum energy gap of the Hamiltonians is exponentially small in the problem size. We discuss generalizations based on initial-state randomization to avoid some slowdowns in adiabatic quantum computing due to small gaps.

H. Neven, et al.

In a previous publication, we proposed discrete global optimization as a method to train a strong binary classifier constructed as a thresholded sum over weak classifiers. Our motivation was to cast the training of a classifier into a format amenable to solution by the quantum adiabatic algorithm. Applying adiabatic quantum computing (AQC) promises to yield solutions that are superior to those which can be achieved with classical heuristic solvers. Interestingly we found that by using heuristic solvers to obtain approximate solutions we could already gain an advantage over the standard method AdaBoost. In this communication, we generalize the baseline method to large-scale classifier training. By large scale, we mean that either the cardinality of the dictionary of candidate weak classifiers or the number of weak learners used in the strong classifier exceeds the number of variables that can be handled effectively in a single global optimization. For such situations, we propose an iterative and piecewise approach in which a subset of weak classifiers is selected in each iteration via global optimization. The strong classifier is then constructed by concatenating the subsets of weak classifiers. We show in numerical studies that the generalized method again successfully competes with AdaBoost. We also provide theoretical arguments as to why the proposed optimization method, which does not only minimize the empirical loss but also adds L0-norm regularization, is superior to versions of boosting that only minimize the empirical loss. By conducting a Quantum Monte Carlo simulation we gather evidence that the quantum adiabatic algorithm is able to handle a generic training problem efficiently.

H. Neven, et al.

This paper describes how to make the problem of binary classification amenable to quantum computing. A formulation is employed in which the binary classifier is constructed as a thresholded linear superposition of a set of weak classifiers. The weights in the superposition are optimized in a learning process that strives to minimize the training error as well as the number of weak classifiers used. No efficient solution to this problem is known. To bring it into a format that allows the application of adiabatic quantum computing (AQC), we first show that the bit-precision with which the weights need to be represented only grows logarithmically with the ratio of the number of training examples to the number of weak classifiers. This allows to effectively formulate the training process as a binary optimization problem. Solving it with heuristic solvers such as tabu search, we find that the resulting classifier outperforms a widely used state-of-the-art method, AdaBoost, on a variety of benchmark problems. Moreover, we discovered the interesting fact that bit-constrained learning machines often exhibit lower generalization error rates. Changing the loss function that measures the training error from 0-1 loss to least squares maps the training to quadratic unconstrained binary optimization. This corresponds to the format required by D-Wave's implementation of AQC. Simulations with heuristic solvers again yield results better than those obtained with boosting approaches. Since the resulting quadratic binary program is NP-hard, additional gains can be expected from applying the actual quantum processor.

Many artificial intelligence (AI) problems naturally map to NP-hard optimization problems. This has the interesting consequence that enabling human-level capability in machines often requires systems that can handle formally intractable problems. This issue can sometimes (but possibly not always) be resolved by building special-purpose heuristic algorithms, tailored to the problem in question. Because of the continued difficulties in automating certain tasks that are natural for humans, there remains a strong motivation for AI researchers to investigate and apply new algorithms and techniques to hard AI problems. Recently a novel class of relevant algorithms that require quantum mechanical hardware has been proposed. These algorithms, referred to as quantum adiabatic algorithms, represent a new approach to designing both complete and heuristic solvers for NP-hard optimization problems. In this work, we describe how to formulate image recognition, which is a canonical NP-hard AI problem, as a Quadratic Unconstrained Binary Optimization (QUBO) problem. The QUBO format corresponds to the input format required for D-Wave superconducting adiabatic quantum computing (AQC) processors.