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

International Journal of Quantum Information

ENTANGLEMENT IN ADIABATIC QUANTUM SEARCHING ALGORITHMS

Wen Jiayan, Daowen Qiu

Published Oct 1, 2008• 9 citations
Publisher

Abstract

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.

DOI
10.1142/s0219749908004249

Related papers

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

The Dynamics of Entanglement in the Adiabatic Search and Deutsch Algorithms

K. Choy, Gina Passante, Daria 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.

•May 3, 2006•3 citations

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

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

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