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

Journal of the Indian Institute of Science

Role of entanglement in quantum computation

Arun Kumar Pati, Samuel L. Braunstein

Published Jan 1, 2009• 6 citations
OpenAlex

Abstract

Abstract | Quantum computers are believed to surpass their classical counterparts in speed-up and efficiency. However, the origin of this speed-up in quantum algorithms is not yet fully understood. There are indications that entanglement plays an important role in quantum computation. Quantum algorithms that do not involve entanglement appear to require an exponential amount of resources and may be efficiently simulated on a classical computer. Here we discuss the role of entanglement in quantum computation. As an illustration, we consider Grover’s algorithm and how entanglement arises in this case. We will show that even though entanglement is present throughout the computation, the change of entanglement per iteration is exponentially small for large databases. 1

Related papers

Entanglement guides quantum computation

Arun Kumar Pati

Origin of the speed‐up in quantum algorithms is not yet fully understood. But there are indications that entanglement does play an important role in quantum computation. Algorithms that do not involve entanglement can be efficiently simulated on a classical computer. Here I make a simple observation. I show that infinitesimal change in multi‐particle pure product state always gives rise to an entangled state. During quantum computation even though at each time instant the state is not entangled, it does pass through entangled states at infinitesimal time steps. This applies to multi‐particle pure, pseudo‐pure and general mixed states as well. This suggests that even though unitary operators do not produce any entanglement, quantum entanglement guides the process of quantum computation.

AIP conference proceedings•Jan 1, 2006•1 citation

Superposition, entanglement and quantum computation

Tim Forcer, Tony Hey, Douglas Alan Ross +1 more

The paper examines the roles played by superposition and entanglement in quantum computing. The analysis is illustrated by discussion of a "classical" electronic implementation of Grover's quantum search algorithm. It is shown explicitly that the absence of multi-particle entanglement leads to exponentially rising resources for implementing such quantum algorithms.

Quantum Information and Computation•Feb 1, 2002•40 citations

On the role of entanglement in quantum-computational speed-up

Richard Jozsa, Noah Linden

For any quantum algorithm operating on pure states, we prove that the presence of multi‐partite entanglement, with a number of parties that increases unboundedly with input size, is necessary if the quantum algorithm is to offer an exponential speed‐up over classical computation. Furthermore, we prove that the algorithm can be efficiently simulated classically to within a prescribed tolerance η even if a suitably small amount of global entanglement is present. We explicitly identify the occurrence of increasing multi‐partite entanglement in Shor's algorithm. Our results do not apply to quantum algorithms operating on mixed states in general and we discuss the suggestion that an exponential computational speed‐up might be possible with mixed states in the total absence of entanglement. Finally, despite the essential role of entanglement for pure‐state algorithms, we argue that it is nevertheless misleading to view entanglement as a key resource for quantum‐computational power.

arXiv:quant-ph/0201143•Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences•Aug 8, 2003•919 citations

The role of quantum correlations beyond entanglement in quantum information theory

Alexander Streltsov

Quantum entanglement is the most popular kind of quantum correlations. Its role in several tasks in quantum information theory like quantum cryptography, quantum dense coding and quantum teleportation is indisputable. The role of entanglement in quantum algorithms has also attracted enormous amount of attention in the literature. The research in this direction is motivated by the finding that a quantum computer can efficiently factorize arbitrary integer numbers. Since no classical algorithm is known today that can solve this problem efficiently, this example clearly demonstrates the superiority of a quantum computer compared to its classical counterpart. In this context, entanglement also plays a crucial role: if the quantum computer operates on a pure state without entanglement, then the computational process can be simulated efficiently on a classical computer. In this case entanglement is the key ingredient that makes the difference between a quantum and a classical computer. However, the situation is more involved if the computational process is not perfect. In this case the quantum computer operates on a mixed state, and the role of entanglement is less obvious. A seminal result in this direction is a quantum algorithm known under the acronym DQC1. This algorithm operates on an almost maximally mixed state with vanishingly little entanglement. However, DQC1 can still perform tasks efficiently for which no efficient classical algorithm is known today. Thus, it is reasonable to assume that entanglement in general is not related to the efficiency of a quantum algorithm. Triggered by this observation other kinds of quantum correlations have been studied. In this context a particular measure of quantum correlations known as quantum discord is referred to frequently in the literature. Quantum discord is a measure of quantum correlations beyond entanglement, i.e., a quantum state can have no entanglement, but nonvanishing quantum discord. Quantum discord is also regarded as the key resource in the DQC1 algorithm. Although this statement is still controversial, it was shown under very general assumptions that quantum discord is required if a quantum computer is to show an exponential speedup over any classical algorithm. In this thesis we give a short introduction into the theory of entanglement and general quantum correlations, and further discuss our results. In particular, we show that two different kinds of entanglement measures can coincide. This result is used to build an algorithm for computing entanglement. We also consider the role of quantum correlations for the distribution of entanglement and for the quantum measurement process. We further discuss the behavior of quantum correlations under local noise, and their monogamy properties.

•Jan 1, 2013•1 citation

Entanglement in the Grover's Search Algorithm

Shantanav Chakraborty, Subhashish Banerjee, Satyabrata Adhikari +1 more

Quantum Algorithms have long captured the imagination of computer scientists and physicists primarily because of the speed up achieved by them over their classical counterparts using principles of quantum mechanics. Entanglement is believed to be the primary phenomena behind this speed up. However their precise role in quantum algorithms is yet unclear. In this article, we explore the nature of entanglement in the Grover's search algorithm. This algorithm enables searching of elements from an unstructured database quadratically faster than the best known classical algorithm. Geometric measure of entanglement has been used to quantify and analyse entanglement across iterations of the algorithm. We reveal how the entanglement varies with increase in the number of qubits and also with the number of marked or solution states. Numerically, it is seen that the behaviour of the maximum value of entanglement is monotonous with the number of qubits. Also, for a given value of the number of qubits, a change in the marked states alters the amount of entanglement. The amount of entanglement in the final state of the algorithm has been shown to depend solely on the nature of the marked states. Explicit analytical expressions are given showing the variation of entanglement with the number of iterations and the global maximum value of entanglement attained across all iterations of the algorithm.

arXiv:1305.4454•May 20, 2013•20 citations

Entanglement and its role in Shor's algorithm

Viv M. Kendon, William J. Munro

Entanglement has been termed a critical resource for quantum information processing and is thought to be the reason that certain quantum algorithms, such as Shor's factoring algorithm, can achieve exponentially better performance than their classical counterparts. The nature of this resource is still not fully understood: here we use numerical simulation to investigate how entanglement between register qubits varies as Shor's algorithm is run on a quantum computer. The shifting patterns in the entanglement are found to relate to the choice of basis for the quantum Fourier transform.

arXiv:quant-ph/0412140•Quantum Information and Computation•Nov 1, 2006•44 citations
Abstract | Quantum computers are believed to surpass their classical counterparts in speed-up and efficiency. However, the origin of this speed-up in quantum algorithms is not yet fully understood. There are indications that entanglement plays an important role in quantum computation. Quantum algorithms that do not involve entanglement appear to require an exponential amount of resources and may be efficiently simulated on a classical computer. Here we discuss the role of entanglement in quantum computation. As an illustration, we consider Grover’s algorithm and how entanglement arises in this case. We will show that even though entanglement is present throughout the computation, the change of entanglement per iteration is exponentially small for large databases. 1
Origin of the speed‐up in quantum algorithms is not yet fully understood. But there are indications that entanglement does play an important role in quantum computation. Algorithms that do not involve entanglement can be efficiently simulated on a classical computer. Here I make a simple observation. I show that infinitesimal change in multi‐particle pure product state always gives rise to an entangled state. During quantum computation even though at each time instant the state is not entangled, it does pass through entangled states at infinitesimal time steps. This applies to multi‐particle pure, pseudo‐pure and general mixed states as well. This suggests that even though unitary operators do not produce any entanglement, quantum entanglement guides the process of quantum computation.
For any quantum algorithm operating on pure states, we prove that the presence of multi‐partite entanglement, with a number of parties that increases unboundedly with input size, is necessary if the quantum algorithm is to offer an exponential speed‐up over classical computation. Furthermore, we prove that the algorithm can be efficiently simulated classically to within a prescribed tolerance η even if a suitably small amount of global entanglement is present. We explicitly identify the occurrence of increasing multi‐partite entanglement in Shor's algorithm. Our results do not apply to quantum algorithms operating on mixed states in general and we discuss the suggestion that an exponential computational speed‐up might be possible with mixed states in the total absence of entanglement. Finally, despite the essential role of entanglement for pure‐state algorithms, we argue that it is nevertheless misleading to view entanglement as a key resource for quantum‐computational power.
Quantum entanglement is the most popular kind of quantum correlations. Its role in several tasks in quantum information theory like quantum cryptography, quantum dense coding and quantum teleportation is indisputable. The role of entanglement in quantum algorithms has also attracted enormous amount of attention in the literature. The research in this direction is motivated by the finding that a quantum computer can efficiently factorize arbitrary integer numbers. Since no classical algorithm is known today that can solve this problem efficiently, this example clearly demonstrates the superiority of a quantum computer compared to its classical counterpart. In this context, entanglement also plays a crucial role: if the quantum computer operates on a pure state without entanglement, then the computational process can be simulated efficiently on a classical computer. In this case entanglement is the key ingredient that makes the difference between a quantum and a classical computer. However, the situation is more involved if the computational process is not perfect. In this case the quantum computer operates on a mixed state, and the role of entanglement is less obvious. A seminal result in this direction is a quantum algorithm known under the acronym DQC1. This algorithm operates on an almost maximally mixed state with vanishingly little entanglement. However, DQC1 can still perform tasks efficiently for which no efficient classical algorithm is known today. Thus, it is reasonable to assume that entanglement in general is not related to the efficiency of a quantum algorithm. Triggered by this observation other kinds of quantum correlations have been studied. In this context a particular measure of quantum correlations known as quantum discord is referred to frequently in the literature. Quantum discord is a measure of quantum correlations beyond entanglement, i.e., a quantum state can have no entanglement, but nonvanishing quantum discord. Quantum discord is also regarded as the key resource in the DQC1 algorithm. Although this statement is still controversial, it was shown under very general assumptions that quantum discord is required if a quantum computer is to show an exponential speedup over any classical algorithm. In this thesis we give a short introduction into the theory of entanglement and general quantum correlations, and further discuss our results. In particular, we show that two different kinds of entanglement measures can coincide. This result is used to build an algorithm for computing entanglement. We also consider the role of quantum correlations for the distribution of entanglement and for the quantum measurement process. We further discuss the behavior of quantum correlations under local noise, and their monogamy properties.
Quantum Algorithms have long captured the imagination of computer scientists and physicists primarily because of the speed up achieved by them over their classical counterparts using principles of quantum mechanics. Entanglement is believed to be the primary phenomena behind this speed up. However their precise role in quantum algorithms is yet unclear. In this article, we explore the nature of entanglement in the Grover's search algorithm. This algorithm enables searching of elements from an unstructured database quadratically faster than the best known classical algorithm. Geometric measure of entanglement has been used to quantify and analyse entanglement across iterations of the algorithm. We reveal how the entanglement varies with increase in the number of qubits and also with the number of marked or solution states. Numerically, it is seen that the behaviour of the maximum value of entanglement is monotonous with the number of qubits. Also, for a given value of the number of qubits, a change in the marked states alters the amount of entanglement. The amount of entanglement in the final state of the algorithm has been shown to depend solely on the nature of the marked states. Explicit analytical expressions are given showing the variation of entanglement with the number of iterations and the global maximum value of entanglement attained across all iterations of the algorithm.
Entanglement has been termed a critical resource for quantum information processing and is thought to be the reason that certain quantum algorithms, such as Shor's factoring algorithm, can achieve exponentially better performance than their classical counterparts. The nature of this resource is still not fully understood: here we use numerical simulation to investigate how entanglement between register qubits varies as Shor's algorithm is run on a quantum computer. The shifting patterns in the entanglement are found to relate to the choice of basis for the quantum Fourier transform.