Zhang, H., Boothby, K. & Kamenev, A. Cyclic quantum annealing: searching for deep low-energy states in 5000-qubit spin glass. Sci Rep 14, 30784 (2024). https://doi.org/10.1038/s41598-024-80761-z

Quantum computers promise a qualitative speedup in solving a broad spectrum of practical optimization problems. The latter can be mapped onto the task of finding low-energy states of spin glasses, which is known to be exceedingly difficult. Using D-Wave’s 5000-qubit quantum processor, we demonstrate that a recently proposed iterative cyclic quantum annealing algorithm can find deep low-energy states in record time. We also find intricate structures in a low-energy landscape of spin glasses, such as a power-law distribution of connected clusters with a small surface energy. These observations offer guidance for further improvement of the optimization algorithms.

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

Catherine McGeoch, D-Wave; David Esteban Bernal Neira, Purdue University; Susan Mniszewski, Los Alamos National Laboratory; Nicholas Chancellor, Durham University 

The past decade has seen four generations of quantum annealing processors, with qubit counts increasing from 512 on the D-Wave Two (released in 2013), to over 5000 on Advantage processors available in 2023. During this time, expanding access for researchers has sparked enormous growth in publications and in the body of knowledge surrounding capabilities, applications, and best practices in use of these novel computing systems.

This Research Topic will invite submissions on all aspects of empirical experience with annealing-based quantum computers. The intention is to present a broad survey of the current state of knowledge about quantum annealing hardware, performance, software infrastructures, and application

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.

Andrew D. King, et al.

Quantum computers hold the promise of solving certain problems that lie beyond the reach of conventional computers. Establishing this capability, especially for impactful and meaningful problems, remains a central challenge. One such problem is the simulation of nonequilibrium dynamics of a magnetic spin system quenched through a quantum phase transition. State-of-the-art classical simulations demand resources that grow exponentially with system size. Here we show that superconducting quantum annealing processors can rapidly generate samples in close agreement with solutions of the Schrödinger equation. We demonstrate area-law scaling of entanglement in the model quench in two-, three- and infinite-dimensional spin glasses, supporting the observed stretched-exponential scaling of effort for classical approaches. We assess approximate methods based on tensor networks and neural networks and conclude that no known approach can achieve the same accuracy as the quantum annealer within a reasonable timeframe. Thus quantum annealers can answer questions of practical importance that classical computers cannot.

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.

Alejandro Lopez-Bezanilla, Andrew D. King, Cristiano Nisoli, and Avadh Saxena 

Nature Communications volume 15, Article number: 589 (2024) 

Fluctuations may induce the degradation of order by overcoming ordering interactions, consequently leading to an increase of entropy. This is particularly evident in magnetic systems characterized by nontrivial, constrained disorder, where thermal or quantum fluctuations can yield counterintuitive forms of ordering. Using the proven efficiency of quantum annealers as programmable spin system simulators, we present a study based on entropy postulates and experiments on a platform of programmable superconducting qubits to show that a low level of uncertainty can promote ordering in a system impacted by both thermal and quantum fluctuations. A set of experiments is proposed on a lattice of interacting qubits arranged in a triangular geometry with precisely controlled disorder, effective temperature, and quantum fluctuations. Our results demonstrate the creation of ordered ferrimagnetic and layered anisotropic disordered phases, displaying characteristics akin to the elegant order-by-disorder phenomenon. Extensive experimental evidence is provided for the role of quantum fluctuations in lowering the total energy of the system by increasing entropy and defect clustering. Our thorough and comprehensive application of an intentionally introduced noise on a quantum platform provides insight into the dynamics of defects and fluctuations in quantum devices, which may help to reduce the cost associated with quantum processing.

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.

Lopez-Bezanilla, A., Raymond, J., Boothby, K. et al. Kagome qubit ice. Nat Commun 14, 1105 (2023). https://doi.org/10.1038/s41467-023-36760-1

Topological phases of spin liquids with constrained disorder can host a kinetics of fractionalized excitations. However, spin-liquid phases with distinct kinetic regimes have proven difficult to observe experimentally. Here we present a realization of kagome spin ice in the superconducting qubits of a quantum annealer, and use it to demonstrate a field-induced kinetic crossover between spin-liquid phases. Employing fine control over local magnetic fields, we show evidence of both the Ice-I phase and an unconventional field-induced Ice-II phase. In the latter, a charge-ordered yet spin-disordered topological phase, the kinetics proceeds via pair creation and annihilation of strongly correlated, charge conserving, fractionalized excitations. As these kinetic regimes have resisted characterization in other artificial spin ice realizations, our results demonstrate the utility of quantum-driven kinetics in advancing the study of topological phases of spin liquids.

Mohammad H. Amin, et al.

Quantum Error Mitigation (QEM) presents a promising near-term approach to reduce error when estimating expectation values in quantum computing. Here, we introduce QEM techniques tailored for quantum annealing, using Zero-Noise Extrapolation (ZNE). We implement ZNE through zero-temperature extrapolation as well as energy-time rescaling. We conduct experimental investigations into the quantum critical dynamics of a transverse-field Ising spin chain, demonstrating the successful mitigation of thermal noise through both of these techniques. Moreover, we show that energy-time rescaling effectively mitigates control errors in the coherent regime where the effect of thermal noise is minimal. Our ZNE results agree with exact calculations of the coherent evolution over a range of annealing times that exceeds the coherent annealing range by almost an order of magnitude.

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

Kevin Chern, Kelly Boothby, Jack Raymond, Pau Farré, Andrew D. King

Front. Comput. Sci., 15 September 2023
Sec. Theoretical Computer Science
Volume 5 - 2023 | https://doi.org/10.3389/fcomp.2023.1238988

Quantum annealing has emerged as a powerful platform for simulating and optimizing classical and quantum Ising models. Quantum annealers, like other quantum and/or analog computing devices, are susceptible to non-idealities including crosstalk, device variation, and environmental noise. Compensating for these effects through calibration refinement or “shimming” can significantly improve performance but often relies on ad-hoc methods that exploit symmetries in both the problem being solved and the quantum annealer itself. In this tutorial, we attempt to demystify these methods. We introduce methods for finding exploitable symmetries in Ising models and discuss how to use these symmetries to suppress unwanted bias. We work through several examples of increasing complexity and provide complete Python code. We include automated methods for two important tasks: finding copies of small subgraphs in the qubit connectivity graph and automatically finding symmetries of an Ising model via generalized graph automorphism. We conclude the tutorial by surveying additional methods, providing practical implementation tips, and discussing limitations and remedies of the calibration procedure. Code is available at: https://github.com/dwavesystems/shimming-tutorial.

Catherine C. McGeoch, Pau Farre.

We introduce quantum utility, a new approach to evaluating quantum performance that aims to capture the user experience by including overhead costs associated with the quantum computation. A demonstration of quantum utility by a quantum processing unit (QPU) shows that the QPU can outperform classical solvers at some tasks of interest to practitioners, when considering computational overheads. We consider overhead costs that arise in standalone use of the QPU (as opposed to a hybrid computation context). We define three early milestones on the path to broad-scale quantum utility that focus on restricted subsets of overheads: Milestone 0 considers pure anneal time (no overheads) and has been demonstrated in previous work; Milestone 1 includes overhead times to access the QPU (that is, programming and readout); and Milestone 2 incorporates an indirect cost associated with minor embedding.

We evaluate the performance of a D-Wave Advantage QPU with respect to Milestones 1 and 2, using a testbed of 13 input classes and seven classical solvers implemented on CPUs and GPUs. For Milestone 1, the QPU outperformed all classical solvers in 99% of our tests. For Milestone 2, the QPU outperformed all classical solvers in 19% of our tests, and the scenarios in which the QPU found success correspond to cases where classical solvers most frequently failed.
Analysis of test results on specific inputs reveals fundamentally distinct underlying mechanisms that explain the observed differences in quantum and classical performance profiles. We present evidence-based arguments that these distinctions bode well for future annealing quantum processors to support demonstrations of quantum utility on ever-expanding classes of inputs and for more challenging milestones.

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.

King, A.D., Raymond, J., Lanting, T. et al. Quantum critical dynamics in a 5,000-qubit programmable spin glass. Nature 617, 61–66 (2023). https://doi.org/10.1038/s41586-023-05867-2

Experiments on disordered alloys suggest that spin glasses can be brought into low-energy states faster by annealing quantum fluctuations than by conventional thermal annealing. Owing to the importance of spin glasses as a paradigmatic computational testbed, reproducing this phenomenon in a programmable system has remained a central challenge in quantum optimization4–13. Here we achieve this goal by realizing quantum-critical spin-glass dynamics on thousands of qubits with a superconducting quantum annealer. We first demonstrate quantitative agreement between quantum annealing and timeevolution of the Schrödinger equation in small spin glasses. We then measure dynamics in three-dimensional spin glasses on thousands of qubits, for which classical simulation of many-body quantum dynamics is intractable. We extract critical exponents that clearly distinguish quantum annealing from the slower stochastic dynamics of analogous Monte Carlo algorithms, providing both theoretical and experimental support for large-scale quantum simulation and a scaling advantage in energy optimization.

Jack Raymond et al. (2023). Hybrid Quantum Annealing for Larger-than-QPU Lattice-structured Problems. ACM Transactions on Quantum Computing 4, 3, Article 17

Quantum processing units (QPUs) executing annealing algorithms have shown promise in optimization and simulation applications. Hybrid algorithms are a natural bridge to larger applications. We present a simple greedy method for solving larger-than-QPU lattice-structured Ising optimization problems. The method, implemented in the open source D-Wave Hybrid framework, uses a QPU coprocessor operating with generic parameters. Performance is evaluated for standard spin-glass problems on two lattice types with up to 11,616 spin variables, double the size that is directly programmable on any available QPU. The proposed method is shown to converge to low-energy solutions faster than an open source simulated annealing method that is either directly employed or substituted as a coprocessor in the hybrid method. Using newer Advantage QPUs in place of D-Wave 2000Q QPUs is shown to enhance convergence of the hybrid method to low energies and to achieve a lower final energy.

Alexander M. Whiticar, et al.

We report on measurements of flux and charge noise in an rf-SQUID (superconducting quantum interference device) flux qubit using macroscopic resonant tunneling (MRT). We measure rates of incoherent tunneling from the lowest energy state in the initial well to the ground and first excited states in the target well. The result of the measurement consists of two peaks. The first peak corresponds to tunneling to the ground state of the target well, and is dominated by flux noise. The second peak is due to tunneling to the excited state and is wider due to an intrawell relaxation process dominated by charge noise. We develop a theoretical model that allows us to extract information about flux and charge noise within one experimental setup. The model agrees very well with experimental data over a wide dynamic range and provides parameters that characterize charge and flux noise.

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]

Anatoly Y. Smirnov, et al.

Macroscopic resonant tunneling (MRT) in flux qubits is an important experimental tool for extracting information about noise produced by a qubit's surroundings. Here we present a detailed derivation of the MRT signal in the RF-SQUID flux qubit allowing for effects of flux and charge fluctuations on the interwell and intrawell transitions in the system. Taking into consideration transitions between the ground state in the initial well and excited states in the target well enable us to characterize both flux and charge noise source affecting the operation of the flux qubit. The MRT peak is formed by the dominant noise source affecting specific transition, with flux noise determining the lineshape of the ground to ground tunneling, whereas charge noise reveals itself as additional broadening of the ground to excited peak.

King, A.D., Suzuki, S., Raymond, J. et al. Coherent quantum annealing in a programmable 2,000 qubit Ising chain. Nat. Phys. (2022)

Quantum simulation has emerged as a valuable arena for demonstrating and understanding the capabilities of near-term quantum computers. Quantum annealing has been successfully used in simulating a range of open quantum systems, both at equilibrium and out of equilibrium. However, in all previous experiments, annealing has been too slow to coherently simulate a closed quantum system, due to the onset of thermal effects from the environment. Here we demonstrate coherent evolution through a quantum phase transition in the paradigmatic setting of a one-dimensional transverse-field Ising chain, using up to 2,000 superconducting flux qubits in a programmable quantum annealer. In large systems, we observe the quantum Kibble–Zurek mechanism with theoretically predicted kink statistics, as well as characteristic positive kink–kink correlations, independent of temperature. In small chains, excitation statistics validate the picture of a Landau–Zener transition at a minimum gap. In both cases, the results are in quantitative agreement with analytical solutions to the closed-system quantum model. For slower anneals, we observe anti-Kibble–Zurek scaling in a crossover to the open quantum regime. The coherent dynamics of large-scale quantum annealers demonstrated here can be exploited to perform approximate quantum optimization, machine learning and simulation tasks.

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.

T. Morstyn, "Annealing-based Quantum Computing for Combinatorial Optimal Power Flow," in IEEE Transactions on Smart Grid, 2022,

This paper proposes the use of annealing-based quantum computing for solving combinatorial optimal power flow problems. Quantum annealers provide a physical computing platform which utilises quantum phase transitions to solve specific classes of combinatorial problems. These devices have seen rapid increases in scale and performance, and are now approaching the point where they could be valuable for industrial applications. This paper shows how an optimal power flow problem incorporating linear multiphase network modelling, discrete sources of energy flexibility, renewable generation placement/sizing and network upgrade decisions can be formulated as a quadratic unconstrained binary optimisation problem, which can be solved by quantum annealing. Case studies with these components integrated with the IEEE European Low Voltage Test Feeder are implemented using D-Wave Systems’ 5,760 qubit Advantage quantum processing unit and hybrid quantum-classical solver.

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. 

Jack Raymond, et al.

Quantum processing units (QPUs) executing annealing algorithms have shown promise in optimization and simulation applications. Hybrid algorithms are a natural bridge to additional applications of larger scale. We present a straightforward and effective method for solving larger-than-QPU lattice-structured Ising optimization problems. Performance is compared against simulated annealing with promising results, and improvement is shown as a function of the generation of D-Wave QPU used.

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.

Matthew R.C. Fitzpatrick, et al.

We present an essentially exact numerical method for modeling flux qubit chains subject to charge and flux noise. We define an essentially exact method as one that introduces errors that are completely controlled such that they can be made arbitrarily small by tuning the simulation parameters. The method adopts the quasi-adiabatic path integral formalism to express the system's reduced density matrix as a time-discretized path integral, comprising a series of influence functionals that encode the non-Markovian dynamics of the system. We present a detailed derivation of the path integral expression for the system's reduced density matrix and describe in detail the tensor network algorithm used to evaluate the path integral expression. We have implemented our method in an open-sourced Python library called "spinbosonchain". When appropriate, we draw connections between concepts covered in this manuscript and the library's code.

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.

Kelly Boothby, et al.

Early generations of superconducting quantum annealing processors have provided a valuable platform for studying the performance of a scalable quantum computing technology. These studies have directly informed our approach to the design of the next-generation processor. Our design priorities for this generation include an increase in per-qubit connectivity, a problem Hamiltonian energy scale similar to previous generations, reduced Hamiltonian specification errors, and an increase in the processor scale that also leaves programming and readout times fixed or reduced. Here we discuss the specific innovations that resulted in a processor architecture that satisfies these design priorities.

Andrew D. King, et al.

Artificial spin ices are frustrated spin systems that can be engineered, in which fine-tuning of geometry and topology has allowed the design and characterization of exotic emergent phenomena at the constituent level. Here, we report a realization of spin ice in a lattice of superconducting qubits. Unlike conventional artificial spin ice, our system is disordered by both quantum and thermal fluctuations. The ground state is classically described by the ice rule, and we achieved control over a fragile degeneracy point, leading to a Coulomb phase. The ability to pin individual spins allows us to demonstrate Gauss’s law for emergent effective monopoles in two dimensions. The demonstrated qubit control lays the groundwork for potential future study of topologically protected artificial quantum spin liquids.

Eleni Marina Lykiardopoulou, et al.

Nonstoquastic Hamiltonians are hard to simulate due to the sign problem in quantum Monte Carlo simulation. It is, however, unclear whether nonstoquasticity can lead to an advantage in quantum annealing. Here we show that YY interactions between the qubits make the adiabatic path during quantum annealing, and therefore the performance, dependent on spin-reversal transformations. With the right choice of spin-reversal transformation, a nonstoquastic Hamiltonian with YY interaction can outperform stoquastic Hamiltonians with similar parameters. We introduce an optimization protocol to determine the optimal transformation and discuss the effect of suboptimality.

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.

Andrew D. King, et al.

The promise of quantum computing lies in harnessing programmable quantum devices for practical applications such as efficient simulation of quantum materials and condensed matter systems. One important task is the simulation of geometrically frustrated magnets in which topological phenomena can emerge from competition between quantum and thermal fluctuations. Here we report on experimental observations of equilibration in such simulations, measured on up to 1440 qubits with microsecond resolution. By initializing the system in a state with topological obstruction, we observe quantum annealing (QA) equilibration timescales in excess of one microsecond. Measurements indicate a dynamical advantage in the quantum simulation compared with spatially local update dynamics of path-integral Monte Carlo (PIMC). The advantage increases with both system size and inverse temperature, exceeding a million-fold speedup over an efficient CPU implementation. PIMC is a leading classical method for such simulations, and a scaling advantage of this type was recently shown to be impossible in certain restricted settings. This is therefore an important piece of experimental evidence that PIMC does not simulate QA dynamics even for sign-problem-free Hamiltonians, and that near-term quantum devices can be used to accelerate computational tasks of practical relevance.

Andrew D. King, et al.

Geometrically frustrated spin-chain compounds such as Ca3Co2O6 exhibit extremely slow relaxation under a changing magnetic field. Consequently, both low-temperature laboratory experiments and Monte Carlo simulations have shown peculiar out-of-equilibrium magnetization curves, which arise from trapping in metastable configurations. In this work we simulate this phenomenon in a superconducting quantum annealing processor, allowing us to probe the impact of quantum fluctuations on both equilibrium and dynamics of the system. Increasing the quantum fluctuations with a transverse field reduces the impact of metastable traps in out-of-equilibrium samples, and aids the development of three-sublattice ferrimagnetic (up-up-down) long-range order. At equilibrium we identify a finite-temperature shoulder in the 1/3-to-saturated phase transition, promoted by quantum fluctuations but with entropic origin. This work demonstrates the viability of dynamical as well as equilibrium studies of frustrated magnetism using large-scale programmable quantum systems, and is therefore an important step toward programmable simulation of dynamics in materials using quantum hardware.

Paul Kairys, et al.

A core concept in condensed matter physics is geometric frustration that leads to emergent spin phases in magnetic materials. These distinct phases, which depart from the conventional ferromagnet or the antiferromagnet, require unique computational techniques to decipher. In this study, we use the canonical Ising Shastry-Sutherland lattice to demonstrate new techniques for solving frustrated Hamiltonians using a quantum annealer of programmable superconducting qubits. This Hamiltonian can be tuned to produce a variety of intriguing ground states ranging from short- and long-range orders and fractional order parameters. We show that a large-scale finite-field quantum annealing experiment is possible on 468 logical spins of this model embedded into the quantum hardware. We determine microscopic spin configurations using an iterative quantum annealing protocol and develop mean-field boundary conditions to attenuate finite-size effects and defects. We not only recover all phases of the Shastry-Sutherland Ising model—including the well-known fractional magnetization plateau in a longitudinal field—but also predict the spin behavior at the critical points with significant ground-state degeneracy and in the presence of defects. The results lead us to establish the connection to the diffuse neutron scattering experiments by calculation of the static structure factors.

Jack Raymond, et al.

Optimization or sampling of arbitrary pairwise Ising models, in a quantum annealing protocol of constrained interaction topology, can be enabled by a minor-embedding procedure. The logical problem of interest is transformed to a physical (device programmable) problem, where one binary variable is represented by a logical qubit consisting of multiple physical qubits. In this paper we discuss tuning of this transformation for the cases of clique, biclique, and cubic lattice problems on the D-Wave 2000Q quantum computer. We demonstrate parameter tuning protocols in spin glasses and channel communication problems, focusing on anneal duration, chain strength, and mapping from the result on physical qubits back to the logical space. Inhomogeneities in effective coupling strength arising from minor-embedding are shown to be mitigated by an efficient reweighting of programmed couplings, accounting for logical qubit topology.

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.

T. Lanting, et al.

We present measurements of the dynamics of a polarized magnetic environment coupled to the flux degree of freedom of rf-SQUID flux qubits. The qubits are used as both sources of polarizing field and detectors of the environmental polarization. We probe dynamics at timescales from 5 μs to 5 ms and at temperatures between 12.5 and 22 mK. The measured polarization versus temperature provides strong evidence for a phase transition at a temperature of 5.7±0.3 mK. Furthermore, the environmental polarization grows initially as t√, consistent with spin diffusion dynamics. However, spin diffusion model deviates from data at long timescales, suggesting that a different phenomenon is responsible for the low-frequency behavior. A simple 1/f model can fit the data at all time scales but it requires empirical low- and high-frequency cutoffs. We argue that these results are consistent with an environment comprised of random clusters of spins, with fast spin diffusion dynamics within the clusters and slow fluctuations of the total moments of the clusters.

Walter Vinci, et al.

The development of quantum-classical hybrid (QCH) algorithms is critical to achieve state-of-the-art computational models. A QCH variational autoencoder (QVAE) was introduced in Ref. [1] by some of the authors of this paper. QVAE consists of a classical auto-encoding structure realized by traditional deep neural networks to perform inference to, and generation from, a discrete latent space. The latent generative process is formalized as thermal sampling from either a quantum or classical Boltzmann machine (QBM or BM). This setup allows quantum-assisted training of deep generative models by physically simulating the generative process with quantum annealers. In this paper, we have successfully employed D-Wave quantum annealers as Boltzmann samplers to perform quantum-assisted, end-to-end training of QVAE. The hybrid structure of QVAE allows us to deploy current-generation quantum annealers in QCH generative models to achieve competitive performance on datasets such as MNIST. The results presented in this paper suggest that commercially available quantum annealers can be deployed, in conjunction with well-crafted classical deep neutral networks, to achieve competitive results in unsupervised and semisupervised tasks on large-scale datasets. We also provide evidence that our setup is able to exploit large latent-space (Q)BMs, which develop slowly mixing modes. This expressive latent space results in slow and inefficient classical sampling, and paves the way to achieve quantum advantage with quantum annealing in realistic sampling applications.

I. Ozfidan, et al.

Quantum annealing (QA) is a heuristic algorithm for finding low-energy configurations of a system, with applications in optimization, machine learning, and quantum simulation. Up to now, all implementations of QA have been limited to qubits coupled via a single degree of freedom. This gives rise to a stoquastic Hamiltonian that has no sign problem in quantum Monte Carlo (QMC) simulations. In this paper, we report implementation and measurements of two superconducting flux qubits coupled via two canonically conjugate degrees of freedom (charge and flux) to achieve a nonstoquastic Hamiltonian. Such coupling can enhance performance of QA processors, extend the range of quantum simulations. We perform microwave spectroscopy to extract circuit parameters and show that the charge coupling manifests itself as a YY interaction in the computational basis. We observe destructive interference in quantum coherent oscillations between the computational basis states of the two-qubit system. Finally, we show that the extracted Hamiltonian is nonstoquastic over a wide range of parameters.

Zhengbing Bian, et al.

Quantum annealers (QAs) are specialized quantum computers that minimize objective functions over discrete variables by physically exploiting quantum effects. Current QA platforms allow for the optimization of quadratic objectives defined over binary variables (qubits), also known as Ising problems. In the last decade, QA systems as implemented by D-Wave have scaled with Moore-like growth. Current architectures provide 2048 sparsely-connected qubits, and continued exponential growth is anticipated, together with increased connectivity.We explore the feasibility of such architectures for solving SAT and MaxSAT problems as QA systems scale. We develop techniques for effectively encoding SAT –and, with some limitations, MaxSAT– into Ising problems compatible with sparse QA architectures. We provide the theoretical foundations for this mapping, and present encoding techniques that combine offline Satisfiability and Optimization Modulo Theories with on-the-fly placement and routing. Preliminary empirical tests on a current generation 2048-qubit D-Wave system support the feasibility of the approach for certain SAT and MaxSAT problems.

Jesse J. Berwald, et al.

Persistence diagrams are a useful tool from topological data analysis which can be used to provide a concise description of a filtered topological space. What makes them even more useful in practice is that they come with a notion of a metric, the Wasserstein distance (closely related to but not the same as the homonymous metric from probability theory). Further, this metric provides a notion of stability; that is, small noise in the input causes at worst small differences in the output. In this paper, we show that the Wasserstein distance for persistence diagrams can be computed through quantum annealing. We provide a formulation of the problem as a Quadratic Unconstrained Binary Optimization problem, or QUBO, and prove correctness. Finally, we test our algorithm, exploring parameter choices and problem size capabilities, using a D-Wave 2000Q quantum annealing computer.

Anatoly Yu Smirnov, et al. 

We develop a theory to describe dynamics of a non-stationary open quantum system interacting with a hybrid environment, which includes high-frequency and low-frequency noise components. One part of the system–bath interaction is treated in a perturbative manner, whereas the other part is considered exactly. This approach allows us to derive a set of master equations where the relaxation rates are expressed as convolutions of the Bloch–Redfield and Marcus formulas. Our theory enables analysis of systems that have extremely small energy gaps in the presence of a realistic environment. As an illustration, we apply the theory to the 16 qubit quantum annealing problem with dangling qubits (Dickson et al 2013 Nat. Commun. 4 1903) and show qualitative agreement with experimental results.

Andrew King, et al.

The work of Berezinskii, Kosterlitz and Thouless in the 1970s revealed exotic phases of matter governed by the topological properties of low-dimensional materials such as thin films of superfluids and superconductors. A hallmark of this phenomenon is the appearance and interaction of vortices and antivortices in an angular degree of freedom—typified by the classical XY model—owing to thermal fluctuations. In the two-dimensional Ising model this angular degree of freedom is absent in the classical case, but with the addition of a transverse field it can emerge from the interplay between frustration and quantum fluctuations. Consequently, a Kosterlitz–Thouless phase transition has been predicted in the quantum system—the two-dimensional transverse-field Ising model—by theory and simulation. Here we demonstrate a large-scale quantum simulation of this phenomenon in a network of 1,800 in situ programmable superconducting niobium flux qubits whose pairwise couplings are arranged in a fully frustrated square-octagonal lattice. Essential to the critical behaviour, we observe the emergence of a complex order parameter with continuous rotational symmetry, and the onset of quasi-long-range order as the system approaches a critical temperature. We describe and use a simple approach to statistical estimation with an annealing-based quantum processor that performs Monte Carlo sampling in a chain of reverse quantum annealing protocols. Observations are consistent with classical simulations across a range of Hamiltonian parameters. We anticipate that our approach of using a quantum processor as a programmable magnetic lattice will find widespread use in the simulation and development of exotic materials.

R. Harris, et. al

Understanding magnetic phases in quantum mechanical systems is one of the essential goals in condensed matter physics, and the advent of prototype quantum simulation hardware has provided new tools for experimentally probing such systems. We report on the experimental realization of a quantum simulation of interacting Ising spins on three-dimensional cubic lattices up to dimensions 8 × 8 × 8 on a D-Wave processor (D-Wave Systems, Burnaby, Canada). The ability to control and read out the state of individual spins provides direct access to several order parameters, which we used to determine the lattice’s magnetic phases as well as critical disorder and one of its universal exponents. By tuning the degree of disorder and effective transverse magnetic field, we observed phase transitions between a paramagnetic, an antiferromagnetic, and a spin-glass phase.

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.

Amir H. Khoshaman, et al.

Boltzmann machines (BMs) are appealing candidates for powerful priors in variational autoencoders (VAEs), as they are capable of capturing nontrivial and multi-modal distributions over discrete variables. However, indifferentiability of the discrete units prohibits using the reparameterization trick, essential for low-noise back propagation. The Gumbel trick resolves this problem in a consistent way by relaxing the variables and distributions, but it is incompatible with BM priors. Here, we propose the GumBolt, a model that extends the Gumbel trick to BM priors in VAEs. GumBolt is significantly simpler than the recently proposed methods with BM prior and outperforms them by a considerable margin. It achieves state-of-the-art performance on permutation invariant MNIST and OMNIGLOT datasets in the scope of models with only discrete latent variables. Moreover, the performance can be further improved by allowing multi-sampled (importance-weighted) estimation of log-likelihood in training, which was not possible with previous models.

Arash Vahdat, et al.

Boltzmann machines are powerful distributions that have been shown to be an effective prior over binary latent variables in variational autoencoders (VAEs). However, previous methods for training discrete VAEs have used the evidence lower bound and not the tighter importance-weighted bound. We propose two approaches for relaxing Boltzmann machines to continuous distributions that permit training with importance-weighted bounds. These relaxations are based on generalized overlapping transformations and the Gaussian integral trick. Experiments on the MNIST and OMNIGLOT datasets show that these relaxations outperform previous discrete VAEs with Boltzmann priors.

Arash Vahdat

Collecting large training datasets, annotated with high-quality labels, is costly and time-consuming. This paper proposes a novel framework for training deep convolutional neural networks from noisy labeled datasets that can be obtained cheaply. The problem is formulated using an undirected graphical model that represents the relationship between noisy and clean labels, trained in a semi-supervised setting. In our formulation, the inference over latent clean labels is tractable and is regularized during training using auxiliary sources of information. The proposed model is applied to the image labeling problem and is shown to be effective in labeling unseen images as well as reducing label noise in training on CIFAR-10 and MS COCO datasets.

Amir Khoshaman, et al.

Variational autoencoders (VAEs) are powerful generative models with the salient ability to perform inference. Here, we introduce a quantum variational autoencoder (QVAE): a VAE whose latent generative process is implemented as a quantum Boltzmann machine (QBM). We show that our model can be trained end-to-end by maximizing a well-defined loss-function: a “quantum” lower- bound to a variational approximation of the log-likelihood. We use quantum Monte Carlo (QMC) simulations to train and evaluate the performance of QVAEs. To achieve the best performance, we first create a VAE platform with discrete latent space generated by a restricted Boltzmann machine (RBM). Our model achieves state-of-the-art performance on the MNIST dataset when compared against similar approaches that only involve discrete variables in the generative process. We consider QVAEs with a smaller number of latent units to be able to perform QMC simulations, which are computationally expensive. We show that QVAEs can be trained effectively in regimes where quantum effects are relevant despite training via the quantum bound. Our findings open the way to the use of quantum computers to train QVAEs to achieve competitive performance for generative models. Placing a QBM in the latent space of a VAE leverages the full potential of current and next-generation quantum computers as sampling devices.

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.

Arash Vahdat, et al.

Training of discrete latent variable models remains challenging because passing gradient information through discrete units is difficult. We propose a new class of smoothing transformations based on a mixture of two overlapping distributions, and show that the proposed transformation can be used for training binary latent models with either directed or undirected priors. We derive a new variational bound to efficiently train with Boltzmann machine priors. Using this bound, we develop DVAE++, a generative model with a global discrete prior and a hierarchy of convolutional continuous variables. Experiments on several benchmarks show that overlapping transformations outperform other recent continuous relaxations of discrete latent variables including Gumbel-Softmax (Maddison et al., 2016; Jang et al., 2016), and discrete variational autoencoders (Rolfe, 2016).

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.

Firas Hamze, et al.

We present a methodology for generating Ising Hamiltonians of tunable complexity and with a priori known ground states based on a decomposition of the model graph into edge-disjoint subgraphs. The idea is illustrated with a spin-glass model defined on a cubic lattice, where subproblems, whose couplers are restricted to the two values {-1,+1}, are specified on unit cubes and are parametrized by their local degeneracy. The construction is shown to be equivalent to a type of three-dimensional constraint satisfaction problem known as the tiling puzzle. By varying the proportions of subproblem types, the Hamiltonian can span a dramatic range of typical computational complexity, from fairly easy to many orders of magnitude more difficult than prototypical bimodal and Gaussian spin glasses in three space dimensions. We corroborate this behavior via experiments with different algorithms and discuss generalizations and extensions to different types of graphs.

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.

Trevor Lanting, et al.

Perturbative anticrossings have long been identified as a potential computational bottleneck for quantum annealing. This bottleneck can appear, for example, when a uniform transverse driver Hamiltonian is applied to each qubit. Previous theoretical research sought to alleviate such anticrossings by adjusting the transverse driver Hamiltonians on individual qubits according to a perturbative approximation. Here we apply this principle to a physical implementation of quantum annealing in a D-Wave 2000Q system. We use samples from the quantum annealing hardware and per-qubit anneal offsets to produce nonuniform driver Hamiltonians. On small instances with severe perturbative anticrossings, our algorithm yields an increase in minimum eigengaps, ground state success probabilities, and escape rates from metastable valleys. We also demonstrate that the same approach can mitigate biased sampling of degenerate ground states

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.

Evgeny Andriyash, et al.

Recent theoretical and experimental studies have suggested that quantum Monte Carlo (QMC) simulation can behave similarly to quantum annealing (QA). Here, we compare incoherent tunneling and QMC escape using perturbation theory, which has much wider validity than WKB approximation. We show that the two do not scale the same way when there are multiple homotopy-inequivalent paths for tunneling. We demonstrate through examples that frustration can generate an exponential number of tunneling paths, which under certain conditions can lead to an exponential advantage for incoherent tunneling over classical QMC escape. We provide analytical and numerical evidence for such an advantage and show that it holds beyond perturbation theory.

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.

Anatoly Yu. Smirnov, et al.

Measurement of the energy eigenvalues (spectrum) of a multi-qubit system has recently become possible by qubit tunneling spectroscopy (QTS). In the standard QTS experiments, an incoherent probe qubit is strongly coupled to one of the qubits of the system in such a way that its incoherent tunneling rate provides information about the energy eigenvalues of the original (source) system. In this paper, we generalize QTS by coupling the probe qubit to many source qubits. We show that by properly choosing the couplings, one can perform projective measurements of the source system energy eigenstates in an arbitrary basis, thus performing quantum eigenstate tomography. As a practical example of a limited tomography, we apply our scheme to probe the eigenstates of a kink in a frustrated transverse Ising chain.

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.

Jack Raymond, et al.

Sampling from a Boltzmann distribution is NP-hard and so requires heuristic approaches. Quantum annealing is one promising candidate. The failure of annealing dynamics to equilibrate on practical time scales is a well understood limitation, but does not always prevent a heuristically useful distribution from being generated. In this paper we evaluate several methods for determining a useful operational temperature range for annealers.

Zhengbing Bian, et al.

Current quantum annealing (QA) hardware suffers from practical limitations such as finite temperature, sparse connectivity, small qubit numbers, and control error. We propose new algorithms for mapping boolean constraint satisfaction problems (CSPs) onto QA hardware mitigating these limitations. In particular we develop a new embedding algorithm for mapping a CSP onto a hardware Ising model with a fixed sparse set of interactions, and propose two new decomposition algorithms for solving problems too large to map directly into hardware.

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.

Mohammad H. Amin, et al.

Inspired by the success of Boltzmann Machines based on classical Boltzmann distribution, we propose a new machine learning approach based on quantum Boltzmann distribution of a transverse-field Ising Hamiltonian. Due to the non-commutative nature of quantum mechanics, the training process of the Quantum Boltzmann Machine (QBM) can become nontrivial. We circumvent the problem by introducing bounds on the quantum probabilities. This allows us to train the QBM efficiently by sampling. We show examples of QBM training with and without the bound, using exact diagonalization, and compare the results with classical Boltzmann training. We also discuss the possibility of using quantum annealing processors like D-Wave for QBM training and application.

J. D. Whittaker, et al.

Superconducting microresonators have been successfully utilized as detection elements for a wide variety of applications. With multiplexing factors exceeding 1000 detectors per transmission line, they are the most scalable low-temperature detector technology demonstrated to date. For high-throughput applications, fewer detectors can be coupled to a single wire but utilize a larger per-detector bandwidth. For all existing designs, fluctuations in fabrication tolerances result in a non-uniform shift in resonance frequency and sensitivity, which ultimately limits the efficiency of bandwidth utilization. Here, we present the design, implementation, and initial characterization of a superconducting microresonator readout integrating two tunable inductances per detector. We demonstrate that these tuning elements provide independent control of both the detector frequency and sensitivity, allowing us to maximize the transmission line bandwidth utilization. Finally, we discuss the integration of these detectors in a multilayer fabrication stack for high-speed readout of the D-Wave quantum processor, highlighting the use of control and routing circuitry composed of single-flux-quantum loops to minimize the number of control wires at the lowest temperature stage.

Andrew D. King, et al.

Both simulated quantum annealing and physical quantum annealing have shown the emergence of "heavy tails" in their performance as optimizers: The total time needed to solve a set of random input instances is dominated by a small number of very hard instances…On similar inputs designed to suppress local degeneracy, performance of a quantum annealing processor on hard instances improves by orders of magnitude at the 512-qubit scale, while classical performance remains relatively unchanged.

Kelly Boothby, et al.

The current generation of D-Wave quantum annealing processor is designed to minimize the energy of an Ising spin configuration whose pairwise interactions lie on the edges of a Chimera graph C, M,N,L. In order to solve an Ising spin problem with arbitrary pairwise interaction structure, the corresponding graph must be minor-embedded into a Chimera graph. We define a combinatorial class of native clique minors in Chimera graphs with vertex images of uniform, near minimal size, and provide a polynomial-time algorithm that finds a maximum native clique minor in a given induced subgraph of a Chimera graph. These minors allow improvement over recent work and have immediate practical applications in the field of quantum annealing.

Adam Douglass, et al.

SAT filters are a novel and compact data structure that can be used to quickly query a word for membership in a fixed set. They have the potential to store more information in a fixed storage limit than a Bloom filter. Constructing a SAT filter requires sampling diverse solutions to randomly constructed constraint satisfaction instances, but there is flexibility in the choice of constraint satisfaction problem. Presented here is a case study of SAT filter construction with a focus on constraint satisfaction problems based on MAX-CUT clauses (Not-all-equal 3-SAT, 2-in-4-SAT, etc.) and frustrated cycles in the Ising model. Solutions are sampled using a D-Wave quantum annealer, and results are measured against classical approaches. The SAT variants studied are of interest in the context of SAT filters, independent of the solvers used.

A.D.King, et al.

The performance of a D-Wave Vesuvius quantum annealing processor was recently compared to a suite of classical algorithms on a class of constraint satisfaction instances based on frustrated loops. However, the construction of these instances leads the maximum coupling strength to increase with problem size. As a result, larger instances are subject to amplified analog control error, and are effectively annealed at higher temperatures in both hardware and software. We generate similar constraint satisfaction instances with limited range of coupling strength and perform a similar comparison to classical algorithms. On these instances the D-Wave Vesuvius processor, run with a fixed 20µs anneal time, shows a scaling advantage in the median case over the software solvers for the hardest regime studied. This scaling advantage implies that quantum speedup is not ruled out for these problems. Our results support the hypothesis that performance of D-Wave Vesuvius processors is strongly influenced by analog control error, which can be reduced and mitigated as the technology matures.

Mohammad H. Amin

We argue that a quantum annealer at very long annealing times is likely to experience a quasistatic evolution, returning a final population that is close to a Boltzmann distribution of the Hamiltonian at a single (freeze-out) point during the annealing. Such a system is expected to correlate with classical algorithms that return the same equilibrium distribution. These correlations do not mean that the evolution of the system is classical or can be simulated by these algorithms. The computation time extracted from such a distribution reflects the equilibrium behavior with no information about the underlying quantum dynamics. This makes the search for quantum speedup problematic.

Sergio Boixo, et al.

Quantum tunneling is a phenomenon in which a quantum state traverses energy barriers above the energy of the state itself. Tunneling has been hypothesized as an advantageous physical resource for optimization. Here we present the first experimental evidence of a computational role of multiqubit quantum tunneling in the evolution of a programmable quantum annealer. We develop a theoretical model based on a NIBA Quantum Master Equation to describe the multiqubit dissipative tunneling effects under the complex noise characteristics of such quantum devices. We start by considering a computational primitive, an optimization problem consisting of just one global and one false minimum. The quantum evolutions enable tunneling to the global minimum while the corresponding classical paths are trapped in a false minimum. In our study the non-convex potentials are realized by frustrated networks of qubit clusters with strong intra-cluster coupling. We show that the collective effect of the quantum environment is suppressed in the “critical” phase during the evolution where quantum tunneling “decides” the right path to solution. In a later stage dissipation facilitates the multiqubit tunneling leading to the solution state. The predictions of the model accurately describe the experimental data from the D-Wave Two quantum annealer at NASA Ames. In our computational primitive the temperature dependence of the probability of success in the quantum model is opposite to that of the classical paths with thermal hopping. Specifically, we provide an analysis of an optimization problem with sixteen qubits, demonstrating eight qubit tunneling that increases success probabilities. Furthermore, we report results for larger problems with up to 200 qubits that contain the primitive as subproblems.

Jun Cai, et al.

We present a heuristic algorithm for finding a graph H as a minor of a graph G that is practical for sparse G and H with hundreds of vertices. We also explain the practical importance of finding graph minors in mapping quadratic pseudo-boolean optimization problems onto an adiabatic quantum annealer.

T. Lanting, et al.

In this paper, we present experimental evidence that, during a critical portion of QA, qubits in the D-Wave processor become entangled and entanglement persists even as these systems reach equilibrium with a thermal environment. Our results provide an encouraging sign that quantum annealing is a viable technology for large-scale quantum computing.

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.

P. Bunyk, et al.

We have developed a quantum annealing processor, based on an array of tunably coupled rf-SQUID flux qubits, fabricated in a superconducting integrated circuit process [1]. Implementing this type of processor at a scale of 512 qubits and 1472 programmable inter-qubit couplers and operating at ∼ 20 mK has required attention to a number of considerations that one may ignore at the smaller scale of a few dozen or so devices. Here we discuss some of these considerations, and the delicate balance necessary for the construction of a practical processor that respects the demanding physical requirements imposed by a quantum algorithm. In particular we will review some of the design trade-offs at play in the floor-planning of the physical layout, driven by the desire to have an algorithmically useful set of inter-qubit couplers, and the simultaneous need to embed programmable control circuitry into the processor fabric. In this context we have developed a new ultra-low power embedded superconducting digital-to-analog flux converters (DACs) used to program the processor with zero static power dissipation, optimized to achieve maximum flux storage density per unit area. The 512 single-stage, 3520 two-stage, and 512 three-stage fluxDACs are controlled with an XYZ addressing scheme requiring 56 wires. Our estimate of on-chip dissipated energy for worst-case reprogramming of the whole processor is ∼ 65 fJ. Several chips based on this architecture have been fabricated and operated successfully at our facility, as well as two outside facilities.

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.

T. Lanting, et al.

The intrinsic flux noise observed in superconducting quantum interference devices (SQUIDs) is thought to be due to the fluctuation of electron spin impurities, but the frequency and temperature dependence observed in experiments do not agree with the usual 1/f models. We present theoretical calculations and experimental measurements of flux noise in rf-SQUID flux qubits that show how these observations, and previous reported measurements, can be interpreted in terms of a spindiffusion constant that increases with temperature. We fit measurements of flux noise in sixteen devices, taken in the 20−80 mK temperature range, to the spin-diffusion model. This allowed us to extract the spin-diffusion constant and its temperature dependence, suggesting that the spin system is close to a spin-glass phase transition.

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.

A. J. Berkley, et al. 

We describe a quantum tunneling spectroscopy technique that requires only low-bandwidth control. The method involves coupling a probe qubit to the system under study to create a localized probe state. The energy of the probe state is then scanned with respect to the unperturbed energy levels of the probed system. Incoherent tunneling transitions that flip the state of the probe qubit occur when the energy bias of the probe is close to an eigenenergy of the probed system. Monitoring these transitions allows the reconstruction of the probed system eigenspectrum. We demonstrate this method on an rf SQUID flux qubit.

N. G. Dickson, et al. 

Efforts to develop useful quantum computers have been blocked primarily by environmental noise. Here we examine the environment’s effect on quantum annealing using 16 qubits of a superconducting quantum processor. For a problem instance with an isolated small-gap anticrossing between the lowest two energy levels, we experimentally demonstrate that, even with annealing times eight orders of magnitude longer than the predicted single-qubit decoherence time, the probabilities of performing a successful computation are similar to those expected for a fully coherent system. Moreover, for the problem studied, we show that quantum annealing can take advantage of a thermal environment to achieve a speedup factor of up to 1,000 over a closed system.

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.

M.H. Amin, et al. 

Most realistic solid state devices considered as qubits are not true two-state systems. If the energy separation of the upper energy levels from the lowest two levels is not large, then these upper states may affect the evolution of the ground state over time and therefore cannot be neglected. In this work, we study the effect of energy levels beyond the lowest two energy levels on adiabatic quantum optimization in a device with a double-well potential as the basic logical element. We show that the extra levels can be modeled by adding additional ancilla qubits coupled to the original logical qubits, and that the presence of upper levels has no effect on the final ground state. We also study the influence of upper energy levels on the minimum gap for a set of 8-qubit spin glass instances.

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

N. G. Dickson, et al. 

It is believed that the presence of anticrossings with exponentially small gaps between the lowest two energy levels of the system Hamiltonian can render adiabatic quantum optimization inefficient. Here, we present a simple adiabatic quantum algorithm designed to eliminate exponentially small gaps caused by anticrossings between eigenstates that correspond with the local and global minima of the problem Hamiltonian. In each iteration of the algorithm, information is gathered about the local minima that are reached after passing the anticrossing nonadiabatically. This information is then used to penalize pathways to the corresponding local minima by adjusting the initial Hamiltonian. This is repeated for multiple clusters of local minima as needed. We generate 64-qubit random instances of the maximum independent set problem, skewed to be extremely hard, with between ${105}^{}$ and ${106}^{}$ highly degenerate local minima. Using quantum Monte Carlo simulations, it is found that the algorithm can trivially solve all of the instances in $\sim$10 iterations.

M. H. Amin, et al.

An approximate diagonalization method is proposed that combines exact diagonalization and perturbation expansion to calculate low-energy eigenvalues and eigenfunctions of a Hamiltonian. The method involves deriving an effective Hamiltonian for each eigenvalue to be calculated, using perturbation expansion, and extracting the eigenvalue from the diagonalization of the effective Hamiltonian. The size of the effective Hamiltonian can be significantly smaller than that of the original Hamiltonian, hence the diagonalization can be done much faster. We compare our approximate diagonalization results with those obtained using exact diagonalization and quantum Monte Carlo calculation for random problem instances with up to 128 qubits.

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.

T. Lanting, et al. 

We have developed a method for extracting the high-frequency noise spectral density of an rf-SQUID flux qubit from macroscopic resonant tunneling (MRT) rate measurements. The extracted noise spectral density is consistent with that of an ohmic environment up to frequencies $~$4 GHz. We have also derived an expression for the MRT line shape expected for a noise spectral density consisting of such a broadband ohmic component and an additional strongly peaked low-frequency component. This hybrid model provides an excellent fit to experimental data across a range of tunneling amplitudes and temperatures.

N. G. Dickson, et al.

It has been recently argued that adiabatic quantum optimization would fail in solving NP-complete problems because of the occurrence of exponentially small gaps due to crossing of local minima of the final Hamiltonian with its global minimum near the end of the adiabatic evolution. Using perturbation expansion, we analytically show that for the NP-hard problem of maximum independent set there always exist adiabatic paths along which no such crossings occur. Therefore, in order to prove that adiabatic quantum optimization fails for any NP-complete problem, one must prove that it is impossible to find any such path in polynomial time.

N. Dickson, et al. 

Much of the current focus in high-performance computing is on multi-threading, multi-computing, and graphics processing unit (GPU) computing. However, vectorization and non-parallel optimization techniques, which can often be employed additionally, are less frequently discussed. In this paper, we present an analysis of several optimizations done on both central processing unit (CPU) and GPU implementations of a particular computationally intensive Metropolis Monte Carlo algorithm. Explicit vectorization on the CPU and the equivalent, explicit memory coalescing, on the GPU are found to be critical to achieving good performance of this algorithm in both environments. The fully-optimized CPU version achieves a 9x to 12x speedup over the original CPU version, in addition to speedup from multi-threading. This is 2x faster than the fully-optimized GPU version.

Z. Bian, et al. 

In this paper we investigate the use of hardware which physically realizes quantum annealing for machine learning applications. We show how to take advantage of the hardware in both zero- and finite-temperature modes of operation. At zero temperature the hardware is used as a heuristic minimizer of Ising energy functions, and at finite temperature the hardware allows for sampling from the corresponding Boltzmann distribution. We rely on quantum mechanical processes to perform both these tasks more efficiently than is possible through software simulation on classical computers. We show how Ising energy functions can be sculpted to solve a range of supervised learning problems. Finally, we validate the use of the hardware by constructing learning algorithms trained using quantum annealing on several synthetic and real data sets. We demonstrate that this novel approach to learning using quantum mechanical hardware can provide significant performance gains for a number of structured supervised learning problems.

K. Karimi, et al. 

Adiabatic quantum optimization offers a new method for solving hard optimization problems. In this paper we calculate median adiabatic times (in seconds) determined by the minimum gap during the adiabatic quantum optimization for an NP-hard Ising spin glass instance class with up to 128 binary variables. Using parameters obtained from a realistic superconducting adiabatic quantum processor, we extract the minimum gap and matrix elements using high performance Quantum Monte Carlo simulations on a large-scale Internet-based computing platform. We compare the median adiabatic times with the median running times of two classical solvers and find that, for the considered problem sizes, the adiabatic times for the simulated processor architecture are about 4 and 6 orders of magnitude shorter than the two classical solvers' times. This shows that if the adiabatic time scale were to determine the computation time, adiabatic quantum optimization would be significantly superior to those classical solvers for median spin glass problems of at least up to 128 qubits. We also discuss important additional constraints that affect the performance of a realistic system.

M. W. Johnson, et al.

We have designed, fabricated and operated a scalable system for applying independently programmable time-independent, and limited time-dependent flux biases to control superconducting devices in an integrated circuit. Here we report on the operation of a system designed to supply 64 flux biases to devices in a circuit designed to be a unit cell for a superconducting adiabatic quantum optimization system. The system requires six digital address lines, two power lines, and a handful of global analog lines.

R. Harris, et al.

A novel rf-SQUID flux qubit that is robust against fabrication variations in Josephson junction critical currents and device inductance has been implemented. Measurements of the persistent current and of the tunneling energy between the two lowest lying states, both in the coherent and incoherent regime, are presented. These experimental results are shown to be in agreement with predictions of a quantum mechanical Hamiltonian whose parameters were independently calibrated, thus justifying the identification of this device as a flux qubit. In addition, measurements of the flux and critical current noise spectral densities are presented that indicate that these devices with Nb wiring are comparable to the best Al wiring rf-SQUIDs reported in the literature. An explicit formula for converting the observed flux noise spectral density into a free induction decay time for a flux qubit biased to its optimal point and operated in the energy eigenbasis is presented.

K. Karimi, et al.

This paper presents two conceptually simple methods for parallelizing a Parallel Tempering Monte Carlo simulation in a distributed volunteer computing context, where computers belonging to the general public are used. The first method uses conventional multi-threading. The second method uses CUDA, a graphics card computing system. Parallel Tempering is described, and challenges such as parallel random number generation and mapping of Monte Carlo chains to different threads are explained. While conventional multi-threading on CPUs is well-established, GPGPU programming techniques and technologies are still developing and present several challenges, such as the effective use of a relatively large number of threads. Having multiple chains in Parallel Tempering allows parallelization in a manner that is similar to the serial algorithm. Volunteer computing introduces important constraints to high performance computing, and we show that both versions of the application are able to adapt themselves to the varying and unpredictable computing resources of volunteers' computers, while leaving the machines responsive enough to use. We present experiments to show the scalable performance of these two approaches, and indicate that the efficiency of the methods increases with bigger problem sizes.

F. Hamze, et al.

This paper describes an algorithm for selecting parameter values (e.g. temperature values) at which to measure equilibrium properties with Parallel Tempering Monte Carlo simulation. Simple approaches to choosing parameter values can lead to poor equilibration of the simulation, especially for Ising spin systems that undergo 1st-order phase transitions. However, starting from an initial set of parameter values, the careful, iterative respacing of these values based on results with the previous set of values greatly improves equilibration. Example spin systems presented here appear in the context of Quantum Monte Carlo.

R. Harris, et al.

A superconducting chip containing a regular array of flux qubits, tunable interqubit inductive couplers, an XY-addressable readout system, on-chip programmable magnetic memory, and a sparse network of analog control lines has been studied. The architecture of the chip and the infrastructure used to control it were designed to facilitate the implementation of an adiabatic quantum optimization algorithm. The performance of an eight-qubit unit cell on this chip has been characterized by measuring its success in solving a large set of random Ising spin glass problem instances as a function of temperature. The experimental data are consistent with the predictions of a quantum mechanical model of an eight-qubit system coupled to a thermal environment. These results highlight many of the key practical challenges that we have overcome and those that lie ahead in the quest to realize a functional large scale adiabatic quantum information processor.

T. Lanting, et al.

We report measurements of macroscopic resonant tunneling between the two lowest energy states of a pair of magnetically coupled rf-SQUID flux qubits. This technique provides a direct means of observing two-qubit dynamics and a probe of the environment coupled to the pair of qubits. Measurements of the tunneling rate as a function of qubit flux bias show a Gaussian line shape that is well matched to theoretical predictions. Moreover, the peak widths indicate that each qubit is coupled to a local environment whose fluctuations are uncorrelated with that of the other qubit.

A. J. Berkley, et al.

We have designed, fabricated and tested an XY-addressable readout system that is specifically tailored for the reading of superconducting flux qubits in an integrated circuit that could enable adiabatic quantum optimization. In such a system, the flux qubits only need to be read at the end of an adiabatic evolution when quantum mechanical tunneling has been suppressed, thus simplifying many aspects of the readout process. The readout architecture for an N-qubit adiabatic quantum optimization system comprises N hysteretic dc SQUIDs and N rf SQUID latches controlled by 2N‾‾√+2 bias lines. The latching elements are coupled to the qubits and the dc SQUIDs are then coupled to the latching elements. This readout scheme provides two key advantages: First, the latching elements provide exceptional flux sensitivity that significantly exceeds what may be achieved by directly coupling the flux qubits to the dc SQUIDs using a practical mutual inductance. Second, the states of the latching elements are robust against the influence of ac currents generated by the switching of the hysteretic dc SQUIDs, thus allowing one to interrogate the latching elements repeatedly so as to mitigate the effects of stochastic switching of the dc SQUIDs. We demonstrate that it is possible to achieve single qubit read error rates of <10−6 with this readout scheme. We have characterized the system-level performance of a 128-qubit readout system and have measured a readout error probability of 8×10−5 in the presence of optimal latching element bias conditions.

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.

M. H. S. Amin, et al.

We present a detailed study of the non-Markovian two-state system dynamics for the regime of incoherent quantum tunneling. Using perturbation theory in the system tunneling amplitude Δ, and in the limit of strong system-bath coupling, we determine the short time evolution of the reduced density matrix and thereby find a general equation of motion for the non-Markovian evolution at longer times. We relate the nonlocality in time due to the non-Markovian effects with the environment characteristic response time. In addition, we study the incoherent evolution of a system with a double-well potential, where each well consists several quantized energy levels. We determine the crossover temperature to a regime where many energy levels in the wells participate in the tunneling process, and observe that the required temperature can be much smaller than the one associated with the system plasma frequency. We also discuss experimental implications of our theoretical analysis.

M. H. S. Amin, et al.

We have studied the decoherence properties of adiabatic quantum computation (AQC) in the presence of in general non-Markovian, e.g., low-frequency, noise. The developed description of the incoherent Landau-Zener transitions shows that the global AQC maintains its properties even for decoherence larger than the minimum gap at the anticrossing of the two lowest energy levels. The more efficient local AQC, however, does not improve scaling of the computation time with the number of qubits n as in the decoherence-free case. The scaling improvement requires phase coherence throughout the computation, limiting the computation time and the problem size n.

R. Harris, et al.

An improved tunable coupling element for building networks of coupled rf-SQUID flux qubits has been experimentally demonstrated. This new form of coupler, based upon the compound Josephson junction rf-SQUID, provides a sign and magnitude tunable mutual inductance between qubits with minimal nonlinear crosstalk from the coupler tuning parameter into the qubits. Quantitative agreement is shown between an effective one-dimensional model of the coupler's potential and measurements of the coupler persistent current and susceptibility.

J. Johansson, et al.

We report an experimental measurement of Landau-Zener transitions on an individual flux qubit within a multi-qubit superconducting chip designed for adiabatic quantum computation. The method used isolates a single qubit, tunes its tunneling amplitude Delta into the limit where Delta is much less than both the temperature T and the decoherence-induced energy level broadening and forces it to undergo a Landau-Zener transition. We find that the behavior of the qubit agrees to a high degree of accuracy with theoretical predictions for Landau-Zener transition probabilities for a double-well quantum system coupled to 1/f magnetic flux noise.

A. T. S. Wan, et al.

We study the effect of an environment consisting of noninteracting two level systems on Landau-Zener transitions with an interest on the performance of an adiabatic quantum computer. We show that if the environment is initially at zero temperature, it does not affect the transition probability. An excited environment, however, will always increase the probability of making a transition out of the ground state. For the case of equal intermediate gaps, we find an analytical upper bound for the transition probability in the limit of large number of environmental spins. We show that such an environment will only suppress the probability of success for adiabatic quantum computation by at most a factor close to 1/2.

M. H. S. Amin, et al.

We investigate the connection between local minima in the problem Hamiltonian and first order quantum phase transitions during an adiabatic quantum computation. We demonstrate how some properties of the local minima can lead to an extremely small gap that is exponentially sensitive to the Hamiltonian parameters. Using perturbation expansion, we derive an analytical formula that can not only predict the behavior of the gap, but also provide insight on how to controllably vary the gap size by changing the parameters. We show agreement with numerical calculations for a weighted maximum independent set problem instance.

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.

M. H. S. Amin, et al.

We develop a theory of macroscopic resonant tunneling of flux in a double-well potential in the presence of realistic flux noise with significant low-frequency component. The rate of incoherent flux tunneling between the wells exhibits resonant peaks, the shape and position of which reflect qualitative features of the noise, and can thus serve as a diagnostic tool for studying the low-frequency flux noise in SQUID qubits. We show, in particular, that the noise-induced renormalization of the first resonant peak provides direct information on the temperature of the noise source and the strength of its quantum component.

A. Perdomo, et al.

In this report, we explore the use of a quantum optimization algorithm for obtaining low energy conformations of protein models. We discuss mappings between protein models and optimization variables, which are in turn mapped to a system of coupled quantum bits. General strategies are given for constructing Hamiltonians to be used to solve optimization problems of physical/chemical/biological interest via quantum computation by adiabatic evolution. As an example, we implement the Hamiltonian corresponding to the Hydrophobic-Polar (HP) model for protein folding. Furthermore, we present an approach to reduce the resulting Hamiltonian to two-body terms gearing towards an experimental realization.

M. H. S. Amin, et al.

We present a perturbative method to estimate the spectral gap for adiabatic quantum optimization, based on the structure of the energy levels in the problem Hamiltonian. We show that for problems that have exponentially large number of local minima close to the global minimum, the gap becomes exponentially small making the computation time exponentially long. The quantum advantage of adiabatic quantum computation may then be accessed only via the local adiabatic evolution, which requires phase coherence throughout the evolution and knowledge of the spectrum. Such problems, therefore, are not suitable for adiabatic quantum computation.

M. H. S. Amin, et al.

We study the effect of a thermal environment on adiabatic quantum computation using the Bloch-Redfield formalism. We show that in certain cases the environment can enhance the performance in two different ways: (i) by introducing a time scale for thermal mixing near the anticrossing that is smaller than the adiabatic time scale, and (ii) by relaxation after the anticrossing. The former can enhance the scaling of computation when the environment is superohmic, while the latter can only provide a prefactor enhancement. We apply our method to the case of adiabatic Grover search and show that performance better than classical is possible with a superohmic environment, with no a priori knowledge of the energy spectrum.

R. Harris, et al.

Macroscopic resonant tunneling between the two lowest lying states of a bistable RF-SQUID is used to characterize noise in a flux qubit. Measurements of the incoherent decay rate as a function of flux bias revealed a Gaussian shaped profile that is not peaked at the resonance point, but is shifted to a bias at which the initial well is higher than the target well. The r.m.s. amplitude of the noise, which is proportional to the decoherence rate 1/T_2^*, was observed to be weakly dependent on temperature below 70 mK. Analysis of these results indicates that the dominant source of low frequency (1/f) flux noise in this device is a quantum mechanical environment in thermal equilibrium.

J. D. Biamonte, et al.

It has been established that local lattice spin Hamiltonians can be used for universal adiabatic quantum computation. However, the 2-local model Hamiltonians used in these proofs are general and hence do not limit the types of interactions required between spins. To address this concern, the present paper provides two simple model Hamiltonians that are of practical interest to experimentalists working towards the realization of a universal adiabatic quantum computer. The model Hamiltonians presented are the simplest known QMA-complete 2-local Hamiltonians. The 2-local Ising model with 1-local transverse field which has been realized using an array of technologies, is perhaps the simplest quantum spin model but is unlikely to be universal for adiabatic quantum computation. We demonstrate that this model can be rendered universal and QMA-complete by adding a tunable 2-local transverse XX coupling. We also show the universality and QMA-completeness of spin models with only 1-local Z and X fields and 2-local ZX interactions.

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.

R. Harris, et al.

We experimentally confirm the functionality of a coupling element for flux-based superconducting qubits, with a coupling strength J whose sign and magnitude can be tuned {\it in situ}. To measure the effective J, the groundstate of a coupled two-qubit system has been mapped as a function of the local magnetic fields applied to each qubit. The state of the system is determined by directly reading out the individual qubits while tunneling is suppressed. These measurements demonstrate that J can be tuned from antiferromagnetic through zero to ferromagnetic.

P. J. Love, et al.

We define a set of 2n−1−1 entanglement monotones for n qubits and give a single measure of entanglement in terms of these. This measure is zero except on globally entangled (fully inseparable) states. This measure is compared to the Meyer-Wallach measure for two, three, and four qubits. We determine the four-qubit state, symmetric under exchange of qubit labels, which maximizes this measure. It is also shown how the elementary monotones may be computed as a function of observable quantities. We compute the magnitude of our measure for the ground state of the four-qubit superconducting experimental system investigated in [M. Grajcar et al., Phys. Rev. Lett._96_, 047006 (2006)], and thus confirm the presence of global entanglement in the ground state.

M. H. S. Amin, et al.

When a two-level quantum system is irradiated with a microwave signal, in resonance with the energy difference between the levels, it starts Rabi oscillation between those states. If there are other states close, in energy, to the first two, the Rabi signal will also induce a transition to those. Here, we study the probability of transition to the third state, in a three-level system, while a Rabi oscillation between the first two states is performed. We investigate the effect of pulse shaping on the probability and suggest methods for optimizing pulse shapes to reduce transition probability.

M. Grajcar, et al.

We present the first experimental results on a device with more than two superconducting qubits. The circuit consists of four three-junction flux qubits, with simultaneous ferro- and antiferromagnetic coupling implemented using shared Josephson junctions. Its response, which is dominated by the ground state, is characterized using low-frequency impedance measurement with a superconducting tank circuit coupled to the qubits. The results are found to be in excellent agreement with the quantum-mechanical predictions.

S. H. W. van der Ploeg, et al.

Controllable adiabatic evolution of a multi-qubit system can be used for adiabatic quantum computation (AQC). This evolution ends at a configuration where the Hamiltonian of the system encodes the solution of the problem to be solved. As a first steps towards realization of AQC we have investigated two, three and four flux qubit systems. These systems were characterized by making use of a radio-frequency method. We designed two-qubit systems with coupling energies up to several kelvins. For the three-flux-qubit systems we determined the complete ground-state flux diagram in the three dimensional flux space around the qubits common degeneracy point. We show that the system's Hamiltonian can be completely reconstructed from our measurements. Our concept for the implementation of AQC, by making use of flux qubits, is discussed.

M. H. S. Amin, et al.

We report on design and fabrication of a new type of flux qubit that capitalizes on intrinsic properties of submicron YBCO grain boundary junctions. The operating point is protected from the fluctuations of the external fields, already on the classical level; the effects of external perturbations are absent, to the second or third order, depending on the character of the coupling. We propose an experiment to observe quantum tunneling and Rabi oscillations in the qubit. Estimate of the decoherence due to fluctuations of the external flux is presented.

M.H.S. Amin, et al.

A superconducting qubit implementation is proposed that takes the advantage of both charge and phase degrees of freedom. Superpositions of flux states in a superconducting loop with three Josephson junctions form the states of the qubit. The charge degree of freedom is used to readout and couple the qubits. Cancellation of first-order coupling to charge and flux fluctuations, at the working point of the qubit, protects it from the dephasing due to these sources.

A. M. van den Brink, et al.

It is sketched how a monostable rf- or dc-SQUID can mediate an inductive coupling between two adjacent flux qubits. The nontrivial dependence of the SQUID's susceptibility on external flux makes it possible to continuously tune the induced coupling from antiferromagnetic (AF) to ferromagnetic (FM). In particular, for suitable parameters, the induced FM coupling can be sufficiently large to overcome any possible direct AF inductive coupling between the qubits. The main features follow from a classical analysis of the multi-qubit potential. A fully quantum treatment yields similar results, but with a modified expression for the SQUID susceptibility. Since the latter is exact, it can also be used to evaluate the susceptibility--or, equivalently, energy-level curvature--of an isolated rf-SQUID for larger shielding and at degenerate flux bias, i.e., a (bistable) qubit. The result is compared to the standard two-level (pseudospin) treatment of the anticrossing, and the ensuing conclusions are verified numerically.

M. Grajcar, et al.

We have demonstrated strong antiferromagnetic coupling between two three-junction flux qubits based on a shared Josephson junction, and therefore not limited by the small inductances of the qubit loops. The coupling sign and magnitude were measured by coupling the system to a high-quality superconducting tank circuit. Design modifications allowing to continuously tune the coupling strength and/or make the coupling ferromagnetic are discussed.

A. Aspuru-Guzik, et al.

The calculation time for the energy of atoms and molecules scales exponentially with system size on a classical computer but polynomially using quantum algorithms. We demonstrate that such algorithms can be applied to problems of chemical interest using modest numbers of quantum bits. Calculations of the water and lithium hydride molecular ground-state energies have been carried out on a quantum computer simulator using a recursive phase-estimation algorithm. The recursive algorithm reduces the number of quantum bits required for the readout register from about 20 to 4. Mappings of the molecular wave function to the quantum bits are described. An adiabatic method for the preparation of a good approximate ground-state wave function is described and demonstrated for a stretched hydrogen molecule. The number of quantum bits required scales linearly with the number of basis functions, and the number of gates required grows polynomially with the number of quantum bits.

A. M. van den Brink, et al.

An effective Hamiltonian is derived for two coupled three-Josephson-junction (3JJ) qubits. This is not quite trivial, for the customary "free" 3JJ Hamiltonian is written in the limit of zero inductance L. Neglecting the self-flux is already dubious for one qubit when it comes to readout, and becomes untenable when discussing inductive coupling. First, inductance effects are analyzed for a single qubit. For small L, the self-flux is a "fast variable" which can be eliminated adiabatically. However, the commonly used junction phases are_not_ appropriate "slow variables", and instead one introduces degrees of freedom which are decoupled from the loop current to leading order. In the quantum case, the zero-point fluctuations (LC oscillations) in the loop current diverge as L->0. Fortunately, they merely renormalize the Josephson couplings of the effective (two-phase) theory.
In the coupled case, the strong zero-point fluctuations render the full (six-phase) wave function significantly entangled in leading order. However, in going to the four-phase theory, this uncontrollable entanglement is integrated out completely, leaving a computationally usable mutual-inductance term of the expected form as the effective interaction.

M. H. S. Amin, et al.

In a qubit system, the measurement operator does not necessarily commute with the qubit Hamiltonian, so that the readout process demolishes (mixes) the qubit energy eigenstates. The readout time is therefore limited by such a mixing time and its fidelity will be reduced. A quantum nondemolition readout scheme is proposed in which the charge of a flux qubit is measured. The measurement operator is shown to commute with the qubit Hamiltonian in the reduced two-level Hilbert space, even though the Hamiltonian contains non-commuting charge and flux terms.

A. Izmalkov, et al.

We have studied the low-frequency magnetic susceptibility of two inductively coupled flux qubits using the impedance measurement technique (IMT), through their influence on the resonant properties of a weakly coupled high-quality tank circuit. In a single qubit, an IMT dip in the tank's current-voltage phase angle at the level anticrossing yields the amplitude of coherent flux tunneling. For two qubits, the difference (IMT deficit) between the sum of single-qubit dips and the dip amplitude when both qubits are at degeneracy shows that the system is in a mixture of entangled states (a necessary condition for entanglement). The dependence on temperature and relative bias between the qubits allows one to determine all the parameters of the effective Hamiltonian and equilibrium density matrix, and confirms the formation of entangled eigenstates.

M. Grajcar, et al.

We have observed signatures of resonant tunneling in an Al three-junction qubit, inductively coupled to a Nb LC tank circuit. The resonant properties of the tank oscillator are sensitive to the effective susceptibility (or inductance) of the qubit, which changes drastically as its flux states pass through degeneracy. The tunneling amplitude is estimated from the data. We find good agreement with the theoretical predictions in the regime of their validity.

M. H. S. Amin, et al.

It is usually argued that the presence of gapless quasiparticle excitations at the nodes of the d-wave superconducting gap should strongly decohere the quantum states of a d-wave qubit, making quantum effects practically unobservable. Using a self-consistent linear response non-equilibrium quasiclassical formalism, we show that this is not necessarily true. We find quasiparticle conductance of a d-wave grain boundary junction to be strongly phase-dependent. Midgap states as well as nodal quasiparticles contribute to the conductance and therefore decoherence. Quantum behavior is estimated to be detectable in a qubit containing a d-wave junction with appropriate parameters.

A. Izmalkov, et al.

A two-level system traversing a level anticrossing has a small probability to make a so-called Landau-Zener (LZ) transition between its energy bands, in deviation from simple adiabatic evolution. This effect takes on renewed relevance due to the observation of quantum coherence in superconducting qubits (macroscopic "Schrodinger cat" devices). We report an observation of LZ transitions in an Al three-junction qubit coupled to a Nb resonant tank circuit.

M. H. S. Amin, et al.

A technique to study collisionless dynamics of a homogeneous superconducting system is developed, which is based on Riccati parametrization of Wigner distribution function. The quantum evolution of the superconductiung order parameter, initially deviated from the equilibrium value, is calculated using this technique. The effect of a time-dependent BCS paring interaction on the dynamics of the order parameter is also studied.

M. H. S. Amin, et al.

A central task towards building a practical quantum computer is to protect individual qubits from decoherence while retaining the ability to perform high-fidelity entangling gates involving arbitrary two qubits. Here we propose and demonstrate a dephasing-insensitive procedure for storing and processing quantum information in an all-to-all connected superconducting circuit involving multiple frequency-tunable qubits, each of which can be controllably coupled to any other through a central bus resonator. Although it is generally believed that the extra frequency tunability enhances the control freedom but induces more dephasing impact for superconducting qubits, our results show that any individual qubit can be dynamically decoupled from dephasing noise by applying a weak continuous and resonant driving field whose phase is reversed in the middle of the pulse. More importantly, we demonstrate a new method for realizing two-qubit phase gate with inherent dynamical decoupling via the combination of continuous driving and qubit-qubit swapping coupling. We find that the weak continuous driving fields not only enable the conditional dynamics essential for quantum information processing, but also protect both qubits from dephasing during the gate operation.

M.H.S Amin 

We present a non-equilibrium quasiclassical formalism suitable for studying linear response ac properties of Josephson junctions. The non-equilibrium self-consistency equations are satisfied, to very good accuracy, already in zeroth iteration. We use the formalism to study ac Josephson effect in a ballistic superconducting point contact. The real and imaginary parts of the ac linear conductance are calculated both analytically (at low frequencies) and numerically (at arbitrary frequency). They show strong temperature, frequency, and phase dependence. Many anomalous properties appear near phi = pi. We ascribe them to the presence of zero energy bound states.

M. H. S. Amin, et al.

We show that a complete set of one-bit gates can be realized by coupling the two logical states of a phase qubit to a third level (at higher energy) using microwave pulses. Thus, one can achieve coherent control without invoking any tunneling between the qubit levels. We propose two implementations, using rf-SQUIDs and d-wave Josephson junctions.

T. Lindstrom, et al.

The predominant d-wave pairing symmetry in high temperature superconductors allows for a variety of current-phase relations in Josephson junctions, which is to a certain degree fabrication controlled. In this letter, we report on direct experimental observations of the effects of a non-sinusoidal current-phase dependence in YBCO dc-SQUIDs, which agree with the theoretical description of the system.

C. Kurter, et al.

Josephson junctions with topological insulator weak links can host low energy Andreev bound states giving rise to a current phase relation that deviates from sinusoidal behaviour. Of particular interest are zero energy Majorana bound states that form at a phase difference of π. Here we report on interferometry studies of Josephson junctions and superconducting quantum interference devices (SQUIDs) incorporating topological insulator weak links. We find that the nodes in single junction diffraction patterns and SQUID oscillations are lifted and independent of chemical potential. At high temperatures, the SQUID oscillations revert to conventional behavior, ruling out asymmetry. The node lifting of the SQUID oscillations is consistent with low energy Andreev bound states exhibiting a nonsinusoidal current phase relation, coexisting with states possessing a conventional sinusoidal current phase relation. However, the finite nodal currents in the single junction diffraction pattern suggest an anomalous contribution to the supercurrent possibly carried by Majorana bound states, although we also consider the possibility of inhomogeneity.

M. H. S. Amin, et al.

We present a non-equilibrium quasiclassical formalism suitable for studying linear response ac properties of Josephson junctions. The non-equilibrium self-consistency equations are satisfied, to very good accuracy, already in zeroth iteration. We use formalism to study ac Josephson effect in a ballistic superconducting point contact. The real and imaginary parts of the ac linear conductance are calculated both analytically (at low frequencies) and numerically (at arbitrary frequency). They show strong temperature, frequency, and phase dependence. Many anomalous properties appear near phi = pi. We ascribe them to the presence of zero energy-bound states.

M. H. S. Aminm, et al.

Calculation of current and order parameter distribution in inhomogeneous superconductors is often based on a self-consistent solution of Eilenberger equations for quasiclassical Green's functions. Compared to the original Gorkov equations, the problem is much simplified due to the fact that the values of Green's functions at a given point are connected to the bulk ones at infinity (boundary values) by ``dragging'' along the classical trajectories of quasiparticles. In finite size systems, where classical trajectories undergo multiple reflections from surfaces and interfaces, the usefulness of the approach is no longer obvious, since there is no simple criterion to determine what boundary value a trajectory corresponds to, and whether it reaches infinity at all. Here, we demonstrate the modification of the approach based on the Schophol-Maki transformation, which provides the basis for stable numerical calculations in 2D. We apply it to two examples: generation of spontaneous currents and magnetic moments in isolated islands of d-wave superconductor with subdominant order-parameters s and d_{xy}, and in a grain boundary junction between two arbitrarily oriented d-wave superconductors. Both examples are relevant to the discussion of time-reversal symmetry breaking in unconventional superconductors, as well as for application in quantum computing.

E. Il'ichev, et al.

Under resonant irradiation, a quantum system can undergo coherent (Rabi) oscillations in time. We report evidence for such oscillations in a _continuously_ observed three-Josephson-junction flux qubit, coupled to a high-quality tank circuit tuned to the Rabi frequency. In addition to simplicity, this method of_Rabi spectroscopy_ enabled a long coherence time of about 2.5 microseconds, corresponding to an effective qubit quality factor \~7000.

A. Y. Smirnov, et al.

Continuous spectroscopic measurements of a strongly driven superconducting qubit by means of a high-quality tank circuit (a linear detector) are under study. Output functions of the detector, namely, a spectrum of voltage fluctuations and an impedance, are expressed in terms of the qubit spectrum and magnetic susceptibility. The nonequilibrium spectrum of the current fluctuations in the qubit loop and the linear response function of the driven qubit coupled to a heat bath are calculated with Bloch-Redfield and rotating wave approximations. The backaction effects of the qubit on the tank and the tank on the qubit are analyzed quantitatively. We show that the voltage spectrum of the tank provides detailed information about the frequency and decay rate of Rabi oscillations in the qubit. It is found that both an efficiency of spectroscopic measurement and measurement-induced decoherence of the qubit demonstrate a resonant behavior as the Rabi frequency approaches the resonant frequency of the tank. We determine conditions when the spectroscopic observation of the Rabi oscillations in the flux qubit with the tank circuit can be considered as a weak continuous quantum measurement.

A. Blais, et al.

We study an LC-circuit implemented using a current-biased Josephson junction (CBJJ) as a tunable coupler for superconducting qubits. By modulating the bias current, the junction can be tuned in and out of resonance and entangled with the qubits coupled to it. One can thus implement two-qubit operations by mediating entanglement. We consider the examples of CBJJ and charge--phase qubits. A simple recoupling scheme leads to a generalization to arbitrary qubit designs.

T. Lindstrom, et al.

The predominant d-wave pairing symmetry in high temperature superconductors allows for a variety of current-phase relations in Josephson junctions, which is to a certain degree fabrication controlled. In this letter we report on direct experimental observations of the effects of a non-sinusoidal current-phase dependence in YBCO dc-SQUIDs, which agree with the theoretical description of the system.

Y. S. Greenberg, et al.

We propose to investigate flux qubits by the impedance measurement technique (IMT), currently used to determine the current--phase relation in Josephson junctions. We analyze in detail the case of a high-quality tank circuit coupled to a persistent-current qubit, to which IMT was successfully applied in the classical regime. It is shown that low-frequency IMT can give considerable information about the level anticrossing, in particular the value of the tunneling amplitude. An interesting difference exists between applying the ac bias directly to the tank and indirectly via the qubit. In the latter case, a convenient way to find the degeneracy point in situ is described. Our design only involves existing technology, and its noise tolerance is quantitatively estimated to be realistic.

M. H. S. Amin, et al.

Mesoscopic multi-terminal Josephson junctions are novel devices that provide weak coupling between several bulk superconductors through a common normal layer. Because of the nonlocal coupling of the superconducting banks, a current flow between two of the terminals can induce a phase difference and/or current flow in the other terminals. This "phase dragging" effect is used in designing a new type of superconducting phase qubit, the basic element of a quantum computer. Time-reversal symmetry breaking can be achieved by inserting a pi-phase shifter into the flux loop. Logical operations are done by applying currents. This removes the necessity for local external magnetic fields to achieve bistability or controllable operations.

M. H. S. Amin, et al.

A new DC-SQUID is proposed that exploits the properties of the grain boundary junctions in high T_c superconductors. The orientations of the grain boundaries are chosen in such a way to establish a pi/2 (rather than 0 or pi) phase difference between the equilibrium phases of the two Josephson junctions in the SQUID loop. This property is exploited to increase the sensitivity and direction dependence of the SQUID for measuring magnetic flux without additional flux-generating coils.

M. H. S. Amin et al.

The time-reversal symmetry (Τ) breaking on surfaces and interfaces of superconductors with d-wave orbital pairing has been intensively investigated in last years both in theory and experiment (see reviews [1, 2]). Several mechanisms of Τ-breaking and corresponding spontaneous currents generation have been proposed and studied, particularly: the appearance of a subdominant order parameter and the proximity effect. The latter case is realized, in particular, at the interface of two d-wave superconductors with different lattice axes orientation (Josephson d-d junction). In the present paper, we consider the generation of spontaneous currents and obtain the pattern of current distribution in the ballistic point d-d junction.

M. H. S. Amin, et al.

We investigate the properties of spontaneous currents generated at surfaces and interfaces of d-wave superconductors using the self-consistent quasiclassical Eilenberger equations. The influence of the roughness and reflectivity of the boundaries on the spontaneous current are studied. We show that these have very different effects at the surfaces compared to the interfaces, which reflects the different nature of the time-reversal symmetry breaking states in these two systems. We find a signature of the "anomalous proximity effect'' at rough d-wave interfaces. We also show that the existence of a subdominant order parameter, which is necessary for time-reversal symmetry breaking at the surface, suppresses the spontaneous current generation due to the proximity effect at the interface between two superconductors. We associate orbital moments to the spontaneous currents to explain the "superscreening'' effect, which seems to be present at all ideal d-wave surfaces and interfaces, where d_{xy} is the favorite subdominant symmetry.

M. H. S. Amin, et al.

We report self-consistent quasiclassical calculations of spontaneous currents and magnetic moments in finite-size unconventional superconducting systems, namely: (i) in isolated d-wave superconductor islands where, in addition to the dominant order parameter (with a d_{x^2-y^2} symmetry), a subdominant order parameter of s or d_{xy} symmetry is added; (ii) in grain boundary junctions between two arbitrarily oriented d-wave superconductors, and between a d-wave and an s-wave superconductor. We show that the profile of the spontaneous current density and the magnetic field distribution depends on the time-reversal symmetry-breaking properties of the system. For the d_{x^2-y^2}+id_{xy} state, vortices appear near the edges of the finite size systems. We associate these vortices with the chiral nature of the mixed order parameter. The method developed here is quite general and can be used for predicting the properties of any finite-size superconducting system.

M. H. S. Amin, et al.

A theory is offered for a novel device, mesoscopic four-terminal SQUID. The studied system consists of a mesoscopic four-terminal junction, one pair of terminals of which is incorporated in a superconducting ring and the other one is connected with a transport circuit. The nonlocal weak coupling between the terminals leads to effects of phase dragging and magnetic flux transfer. The behavior of a four-terminal SQUID, controlled by the external parameters, the applied magnetic flux, and the transport current is investigated. The critical current and the current-voltage characteristics as functions of magnetic flux are calculated. In the nonlocal mesoscopic case, they depend not only on the magnitude of the applied flux but also on its sign, allowing measurement of the direction of the external magnetic field.

M. H. S. Amin, et al.

We investigate nonlocal coherent transport in ballistic four-terminal Josephson structures (where bulk superconductors (terminals) are connected through a clean normal layer, e.g., a two-dimensional electron gas). Coherent anisotropic superposition of macroscopic wave functions of the superconductors in the normal region produces phase slip lines (2D analogs to phase slip centres) and time-reversal symmetry breaking 2D vortex states in it, as well as such effects as phase dragging and magnetic flux transfer. The tunneling density of local Andreev states in the normal layer was shown to contain peaks at the positions controlled by the phase differences between the terminals. We have obtained general dependence of these effects on the controlling supercurrent/phase differences between the terminals of the ballistic mesoscopic four-terminal SQUID.

E. Il'ichev, et al.

We have measured the current-phase relationship (CPR) of symmetric 45 degree YBaCuO grain boundary Josephson junctions. Substantial deviations of the CPR from conventional tunnel-junction behavior have been observed: (i) The critical current exhibits, as a function of temperature T, a local minimum at a temperature T*. (ii) At T approximately equal to T*, the first harmonic of the CPR changes sign. (iii) For T<T*, the second harmonic of the CPR is comparable to the first harmonic, and (iv) the ground state of the junction becomes degenerate. The results are in good agreement with a microscopic model of Josephson junctions between d-wave superconductors.

M. H. S. Amin, et al.

A boundary between two d-wave superconductors or an s-wave and a d-wave superconductor generally breaks time-reversal symmetry and can generate spontaneous currents due to the proximity effect. On the other hand, surfaces and interfaces in d-wave superconductors can produce localized current-carrying states by supporting the T-breaking combination of dominant and subdominant order parameters. We investigate spontaneous currents in the presence of both mechanisms and show that at low temperature, counter-intuitively, the subdominant coupling decreases the amplitude of the spontaneous current due to the proximity effect. Superscreening of spontaneous currents is demonstrated to be present in any d-d (but not s-d) junction and surface with d+id' order parameter symmetry. We show that this supercreening is the result of contributions from the local magnetic moment of the condensate to the spontaneous current.