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:2407.18301 · Quantum Science and Technology

Adiabatic dynamics of entanglement

Einar Gabbassov, Achim Kempf

Published Sep 4, 2025• 0 citations
arXivHTMLPDF

Abstract

Abstract We show that, during adiabatic evolution, any changes in entanglement can be attributed to a succession of avoided energy level crossings at which eigenvalues swap their eigenvectors. These swaps mediate the generation and redistribution of entanglement in multipartite systems. The efficiency of this redistribution depends on the narrowness of the avoided level crossings and thus constrains the speed of adiabatic evolution. Moreover, we relate the amount of entanglement involved to the ruggedness of the energy landscape, which directly affects the hardness of a computational problem. This enables an analysis of computational complexity and quantum advantage from the point of view of entanglement requirements. Applied to adiabatic quantum computation, our findings directly relate the computation’s speed to its utilization of entanglement as a resource. The same principles extend to gate-based discretized adiabatic quantum algorithms, including those for Hamiltonian simulation and combinatorial optimization.

DOI
10.1088/2058-9565/ae0364

Related papers

Dynamics of quantum adiabatic evolution algorithm for Number Partitioning

Vadim Smelyanskiy, U. von Toussaint, Doǧan A. Timuçin

We have developed a general technique to study the dynamics of the quantum adiabatic evolution algorithm applied to random combinatorial optimization problems in the asymptotic limit of large problem size $n$. We use as an example the NP-complete Number Partitioning problem and map the algorithm dynamics to that of an auxilary quantum spin glass system with the slowly varying Hamiltonian. We use a Green function method to obtain the adiabatic eigenstates and the minimum excitation gap, $g_{\rm min}={\cal O}(n 2^{-n/2})$, corresponding to the exponential complexity of the algorithm for Number Partitioning. The key element of the analysis is the conditional energy distribution computed for the set of all spin configurations generated from a given (ancestor) configuration by simulteneous fipping of a fixed number of spins. For the problem in question this distribution is shown to depend on the ancestor spin configuration only via a certain parameter related to the energy of the configuration. As the result, the algorithm dynamics can be described in terms of one-dimenssional quantum diffusion in the energy space. This effect provides a general limitation on the power of a quantum adiabatic computation in random optimization problems. Analytical results are in agreement with the numerical simulation of the algorithm.

arXiv:quant-ph/0202155•Feb 26, 2002•10 citations

Adiabatic quantum computation with a one-dimensional projector Hamiltonian

Avatar Tulsi

Adiabatic quantum computation is based on the adiabatic evolution of quantum systems. We analyze a particular class of quantum adiabatic evolutions where either the initial or final Hamiltonian is a one-dimensional projector Hamiltonian on the corresponding ground state. The minimum-energy gap, which governs the time required for a successful evolution, is shown to be proportional to the overlap of the ground states of the initial and final Hamiltonians. We show that such evolutions exhibit a rapid crossover as the ground state changes abruptly near the transition point where the energy gap is minimum. Furthermore, a faster evolution can be obtained by performing a partial adiabatic evolution within a narrow interval around the transition point. These results generalize and quantify earlier works.

arXiv:0806.0385•Physical Review A•Nov 23, 2009•27 citations

Speedup in Quantum Adiabatic Evolution Algorithm

Joonwoo Bae, Younghun Kwon

The quantum adiabatic evolution algorithm suggested by Farhi et al. was effective in solving NPcomplete problems. The algorithm is governed by the adiabatic theorem. Therefore, in order to reduce the running time, it is essential to examine the minimum energy gap between the ground level and the next one in the evolution. In this paper we show a way of speedup in the quantum adiabatic evolution algorithm, using an extended Hamiltonian. We present the exact relation between the energy gap and the elements of the extended Hamiltonian, which provides a new point of view to reduce the running time.

arXiv:quant-ph/0205048•Zeitschrift für Naturforschung A•Apr 1, 2003•0 citations

Principles of Quantum Optimization for Constrained Problems

Einar Gabbassov, Gurpahul Singh, Achim Kempf

Constrained combinatorial optimization underlies many industrial and technological decision problems. We develop a spectral theory that unifies many quantum optimization algorithms. We show that computational slowdown is driven by entanglement restructuring: the creation, redistribution, and destruction of entanglement during system evolution. The severity of the slowdown depends on how much entanglement must be changed. We show that algebraic properties of constraints induce such restructuring, and that constraint-aware dynamics reduce the associated slowdown by avoiding unnecessary restructuring. This framework explains why constraint-aware quantum methods can outperform generic penalty-based approaches. The theory connects constrained optimization, computational complexity, entanglement dynamics, and Hamiltonian spectral structure across continuous-time and circuit-based quantum optimization paradigms.

quant-pharXiv:2607.14227•Jul 17, 2026•0 citations

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

ENTANGLEMENT PROPERTIES OF ADIABATIC QUANTUM ALGORITHMS

Wen Jiayan, Yi Huang, Daowen Qiu

In this paper, by constructing a more entangled quantum system, we shorten the adiabatic quantum search algorithm to constant time. On the other hand, we show that the speed-up of adiabatic quantum algorithms by selecting particular adiabatic evolution paths or injecting energy into the quantum system can be explained as a form of entanglement enlargement. These findings suggest that entanglement plays a fundamental role for the efficiency of algorithm performance.

International Journal of Quantum Information•Dec 1, 2009•5 citations
Abstract We show that, during adiabatic evolution, any changes in entanglement can be attributed to a succession of avoided energy level crossings at which eigenvalues swap their eigenvectors. These swaps mediate the generation and redistribution of entanglement in multipartite systems. The efficiency of this redistribution depends on the narrowness of the avoided level crossings and thus constrains the speed of adiabatic evolution. Moreover, we relate the amount of entanglement involved to the ruggedness of the energy landscape, which directly affects the hardness of a computational problem. This enables an analysis of computational complexity and quantum advantage from the point of view of entanglement requirements. Applied to adiabatic quantum computation, our findings directly relate the computation’s speed to its utilization of entanglement as a resource. The same principles extend to gate-based discretized adiabatic quantum algorithms, including those for Hamiltonian simulation and combinatorial optimization.
We have developed a general technique to study the dynamics of the quantum adiabatic evolution algorithm applied to random combinatorial optimization problems in the asymptotic limit of large problem size nnn. We use as an example the NP-complete Number Partitioning problem and map the algorithm dynamics to that of an auxilary quantum spin glass system with the slowly varying Hamiltonian. We use a Green function method to obtain the adiabatic eigenstates and the minimum excitation gap, gmin=O(n2−n/2)g_{\rm min}={\cal O}(n 2^{-n/2})gmin​=O(n2−n/2), corresponding to the exponential complexity of the algorithm for Number Partitioning. The key element of the analysis is the conditional energy distribution computed for the set of all spin configurations generated from a given (ancestor) configuration by simulteneous fipping of a fixed number of spins. For the problem in question this distribution is shown to depend on the ancestor spin configuration only via a certain parameter related to the energy of the configuration. As the result, the algorithm dynamics can be described in terms of one-dimenssional quantum diffusion in the energy space. This effect provides a general limitation on the power of a quantum adiabatic computation in random optimization problems. Analytical results are in agreement with the numerical simulation of the algorithm.
Adiabatic quantum computation is based on the adiabatic evolution of quantum systems. We analyze a particular class of quantum adiabatic evolutions where either the initial or final Hamiltonian is a one-dimensional projector Hamiltonian on the corresponding ground state. The minimum-energy gap, which governs the time required for a successful evolution, is shown to be proportional to the overlap of the ground states of the initial and final Hamiltonians. We show that such evolutions exhibit a rapid crossover as the ground state changes abruptly near the transition point where the energy gap is minimum. Furthermore, a faster evolution can be obtained by performing a partial adiabatic evolution within a narrow interval around the transition point. These results generalize and quantify earlier works.
The quantum adiabatic evolution algorithm suggested by Farhi et al. was effective in solving NPcomplete problems. The algorithm is governed by the adiabatic theorem. Therefore, in order to reduce the running time, it is essential to examine the minimum energy gap between the ground level and the next one in the evolution. In this paper we show a way of speedup in the quantum adiabatic evolution algorithm, using an extended Hamiltonian. We present the exact relation between the energy gap and the elements of the extended Hamiltonian, which provides a new point of view to reduce the running time.
Constrained combinatorial optimization underlies many industrial and technological decision problems. We develop a spectral theory that unifies many quantum optimization algorithms. We show that computational slowdown is driven by entanglement restructuring: the creation, redistribution, and destruction of entanglement during system evolution. The severity of the slowdown depends on how much entanglement must be changed. We show that algebraic properties of constraints induce such restructuring, and that constraint-aware dynamics reduce the associated slowdown by avoiding unnecessary restructuring. This framework explains why constraint-aware quantum methods can outperform generic penalty-based approaches. The theory connects constrained optimization, computational complexity, entanglement dynamics, and Hamiltonian spectral structure across continuous-time and circuit-based quantum optimization paradigms.
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.