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/0112097 · Physical Review A

Entanglement monotone derived from Grover’s algorithm

Ofer Biham, Michael A. Nielsen, Tobias J. Osborne

Published Jun 13, 2002• 63 citations
arXivHTMLPDF

Abstract

This paper demonstrates that how well a state performs as an input to Grover's search algorithm depends critically upon the entanglement present in that state; the more the entanglement, the less well the algorithm performs. More precisely, suppose we take a pure state input, and prior to running the algorithm apply local unitary operations to each qubit in order to maximize the probability ${P}_{\mathrm{max}}$ that the search algorithm succeeds. We prove that, for pure states, ${P}_{\mathrm{max}}$ is an entanglement monotone, in the sense that ${P}_{\mathrm{max}}$ can never be decreased by local operations and classical communication.

DOI
10.1103/physreva.65.062312

Related papers

Entanglement of multipartite quantum states and the generalized quantum search

Robert M. Gingrich

In chapter 2 various parameterizations for the orbits under local unitary transformations of three-qubit pure states are analyzed. It is shown that the entanglement monotones of any multipartite pure state uniquely determine the orbit of that state. It follows that there must be an entanglement monotone for three-qubit pure states which depends on the Kempe invariant defined in [1]. A form for such an entanglement monotone is proposed. A theorem is proved that significantly reduces the number of entanglement monotones that must be looked at to find the maximal probability of transforming one multipartite state to another. In chapter 3 Grover's unstructured quantum search algorithm is generalized to use an arbitrary starting superposition and an arbitrary unitary matrix. A formula for the probability of the generalized Grover's algorithm succeeding after n iterations is derived. This formula is used to determine the optimal strategy for using the unstructured quantum search algorithm. The speedup obtained illustrates that a hybrid use of quantum computing and classical computing techniques can yield a performance that is better than either alone. The analysis is extended to the case of a society of k quantum searches acting in parallel. In chapter 4 the positive map Г : p → (Trρ) - ρ is introduced as a separability criterion. Any separable state is mapped by the tensor product of Г and the identity in to a non-negative operator, which provides a necessary condition for separability. If Г acts on a two-dimensional subsystem, then it is equivalent to partial transposition and therefore also sufficient for 2 x 2 and 2 x 3 systems. Finally, a connection between this map for two qubits and complex conjugation in the magic basis [2] is displayed.

•Sep 1, 2002•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•24 citations

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•9 citations

Groverian measure of entanglement for mixed states

Daniel Shapira, Yishai Shimoni, Ofer Biham

The Groverian entanglement measure, introduced earlier for pure quantum states of multiple qubits [O. Biham, M.A. Nielsen, and T. Osborne, Phys. Rev. A 65, 062312 (2002)], is generalized to the case of mixed states. The Groverian measure of a mixed state of $n$ qubits is obtained by a purification procedure into a pure state of $2n$ qubits, followed by an optimization process, before the resulting state is fed into Grover's search algorithm. It is expressed in terms of the maximal success probability of the algorithm and in this sense provides an operational measure of entanglement.

arXiv:quant-ph/0508108•Physical Review A•Apr 5, 2006•32 citations

Quantifying entanglement in terms of an operational way*

Deng-hui Yu, Chang‐shui Yu

We establish entanglement monotones in terms of an operational approach, which is closely connected with the state conversion from pure states to the objective state by the local operations and classical communications. It is shown that any good entanglement quantifier defined on pure states can induce an entanglement monotone for all density matrices. Particularly, we show that our entanglement monotone is the maximal one among all those having the same form for pure states. In some special cases, our proposed entanglement monotones turn to be equivalent to the convex roof construction, which hence gain an operational meaning. Some examples are given to demonstrate different cases.

arXiv:2109.02888•Chinese Physics B•Oct 15, 2020•3 citations

Infinitesimal local operations and differential conditions for entanglement monotones

Ognyan Oreshkov, Todd A. Brun

Much of the theory of entanglement concerns the transformations that are possible to a state under local operations with classical communication (LOCC); however, this set of operations is complicated and difficult to describe mathematically. An idea which has proven very useful is that of the entanglement monotone: a function of the state which is invariant under local unitary transformations and always decreases (or increases) on average after any local operation. In this paper we look on LOCC as the set of operations generated by infinitesimal local operations, operations which can be performed locally and which leave the state little changed. We show that a necessary and sufficient condition for a function of the state to be an entanglement monotone under local operations that do not involve information loss is that the function be a monotone under infinitesimal local operations. We then derive necessary and sufficient differential conditions for a function of the state to be an entanglement monotone. We first derive two conditions for local operations without information loss, and then show that they can be extended to more general operations by adding the requirement of convexity. We then demonstrate that a number of known entanglement monotones satisfy these differential criteria. Finally, as an application, we use the differential conditions to construct a new polynomial entanglement monotone for three-qubit pure states. It is our hope that this approach will avoid some of the difficulties in the theory of multipartite and mixed-state entanglement.

arXiv:quant-ph/0506181•Physical Review A•Apr 13, 2006•6 citations
This paper demonstrates that how well a state performs as an input to Grover's search algorithm depends critically upon the entanglement present in that state; the more the entanglement, the less well the algorithm performs. More precisely, suppose we take a pure state input, and prior to running the algorithm apply local unitary operations to each qubit in order to maximize the probability Pmax{P}_{\mathrm{max}}Pmax​ that the search algorithm succeeds. We prove that, for pure states, Pmax{P}_{\mathrm{max}}Pmax​ is an entanglement monotone, in the sense that Pmax{P}_{\mathrm{max}}Pmax​ can never be decreased by local operations and classical communication.
In chapter 2 various parameterizations for the orbits under local unitary transformations of three-qubit pure states are analyzed. It is shown that the entanglement monotones of any multipartite pure state uniquely determine the orbit of that state. It follows that there must be an entanglement monotone for three-qubit pure states which depends on the Kempe invariant defined in [1]. A form for such an entanglement monotone is proposed. A theorem is proved that significantly reduces the number of entanglement monotones that must be looked at to find the maximal probability of transforming one multipartite state to another. In chapter 3 Grover's unstructured quantum search algorithm is generalized to use an arbitrary starting superposition and an arbitrary unitary matrix. A formula for the probability of the generalized Grover's algorithm succeeding after n iterations is derived. This formula is used to determine the optimal strategy for using the unstructured quantum search algorithm. The speedup obtained illustrates that a hybrid use of quantum computing and classical computing techniques can yield a performance that is better than either alone. The analysis is extended to the case of a society of k quantum searches acting in parallel. In chapter 4 the positive map Г : p → (Trρ) - ρ is introduced as a separability criterion. Any separable state is mapped by the tensor product of Г and the identity in to a non-negative operator, which provides a necessary condition for separability. If Г acts on a two-dimensional subsystem, then it is equivalent to partial transposition and therefore also sufficient for 2 x 2 and 2 x 3 systems. Finally, a connection between this map for two qubits and complex conjugation in the magic basis [2] is displayed.
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.
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.
The Groverian entanglement measure, introduced earlier for pure quantum states of multiple qubits [O. Biham, M.A. Nielsen, and T. Osborne, Phys. Rev. A 65, 062312 (2002)], is generalized to the case of mixed states. The Groverian measure of a mixed state of nnn qubits is obtained by a purification procedure into a pure state of 2n2n2n qubits, followed by an optimization process, before the resulting state is fed into Grover's search algorithm. It is expressed in terms of the maximal success probability of the algorithm and in this sense provides an operational measure of entanglement.
We establish entanglement monotones in terms of an operational approach, which is closely connected with the state conversion from pure states to the objective state by the local operations and classical communications. It is shown that any good entanglement quantifier defined on pure states can induce an entanglement monotone for all density matrices. Particularly, we show that our entanglement monotone is the maximal one among all those having the same form for pure states. In some special cases, our proposed entanglement monotones turn to be equivalent to the convex roof construction, which hence gain an operational meaning. Some examples are given to demonstrate different cases.
Much of the theory of entanglement concerns the transformations that are possible to a state under local operations with classical communication (LOCC); however, this set of operations is complicated and difficult to describe mathematically. An idea which has proven very useful is that of the entanglement monotone: a function of the state which is invariant under local unitary transformations and always decreases (or increases) on average after any local operation. In this paper we look on LOCC as the set of operations generated by infinitesimal local operations, operations which can be performed locally and which leave the state little changed. We show that a necessary and sufficient condition for a function of the state to be an entanglement monotone under local operations that do not involve information loss is that the function be a monotone under infinitesimal local operations. We then derive necessary and sufficient differential conditions for a function of the state to be an entanglement monotone. We first derive two conditions for local operations without information loss, and then show that they can be extended to more general operations by adding the requirement of convexity. We then demonstrate that a number of known entanglement monotones satisfy these differential criteria. Finally, as an application, we use the differential conditions to construct a new polynomial entanglement monotone for three-qubit pure states. It is our hope that this approach will avoid some of the difficulties in the theory of multipartite and mixed-state entanglement.