Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1108.0560

Adiabatic Quantum Computing

Sebastian D. Pinski

Published Aug 2, 2011• 1 citation
arXivHTMLPDF

Abstract

Adiabatic Quantum Computing (AQC) is a relatively new subject in the world of quantum computing, let alone Physics. Inspiration for this project has come from recent controversy around D-Wave Systems in British Columbia, Canada, who claim to have built a working AQC which is now commercially available and hope to be distributing a 1024 qubit chip by the end of 2008. Their 16 qubit chip was demonstrated online for the Supercomputing 2007 conference within which a few small problems were solved; although the explanations that journalists and critics received were minimal and very little was divulged in the question and answer session. This 'unconvincing' demonstration has caused physicists and computer scientists to hit back at D-Wave. The aim of this project is to give an introduction to the historic advances in classical and quantum computing and to explore the methods of AQC. Through numerical simulations an algorithm for the Max Independent Set problem is empirically obtained.

DOI
10.48550/arxiv.1108.0560

Related papers

Adiabatic Quantum Computation

Vicky Choi

Adiabatic Quantum Computation (AQC) is a quantum model proposed by Farhi, et al., in 2000, and has been proven to be equivalent to conventional quantum computation (quantum gate model). Unlike classical computation or conventional quantum (gate) model in which an algorithm is discrete, an adiabatic quantum algorithm is continuous. In this talk, I will give an introduction of AQC, in particular, on the design and analysis of adiabatic quantum algorithms for the NP-hard maximum independent set problem. I will also discuss the adiabatic quantum architecture design and minor-embedding problems.

•Jan 1, 2009•0 citations

D-Wave and predecessors: From simulated to quantum annealing

Eliahu Cohen, Boaz Tamir

On May 2011, D-Wave Systems Inc. announced "D-Wave One", as "the world's first commercially available quantum computer". No wonder this adiabatic quantum computer based on 128-qubit chip-set provoked an immediate controversy. Over the last 40 years, quantum computation has been a very promising yet challenging research area, facing major difficulties producing a large scale quantum computer. Today, after Google has purchased "D-Wave Two" containing 512 qubits, criticism has only increased. In this work, we examine the theory underlying the D-Wave, seeking to shed some light on this intriguing quantum computer. Starting from classical algorithms such as Metropolis algorithm, genetic algorithm (GA), hill climbing and simulated annealing, we continue to adiabatic computation and quantum annealing towards better understanding of the D-Wave mechanism. Finally, we outline some applications within the fields of information and image processing. In addition, we suggest a few related theoretical ideas and hypotheses.

International Journal of Quantum Information•Apr 1, 2014•29 citations

Adiabatic Quantum Computing with QUBO Formulations

Rui Hua

Quantum physics has the potential to revolutionize computer science by building what is called a quantum computer. Quantum computers can perform tasks that are impossible with Turing-machine based classical computers (e.g., generating random sequences of bits) and can outperform classical computers (to different degrees) in a variety of classical computation problems. Several different models of quantum computing exist. Based on the Adiabatic Theorem in physics, Adiabatic Quantum Computing is a novel computing framework that is drastically different from the more traditional quantum logic gate model. Traditionally, quantum computing has only been tested on devices with a very small number of qubits, severely limiting their uses in practice. In recent years however, advances in engineering and physics have allowed the construction for (relatively) large machines called quantum annealers that do what is known as a specific type of adiabatic quantum computation called quantum annealing. Solving classical computation problems with the quantum annealing framework is not an easy task and there are many obstacles to overcome if we want to achieve any kind of speedups over classical algorithms. In this thesis, we present quantum annealing solutions to several classical problems including the Hamiltonian Cycle Problem, Mixed Dominating Set Problem, Graph Isomorphism Problem, Densest k-Subgraph Problem and the Maximum Weighted Independent Set Problem. Experimental results of these quantum solutions on DWave quantum annealers are also reported. We also look at some of the bottlenecks in the quantum annealing framework and propose several novel approach to mitigate their effects on the efficiency of the quantum solutions.

•Jan 1, 2016•2 citations

Quantum speedup in stoquastic adiabatic quantum computation

Keisuke Fujii

Quantum computation provides exponential speedup for solving certain mathematical problems against classical computers. Motivated by current rapid experimental progress on quantum computing devices, various models of quantum computation have been investigated to show quantum computational supremacy. At a commercial side, quantum annealing machine realizes the quantum Ising model with a transverse field and heuristically solves combinatorial optimization problems. The computational power of this machine is closely related to adiabatic quantum computation (AQC) with a restricted type of Hamiltonians, namely stoquastic Hamiltonians, and has been thought to be relatively less powerful compared to universal quantum computers. Little is known about computational quantum speedup nor advantage in AQC with stoquastic Hamiltonians. Here we characterize computational capability of AQC with stoquastic Hamiltonians, which we call stoqAQC. We construct a concrete stoqAQC model, whose lowest energy gap is lower bounded polynomially, and hence the final state can be obtained in polynomial time. Then we show that it can simulate universal quantum computation if adaptive single-qubit measurements in non-standard bases are allowed on the final state. Even if the measurements are restricted to non-adaptive measurements to respect the robustness of AQC, the proposed model exhibits quantum computational supremacy; classical simulation is impossible under complexity theoretical conjectures. Moreover, it is found that such a stoqAQC model can simulate Shor's algorithm and solve the factoring problem in polynomial time. We also propose how to overcome the measurement imperfections via quantum error correction within the stoqAQC model and also an experimentally feasible verification scheme to test whether or not stoqAQC is done faithfully.

arXiv:1803.09954•Mar 27, 2018•6 citations

Adiabatic quantum computing

Elisabeth Lobe, Tobias Stollenwerk, Anke Tröltzsch

In the recent years, the field of adiabatic quantum computing has gained importance due to the advances in the realisation of such machines, especially by the company D-Wave Systems. These machines are suited to solve discrete optimisation problems which are typically very hard to solve on a classical computer. Due to the quantum nature of the device it is assumed that there is a substantial speedup compared to classical HPC facilities. We explain the basic principles of adiabatic quantum computing as well as its advantages and limitations. By using a quantum computer simulation software we present how discrete optimisation problems, like map colouring and the maximal Clique problem, can be solved. In addition, we investigate the applicability of adiabatic quantum computing to DLR specific problems.

•Jan 1, 2015•6 citations

Building an adiabatic quantum computer simulation in the classroom

Javier Rodríguez-Laguna, Silvia N. Santalla

We present a didactic introduction to adiabatic quantum computation (AQC) via the explicit construction of a classical simulator of quantum computers. This constitutes a suitable route to introduce several important concepts for advanced undergraduates in physics: quantum many-body systems, quantum phase transitions, disordered systems, spin-glasses, and computational complexity theory.

American Journal of Physics•Apr 19, 2018•4 citations
Adiabatic Quantum Computing (AQC) is a relatively new subject in the world of quantum computing, let alone Physics. Inspiration for this project has come from recent controversy around D-Wave Systems in British Columbia, Canada, who claim to have built a working AQC which is now commercially available and hope to be distributing a 1024 qubit chip by the end of 2008. Their 16 qubit chip was demonstrated online for the Supercomputing 2007 conference within which a few small problems were solved; although the explanations that journalists and critics received were minimal and very little was divulged in the question and answer session. This 'unconvincing' demonstration has caused physicists and computer scientists to hit back at D-Wave. The aim of this project is to give an introduction to the historic advances in classical and quantum computing and to explore the methods of AQC. Through numerical simulations an algorithm for the Max Independent Set problem is empirically obtained.
Adiabatic Quantum Computation (AQC) is a quantum model proposed by Farhi, et al., in 2000, and has been proven to be equivalent to conventional quantum computation (quantum gate model). Unlike classical computation or conventional quantum (gate) model in which an algorithm is discrete, an adiabatic quantum algorithm is continuous. In this talk, I will give an introduction of AQC, in particular, on the design and analysis of adiabatic quantum algorithms for the NP-hard maximum independent set problem. I will also discuss the adiabatic quantum architecture design and minor-embedding problems.
On May 2011, D-Wave Systems Inc. announced "D-Wave One", as "the world's first commercially available quantum computer". No wonder this adiabatic quantum computer based on 128-qubit chip-set provoked an immediate controversy. Over the last 40 years, quantum computation has been a very promising yet challenging research area, facing major difficulties producing a large scale quantum computer. Today, after Google has purchased "D-Wave Two" containing 512 qubits, criticism has only increased. In this work, we examine the theory underlying the D-Wave, seeking to shed some light on this intriguing quantum computer. Starting from classical algorithms such as Metropolis algorithm, genetic algorithm (GA), hill climbing and simulated annealing, we continue to adiabatic computation and quantum annealing towards better understanding of the D-Wave mechanism. Finally, we outline some applications within the fields of information and image processing. In addition, we suggest a few related theoretical ideas and hypotheses.
Quantum physics has the potential to revolutionize computer science by building what is called a quantum computer. Quantum computers can perform tasks that are impossible with Turing-machine based classical computers (e.g., generating random sequences of bits) and can outperform classical computers (to different degrees) in a variety of classical computation problems. Several different models of quantum computing exist. Based on the Adiabatic Theorem in physics, Adiabatic Quantum Computing is a novel computing framework that is drastically different from the more traditional quantum logic gate model. Traditionally, quantum computing has only been tested on devices with a very small number of qubits, severely limiting their uses in practice. In recent years however, advances in engineering and physics have allowed the construction for (relatively) large machines called quantum annealers that do what is known as a specific type of adiabatic quantum computation called quantum annealing. Solving classical computation problems with the quantum annealing framework is not an easy task and there are many obstacles to overcome if we want to achieve any kind of speedups over classical algorithms. In this thesis, we present quantum annealing solutions to several classical problems including the Hamiltonian Cycle Problem, Mixed Dominating Set Problem, Graph Isomorphism Problem, Densest k-Subgraph Problem and the Maximum Weighted Independent Set Problem. Experimental results of these quantum solutions on DWave quantum annealers are also reported. We also look at some of the bottlenecks in the quantum annealing framework and propose several novel approach to mitigate their effects on the efficiency of the quantum solutions.
Quantum computation provides exponential speedup for solving certain mathematical problems against classical computers. Motivated by current rapid experimental progress on quantum computing devices, various models of quantum computation have been investigated to show quantum computational supremacy. At a commercial side, quantum annealing machine realizes the quantum Ising model with a transverse field and heuristically solves combinatorial optimization problems. The computational power of this machine is closely related to adiabatic quantum computation (AQC) with a restricted type of Hamiltonians, namely stoquastic Hamiltonians, and has been thought to be relatively less powerful compared to universal quantum computers. Little is known about computational quantum speedup nor advantage in AQC with stoquastic Hamiltonians. Here we characterize computational capability of AQC with stoquastic Hamiltonians, which we call stoqAQC. We construct a concrete stoqAQC model, whose lowest energy gap is lower bounded polynomially, and hence the final state can be obtained in polynomial time. Then we show that it can simulate universal quantum computation if adaptive single-qubit measurements in non-standard bases are allowed on the final state. Even if the measurements are restricted to non-adaptive measurements to respect the robustness of AQC, the proposed model exhibits quantum computational supremacy; classical simulation is impossible under complexity theoretical conjectures. Moreover, it is found that such a stoqAQC model can simulate Shor's algorithm and solve the factoring problem in polynomial time. We also propose how to overcome the measurement imperfections via quantum error correction within the stoqAQC model and also an experimentally feasible verification scheme to test whether or not stoqAQC is done faithfully.
In the recent years, the field of adiabatic quantum computing has gained importance due to the advances in the realisation of such machines, especially by the company D-Wave Systems. These machines are suited to solve discrete optimisation problems which are typically very hard to solve on a classical computer. Due to the quantum nature of the device it is assumed that there is a substantial speedup compared to classical HPC facilities. We explain the basic principles of adiabatic quantum computing as well as its advantages and limitations. By using a quantum computer simulation software we present how discrete optimisation problems, like map colouring and the maximal Clique problem, can be solved. In addition, we investigate the applicability of adiabatic quantum computing to DLR specific problems.