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/0308042 · Physical Review A

Adiabatic quantum computation and quantum phase transitions

José Ignacio Latorre, Román Orús

Published Jun 2, 2004• 57 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physreva.69.062302

Related papers

Universality of entanglement and quantum-computation complexity

Román Orús, José Ignacio Latorre

We study the universality of scaling of entanglement in Shor's factoring algorithm and in adiabatic quantum algorithms across a quantum phase transition for both the $NP$-complete exact cover problem as well as Grover's problem. The analytic result for Shor's algorithm shows a linear scaling of the entropy in terms of the number of qubits, therefore making it hard to generate an efficient classical simulation protocol. A similar result is obtained numerically for the quantum adiabatic evolution exact cover algorithm, which also shows universality of the quantum phase transition near which the system evolves. On the other hand, entanglement in Grover's adiabatic algorithm remains a bounded quantity even at the critical point. The classification of scaling of entanglement appears as a natural grading of the computational complexity of simulating quantum phase transitions.

arXiv:quant-ph/0311017•Physical Review A•May 12, 2004•76 citations

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

Ralf Schützhold, Gernot Schaller

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.

arXiv:quant-ph/0608017•Physical Review A•Dec 28, 2006•79 citations

Adiabatic computation: A toy model

Pedro Ribeiro, Rémy Mosseri

We discuss a toy model for adiabatic quantum computation which displays some phenomenological properties expected in more realistic implementations. This model has two free parameters: the adiabatic evolution parameter $s$ and the $\ensuremath{\alpha}$ parameter, which emulates many-variable constraints in the classical computational problem. The proposed model presents, in the $s\text{\ensuremath{-}}\ensuremath{\alpha}$ plane, a line of first-order quantum phase transition that ends at a second-order point. The relation between computation complexity and the occurrence of quantum phase transitions is discussed. We analyze the behavior of the ground and first excited states near the quantum phase transition, the gap, and the entanglement content of the ground state.

arXiv:quant-ph/0606194•Physical Review A•Oct 26, 2006•5 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 ${\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

How the High-energy Part of the Spectrum Affects the Adiabatic Computation Gap

Yosi Atia, Dorit Aharonov

Towards better understanding of how to design efficient adiabatic quantum algorithms, we study how the adiabatic gap depends on the spectra of the initial and final Hamiltonians in a natural family of test-bed examples. We show that perhaps counter-intuitively, changing the energy in the initial and final Hamiltonians of only highly excited states (we do this by assigning all eigenstates above a certain cutoff the same value), can turn the adiabatic algorithm from being successful to failing. Interestingly, our system exhibits a phase transition; when the cutoff in the spectrum becomes smaller than roughly $n/2$, $n$ being the number of qubits, the behavior transitions from a successful adiabatic process to a failed one. To analyze this behavior, and provide an upper bound on both the minimal gap as well as the success of the adiabatic algorithm, we introduce the notion of "escape rate", which quantifies the rate by which the system escapes the initial ground state (a related notion was also used by Ilin and Lychkovskiy in arXiv:1805.04083). Our results indicate a phenomenon that is interesting on its own right: an adiabatic evolution may be robust to bounded-rank perturbations, even when the latter closes the gap or makes it exponentially small.

arXiv:1906.02581•Jun 6, 2019•0 citations
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.
We study the universality of scaling of entanglement in Shor's factoring algorithm and in adiabatic quantum algorithms across a quantum phase transition for both the NPNPNP-complete exact cover problem as well as Grover's problem. The analytic result for Shor's algorithm shows a linear scaling of the entropy in terms of the number of qubits, therefore making it hard to generate an efficient classical simulation protocol. A similar result is obtained numerically for the quantum adiabatic evolution exact cover algorithm, which also shows universality of the quantum phase transition near which the system evolves. On the other hand, entanglement in Grover's adiabatic algorithm remains a bounded quantity even at the critical point. The classification of scaling of entanglement appears as a natural grading of the computational complexity of simulating quantum phase transitions.
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.
We discuss a toy model for adiabatic quantum computation which displays some phenomenological properties expected in more realistic implementations. This model has two free parameters: the adiabatic evolution parameter sss and the $\ensuremath{\alpha}$ parameter, which emulates many-variable constraints in the classical computational problem. The proposed model presents, in the $s\text{\ensuremath{-}}\ensuremath{\alpha}$ plane, a line of first-order quantum phase transition that ends at a second-order point. The relation between computation complexity and the occurrence of quantum phase transitions is discussed. We analyze the behavior of the ground and first excited states near the quantum phase transition, the gap, and the entanglement content of the ground state.
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).
Towards better understanding of how to design efficient adiabatic quantum algorithms, we study how the adiabatic gap depends on the spectra of the initial and final Hamiltonians in a natural family of test-bed examples. We show that perhaps counter-intuitively, changing the energy in the initial and final Hamiltonians of only highly excited states (we do this by assigning all eigenstates above a certain cutoff the same value), can turn the adiabatic algorithm from being successful to failing. Interestingly, our system exhibits a phase transition; when the cutoff in the spectrum becomes smaller than roughly n/2n/2n/2, nnn being the number of qubits, the behavior transitions from a successful adiabatic process to a failed one. To analyze this behavior, and provide an upper bound on both the minimal gap as well as the success of the adiabatic algorithm, we introduce the notion of "escape rate", which quantifies the rate by which the system escapes the initial ground state (a related notion was also used by Ilin and Lychkovskiy in arXiv:1805.04083). Our results indicate a phenomenon that is interesting on its own right: an adiabatic evolution may be robust to bounded-rank perturbations, even when the latter closes the gap or makes it exponentially small.