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:1002.0846

On fixed-gap adiabatic quantum computation

Ari Mizel

Published Feb 4, 2010• 1 citation
arXivHTMLPDF

Abstract

Quantum computation has revolutionary potential for speeding algorithms and for simulating quantum systems such as molecules. We report here a quantum computer design that performs universal quantum computation within a single non-degenerate ground state protected from decohering noise by an energy gap that we argue is system-size-independent. Closely analogous to a traditional electric circuit, it substantially changes the requirements for quantum computer construction, easing measurement, timing, and heating problems. Using the standard adiabatic condition, we present evidence that this design permits "quantum concurrent processing" distributing a quantum computation among extra qubits to perform a quantum algorithm of N gates in an amount of time that scales with the square root of N. One consequence of our work is a fixed gap version of adiabatic quantum computation, which several arguments hinted could be impossible.

DOI
10.48550/arxiv.1002.0846

Related papers

Fault-tolerant, Universal Adiabatic Quantum Computation

Ari Mizel

Quantum computation has revolutionary potential for speeding computational tasks such as factoring and simulating quantum systems, but the task of constructing a quantum computer is daunting. Adiabatic quantum computation and other ``hands-off approaches relieve the need for rapid, precise pulsing to control the system, inspiring at least one high-profile effort to realize a hands-off quantum computing device. But is hands-off incompatible with fault-tolerant? Concerted effort and many innovative ideas have not resolved this question but have instead deepened it, linking it to fundamental problems in quantum complexity theory. Here we present a hands-off approach that is provably (a) capable of scalable universal quantum computation in a non-degenerate ground state and (b) fault-tolerant against an analogue of the usual local stochastic fault model. A satisfying physical and numerical argument indicates that (c) it is also fault-tolerant against thermal excitation below a threshold temperature independent of the computation size.

•Mar 30, 2014•7 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 Gate Teleportation

Dave Bacon, Steven T. Flammia

The difficulty in producing precisely timed and controlled quantum gates is a significant source of error in many physical implementations of quantum computers. Here we introduce a simple universal primitive, adiabatic gate teleportation, which is robust to timing errors and many control errors and maintains a constant energy gap throughout the computation above a degenerate ground state space. This construction allows for geometric robustness based upon the control of two independent qubit interactions. Further, our piecewise adiabatic evolution easily relates to the quantum circuit model, enabling the use of standard methods from fault-tolerance theory for establishing thresholds.

arXiv:0905.0901•Physical Review Letters•Sep 18, 2009•62 citations

Universal Adiabatic Quantum Computation via the Space-Time Circuit-to-Hamiltonian Construction

David Gosset, Barbara M. Terhal, Anna Vershynina

We show how to perform universal adiabatic quantum computation using a Hamiltonian which describes a set of particles with local interactions on a two-dimensional grid. A single parameter in the Hamiltonian is adiabatically changed as a function of time to simulate the quantum circuit. We bound the eigenvalue gap above the unique ground state by mapping our model onto the ferromagnetic XXZ chain with kink boundary conditions; the gap of this spin chain was computed exactly by Koma and Nachtergaele using its q-deformed version of SU(2) symmetry. We also discuss a related time-independent Hamiltonian which was shown by Janzing to be capable of universal computation. We observe that in the limit of large system size, the time evolution is equivalent to the exactly solvable quantum walk on Young's lattice.

arXiv:1409.7745•Physical Review Letters•Apr 6, 2015•47 citations

How powerful is adiabatic quantum computation?

W. van Dam, M. Mosca, U. Vazirani

The authors analyze the computational power and limitations of the recently proposed 'quantum adiabatic evolution algorithm'. Adiabatic quantum computation is a novel paradigm for the design of quantum algorithms; it is truly quantum in the sense that it can be used to speed up searching by a quadratic factor over any classical algorithm. On the question of whether this new paradigm may be used to efficiently solve NP-complete problems on a quantum computer, we show that the usual query complexity arguments cannot be used to rule out a polynomial time solution. On the other hand, we argue that the adiabatic approach may be thought of as a kind of 'quantum local search'. We design a family of minimization problems that is hard for such local search heuristics, and establish an exponential lower bound for the adiabatic algorithm for these problems. This provides insights into the limitations of this approach. It remains an open question whether adiabatic quantum computation can establish an exponential speed-up over traditional computing or if there exists a classical algorithm that can simulate the quantum adiabatic process efficiently.

arXiv:quant-ph/0206003•Annual Symposium on Foundations of Computer Science•Jan 1, 2001•175 citations

Decoherence in adiabatic quantum computation

M. H. S. Amin, D. V. Averin, James A. Nesteroff

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

arXiv:0708.0384•Physical Review A•Feb 6, 2009•88 citations
Quantum computation has revolutionary potential for speeding algorithms and for simulating quantum systems such as molecules. We report here a quantum computer design that performs universal quantum computation within a single non-degenerate ground state protected from decohering noise by an energy gap that we argue is system-size-independent. Closely analogous to a traditional electric circuit, it substantially changes the requirements for quantum computer construction, easing measurement, timing, and heating problems. Using the standard adiabatic condition, we present evidence that this design permits "quantum concurrent processing" distributing a quantum computation among extra qubits to perform a quantum algorithm of N gates in an amount of time that scales with the square root of N. One consequence of our work is a fixed gap version of adiabatic quantum computation, which several arguments hinted could be impossible.
Quantum computation has revolutionary potential for speeding computational tasks such as factoring and simulating quantum systems, but the task of constructing a quantum computer is daunting. Adiabatic quantum computation and other ``hands-off approaches relieve the need for rapid, precise pulsing to control the system, inspiring at least one high-profile effort to realize a hands-off quantum computing device. But is hands-off incompatible with fault-tolerant? Concerted effort and many innovative ideas have not resolved this question but have instead deepened it, linking it to fundamental problems in quantum complexity theory. Here we present a hands-off approach that is provably (a) capable of scalable universal quantum computation in a non-degenerate ground state and (b) fault-tolerant against an analogue of the usual local stochastic fault model. A satisfying physical and numerical argument indicates that (c) it is also fault-tolerant against thermal excitation below a threshold temperature independent of the computation size.
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.
The difficulty in producing precisely timed and controlled quantum gates is a significant source of error in many physical implementations of quantum computers. Here we introduce a simple universal primitive, adiabatic gate teleportation, which is robust to timing errors and many control errors and maintains a constant energy gap throughout the computation above a degenerate ground state space. This construction allows for geometric robustness based upon the control of two independent qubit interactions. Further, our piecewise adiabatic evolution easily relates to the quantum circuit model, enabling the use of standard methods from fault-tolerance theory for establishing thresholds.
We show how to perform universal adiabatic quantum computation using a Hamiltonian which describes a set of particles with local interactions on a two-dimensional grid. A single parameter in the Hamiltonian is adiabatically changed as a function of time to simulate the quantum circuit. We bound the eigenvalue gap above the unique ground state by mapping our model onto the ferromagnetic XXZ chain with kink boundary conditions; the gap of this spin chain was computed exactly by Koma and Nachtergaele using its q-deformed version of SU(2) symmetry. We also discuss a related time-independent Hamiltonian which was shown by Janzing to be capable of universal computation. We observe that in the limit of large system size, the time evolution is equivalent to the exactly solvable quantum walk on Young's lattice.
The authors analyze the computational power and limitations of the recently proposed 'quantum adiabatic evolution algorithm'. Adiabatic quantum computation is a novel paradigm for the design of quantum algorithms; it is truly quantum in the sense that it can be used to speed up searching by a quadratic factor over any classical algorithm. On the question of whether this new paradigm may be used to efficiently solve NP-complete problems on a quantum computer, we show that the usual query complexity arguments cannot be used to rule out a polynomial time solution. On the other hand, we argue that the adiabatic approach may be thought of as a kind of 'quantum local search'. We design a family of minimization problems that is hard for such local search heuristics, and establish an exponential lower bound for the adiabatic algorithm for these problems. This provides insights into the limitations of this approach. It remains an open question whether adiabatic quantum computation can establish an exponential speed-up over traditional computing or if there exists a classical algorithm that can simulate the quantum adiabatic process efficiently.
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 nnn as in the decoherence-free case. The scaling improvement requires phase coherence throughout the computation, limiting the computation time and the problem size nnn.