A cross-disciplinary introduction to quantum annealing-based algorithms

Abstract

A central goal in quantum computing is the development of quantum hardware and quantum algorithms in order to analyse challenging scientific and engineering problems. Research in quantum computation involves contributions from both physics and computer science, hence this article presents a concise introduction to basic concepts from both fields that are used in annealing-based quantum computation, an alternative to the more familiar quantum gate model. We introduce some concepts from computer science required to define difficult computational problems and to realise the potential relevance of quantum algorithms to find novel solutions to those problems. We introduce the structure of quantum annealing-based algorithms as well as two examples of this kind of algorithms for solving instances of the max-SAT and Minimum Multicut problems. An overview of the quantum annealing systems manufactured by D-Wave Systems is also presented.

arXiv commentto appear in Contemporary Physics, 31 pages

References in corpus (14)

• Quantum Machine Learning
• Ising formulations of many NP problems
• Quantum Annealing in the Transverse Ising Model
• An introduction to quantum machine learning
• Quantum annealing with more than one hundred qubits
• Architectural considerations in the design of a superconducting quantum annealing processor
• Undecidability of the Spectral Gap (short version)
• Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design
• Quantum annealing of the Traveling Salesman Problem
• Experimental Demonstration of a Robust and Scalable Flux Qubit
• A scalable readout system for a superconducting adiabatic quantum optimization system
• Simulated Quantum Annealing Can Be Exponentially Faster than Classical Simulated Annealing
• Substituting a qubit for an arbitrarily large number of classical bits
• Analysis of patent activity in the field of quantum information processing

Cited by in corpus (23)

• Perspectives of quantum annealing: Methods and implementations
• Recent advances for quantum classifiers
• How to Build the Thermofield Double State
• SU(2) lattice gauge theory on a quantum annealer
• Optimal Control of Traffic Signals using Quantum Annealing
• Polymer Physics by Quantum Computing
• Designing Quantum Annealing Schedules using Bayesian Optimization
• Dominant Reaction Pathways by Quantum Computing
• Inertial Theorem: Overcoming the quantum adiabatic limit
• Sampling Rare Conformational Transitions with a Quantum Computer
• Towards Transfer Learning for Large-Scale Image Classification Using Annealing-based Quantum Boltzmann Machines
• Sampling a rare protein transition with a hybrid classical-quantum computing algorithm
• Quantum Computing for Discrete Optimization: A Highlight of Three Technologies
• Dynamic Asset Allocation with Expected Shortfall via Quantum Annealing
• Energy Landscape Structure of Small Graph Isomorphism Under Variational Optimization
• Forecasting Election Polls with Spin Systems
• Inductive Construction of Variational Quantum Circuit for Constrained Combinatorial Optimization
• The Quantum Cocktail Party Problem
• Multiobjective Optimization in a Quantum Adiabatic Computer
• Spatial correlations in the qubit properties of D-Wave 2000Q measured and simulated qubit networks
• An encoding of argumentation problems using quadratic unconstrained binary optimization
• Quick design of feasible tensor networks for constrained combinatorial optimization
• Curve fitting on a quantum annealer for an advanced navigation method