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

The Dynamics of Entanglement in the Adiabatic Search and Deutsch Algorithms

K. Choy, Gina Passante, Daria Ahrensmeier, M. E. Carrington, T. Fugleberg, R. Kobes, G. Kunstatter

Published May 3, 2006• 3 citations
OpenAlex

Abstract

The goal of this paper is to study the effect of entanglement on the running time of a quantum computation. Adiabatic quantum computation is suited to this kind of study, since it allows us to explicitly calculate the time evolution of the entanglement throughout the calculation. On the other hand however, the adiabatic formalism makes it impossible to study the roles of entanglement and fidelity separately, which means that results have to be interpreted carefully. We study two algorithms: the search algorithm and the Deutsch-Jozsa algorithm. We find some evidence that entanglement can be considered a resource in quantum computation.

Related papers

The dynamics of entanglement in the adiabatic search and Deutsch algorithms

K Choy, G Passante, D Ahrensmeier +4 more

The goal of this paper is to study the effect of entanglement on the running time of a quantum computation. Adiabatic quantum computation is suited to this kind of study, since it allows us to explicitly calculate the time evolution of the entanglement throughout the calculation. On the other hand, however, the adiabatic formalism makes it impossible to study the roles of entanglement and fidelity separately, which means that results have to be interpreted carefully. We study two algorithms: the search algorithm and the Deutsch–Jozsa algorithm. We find some evidence that entanglement can be considered a resource in quantum computation. PACS Nos.: 03.67.Mn, 03.67.Lx

arXiv:quant-ph/0605040•Canadian Journal of Physics•Oct 1, 2007•2 citations

Adiabatic quantum computation and Deutsch’s algorithm

Saurya Das, Randy Kobes, G. Kunstatter

We show that by a suitable choice of a time-dependent Hamiltonian, Deutsch's algorithm can be implemented by an adiabatic quantum computer. We extend our analysis to the Deutsch-Jozsa problem and estimate the required running time for both global and local adiabatic evolutions.

arXiv:quant-ph/0111032•Physical Review A•Jun 5, 2002•48 citations

Entanglement and adiabatic quantum computation

Daria Ahrensmeier

Adiabatic quantum computation provides an alternative approach to quantum computation using a time-dependent Hamiltonian. The time evolution of entanglement during the adiabatic quantum search algorithm is studied, and its relevance as a resource is discussed.PACS Nos.: 03.67.–a, 03.67.Lx, 03.67.Mn

arXiv:quant-ph/0512066•Canadian Journal of Physics•Jan 15, 2006•3 citations

ENTANGLEMENT IN ADIABATIC QUANTUM SEARCHING ALGORITHMS

Wen Jiayan, Daowen Qiu

Quantum entanglement is widely considered as one of the key resources for quantum-computational power. However, present interpretations of entanglement in speeding up of quantum algorithms remain far from complete. We analyze and compare the behaviors of entanglement during the adiabatic evolution of Grover's quantum search algorithms with complexity [Formula: see text] and O(1), respectively. Our results show that entanglement has a significant impact on the computational efficiency of both algorithms. That is, the greater the entanglement, the higher is the quantum computation, and vice versa. Furthermore, the correlations between entanglement and energy are discussed. It is observed that for the algorithm with complexity O(1), its entanglement degree becomes larger when the energy input into the quantum system increases, thus making the algorithm more efficient.

International Journal of Quantum Information•Oct 1, 2008•9 citations

The Constant Speedup Mechanism on Adiabatic Quantum Computation

Zhigang Zhang, Songfeng Lu, Jie Sun +1 more

In the adiabatic quantum computation model, a computational procedure is described by the continuous time evolution of a time dependent Hamiltonian. Classically, the unstructured search problem can be solved only in a running time of order O(G). However, by modifying the structure of local Hamiltonian or using specific interpolating functions, it is possible to do the calculation in constant time for a quantum computer. This paper reveals the cause that lead to the speedup. We analyze two kinds of specific adiabatic quantum models, and conclude that the value of relevant elements in back-diagonal of the local Hamiltonian is the main factors affecting the time complexity of adiabatic quantum algorithms. According to the speedup mechanism, we have proposed two kinds of adiabatic quantum algorithms to make a constant time complexity.

Journal of Computational and Theoretical Nanoscience•Oct 1, 2016•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
The goal of this paper is to study the effect of entanglement on the running time of a quantum computation. Adiabatic quantum computation is suited to this kind of study, since it allows us to explicitly calculate the time evolution of the entanglement throughout the calculation. On the other hand however, the adiabatic formalism makes it impossible to study the roles of entanglement and fidelity separately, which means that results have to be interpreted carefully. We study two algorithms: the search algorithm and the Deutsch-Jozsa algorithm. We find some evidence that entanglement can be considered a resource in quantum computation.
The goal of this paper is to study the effect of entanglement on the running time of a quantum computation. Adiabatic quantum computation is suited to this kind of study, since it allows us to explicitly calculate the time evolution of the entanglement throughout the calculation. On the other hand, however, the adiabatic formalism makes it impossible to study the roles of entanglement and fidelity separately, which means that results have to be interpreted carefully. We study two algorithms: the search algorithm and the Deutsch–Jozsa algorithm. We find some evidence that entanglement can be considered a resource in quantum computation. PACS Nos.: 03.67.Mn, 03.67.Lx
Quantum entanglement is widely considered as one of the key resources for quantum-computational power. However, present interpretations of entanglement in speeding up of quantum algorithms remain far from complete. We analyze and compare the behaviors of entanglement during the adiabatic evolution of Grover's quantum search algorithms with complexity [Formula: see text] and O(1), respectively. Our results show that entanglement has a significant impact on the computational efficiency of both algorithms. That is, the greater the entanglement, the higher is the quantum computation, and vice versa. Furthermore, the correlations between entanglement and energy are discussed. It is observed that for the algorithm with complexity O(1), its entanglement degree becomes larger when the energy input into the quantum system increases, thus making the algorithm more efficient.
In the adiabatic quantum computation model, a computational procedure is described by the continuous time evolution of a time dependent Hamiltonian. Classically, the unstructured search problem can be solved only in a running time of order O(G). However, by modifying the structure of local Hamiltonian or using specific interpolating functions, it is possible to do the calculation in constant time for a quantum computer. This paper reveals the cause that lead to the speedup. We analyze two kinds of specific adiabatic quantum models, and conclude that the value of relevant elements in back-diagonal of the local Hamiltonian is the main factors affecting the time complexity of adiabatic quantum algorithms. According to the speedup mechanism, we have proposed two kinds of adiabatic quantum algorithms to make a constant time complexity.
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.