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/0008018 · Quantum Information and Computation

Speed-up and entanglement in quantum Searching

Samuel L. Braunstein, Arun Kumar Pati

Published Aug 1, 2002• 43 citations
arXivHTMLPDF

Abstract

We investigate the issue of speed-up and the necessity of entanglement in Grover's quantum search algorithm. We find that in a pure state implementation of Grover's algorithm entanglement is present even though the initial and target states are product states. In pseudo-pure state implementations, the separability of the states involved defines an entanglement boundary in terms of a bound on the purity parameter. Using this bound we investigate the necessity of entanglement in quantum searching for these pseudo-pure state implementations. If every active molecule involved in the ensemble is `charged for' then in existing machines speed-up without entanglement is not possible.

DOI
10.26421/qic2.5-6

Related papers

Quantifying computational advantage of Grover’s algorithm with the trace speed

Valentin Gebhart, Luca Pezzè, Augusto Smerzi

Despite intensive research, the physical origin of the speed-up offered by quantum algorithms remains mysterious. No general physical quantity, like, for instance, entanglement, can be singled out as the essential useful resource. Here we report a close connection between the trace speed and the quantum speed-up in Grover's search algorithm implemented with pure and pseudo-pure states. For a noiseless algorithm, we find a one-to-one correspondence between the quantum speed-up and the polarization of the pseudo-pure state, which can be connected to a wide class of quantum statistical speeds. For time-dependent partial depolarization and for interrupted Grover searches, the speed-up is specifically bounded by the maximal trace speed that occurs during the algorithm operations. Our results quantify the quantum speed-up with a physical resource that is experimentally measurable and related to multipartite entanglement and quantum coherence.

arXiv:2001.04486•Scientific Reports•Jan 14, 2021•13 citations

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

Entropy of a needle in a haystack

Yiyuan Fang, L. C. Kwek, Keng Wah Choo +2 more

In a quantum search algorithm, the initial state which is a linear superposition of all possible basis states is a separable state. At each iteration, the state becomes more and more entangled until eventually it disentangles and reverts to a separable state consisting of the marked state. It is therefore interesting to study how entanglement changes in a Grover search algorithm.

Laser Physics•Feb 1, 2006•1 citation

Entanglement

Claude Fabre, Rodrigo G. Cortiñas

Chapter devoted to the basic quantum properties of entanglement and separability. Introduces the Schmidt decomposition for pure states and the positive partial transpose criterion for mixed states as entanglement witnesses. Introduces the famous Einstein–Podolsky–Rosen paradox and its implementation in terms of qubits, then the Bell inequality, quickly reviewing the experimental demonstrations that quantum mechanics violates this inequality. Gives examples of the use of entanglement in a quantum algorithm to accelerate an information task, namely a database search (Grover algorithm) and the possibility of teleportation of a quantum state.

Cambridge University Press eBooks•Jul 27, 2023•0 citations

Coherence and Entanglement Monogamy in the Discrete Analogue of Analog Grover Search

Namit Anand, Arun Kumar Pati

Grover's search algorithm is the optimal quantum algorithm that can search an unstructured database quadratically faster than any known classical algorithm. The role of entanglement and correlations in the search algorithm have been studied in great detail and it is known that entanglement between the qubits is necessary to gain a quadratic speedup, for pure state implementation of the Grover search algorithm. Here, we systematically investigate the behavior of quantum coherence and monogamy of entanglement in the discrete analogue of the $\textit{analog analogue of Grover search algorithm}$. The analog analogue of Grover search is a continuous time quantum algorithm based on the adiabatic Hamiltonian evolution that gives a quadratic speedup, similar to the original Grover search algorithm. We show that the decrease of quantum coherence, quantified using various coherence monotones, is a clear signature of attaining the maximum success probability in the analog Grover search. We also show that for any two qubit reduced density matrix of the system, the concurrence evolves in close vicinity to the increasing rate of success probability. Furthermore, we show that the system satisfies a $n$-party monogamy inequality for arbitrary times, hence bounding the amount of $n$-qubit entanglement during the quantum search.

arXiv:1611.04542•Nov 14, 2016•53 citations

Analysis of Grover’s quantum search algorithm as a dynamical system

Ofer Biham, Daniel Shapira, Yishai Shimoni

Grover's quantum search algorithm is analyzed for the case in which the initial state is an arbitrary pure quantum state $|\ensuremath{\varphi}〉$ of n qubits. It is shown that the optimal time to perform the measurement is independent of $|\ensuremath{\varphi}〉,$ namely, it is identical to the optimal time in the original algorithm in which $|\ensuremath{\varphi}〉=|0〉,$ with the same number of marked states, r. The probability of success ${P}_{\mathrm{s}}$ is obtained in terms of the amplitudes of the state $|\ensuremath{\varphi}〉$ and is shown to be independent of r. A class of states, which includes fixed points and cycles of the Grover iteration operator, is identified. The relevance of these results in the context of using the success probability as an entanglement measure is discussed. In particular, the Groverian entanglement measure, previously limited to a single marked state, is generalized to the case of several marked states.

arXiv:quant-ph/0307141•Physical Review A•Aug 29, 2003•16 citations
We investigate the issue of speed-up and the necessity of entanglement in Grover's quantum search algorithm. We find that in a pure state implementation of Grover's algorithm entanglement is present even though the initial and target states are product states. In pseudo-pure state implementations, the separability of the states involved defines an entanglement boundary in terms of a bound on the purity parameter. Using this bound we investigate the necessity of entanglement in quantum searching for these pseudo-pure state implementations. If every active molecule involved in the ensemble is `charged for' then in existing machines speed-up without entanglement is not possible.
Despite intensive research, the physical origin of the speed-up offered by quantum algorithms remains mysterious. No general physical quantity, like, for instance, entanglement, can be singled out as the essential useful resource. Here we report a close connection between the trace speed and the quantum speed-up in Grover's search algorithm implemented with pure and pseudo-pure states. For a noiseless algorithm, we find a one-to-one correspondence between the quantum speed-up and the polarization of the pseudo-pure state, which can be connected to a wide class of quantum statistical speeds. For time-dependent partial depolarization and for interrupted Grover searches, the speed-up is specifically bounded by the maximal trace speed that occurs during the algorithm operations. Our results quantify the quantum speed-up with a physical resource that is experimentally measurable and related to multipartite entanglement and quantum coherence.
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.
Chapter devoted to the basic quantum properties of entanglement and separability. Introduces the Schmidt decomposition for pure states and the positive partial transpose criterion for mixed states as entanglement witnesses. Introduces the famous Einstein–Podolsky–Rosen paradox and its implementation in terms of qubits, then the Bell inequality, quickly reviewing the experimental demonstrations that quantum mechanics violates this inequality. Gives examples of the use of entanglement in a quantum algorithm to accelerate an information task, namely a database search (Grover algorithm) and the possibility of teleportation of a quantum state.
Grover's search algorithm is the optimal quantum algorithm that can search an unstructured database quadratically faster than any known classical algorithm. The role of entanglement and correlations in the search algorithm have been studied in great detail and it is known that entanglement between the qubits is necessary to gain a quadratic speedup, for pure state implementation of the Grover search algorithm. Here, we systematically investigate the behavior of quantum coherence and monogamy of entanglement in the discrete analogue of the analog analogue of Grover search algorithm\textit{analog analogue of Grover search algorithm}analog analogue of Grover search algorithm. The analog analogue of Grover search is a continuous time quantum algorithm based on the adiabatic Hamiltonian evolution that gives a quadratic speedup, similar to the original Grover search algorithm. We show that the decrease of quantum coherence, quantified using various coherence monotones, is a clear signature of attaining the maximum success probability in the analog Grover search. We also show that for any two qubit reduced density matrix of the system, the concurrence evolves in close vicinity to the increasing rate of success probability. Furthermore, we show that the system satisfies a nnn-party monogamy inequality for arbitrary times, hence bounding the amount of nnn-qubit entanglement during the quantum search.
Grover's quantum search algorithm is analyzed for the case in which the initial state is an arbitrary pure quantum state $|\ensuremath{\varphi}〉$ of n qubits. It is shown that the optimal time to perform the measurement is independent of $|\ensuremath{\varphi}〉,$ namely, it is identical to the optimal time in the original algorithm in which $|\ensuremath{\varphi}〉=|0〉,$ with the same number of marked states, r. The probability of success Ps{P}_{\mathrm{s}}Ps​ is obtained in terms of the amplitudes of the state $|\ensuremath{\varphi}〉$ and is shown to be independent of r. A class of states, which includes fixed points and cycles of the Grover iteration operator, is identified. The relevance of these results in the context of using the success probability as an entanglement measure is discussed. In particular, the Groverian entanglement measure, previously limited to a single marked state, is generalized to the case of several marked states.