Invited Talks

Tameem Albash (ISI)

Title: Simulated Annealing Comparison Between All-to-All Connectivity Schemes

Abstract: Quantum annealing aims to exploit quantum mechanics to speed up the solution to optimization problems. Most problems exhibit complete connectivity between the logical spin variables after they are mapped to the Ising spin Hamiltonian of quantum annealing. To account for hardware constraints of current and future physical quantum annealers, methods enabling the embedding of fully connected graphs of logical spins into a constant-degree graph of physical spins are therefore essential. Here, we compare the recently proposed embedding scheme for quantum annealing with all-to-all connectivity due to Lechner, Hauke and Zoller (LHZ) [Science Advances 1 (2015)] to the commonly used minor embedding (ME) scheme. Using both simulated quantum annealing and parallel tempering simulations, we find that for a set of instances randomly chosen from a class of fully connected, random Ising problems, the ME scheme outperforms the LHZ scheme when using identical simulation parameters, despite the fault tolerance of the latter to weakly correlated spin-flip noise. This result persists even after we introduce several decoding strategies for the LHZ scheme, including a minimum-weight decoding algorithm that results in substantially improved performance over the original LHZ scheme. We explain the better performance of the ME scheme in terms of more efficient spin updates, which allows it to better tolerate the correlated spin-flip errors that arise in our model of quantum annealing. Our results leave open the question of whether the performance of the two embedding schemes can be improved using scheme-specific parameters and new error correction approaches.

Title: Building quantum annealer v2.0

Abstract: Quantum annealer, constructed from an array of coupled flux qubits,  represents an analog approach to build a quantum computer. In Quantum A.I. Lab, we are working on building an enhanced-performance quantum annealer - quantum annealer v2.0. We introduce the "fluxmon" flux qubit as the building block of quantum annealer v2.0. With the capacitance and inductance provided by a coplanar waveguide, the fluxmon qubit design balances between coherence and coupling.  Utilizing a microwave control and readout, we were able to characterize single-qubit performance and discovered that the qubit decoherence is dominated by 1/f flux noise over a wide range of frequencies.  Meanwhile, with the linear inductance distributed over a macroscopic length scale, we discuss that the fluxmon design allows for GHz-scale coupling for multiple qubits, suitable for highly connected annealer architectures.

Elizabeth Crosson (Caltech)

Title: Simulated quantum annealing can be exponentially faster than classical simulated annealing

Abstract: Cost functions with thin, high energy barriers can exhibit exponential separations between the run-time of classical simulated annealing, for which thermal fluctuations take exponential time to climb these barriers, and quantum annealing which can in some cases pass through such barriers efficiently, arguably by taking advantage of quantum tunneling.  In this talk we will describe a proof which demonstrates that the Markov chain underlying SQA can efficiently sample its target distribution and find the global minimum of such a spike cost function in polynomial time. This result provides evidence for the growing consensus that SQA inherits at least some of the advantages that arise from tunneling in QA, and we will emphasize techniques in the proof which contribute to a further understanding of both the equilibrium distribution and the nonequilibrium dynamics of SQA.

Toby Cubitt (UCL)

Title: Hamiltonian Simulation and Universal Models

Abstract: Physical (or "analogue" - from analogous) Hamiltonian simulation involves engineering a Hamiltonian of interest in the laboratory, and studying its properties experimentally (somewhat analogous to building a model of an aeroplane and studying it in a wind tunnel). This is often cited as the most promising near-term application of quantum computing technology, as (it is claimed) it does not require a scalable, fault-tolerant quantum computer. Indeed, Hamiltonian simulation is already being done in the laboratory. Adiabatic quantum computing can be viewed as a version of Hamiltonian simulation in which a continuous path of Hamiltonians is Simulated. Despite this, the theoretical basis for Hamiltonian simulation is surprisingly sparse. Even a precise definition of what it means to simulate a Hamiltonian has been lacking! By drawing on techniques from Hamiltonian complexity, we can put Hamiltonian simulation on a sound theoretical footing. In recent work (with de las Cuevas, Montanaro and Piddock) we then used this to prove that there exist simple universal spin models that are capable of simulating any other Hamiltonian Whatsoever. In the talk, I will focus mainly on the mathematically simpler classical case [de las Cuevas and Cubitt, Science (2016)]. If time allows, I will mention new results on the quantum case.

Title: What is the Computational Value of Finite Range Tunneling?

Abstract: Quantum annealing (QA) has been proposed as a quantum enhanced optimization heuristic exploiting tunneling. Here, we demonstrate how finite range tunneling can provide considerable computational advantage. For a crafted problem designed to have tall and narrow energy barriers separating local minima, the D-Wave 2X quantum annealer achieves significant runtime advantages relative to Simulated Annealing (SA). For instances with 945 variables, this results in a time-to-99%-success-probability that is ∼108 times faster than SA running on a single processor core. We also compared physical QA with Quantum Monte Carlo (QMC), an algorithm that emulates quantum tunneling on classical processors. We observe a substantial constant overhead against physical QA: D-Wave 2X again runs up to ∼108 times faster than an optimized implementation of QMC on a single core. We note that there exist heuristic classical algorithms that can solve most instances of Chimera structured problems in a timescale comparable to the D-Wave 2X. However, we believe that such solvers will become ineffective for the next generation of annealers currently being designed. To investigate whether finite range tunneling will also confer an advantage for problems of practical interest, we conduct numerical studies on binary optimization problems that cannot yet be represented on quantum hardware. For random instances of the number partitioning problem, we find numerically that QMC, as well as other algorithms designed to simulate QA, scale better than SA. We discuss the implications of these findings for the design of next generation quantum annealers.

Aram Harrow (MIT)

Title: Quantum Monte Carlo vs Tunneling in Adiabatic Optimization

Abstract: Can quantum adiabatic evolution solve optimization problems much faster than classical computers?  One piece of evidence for this has been their apparent advantage in "tunneling" through barriers to escape local minima.  However, I will argue that quantum Monte Carlo is at most polynomially slower than stoquastic quantum adiabatic optimization under a wide variety of settings. I will then discuss some prospects for demonstrating quantum supremacy with a near-term quantum computer. I will explain the difficulties in achieving this using adiabatic evolution and will explain the possibility of achieving this with low-depth quantum circuits.

Emile Hoskinson (D-Wave)

Title: Domain freeze-out in quantum annealing

Abstract: A domain of strongly coupled qubits can act as a logical qubit, but with a tunneling rate that is suppressed compared to that of a single isolated qubit. This tunneling rate depends strongly on the domain structure and internal coupling strength. In any given quantum annealing problem, multiple domains of different sizes and coupling strengths may form. The resulting inhomogeneity in tunneling rates and freeze-out times can reduce the probability of finding a ground state. I will describe measurements of several small structured example problems that illustrate how domain formation and tunneling rate inhomogeneity can develop. I will argue that synchronizing freeze-out times between domains, by adjusting the annealing path or the physical structure of a problem, can be an effective strategy for avoiding domain freeze-out error.

David Hover (MIT Lincoln Labs)

Title: Tunably Coupled High-Coherence Flux Qubit Architecture Suitable for Quantum Annealing

Abstract: Maintaining qubit coherence is a challenge when designing an extensible quantum computing architecture suitable for either gate-based quantum computing or quantum annealing. Recently, our group has demonstrated reproducible and long-lived capacitively shunted (C-shunt) flux qubits. Here, we discuss our efforts to develop a framework for tunably coupling these qubits using radio frequency (RF) SQUIDs.  Additionally, we experimentally investigate the coherence tradeoffs of this architecture, such as the geometry dependence of the qubit loop on flux noise and noise pickup from the RF SQUID coupler.  This research was funded by the Office of the Director of National Intelligence (ODNI), Intelligence Advanced Research Projects Activity (IARPA) and by the Assistant Secretary of Defense for Research & Engineering under Air Force Contract No. FA8721-05-C-0002. The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies or endorsements, either expressed or implied, of ODNI, IARPA, or the US Government.

Helmut Katzgraber (Texas A&M University)

Title: Quantum vs classical optimization: A status update on the arms race

Abstract: To date, a conclusive detection of quantum speedup remains elusive.  However, recent results from quantum Monte Carlo simulations, as well as the D-Wave 2X quantum annealer show a scaling that clearly outperforms state-of-the-art classical simulated annealing. In this talk an overview of recent benchmarks, as well as attempts to "tickle" any quantumness out of quantum annealing machines is given.  Furthermore, we present a generic framework to validate benchmarks and to detect parameter regimes where quantum annealing might excel over classical heuristics. As such, we provide capabilities to aide in the search for the "killer" application for quantum optimization technologies. Finally, an overview of different sequential, non-tailored, as well as specialized tailored classical state-of-the-art algorithms is given. Current quantum annealing technologies must outperform these to claim the crown in the race for quantum speedup.

Kostyantyn Kechedzhi (USRA)

Title: Multi-qubit quantum tunneling as a computational resource

Abstract: Multi-qubit quantum tunneling is a quantum effect which often determines the efficiency of relaxation of a quantum system. Quantum tunneling is particularly important near bottlenecks arising in the course of quantum annealing and quantum machine learning algorithms. Here we analyze the possible scenarios where quantum tunneling could give rise to speedup in comparison with classical analogs of the algorithms. In this work we focus on the quantum tunneling in presence of realistic noise including both the weak coupling regime and the effects of strong coupling and polaron shift on quantum tunneling. We also focus on the effect of exponential degeneracy of states on the dynamics of quantum system, which may result in non-trivial temperature dependence of the tunneling rate. Furthermore in presence of exponential degeneracy of states, sufficiently high rate of multi-qubit quantum tunneling drives a dynamical phase transition resulting in dramatic changes in the system's dynamics and efficiency of relaxation.

Wolfgang Lechner (University of Innsbruck)

Abstract: In this talk I will present an overview of recent ideas on parity adiabatic quantum computing, a scheme which has been introduced [1] as an alternative to the spin glass paradigm of quantum annealing. In this architecture, a optimization problem is encoded in local fields that act on an extended set of qubits in a constraint subspace. The constraints are problem independent 4-body interactions acting uniformly on all plaquettes of a square lattice. Using a general stabilizer formulation [2], the parity scheme can be implemented efficiently with odd parity constraints and may feature mixtures of differentlogical  k-local terms in a 2D setup. Classical error correction has been developed for uncorrelated noise [2] which is not applicable for other noise models [3].  The parity scheme allows one to implement quantum enhanced optimization protocols with the focus on coherent dynamics in various platforms, including Transmons [5], Rydberg atoms [6] and ions in surface traps. I will outline opportunities in applications such as training of a restricted Boltzmann machine.

Peter Love (Tufts University)

Title: Testing Adiabatic Quantum Computers Using Simple Quantum Simulation

Abstract: Validation of Adiabatic Quantum computers is a significant problem. One of the advantages of the  Adiabatic model is that it does not require the rapid pulsed controls necessary in the gate model of quantum computation. However, eschewing this level of control also makes state and process tomography impossible in purely adiabatic hardware, and hence the quantum nature (if any) of such devices has to be established by indirect evidence. In this talk I will describe how to use Adiabatic quantum computers based on the transverse-field Ising model to simulate elementary one-dimensional quantum systems, and discuss the quantum properties of the machines that can be exhibited by such simulations. I will also discuss how to detect the presence of one type of beyond-transverse-Ising coupling, namely the XX couplings of interest for non-stoquastic Adiabatic machines.

Guglielmo Mazzola (ETH Zurich)

Title: Quantum Monte Carlo simulations and Quantum Annealing

Abstract: The only computational method capable to simulate Quantum Annealing (QA) for realistic and large scale problems is Quantum Monte Carlo (QMC). In this talk I will discuss if QMC, at its finite-temperature path-integral level, can be representative of what happens inside a real QA device and how physical intuition may guide us to devise “Quantum Inspired” algorithms which may outperform existing ones. To this end we study how QMC simulations mimic quantum tunneling in both spin and continuous space models and how the tunneling scales with the size of the system and the shapes of the energy barriers.

Danna Rosenberg (MIT Lincoln Labs)

Title: 3D Integration for Superconducting Qubits

Abstract: As the field of superconducting quantum computing advances from the few-qubit stage to large-scale fault-tolerant devices, scalability requirements will necessitate the use of standard 3D packaging and integration processes. While the field of 3D integration is well-developed, relatively little work has been performed to determine the compatibility of the associated processes with superconducting qubits. Qubit coherence time could potentially be affected by required process steps, such as the deposition of extra metals for a flip-chip process, or by the proximity of an interposer that could introduce extra sources of charge or flux noise. As a first step towards a large-scale quantum information processor, we have used a flip-chip process to bond a chip with capacitively-shunted flux qubits to an interposer containing structures for qubit readout and control. I will present data on the impact of the interposer on qubit coherence time and discuss the implications for integrated multi-qubit devices. This research was funded by the Office of the Director of National Intelligence (ODNI), Intelligence Advanced Research Projects Activity (IARPA) and by the Assistant Secretary of Defense for Research & Engineering under Air Force Contract No. FA8721-05-C-0002. The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies or endorsements, either expressed or implied, of ODNI, IARPA, or the US Government.

Antonello Scardicchio (ICTP)

Title: The quantum spin glass transition on the regular random graph

Abstract: I will report on our work aimed at understanding the properties of the quantum spin glass transition (at zero temperature) of the Ising spin glass with transverse field.  We have performed a Montecarlo study of the properties of such transition, including the entanglement entropies and scaling of gaps. I will present a phenomenology of the transition which accounts for these observations and suggests an attack line for similar models arising from combinatorial optimization problems solved with the adiabatic algorithm. I will also comment on the connections of this phase transition with the many-body localization transition, if this occurs at lower values of the transverse field.

Wim van Dam (UC Santa Barbara)

Title: Merits and limitations of asymptotic analyses for quantum adiabatic optimization

Abstract: We look at the question to what extent numerical spectral gap calculations can be trusted to inform us about the asymptotic behavior of quantum adiabatic optimization. Conversely we also wonder if the asymptotics are useful to predict the efficiency of QAO for reasonably sized systems. These questions are analyzed for the optimization task of tunneling through a polynomially sized barrier. We show that this issue is more subtle than one might expect.

Contributed Talks

Evgeny Andriyash (D-Wave)

Title: Quantum Boltzmann Machine

Abstract: Machine learning is a rapidly growing field in computer science with applications in computer vision, voice recognition, medical diagnosis, spam filtering, search engines, etc. In this presentation, I will introduce a new machine learning approach based on quantum Boltzmann distribution of a transverse-field Ising Model. Due to the non-commutative nature of quantum mechanics, the training process of the Quantum Boltzmann Machine (QBM) can become non-trivial.  I will show how to circumvent this problem by introducing bounds on the quantum probabilities. This allows training the QBM efficiently by sampling. I will then show examples of QBM training with and without the bound, using exact diagonalization, and compare the results with classical Boltzmann training. Finally I will discuss the possibility of using D-Wave quantum annealing processors for QBM training and application.

Title: Towards quantum supremacy with pre-fault-tolerant devices

Abstract: A critical question for the field of quantum computing in the near future is whether quantum devices without error correction can perform a well-defined computational task beyond the capabilities of state-of-the-art classical computers, achieving so-called quantum supremacy. We study the task of sampling from the output distributions of random quantum circuits, a natural task for benchmarking quantum computers. Crucially this requires a direct numerical simulation to solve classically, with computational time and space cost exponential in the size of Hilbert space. This requirement is typical of chaotic systems.

We study the convergence to the chaotic regime using extensive supercomputer simulations, modeling circuits with up to 42 qubits - the largest quantum circuits simulated to date for a computational task that approaches quantum supremacy.

We show that while chaotic states are extremely sensitive to errors, quantum supremacy can be achieved in the near-term with approximately fifty superconducting qubits. We extend previous results to argue that performing this task with a fault tolerant quantum computer would have strong implications in computational complexity theory.   We introduce cross entropy as a useful benchmark of quantum circuits which approximates the circuit fidelity. We show that the cross entropy can be efficiently measured when circuit simulations are available. Beyond the classically tractable regime, the cross entropy can be extrapolated and compared with theoretical estimates of circuit fidelity to define a  practical quantum supremacy test.

Giuseppe Carleo (ETH Zurich)

Title: Accurate Description of Adiabatic Quantum Optimization for a Large Number of Qubits

Abstract: Adiabatic quantum optimization (AQO) is a quantum computing protocol where a system is driven by a time-dependent Hamiltonian. The initial Hamiltonian has an easily prepared ground-state and the final Hamiltonian encodes some desired optimization problem. Adiabatic evolution then yields a solution to the optimization problem. Several challenges emerge in the theoretical description of this protocol: on one hand, the exact simulation of quantum dynamics is exponentially complex in the size of the optimization problem. On the other hand, approximate approaches such as tensor network states (TNS) are limited to small instances by the amount of entanglement that can be encoded.

I will present here an extension of the time-dependent Variational Monte Carlo approach to problems in AQO. This approach is based on a general class of (Jastrow-Feenberg) entangled states, whose parameters are evolved in time according to a stochastic variational principle. We demonstrate this approach for optimization problems of the Ising spin-glass type.

A very good accuracy is achieved when compared to exact time-dependent TNS on small instances.

We then apply this approach to larger problems, and discuss the efficiency of the quantum annealing scheme in comparison with its classical counterpart.

Bela Bauer (Station Q, Microsoft Research, UCSB), Matthias Troyer (Theoretical Physics and Station Q Zurich, ETH Zurich)

Nicholas Chancellor (Durham University)

Title: max-k-SAT, multi-body frustration, and multi-body sampling on a two local Ising system

Abstract: For some time it has been known how to encode satisfiability (SAT) problems and the physics analogue of finding the ground state of a frustrated spin system onto a two local Ising spin model. These previous constructions however do not necessarily yield the statement which satisfies the maximum number of clauses as the ground state (max-SAT), in the language of physics, they did not support frustration of the multi-body terms. Furthermore, the inability to accurately describe frustration means that these methods cannot be used for thermal sampling. We propose a new method of encoding problems which does support max-SAT, frustration, and sampling. I will describe this method in detail, and show how a recent coupling proposal by a different group for unfrustrated Ising couplings is also compatible with frustration and can be made compatible with sampling applications. I will than discuss applications of our method including, direct embedding of max-SAT problems on a chimera graph, optimization with non-linear constraints, and particle simulation.

Stefan Zohren, Oxford University, Paul Warburton, UCL, Simon Benjamin, Oxford University, Stephen Roberts, Oxford University

Nike Dattani (Oxford & Kyoto University)

Title: Three new ways to reduce multi-qubit interactions in AQC without adding auxiliary qubits

Abstract: If you were to take a picture of a map, and then throw away the paper copy, but only later discover that the picture was too blurry to read the street names, what can you do to recover the lost information without the original? We show that our denoising algorithm based on optimizing pixel improvements based on a neural-network trained by comparing millions of blurred images to their unblurred counterparts shows unprecedented accuracy and spectacular performance on a smartphone, but is slow for solar system observations from the S.A.L.T. telescope. We compare this performance with quantum annealing, and we showcase the crucial step of turning the original Hamiltonian with 4-qubit interactions into a 2-local Hamiltonian with the same ground state *and* the same number of qubits.

We likewise introduce for the first time, Hamiltonians whose ground states can be used to determine multi-color and dircted-graph Ramsey numbers, and our extensions of our previous Hamiltonians for integer factorization. We present the Hamiltonians for factoring RSA-220 (a number which no classical computer has yet factored) and for finding a Ramsey number which still remains unknown: R(3,3,4).

In all three applications, we show how our methods "deduc-reduc", "split-reduc", and "ELM" can be used to map the multi-qubit Hamiltonians into simple Hamiltonians which are compatible with current AQC technology, *without* adding auxiliary qubits, or with significantly fewer qubits than previous methods would allow.  The third of these methods (ELM = Energy Landscape Manipulation) allows for the energy gap to be increased without raising the spectral width, without adding auxiliary qubits, and without tampering with the desired ground state.

Richard Tanburn (Oxford University), Emile Okada (Cambridge University, Kyoto University), Toby Cathcart-Burn (Oxford University), Oliver Lunt (Oxford University), Pankaj Gupta (Kyoto University, and Indian Institute of Technology), Nike Dattani (Oxford University, Kyoto University)

Adolfo del Campo (University of Massachusetts)

Title: Driving spin systems with noisy control fields: limits to adiabatic protocols

Abstract: We consider driving a thermally isolated system across a quantum phase transition by a noisy control field. At variance with the defect suppression under slow noise-free driving predicted by the Kibble-Zurek mechanism, we show that in the presence of external noise in the control, the system may exhibit an anti-Kibble-Zurek behavior, where slower driving results in a higher density of excitations at the end of the process. For the transverse field Ising model, we show that the noise-averaged dynamics is effectively described by a purely dephasing Lindbladian. Exploiting this connection, we find the density of defects as a function of the quench rate and the noise strength and determine the optimal driving time for defect suppression, which scales as universal power of the  noise amplitude. Our findings show the limitation of adiabatic protocols imposed by noise in the control fields and motivates the use of shortcuts to adiabaticity as an alternative.

Armin Rahmani, University Of British Columbia, Anirban Dutta, University of Massachusetts

David Ferguson (Northrop Grumman)

Title: Enabling Components for Quantum Enhanced Optimization: Past and Future

Abstract: Northrop Grumman Corporation is a world leader in ultra-low power superconducting computing technology which has been recognized by IARPA as a strong contender for post-CMOS exascale computing.  Northrop Grumman also carries out basic research in superconducting quantum technologies including qubit design, readout, and control technologies.  This talk will describe our past work on distributed qubits which enable high connectivity architectures.  It will also describe on-chip microwave routing and logic technologies which are essential enabling components for future quantum annealing applications.

Kenneth Zick (Northrop Grumman), Anthony Przybysz (Northrop Grumman), Ofer Naaman (Northrop Grumman), Aaron Pesetski, (Northrop Grumman)

Stefan Fillip (IBM Research)

Title: Controlled interactions between superconducting qubits for adiabatic quantum simulations

Abstract: The controlled realization of different types of interactions between qubits without compromising their coherence is essential for adiabatic and analog quantum simulations. In the context of superconducting quantum circuits, highest coherence has been achieved with qubits operated at a fixed frequency. This strategy avoids extra noise-sensitive controls, e.g. via SQUID loops, but inhibits controllable resonant interactions. Here, we present a coupling method between fixed-frequency transmon qubits based on the frequency modulation of an auxiliary capacitively coupled quantum bus. Different types of interactions, such as transverse XX- and YY-type interactions, and longitudinal ZZ-type interactions can be realized by an appropriate choice of the modulation frequency. Since the coupling bus remains in its ground state at all times, its coherence does not significantly influence the fidelity of gate operations resulting in iSWAP gate fidelities of 98%. With the possibility to simultaneously create interactions along different directions, this scheme is suited to engineer Hamiltonians with adjustable coupling terms, for instance to simulate fermionic quantum systems.

N. Moll, IBM Research - Zurich, Switzerland, M. Roth, IBM Research - Zurich, Switzerland, I. Tavernelli, IBM Research - Zurich, Switzerland, A. Fuhrer, IBM Research - Zurich, Switzerland, P. Mueller, IBM Research - Zurich, Switzerland, D. McKay, IBM T. J. Watson Research Center, Yorktown Heights, US, Antonio Mezzacapo, IBM T. J. Watson Research Center, Yorktown Heights, US, Easwar Magesan, IBM T. J. Watson Research Center, Yorktown Heights, US, J. Chow, IBM T. J. Watson Research Center, Yorktown Heights, US, J. Gambetta, IBM T. J. Watson Research Center, Yorktown Heights, US

Kathleen Hamilton (Oak Ridge National Laboratory)

Title: Integrated QPU - CPU programming: parallelized minor embedding and parameter setting framework

Abstract: We discuss progress made in the development of an integrated QPU-CPU programming library (QUELLE) that incorporates adiabatic quantum processing units into existing high performance computing paradigms. The primary function of QUELLE is to facilitate split computation (the distribution of computation across CPU and QPU cores) by providing access to pre-processing and post-processing steps  that are needed to program an adiabatic QPU. These steps include: minor embedding, parameter setting, and statistical filtering functions. QUELLE also provides run-time management of the split-execution system and facilities its interaction with other parts of the host system, which may support a distributed computing model. We leverage the extensibility of QUELLE to investigate performance improvements using new embedding methods, including hard fault-tolerant embeddings of a logic graph based on the method of pre-computed maximal minors, and distributed graph processing libraries.

Jonathan Schrock (Oak Ridge National Laboratory), Alex McCaskey (Oak Ridge National Laboratory), Travis S. Humble (Oak Ridge National Laboratory), Neena Imam (Oak Ridge National Laboratory)

Layla Hormozi (MIT)

Title: Coupled Quantum Fluctuations and Quantum Annealing

Abstract: We study the relative effectiveness of stoquastic and non-stoquastic Hamiltonians consisting of coupled quantum fluctuations compared to Hamiltonians with single spin flips in the performance of quantum annealing. We focus on problem Hamiltonians resembling the Sherrington-Kirkpatrick model of Ising spin glass and examine the performance of different types of driver Hamiltonians with coupled fluctuations by numerically calculating the success probabilities and minimum gaps in systems of up to 20 spins. We find that both stoquastic and non-stoquastic Hamiltonians with coupled fluctuations can provide improvement over Hamiltonians with single spin flips. However, the effectiveness of each driver Hamiltonian and the relation between success probability and the properties of minimum gaps suggest different mechanisms behind their performance.

Itay Hen (ISI)

Title: Classical modeling of quantum tunneling

Abstract: Tunneling is widely believed to be the main advantage quantum annealers have over their classical counterparts.

With neither provable speedups nor no-go theorems demonstrated, the true power of quantum annealers remains debated.

In this talk, I will present preliminary results of numerical simulations of simple classical algorithms that contest, at least to some extent, the belief that quantum tunneling is an important resource.

Tameem Albash, USC, Peter Young, UCSC

Zhang Jiang (NASA Ames)

Title: Scaling analysis and instantons for thermally-assisted tunneling and Quantum Monte Carlo simulations

Abstract: We develop an instantonic calculus to derive an analytical expression for the thermally-assisted tunneling decay rate of a metastable state in a fully connected quantum spin model. The tunneling decay problem can be mapped onto the Kramers escape problem of a classical random dynamical field. This dynamical field is simulated efficiently by path integral Quantum Monte Carlo (QMC). We show analytically that the exponential scaling with the number of spins of the thermally-assisted quantum tunneling rate and the escape rate of the QMC process with periodic boundary conditions are identical. We relate this effect to the existence of a dominant instantonic tunneling path. The instanton trajectory is described by nonlinear dynamical mean-field theory equations for a single site magnetization vector, which we solve exactly. Finally, we derive scaling relations for the spiky barrier shape when the spin tunneling and QMC rates scale polynomially with the number of spins N while a purely classical over-the-barrier activation rate scales exponentially with N.

Stephen Jordan (NIST)

Title: Adiabatic Quantum Computing vs. Diffusion Monte Carlo

Abstract: While adiabatic quantum computation using general Hamiltonians has been proven to be universal for quantum computation, the vast majority of research so far, both experimental and theoretical, focuses on stoquastic Hamiltonians. Conventional wisdom amongst Monte Carlo practitioners states that Monte Carlo simulations of stoquastic adiabatic computation will not suffer from the sign problem and will therefore converge efficiently. If this could be turned into a theorem it would prove that stoquastic adiabatic computers are incapable of exponential speedup over classical computation. The two major classes of Monte Carlo simulation algorithms are path integral Monte Carlo and diffusion Monte Carlo. In 2013, Hastings constructed a class of counterexamples in which path integral Monte Carlo will fail to efficiently simulate stoquastic adiabatic dynamics due to topological obstructions. Diffusion Monte Carlo algorithms should not be affected by topological obstructions. We are nevertheless able to construct a counterexample in which a non-topological obstruction prevents diffusion Monte Carlo from efficiently simulating a stoquastic adiabatic process. On typical instances such simulations may nevertheless work well. In fact, we introduce a new variant of diffusion Monte Carlo, which we call Substochastic Monte Carlo, tailored to simulating stoquastic adiabatic processes. In practice, we find that this performs so well that our Monte Carlo simulations of adiabatic optimization are good classical optimization heuristics in their own right, competitive with the best previous known heuristic solvers for Max-kSAT at k=2,3,4.

Michael Jarret, Joint Center for Quantum Information and Computer Science, University of Maryland, Brad Lackey, Joint Center for Quantum Information and Computer Science, University of Maryland

Andrew King (D-Wave Systems)

Title: Diagnosing and mitigating first-order quantum phase transitions

Abstract: In certain random problem sets, both QA and SQA show very low ground state probability on a small subset of instances.  This phenomenon has been identified variously as a bimodal distribution, a heavy-tailed distribution, and a failure to show speedup on hard problems.  The computational bottleneck: first-order quantum phase transitions, arising from the extreme degeneracy inherent in these random problems.  We show that this phenomenon is very sensitive to small changes in the qubit connectivity graph, and can be eliminated when local degeneracy is suppressed in this way.  A theoretical and empirical study of small instances demonstrates that we can mitigate these bottlenecks by running a quantum annealing system with different parameter values than those suggested by prevailing wisdom.

Mohammad Amin, D-Wave Systems, Evgeny Andriyash, D-Wave Systems, Emile Hoskinson, D-Wave Systems, Trevor Lanting, D-Wave Systems

Sergey Knysh (NASA Ames)

Abstract: Here I will present an alternative description of adiabatic evolution and the Landau-Zener formula. In this formulation, the energy levels are effectively ""renormalized"" as the rate of annealing is ramped up. Evolution of the unitary matrices corresponding to the change of basis is obtained in part by solving a partial differential equation of elliptic type; their asymptotic behavior determines the ultimate success probability.

This analysis is extended to (and contrasted with) the case of non-unitary evolution, such as simulated annealing. Unlike quantum annealing, where the complexity can be inferred from the spectrum, formulating the appropriate condition for its classical counterpart has proved more challenging. It can also be relevant for noisy annealing.

Oleksandr Kyriienko (Niels Bohr Institute)

Title: Floquet quantum annealing with superconducting circuits

Abstract: The successful application of a quantum annealing procedure largely relies on the possibility to implement a non-trivial Hamiltonian in a fully controlled system. The circuit QED platform has shown a tremendous progress in this direction, demonstrating qubit chains with on-site effective magnetic fields being tunable in time along any chosen axis. At the same time, the inter-qubit interaction is typically limited to the isotropic XY model with nearest neighbor flip-flop process, which limits accessible types of Hamiltonian which can be simulated. Typically, surmounting of this restriction requires either construction of unconventional couplings between qubits or digitization of the evolution.

We propose to use Floquet dynamics to perform a quantum simulation with superconducting system. The algorithm relies on fast time modulation of an effective magnetic field for the qubits, such that the resulting time-averaged Floquet Hamiltonian is of the generic Heisenberg XYZ type, and is controllable by the drive parameters. As examples we show recipes for designing transverse Ising and non-stoquastic XYZ Hamiltonians, and perform annealing to the ground state of each configuration. Considering realistic parameters the procedure allows closely following the ideal continuous annealing, yielding a fidelity corresponding to the one achievable by digital evolution with many (>20) Trotter steps.

The scheme does not require modification of existing circuit QED setups, potentially allows for diverse high fidelity quantum annealing with currently accessible system parameters, and can serve as simple yet reliable way towards quantum annealing with limited resources.

Anders S. Sørensen, Niels Bohr Institute

Trevor Lanting (D-Wave Systems, Inc)

Title: Techniques for modifying annealing trajectories in quantum annealing processors

Abstract: A single fixed annealing trajectory for all devices in a quantum annealing processor may not be the correct choice for a particular instance posed to the system. For particular optimization problems, modifying the global annealing trajectory or modifying the annealing path on a per-qubit basis may boost performance. We discuss modifications to the annealing trajectory and limited per-qubit control of the annealing path that are feasible on existing quantum annealing systems. We show that these modifications, when combined with algorithmic methods for identifying local degeneracy, can be effective at boosting problem performance on some small tailored instances.

Evgeny Andriyash, D-Wave, Mohammad H. Amin , D-Wave, Simon Fraser University, Bram Evert, D-Wave, Emile Hoskinson, D-Wave, Andrew D. King, D-Wave, Yuki Sato, D-Wave

Salvatore Mandra (Harvard University/NASA Ames)

Title: Strengths and Weaknesses of Weak-Strong Cluster Problems: A Detailed Overview of State-of-the-art Classical Heuristics vs Quantum Approaches

Abstract: To date, a conclusive detection of quantum speedup remains elusive. Recently, a team by Google Inc. [arXiv:1512.02206] proposed a weak-strong cluster model tailored to have tall and narrow energy barriers separating local minima, with the aim to highlight the value of finite-range tunneling. More precisely, results from quantum Monte Carlo simulations, as well as the D-Wave 2X quantum annealer scale considerably better than state-of-the-art simulated annealing simulations. Moreover, the D-Wave 2X quantum annealer is ∼10^8 times faster than simulated annealing on conventional computer hardware for problems with approximately 10^3 variables. Here, I will give an overview of different sequential, nontailored, as well as specialized tailored algorithms on the Google instances. I will show that the quantum speedup is limited to sequential approaches and study the typical complexity of the benchmark problems using insights from the study of spin glasses.

Salvatore Mandra, Harvard University, Zheng Zhu, Texas A&M University, Wenlong Wang, Texas A&M University, Alejandro Perdomo-Ortiz, NASA Ames Research Center/University of California Santa Cruz, Helmut G. Katzgraber, Texas A&M University/Santa Fe Institute/Coventry University

Title: Roadmap for building a quantum computer
Abstract: I will overview the basic strategy and roadmap for the quantum-AI project at Google, which has the goal of building a useful quantum computer. For hardware, the key metric is building scalable qubits with 2-qubit gate errors below 0.1-0.2% [J.M.Martinis, NPJQI 1, 15005 (2015)]. For software, I will describe a new "quantum-supremacy" test that can demonstrate the exponential power of a quantum processor by checking its output with a classical computer, which is intractable for even the world's most advanced classical supercomputer beyond 42-50 qubits. We are working to perform this experiment in the next 2 years.

Robert McDermott (University of Wisconsin)

Title: Origin and Suppression of 1/f Magnetic Flux Noise

Abstract: Magnetic flux noise is a dominant source of dephasing and energy relaxation in superconducting qubits. The noise power spectral density varies with frequency as 1/f and spans 13 orders of magnitude. Recent work indicates that the noise is from unpaired magnetic defects on the surfaces of the superconducting devices. Here, we demonstrate that adsorbed molecular oxygen is the dominant contributor to magnetism in superconducting thin films. We show that this magnetism can be suppressed by appropriate surface treatment or improvement in the sample vacuum environment. We observe a suppression of static spin susceptibility by more than an order of magnitude, and a suppression of 1/f magnetic flux noise power spectral density by more than a factor of 5. These advances open the door to realization of superconducting qubits with improved quantum coherence.

P. Kumar, U. Wisconsin, S. Sendelbach, U. Wisconsin, M. A. Beck, U. Wisconsin, J. W. Freeland, Argonne Natl. Lab, Z. Wang, UC-Irvine, H. Wang, UC-Irvine, C. C. Yu, UC-Irvine

R. Q. Wu, UC-Irvine, D. P. Pappas, NIST Boulder

Peter McMahon (Stanford)

Title: A fully-programmable measurement-feedback OPO Ising machine with all-to-all connectivity

Abstract: An annealing machine for solving binary combinatorial optimization problems using networks of OPOs was demonstrated with 4 OPOs in 2014 [1]. We have recently extended this concept in two ways: firstly we have realized a network of 100 OPOs, and secondly we have used a measurement-feedback-based scheme to allow coupling of any OPO to any other OPO, allowing the realization of all-to-all couplings in an Ising Hamiltonian.

In this presentation, we will outline the design of our experimental apparatus, and show results of trying to find ground states of various Ising problem instances with up to 100 spins and 10,000 connections.

[1] A. Marandi, et al. doi:10.1038/nphoton.2014.249

Peter McMahon (Stanford University), Alireza Marandi (Stanford University), Yoshitaka Haribara (NII), Ryan Hamerly (Stanford University), MM Fejer (Stanford University), Hideo Mabuchi (Stanford University), Yoshihisa Yamamoto (Stanford University and JST)

Title: Inhomogeneous quasi-adiabatic driving of quantum critical dynamics

Abstract: We introduce an inhomogeneous protocol to drive a weakly disordered quantum spin chain quasi-adiabatically across a quantum phase transition and minimize the residual energy of the final state. The number of spins that simultaneously reach the critical point is controlled by the length scale of the inhomogeneity in which the magnetic field is modulated, introducing an effective size that favors adiabatic dynamics.

The dependence of the residual energy on this length scale and the velocity at which the magnetic field  sweeps out the chain is shown to be nonmonotonic. We determine the conditions for an optimal suppression of the residual energy of the final state and show that inhomogeneous driving can outperform conventional adiabatic schemes based on homogeneous control fields by  several orders of magnitude.

Masayuki Ohzeki (Kyoto University)

Title: Avoiding negative sign problem in simulation of quantum annealing

Abstract: We invent a novel technique to implement the XX-type interaction, which exhibits the negative sign problem in the standard way of the quantum Monte-Carlo simulation, as well as the transverse field.

The method utilizes the auxiliary transverse field which adaptively changes its strength according to the value of the transverse magnetization.

Our proposed method enables us to perform the quantum Monte-Carlo simulation for various models and implement Belief Propagation in quantum spin models.

The former paves a way to simulate the quantum annealing in wider range of the quantum fluctuations.

The latter provides another way to exploits the quantum fluctuation in the various computer science problems as the error-correcting codes, signal processing, compressed sensing, machine learning and so on.

We confirms the validity of our method in the simple model with the anti-ferro magnetic interactions in x directions and the mean-field analysis of the Gaussian-noise channel model (CDMA) with the transverse field and so on.

In the future, we aim at observation of the boundary between the limitation of the classical and quantum computations via our method.

Alejandro Perdomo-Ortiz (NASA Ames Research Center)

Title: A quantum-assisted algorithm for sampling applications in machine learning

Abstract: An increase in the efficiency of sampling from Boltzmann distributions would have a significant impact in deep learning and other machine learning applications. Recently, quantum annealers have been proposed as a potential candidate to speed up this task, but several limitations still bar these state-of-the-art technologies from being used effectively. One of the main limitations is that, while the device may indeed sample from a Boltzmann-like distribution, quantum dynamical arguments suggests it will do so with an instance-dependent effective temperature, different from its physical temperature. Unless this unknown temperature can be unveiled, it might not be possible to effectively use a quantum annealer for Boltzmann sampling. In this work, we propose a strategy to overcome this challenge with a simple effective-temperature estimation algorithm. We provide a systematic study assessing the impact of the effective temperatures in the learning of a kind of restricted Boltzmann machine embedded on quantum hardware, which can serve as a building block for deep learning architectures. We also provide a comparison to k-step contrastive divergence (CD-k) with k up to 100. Although assuming a suitable fixed effective temperature also allows to outperform one step contrastive divergence (CD-1), only when using an instance-dependent effective temperature, we find a performance close to that of CD-100 for the case studied here. I will discuss our recent progress in unsupervised learning beyond restricted Boltzmann machines and larger datasets than those considered in our original contribution (see arXiv:1510.07611).

M. Benedetti (NASA Ames), J. Realpe-Gomez (NASA Ames), R. Biswas (NASA Ames)

Andre G. Petukhov (NASA Ames)

Title: Low Frequency Noise and Inhomogeneous Spin Diffusion in Superconducting Flux Qubits

Abstract: We present theoretical study of geometrical effects related to spin diffusion in superconducting flux qubits. We adopt a model of a long superconducting wire with arbitrary distribution of spins across its surface. Using a continuous transformation from a round cylinder to a flat wire strip, we demonstrate that the noise spectral density tends to a power law $S(\omega)\propto (\omega/\Gamma)^{-s}$ with $s < 1$. The \omega^{-s}$dependence is valid in a broad frequency range above$\omega\agt\Gamma$stretching up to several orders of magnitude in units of characteristic diffusion decay rate$\Gamma \sim 1- 10^2$Hz. The effect is highly sensitive to a cross-sectional aspect ratio of a thin wire thus revealing its geometrical origin. We substantiate our findings by detailed comparison with available experimental data and attribute$\omega^{-s}$power law with$s<1\$ to segregation of spins near edges and to quenched disorder of the static spin density.

Gili Rosenberg (1QBit)

Title: Boosting quantum annealer performance via quantum persistence

Abstract: We propose a novel method for reducing the number of variables in quadratic unconstrained binary optimization problems, using a quantum annealer to fix the state of a large portion of the variables to values with a high probability of being optimal. The method significantly increases the success rate when compared with calling the quantum annealer without using it. The results can be further enhanced by applying the method iteratively or combining it with classical pre-processing. We present results for both Chimera graph-structured problems and embedded problems from real-world applications.

Hamed Karimi, 1QB Information Technologies (1QBit)

Aidan Roy (D-Wave)

Title: Locally-structured embedding: an alternative approach to mapping constrained optimization problems to noisy quantum annealing processors

Abstract: Current and future quantum annealing processors suffer from practical limitations including finite temperature, sparse connectivity, small qubit numbers, and control error. In this talk we propose new techniques for mapping boolean constraint satisfaction problems (CSPs) onto annealing processors so as to mitigate these limitations. In particular we propose a new algorithm for locally-structured embedding, in which processor-compatible Ising models are generated for each problem constraint, and variables appearing in different constraints are chained together using ferromagnetic couplings.  We give an example of a class of CSPs for which the scaling performance of the D-Wave 2X system (DW2X) using local mapping is significantly better than the more commonly used global embedding strategy. As an application of our approach, we apply the DW2X system to the problem of sampling min-faults in circuit-based fault-diagnosis. For circuits that embed directly, we find that despite not sampling ground states uniformly, the system is typically able to find all solutions from a min-fault diagnosis set of size N using 1000N samples, using an annealing rate that is 25 times faster than a leading SAT-based sampling method. For larger problems, we apply decomposition algorithms to find min-faults for circuits that are up to 5 times larger than can be solved directly on current processors. This talk is based on http://arxiv.org/abs/1603.03111.

Zhengbing Bian (1), Fabian Chudak (1), Robert Israel (1), Brad Lackey (2), William G. Macready (1)

(1) D-Wave Systems Inc.

(2) Joint Institute for Quantum Information and Computer Science, University of Maryland

Title: Quantum annealing via environment-mediated quantum diffusion

Abstract: We show that quantum diffusion near the quantum critical point can provide an efficient mechanism of quantum annealing.  It is based on the diffusion-mediated recombination of excitations in open systems far from thermal equilibrium.  We find that, for an Ising spin chain coupled to a bosonic bath and driven by a monotonically decreasing transverse field, excitation diffusion sharply  slows down  below the quantum critical region. This leads to spatial correlations and effective freezing of the excitation density. Still, obtaining an approximate solution of an optimization problem via the diffusion-mediated quantum annealing can be faster than via closed-system quantum annealing or Glauber dynamics.

Rolando Somma (Los Alamos National Laboratory)

Title: Quantum Algorithms for Computing Partition Functions

Abstract: We provide a quantum algorithm to compute the partition function of a quantum system. Our algorithm runs in time proportional to the thermalization time and the inverse of the target accuracy. This is a significant improvement with respect to other quantum algorithms that solve the same problem. Our methods are based on recent techniques for adiabatic state transformations, spectral gap amplification, Hamiltonian simulation, and quantum metrology.

Maxim Vavilov (University of Wisconsin - Madison)

Title: Tunable dissipative elements for thermalization of qubit systems based on resistance shunted Josephson junctions

Abstract: We propose a design of Josephson junction-based tunable dissipators that allow strong damping to be switched on and off on nanosecond timescales.  These tunable damped modes can be used to properly initialize the qubit array and to ensure that the qubits remain in the ground state throughout the annealing schedule.  In this talk, we present a theoretical model of high-quality quantum circuits connected to such dissipators and discuss regime of optimal parameters for reliable and fast preparation of a qubit system in the ground state before the start of an annealing protocol.

Maxim Vavilov, University of Wisconsin - Madison, Clement Wong, Laboratory of Physical Sciences, University of Maryland, Susan Coppersmith, University of Wisconsin - Madison, Robert McDermott, University of Wisconsin - Madison

Walter Vinci (USC)

Title: An Optimal Stopping Approach for Benchmarking Probabilistic Optimizers

Abstract: We propose a strategy for benchmarking probabilistic optimizers based on an optimal stopping approach. We seek to optimize both the objective function and the number of calls to the solver. A crucial advantage of the figure of merit we propose is that it can be defined without knowledge of the global minimum. This allows for benchmarking hard optimization problems when it is not possible to use the time-to-solution metric. It can also be seen as a generalization of time-to-target approaches which avoids the introduction of possible biases due the choice of the target. We present our ideas by performing benchmarking experiments using both classical optimization algorithms and a DW2X quantum optimizer.

Daniel Lidar, University of Southern California

Paul Warburton (UCL)

Title: Going Beyond Two-Body Interactions in a Superconducting Flux Qubit Annealer

Abstract: A major difficulty in encoding optimization problems in physical quantum annealing devices is the fact that many real world optimisation problems require interactions of higher connectivity as well as multi-body terms beyond the current limitations of the physical hardware. In this work we address the question of how to implement multi-body interactions (ZZZ and higher) using hardware which natively only provides two-body (ZZ) interactions. The main result is an efficient circuit design of such multi-body terms using superconducting flux qubits [1]. It is then shown how this circuit can be used as the unit cell of a scalable architecture by applying it to a recently proposed embedding technique [2] for constructing an architecture of logical qubits with arbitrary connectivity using physical qubits which have nearest-neighbour four-body interactions.

[1] Chancellor et al., arXiv:1603.09521

[2] Lechner et al., Science Adv. 1 1500838

Nicholas Chancellor, University of Durham, Stefan Zohren, University of Oxford, Mohamed Sherif Ibrahim, University College London

Zheng Zhu (Texas A&M University)

Title: Predicting quantum tunneling advantage in random spin-glass and application problems

Abstract: Because of strong evidence that native random spin-glass problems are not well suited for benchmarking purposes, recent efforts in the search for quantum speedup have shifted to tailored problems, such as the carefully-crafted Google Inc.'s weak-strong clusters model.  Here we present a post-selection framework to detect subclasses of random problems where quantum annealing might excel over classical heuristics. We illustrate our approach with native random spin-glass instances, as well as instances from circuit fault diagnosis. Large-scale Monte Carlo simulations of these instance classes show that problems with thin and tall energy barriers are best suited for quantum annealing to excel. This also means that we now possess the capability to predict if a particular application domain will benefit from quantum optimization. Alexander Feldman (Xerox PARC), Sergei Isakov (Google Inc.), Helmut G. Katzgraber (Texas A&M University), S. Mandra (Harvard University), H. Munoz-Bauza (Texas A&M University), A. Ochoa (Texas A&M University),  Asier Ozaeta (QC Ware), A. Perdomo-Ortiz (NASA).