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

Laser Physics

Entropy of a needle in a haystack

Yiyuan Fang, L. C. Kwek, Keng Wah Choo, Dagomir Kaszlikowski, C. H. Oh

Published Feb 1, 2006• 1 citation
Publisher

Abstract

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.

DOI
10.1134/s1054660x06020332

Related papers

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

Multipartite entanglement and Grover's search algorithm

Ri Qu, Juan Wang, Zong-shang Li +3 more

We firstly investigate the multipartite entanglement features of the quantum states, including the iteration states achieved by repeated application of Grover iteration and the Oracle ones into which the above iteration states evolve by applying single Oracle operation, employed in Grover's search algorithm by means of the separable degree and the entanglement measure. Then we give the quantitative and qualitative descriptions of the entanglement dynamics in Grover's search algorithm. Our results show that for most instances (i) the separable degrees of these states and ranges of their maximum Schmidt numbers are invariable by following the dynamics of Grover's search algorithm; (ii) the dynamics of Grover's search algorithm is almost "filled" by the fully entangled states.

arXiv:1210.3418•Oct 12, 2012•4 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

Speed-up and entanglement in quantum Searching

Samuel L. Braunstein, Arun Kumar Pati

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.

arXiv:quant-ph/0008018•Quantum Information and Computation•Aug 1, 2002•43 citations

Tsallis relative $α$ entropy of coherence dynamics in Grover's search algorithm

Linlin Ye, Zhaoqi Wu, Shao-Ming Fei

Quantum coherence plays a central role in Grover's search algorithm. We study the Tsallis relative $α$ entropy of coherence dynamics of the evolved state in Grover's search algorithm. We prove that the Tsallis relative $α$ entropy of coherence decreases with the increase of the success probability, and derive the complementarity relations between the coherence and the success probability. We show that the operator coherence of the first $H^{\otimes n}$ relies on the size of the database $N$, the success probability and the target states. Moreover, we illustrate the relationships between coherence and entanglement of the superposition state of targets, as well as the production and deletion of coherence in Grover iterations.

quant-pharXiv:2604.13910•Communications in Theoretical Physics•Apr 16, 2026•12 citations

Determinstic Grover's Algorithm: Finding the Needle in the Haystack Every Time … Well Most Times

F. Mohit, Markus Rambach, Till J. Weinhold +3 more

Grover's algorithm is a quantum algorithm that interrogates an N-element unstructured database in$\sqrt{N}$searches as opposed to the best classical algorithm, which requires$N/2$[1]. The algorithm is non-deterministic, with a significant probability of failing that varies with the size of the database and the number of marked elements. For example, with a single marked element, the success probability is 100% for$N=4$, drops to 87% for$N=7$, is near 100% for$N=9$, and is below 94% for$N=15$. This can be improved by several repetitions of the algorithm, which, however, lowers its quadratic quantum advantage.

Conference on Lasers and Electro-Optics Europe & European Quantum Electronics Conference (CLEO/Europe-EQEC)•Jun 23, 2025•0 citations
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.
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.
We firstly investigate the multipartite entanglement features of the quantum states, including the iteration states achieved by repeated application of Grover iteration and the Oracle ones into which the above iteration states evolve by applying single Oracle operation, employed in Grover's search algorithm by means of the separable degree and the entanglement measure. Then we give the quantitative and qualitative descriptions of the entanglement dynamics in Grover's search algorithm. Our results show that for most instances (i) the separable degrees of these states and ranges of their maximum Schmidt numbers are invariable by following the dynamics of Grover's search algorithm; (ii) the dynamics of Grover's search algorithm is almost "filled" by the fully entangled states.
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.
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.
Tsallis relative ααα entropy of coherence dynamics in Grover's search algorithm
Quantum coherence plays a central role in Grover's search algorithm. We study the Tsallis relative ααα entropy of coherence dynamics of the evolved state in Grover's search algorithm. We prove that the Tsallis relative ααα entropy of coherence decreases with the increase of the success probability, and derive the complementarity relations between the coherence and the success probability. We show that the operator coherence of the first H⊗nH^{\otimes n}H⊗n relies on the size of the database NNN, the success probability and the target states. Moreover, we illustrate the relationships between coherence and entanglement of the superposition state of targets, as well as the production and deletion of coherence in Grover iterations.
Grover's algorithm is a quantum algorithm that interrogates an N-element unstructured database inN\sqrt{N}N​searches as opposed to the best classical algorithm, which requiresN/2N/2N/2[1]. The algorithm is non-deterministic, with a significant probability of failing that varies with the size of the database and the number of marked elements. For example, with a single marked element, the success probability is 100% forN=4N=4N=4, drops to 87% forN=7N=7N=7, is near 100% forN=9N=9N=9, and is below 94% forN=15N=15N=15. This can be improved by several repetitions of the algorithm, which, however, lowers its quadratic quantum advantage.