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.