Session S28: Quantum Annealing: Algorithms & Applications

Universal quantum computation in thermal equilibrium

Adiabatic quantum computation (AQC) is a method for performing universal quantum computation in the ground state of a slowly evolving local Hamiltonian, and in an ideal setting AQC is known to capture all of the computational power of the quantum circuit model. However, despite having an inherent robustness to noise as a result of the adiabatic theorem and the spectral gap of the Hamiltonian, it remains a longstanding theoretical challenge to show that fault-tolerant AQC can in principle be performed below some fixed noise threshold. There are many aspects to this challenge, including the difficulty of adapting known ideas from circuit model fault-tolerance as well as the need to develop an error model that is appropriately tailored for open system AQC. In this talk I will introduce a scheme for combining Feynman-Kitaev history state Hamiltonians with topological quantum error correction, in order to show that universal quantum computation can be encoded not only in the ground state but also in the finite temperature Gibbs state of a local Hamiltonian. Using only local interactions with bounded strength and a polynomial overhead in the number of qubits, the scheme is designed to serve as a proof of principle that universal AQC can be performed at non-zero temperature, and also to further our understanding of the complexity of highly entangled quantum systems in thermal equilibrium.   

Quantum Annealing on Glued Trees: Tunneling and Noise

We analyze the quantum annealing algorithm for the glued-trees problem [PRL, 109, 050501]. This is an oracle problem which has a provable exponential speedup over the best possible classical algorithm. We show that the quantum dynamics of the quantum anneal admit a tunneling description. We further analyze the effect of an additive random matrix noise model [PRA 71, 032330] on the annealing dynamics. We answer the question: How should the strength of the noise and the anneal-time scale with problem size in order to obtain a sufficiently high probability of success?   

Fast quantum annealing protocol for Ising Hamiltonian with strong random field

An individual qubit can be driven fast from one configuration of its Hamiltonian to another without generating transitions by choosing a proper path in the configuration space [M.V. Berry, J. of Physics A 42, 365303 (2009)]. We apply this technique to a system of qubits that is initially described by the non-interacting Hamiltonian of spin 1/2 particles in a uniform magnetic field along x-direction and is transformed to the system described by the Ising Hamiltonian with random field in z-direction. For the limit of strong disorder, the single-qubit correction terms significantly enhance the probability for the whole system to remain in the ground state for the proposed non-stoquastic annealing protocol. We demonstrate that even when transitions occur for stronger interaction between qubits, the most probable quantum state is one of the lower energy states of the final Hamiltonian.   

A Scalable and Tunable Approach to Plant Spin-Glass Solutions

We present an efficient, scalable approach that allows one to construct spin-glass instances with planted solutions and tunable hardness. Here, we demonstrate our method for square lattices. Frustrated cycles are constructed via corner-sharing spins on lattice building blocks such that they share a common local ground state, which guarantees that the ground state energy of the entire problem is known a priori. Using population annealing Monte Carlo, we compare the computational complexity of planted problems across a multiplicity of instance classes that results from the numerous ways in which the frustrated cycles can be chosen. Our method offers significant advantages over previous approaches for planting solutions in that it is easy to implement, the problems have tunable hardness, and it requires no computational overhead.   

Demonstration of a scaling advantage for a quantum annealer over simulated annealing

A complete determination of the optimal time-to-solution (TTS) using the D-Wave quantum annealing processors has not been possible to date, preventing definitive conclusions about the presence of a scaling advantage. The main technical obstacle has been the inability to verify an optimal annealing time within the available range. Here we overcome this obstacle and present a class of problem instances for which we observe an optimal annealing time using a D-Wave 2000Q processor. This allows us to perform an optimal TTS benchmarking analysis and perform a comparison to several classical algorithms, including simulated annealing, spin-vector Monte Carlo, and discrete-time simulated quantum annealing. We establish the first example of a scaling advantage for an experimental quantum annealer over simulated annealing, with 95% confidence, over the range of problem sizes that we can test. However, we do not find evidence for a quantum speedup: simulated quantum annealing exhibits the best scaling by a significant margin.   

Performance of Quantum Annealers on Hard Scheduling Problems

We analyze the performance of three generations of quantum annealers (housed at NASA Ames), D-Wave Two, 2X and 2000Q, on hard scheduling problems. We quantify the improvements of each generation in both absolute time-to-solution and scaling of the time-to-solution with respect to problem sizes. We examined the contributions to this improvement, including the effect of hardware improvements and of the shorter anneal times available on the more recent annealers. We also examined how stronger or weaker ferromagnetic couplings enforcing constraints within vertex models (physical qubits representing the same logical qubit after embedding) affect performance. Our results offer insights about how future quantum annealers can be designed and programmed to be more effective at solving pragmatic optimization problems like the scheduling problems.   

A deceptive step towards quantum speedup detection

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 DW2000Q quantum annealing machine. While there is a sizable constant speedup over all known classical heuristics, a noticeable improvement in the scaling remains elusive. These results represent the first steps towards a detection of potential quantum speedup, albeit without a scaling improvement and for synthetic benchmark problems.   

Solving a Higgs detection optimization problem with quantum annealing for machine learning

The discovery of Higgs-boson decays in a background of standard-model processes was assisted by machine learning methods. The classifiers used to separate signal from background are trained using high quality but imperfect simulations of the physical processes involved, resulting in systematic errors. Here we use quantum and simulated annealing to solve this binary classification problem, mapped to the problem of finding the ground state of a corresponding Ising spin model. We build a set of weak classifiers based on the kinematic observables of the Higgs decay photons, which we then use to construct a strong classifier which is resilient against overtraining and certain systematic errors in the training set. We show that these annealing-based classifier systems perform comparably to the state-of-the-art machine learning methods that are currently used in particle physics while still being simple functions of directly interpretable experimental parameters with clear physical meaning. This technique may find application in other areas of HEP, such as real-time decision making in event-selection problems.   

Improving Machine Learning via Nested Quantum Annealing Correction

Unsupervised machine learning, where algorithms seek to extract patterns from data without predefined labels, is a growing area of interest with application to many different fields. However, the training of such algorithms is difficult, due to the intractability of traditional sampling techniques. Quantum annealing, which has the potential to sample more efficiently and from a wider range of distributions than classical methods, may help lead to future advances in the development of unsurpervised learning algorithms. However, the effective temperature at which experimental quantum annealers sample scales in general with the size of the problems. As such, error correction schemes are needed to counter this trend if there is to be some benefit in using quantm annealing. To this end, we have applied nested quantum annealing correction (NQAC), a scalable and generalizable error correction scheme, to a reduced MNIST dataset, which consists of black-and-white images of hand-written integers, and tested whether NQAC's ability to provide an effective temperature reduction leads to an increase in learning performance with nesting level.   

Quantum Autoencoders via Quantum Adders with Genetic Algorithms

The quantum autoencoder is a recent paradigm in the field of quantum machine learning, which may enable an enhanced use of resources in quantum technologies. To this end, quantum neural networks with less nodes in the inner than in the outer layers were considered. Here, we propose a useful connection between approximate quantum adders and quantum autoencoders. Specifically, this link allows us to employ optimized approximate quantum adders, obtained with genetic algorithms, for the implementation of quantum autoencoders for a variety of initial states. Furthermore, we can also directly optimize the quantum autoencoders via genetic algorithms. Our approach opens a different path for the design of quantum autoencoders in controllable quantum platforms. Ref: arXiv:1709.07409   

Neuro-inspired Quantum Learning Rule Inspired by Boltzmann Machine

To introduce learning function into quantum computing, we have investigated the method to operate a quantum neural network (QNN) in the similar manner for a classical neural network. Thanks to the analogy between neuron-neuron and qubit-qubit interactions [S. Sato et al., 2003, and M. Kinjo et al., 2005], we have established a new model of quantum associative memory (QuAM) [Y. Osakabe et al., 2017]. It means that we have proposed a method for a QNN to store multiple target patterns with a Hamiltonian, but an iterative learning scheme was not developed at that time. Thus, this paper proposes a quantum learning method for a QNN inspired by Hebbian and anti-Hebbian learning utilized in Boltzmann machine (BM); the quantum versions of Hebb and anti-Hebb rules of BM are developed by tuning coupling strengths among qubits repeatedly according to probability distribution of a QNN. Numerical results indicate that the proposed quantum learning rules work well and it is confirmed that the combination of quantum Hebb and anti-Hebb rules certainly improves the learning performance of a QNN.   

Novel Computing Approaches with Superconducting Circuits

Recently, considerable scientific interest has been generated by experimental approaches that employ superconducting circuits to the implementation of quantum information protocols. First, we review the different possibilities, with emphasis on Digital Quantum Simulations. We also discuss the premise that the entire physical universe is describable by information. Mainly, we present the results of our attempts to build a few highly controllable quantum systems to carry out some targeted quantum systems, including the Ising Spin Model, the Heisenberg Spin Model, and the Fermi-Hubbard Model. We also consider the use of parametric flux or voltage modulation.
  

Progress on coherent Ising machines constructed from optical parametric oscillators

We present a scalable optical processor with electronic feedback, based on networks of optical parametric oscillators. The design of our machine is inspired by adiabatic quantum computers, although it is not an AQC itself. Our prototype machine is able to find exact solutions of, or sample good approximate solutions to, a variety of hard instances of Ising problems with up to 100 spins and 10,000 spin-spin connections. We will show results from problems with continuous J_ij couplings and external-field h_i terms, as well as from a comparison with the D-Wave 2000Q quantum annealer on unweighted MAX-CUT problems. Reference: P.L. McMahon*, A. Marandi*, et al. Science 354, No. 6312, pp. 614-617 (2016).