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:quant-ph/0608017 · Physical Review A

Adiabatic quantum algorithms as quantum phase transitions: First versus second order

Ralf Schützhold, Gernot Schaller

Published Dec 28, 2006• 79 citations
arXivHTMLPDF

Abstract

In the continuum limit (large number of qubits), adiabatic quantum algorithms display a remarkable similarity to sweeps through quantum phase transitions. We find that transitions of second or higher order are advantageous in comparison to those of first order. With this insight, we propose an adiabatic quantum algorithm for the solution of 3-satisfiability (3-SAT) problems (exact cover), which is significantly faster than previous proposals according to numerical simulations (up to 20 qubits). These findings suggest that adiabatic quantum algorithms can solve NP-complete problems such as 3-SAT much faster than the Grover search routine (yielding a quadratic enhancement), possibly even with an exponential speedup.

DOI
10.1103/physreva.74.060304

Related papers

The role of symmetries in adiabatic quantum algorithms

Gernot Schaller, Ralf Schützhold

Exploiting the similarity between adiabatic quantum algorithms and quantum phase transitions, we argue that second-order transitions -- typically associated with broken or restored symmetries -- should be advantageous in comparison to first-order transitions. Guided by simple examples we construct an alternative adiabatic algorithm for the NP-complete problem {\em Exact Cover 3}. We show numerically that its average performance (for the considered cases up to ${\cal O}\{20\}$ qubits) is better than that of the conventional scheme. The run-time of adiabatic algorithms is not just determined by the minimum value of the fundamental energy gap (between the ground state and the exited states), but also by its curvature at the critical point. The proposed symmetry-restoring adiabatic quantum algorithm only contains contributions linear and quadratic in the Pauli matrices and can be generalized to other problem Hamiltonians which are decomposed of terms involving one and two qubits. We show how the factoring problem can be cast into such a quadratic form. These findings suggest that adiabatic quantum algorithms can solve a large class of NP problems much faster than the Grover search routine (which corresponds to a first-order transition and yields a quadratic enhancement only).

arXiv:0708.1882•Aug 14, 2007•7 citations

The role of symmetries in adiabatic quantum algorithms

Gernot Schaller, Ralf Schützhold

Exploiting the similarity between adiabatic quantum algorithms and quantum phase transitions, we argue that second-order transitions -- typically associated with broken or restored symmetries -- should be advantageous in comparison to first-order transitions. Guided by simple examples we construct an alternative adiabatic algorithm for the NP-complete problem {\em Exact Cover 3}. We show numerically that its average performance (for the considered cases up to $\ord\{20\}$ qubits) is better than that of the conventional scheme. The run-time of adiabatic algorithms is not just determined by the minimum value of the fundamental energy gap (between the ground state and the exited states), but also by its curvature at the critical point. The proposed symmetry-restoring adiabatic quantum algorithm only contains contributions linear and quadratic in the Pauli matrices and can be generalized to other problem Hamiltonians which are decomposed of terms involving one and two qubits. We show how the factoring problem can be cast into such a quadratic form. These findings suggest that adiabatic quantum algorithms can solve a large class of NP problems much faster than the Grover search routine (which corresponds to a first-order transition and yields a quadratic enhancement only).

Quantum Information and Computation•Jan 1, 2010•28 citations

On Quantum Simulators and Adiabatic Quantum Algorithms

Sarah Mostame

This Thesis focuses on different aspects of quantum computation theory: adiabatic quantum algorithms, decoherence during the adiabatic evolution and quantum simulators. After an overview on the area of quantum computation and setting up the formal ground for the rest of the Thesis we derive a general error estimate for adiabatic quantum computing. We demonstrate that the first-order correction, which has frequently been used as a condition for adiabatic quantum computation, does not yield a good estimate for the computational error. Therefore, a more general criterion is proposed, which includes higher-order corrections and shows that the computational error can be made exponentially small – which facilitates significantly shorter evolution times than the first-order estimate in certain situations. Based on this criterion and rather general arguments and assumptions, it can be demonstrated that a run-time of order of the inverse minimum energy gap is sufficient and necessary. Furthermore, exploiting the similarity between adiabatic quantum algorithms and quantum phase transitions, we study the impact of decoherence on the sweep through a second-order quantum phase transition for the prototypical example of the Ising chain in a transverse field and compare it to the adiabatic version of Grover’s search algorithm. It turns out that (in contrast to first-order transitions) the impact of decoherence caused by a weak coupling to a rather general environment increases with system size (i.e., number of spins/qubits), which might limit the scalability of the system. Finally, we propose the use of electron systems to construct laboratory systems based on present-day technology which reproduce and thereby simulate the quantum dynamics of the Ising model and the O(3) nonlinear sigma model.

•Oct 2, 2008•0 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

Adiabatic quantum computation and quantum phase transitions

José Ignacio Latorre, Román Orús

We analyze the ground-state entanglement in a quantum adiabatic evolution algorithm designed to solve the $NP$-complete Exact Cover problem. The entropy of entanglement seems to obey linear and universal scaling at the point where the energy gap becomes small, suggesting that the system passes near a quantum phase transition. Such a large scaling of entanglement suggests that the effective connectivity of the system diverges as the number of qubits goes to infinity and that this algorithm cannot be efficiently simulated by classical means. On the other hand, entanglement in Grover's algorithm is bounded by a constant.

arXiv:quant-ph/0308042•Physical Review A•Jun 2, 2004•57 citations

Decoherence in a dynamical quantum phase transition

Sarah Mostame, Gernot Schaller, Ralf Schützhold

Motivated by the similarity between adiabatic quantum algorithms and quantum phase transitions, we study the impact of decoherence on the sweep through a second-order quantum phase transition for the prototypical example of the Ising chain in a transverse field and compare it to the adiabatic version of Grover's search algorithm, which displays a first-order quantum phase transition. For site-independent and site-dependent coupling strengths as well as different operator couplings, the results show (in contrast to first-order transitions) that the impact of decoherence caused by a weak coupling to a rather general environment increases with system size (i.e., number of spins or qubits). This might limit the scalability of the corresponding adiabatic quantum algorithm.

arXiv:0910.1750•Physical Review A•Mar 8, 2010•8 citations
In the continuum limit (large number of qubits), adiabatic quantum algorithms display a remarkable similarity to sweeps through quantum phase transitions. We find that transitions of second or higher order are advantageous in comparison to those of first order. With this insight, we propose an adiabatic quantum algorithm for the solution of 3-satisfiability (3-SAT) problems (exact cover), which is significantly faster than previous proposals according to numerical simulations (up to 20 qubits). These findings suggest that adiabatic quantum algorithms can solve NP-complete problems such as 3-SAT much faster than the Grover search routine (yielding a quadratic enhancement), possibly even with an exponential speedup.
Exploiting the similarity between adiabatic quantum algorithms and quantum phase transitions, we argue that second-order transitions -- typically associated with broken or restored symmetries -- should be advantageous in comparison to first-order transitions. Guided by simple examples we construct an alternative adiabatic algorithm for the NP-complete problem {\em Exact Cover 3}. We show numerically that its average performance (for the considered cases up to O{20}{\cal O}\{20\}O{20} qubits) is better than that of the conventional scheme. The run-time of adiabatic algorithms is not just determined by the minimum value of the fundamental energy gap (between the ground state and the exited states), but also by its curvature at the critical point. The proposed symmetry-restoring adiabatic quantum algorithm only contains contributions linear and quadratic in the Pauli matrices and can be generalized to other problem Hamiltonians which are decomposed of terms involving one and two qubits. We show how the factoring problem can be cast into such a quadratic form. These findings suggest that adiabatic quantum algorithms can solve a large class of NP problems much faster than the Grover search routine (which corresponds to a first-order transition and yields a quadratic enhancement only).
Exploiting the similarity between adiabatic quantum algorithms and quantum phase transitions, we argue that second-order transitions -- typically associated with broken or restored symmetries -- should be advantageous in comparison to first-order transitions. Guided by simple examples we construct an alternative adiabatic algorithm for the NP-complete problem {\em Exact Cover 3}. We show numerically that its average performance (for the considered cases up to $\ord\{20\}$ qubits) is better than that of the conventional scheme. The run-time of adiabatic algorithms is not just determined by the minimum value of the fundamental energy gap (between the ground state and the exited states), but also by its curvature at the critical point. The proposed symmetry-restoring adiabatic quantum algorithm only contains contributions linear and quadratic in the Pauli matrices and can be generalized to other problem Hamiltonians which are decomposed of terms involving one and two qubits. We show how the factoring problem can be cast into such a quadratic form. These findings suggest that adiabatic quantum algorithms can solve a large class of NP problems much faster than the Grover search routine (which corresponds to a first-order transition and yields a quadratic enhancement only).
This Thesis focuses on different aspects of quantum computation theory: adiabatic quantum algorithms, decoherence during the adiabatic evolution and quantum simulators. After an overview on the area of quantum computation and setting up the formal ground for the rest of the Thesis we derive a general error estimate for adiabatic quantum computing. We demonstrate that the first-order correction, which has frequently been used as a condition for adiabatic quantum computation, does not yield a good estimate for the computational error. Therefore, a more general criterion is proposed, which includes higher-order corrections and shows that the computational error can be made exponentially small – which facilitates significantly shorter evolution times than the first-order estimate in certain situations. Based on this criterion and rather general arguments and assumptions, it can be demonstrated that a run-time of order of the inverse minimum energy gap is sufficient and necessary. Furthermore, exploiting the similarity between adiabatic quantum algorithms and quantum phase transitions, we study the impact of decoherence on the sweep through a second-order quantum phase transition for the prototypical example of the Ising chain in a transverse field and compare it to the adiabatic version of Grover’s search algorithm. It turns out that (in contrast to first-order transitions) the impact of decoherence caused by a weak coupling to a rather general environment increases with system size (i.e., number of spins/qubits), which might limit the scalability of the system. Finally, we propose the use of electron systems to construct laboratory systems based on present-day technology which reproduce and thereby simulate the quantum dynamics of the Ising model and the O(3) nonlinear sigma model.
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 analyze the ground-state entanglement in a quantum adiabatic evolution algorithm designed to solve the NPNPNP-complete Exact Cover problem. The entropy of entanglement seems to obey linear and universal scaling at the point where the energy gap becomes small, suggesting that the system passes near a quantum phase transition. Such a large scaling of entanglement suggests that the effective connectivity of the system diverges as the number of qubits goes to infinity and that this algorithm cannot be efficiently simulated by classical means. On the other hand, entanglement in Grover's algorithm is bounded by a constant.
Motivated by the similarity between adiabatic quantum algorithms and quantum phase transitions, we study the impact of decoherence on the sweep through a second-order quantum phase transition for the prototypical example of the Ising chain in a transverse field and compare it to the adiabatic version of Grover's search algorithm, which displays a first-order quantum phase transition. For site-independent and site-dependent coupling strengths as well as different operator couplings, the results show (in contrast to first-order transitions) that the impact of decoherence caused by a weak coupling to a rather general environment increases with system size (i.e., number of spins or qubits). This might limit the scalability of the corresponding adiabatic quantum algorithm.