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:1610.08656 · Physical Review A

Coherence depletion in the Grover quantum search algorithm

Hailong Shi, Siyuan Liu, Xiao-Hui Wang, Wen‐Li Yang, Zhan-Ying Yang, Heng Fan

Published Mar 7, 2017• 180 citations
arXivHTMLPDF

Abstract

We investigate the role of quantum coherence depletion (QCD) in the Grover search algorithm (GA) by using several typical measures of quantum coherence and quantum correlations. By using the relative entropy of coherence measure (${\mathcal{C}}_{r}$), we show that the success probability depends on the QCD. The same phenomenon is also found by using the ${l}_{1}$ norm of coherence measure (${\mathcal{C}}_{{l}_{1}}$). In the limit case, the cost performance is defined to characterize the behavior about QCD in enhancing the success probability of GA, which is only related to the number of searcher items and the scale of the database, regardless of using ${\mathcal{C}}_{r}$ or ${\mathcal{C}}_{{l}_{1}}$. In the generalized Grover search algorithm (GGA), the QCD for a class of states increases with the required optimal measurement time. In comparison, the quantification of other quantum correlations in GA, such as pairwise entanglement, multipartite entanglement, pairwise discord, and genuine multipartite discord, cannot be directly related to the success probability or the optimal measurement time. Additionally, we do not detect pairwise nonlocality or genuine tripartite nonlocality in GA since Clauser-Horne-Shimony-Holt inequality and Svetlichny's inequality are not violated.

DOI
10.1103/physreva.95.032307

Related papers

Complementarity between success probability and coherence in Grover search algorithm

Minghua Pan, Haozhen Situ, Shenggen Zheng

Abstract Coherence plays a very important role in Grover search algorithm (GSA). In this paper, we define the normalization coherence , where C is a coherence measurement. By virtue of the constraint of large N and Shannon's maximum entropy principle, a surprising complementary relationship between the coherence and the success probability of GSA is obtained. Namely, , where C is in terms of the relative entropy of coherence and l 1 norm of coherence, t is the number of the search iterations in GSA. Moreover, the equation holds no matter either in ideal or noisy environments. Considering the number of qubits is limited in the recent noisy intermediate-scale quantum (NISQ) era, some exact numerical calculation experiments are presented for different database sizes N with different types of noises. The results show that the complementarity between the success probability and the coherence almost always holds. This work provides a new perspective to improve the success probability by manipulating its complementary coherence, and vice versa. It has an excellent potential for helping quantum algorithms design in the NISQ era.

arXiv:2205.09268•Europhysics Letters (EPL)•May 1, 2022•12 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

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

Performance of various correlation measures in quantum phase transitions using the quantum renormalization-group method

Yao Yao, Hong-Wei Li, Chun-Mei Zhang +4 more

We have investigated the quantum phase transition employing the quantum renormalization-group method while, in most of the previous literature, entanglement (concurrence) has been barely demonstrated. However, it is now well known that entanglement is not the only signature of quantum correlations and a variety of computable measures have been developed to characterize quantum correlations in the composite systems. As an illustration, two cases are elaborated: a one-dimensional anisotropic (i) $XXZ$ model and (ii) an $XY$ model, with various measures of quantum correlations, including quantum discord, geometric discord, measurement-induced disturbance, measurement-induced nonlocality, and violation of Bell inequalities [e.g., Clauser-Horne-Shimony-Holt (CHSH) inequality]. We have proved that all of these correlation measures can effectively detect the quantum critical points associated with quantum phase transitions after several iterations of the renormalization in both cases. Nonetheless, it is shown that some of their dynamical behaviors are not totally similar with entanglement and, even when concurrence vanishes, there still exists some kind of quantum correlation which is not captured by entanglement. Intriguingly, CHSH inequality can never be violated in the whole iteration procedure, which indicates that block-block entanglement cannot revealed by the CHSH inequality. Moreover, the nonanalytic and scaling behaviors of Bell violation have also been discussed in detail. As a by-product, we verify that measurement-induced disturbance is exactly equal to the quantum discord measured by ${\ensuremath{\sigma}}_{z}$ for general $\mathsf{X}$-structured states.

arXiv:1206.1202•Physical Review A•Oct 3, 2012•74 citations

Operator coherence dynamics in Grover's quantum search algorithm

Minghua Pan, Daowen Qiu

Coherence is one of the most basic concepts and resources in quantum information. To clear the role coherence plays on the essential operator level in Grover's search algorithm, here we discuss the coherence dynamics of the state after each basic operator is applyied. As it is known, Grover's search algorithm repeats the application of Grover operator $G$, which can be decomposed into $G={H}^{\ensuremath{\bigotimes}n}P{H}^{\ensuremath{\bigotimes}n}O$, where $H$ is Hadamard operator, $P$ is the condition phase-shift operator, and $O$ is the oracle operator. First, we show that $O$ and $P$ are incoherent operators while ${H}^{\ensuremath{\bigotimes}n}$ is coherent. Second, we prove that the amount of the operator coherence of the first ${H}^{\ensuremath{\bigotimes}n}$ and the operator coherence produced or depleted by ${H}^{\ensuremath{\bigotimes}n}$ depends not only on the size of the database and the success probability, but also on target states. Moreover, the amount of operator coherence is larger when the superposition state of targets is entangled rather than product. Third, we show that the two ${H}^{\ensuremath{\bigotimes}n}$ have different effects on coherence that one produces coherence and the other depletes coherence, and the depletion plays a major role. Therefore, the coherence is vibrating during the search process and the overall effect is that coherence is in depletion.

Physical Review A•Jul 31, 2019•25 citations

Coherence Fraction in Grover Search Algorithm

Si-Qi Zhou, Hai Jin, Jin-Min Liang +3 more

The question of which resources drive the advantages in quantum algorithms has long been a fundamental challenge. While entanglement and coherence are critical to many quantum algorithms, our results indicate that they do not fully explain the quantum advantage achieved by the Grover search algorithm. By introducing a generalized Grover search algorithm, we demonstrate that the success probability depends not only on the querying number of oracles but also on the coherence fraction, which quantifies the fidelity between an arbitrary initial quantum state and the equal superposition state. Additionally, we explore the role of the coherence fraction in the quantum minimization algorithm, which offers a framework for solving complex problems in quantum machine learning. These findings offer insights into the origins of quantum advantage and open pathways for the development of new quantum algorithms.

quant-pharXiv:2511.06835•Physical Review A•Nov 11, 2025•6 citations
We investigate the role of quantum coherence depletion (QCD) in the Grover search algorithm (GA) by using several typical measures of quantum coherence and quantum correlations. By using the relative entropy of coherence measure (Cr{\mathcal{C}}_{r}Cr​), we show that the success probability depends on the QCD. The same phenomenon is also found by using the l1{l}_{1}l1​ norm of coherence measure (Cl1{\mathcal{C}}_{{l}_{1}}Cl1​​). In the limit case, the cost performance is defined to characterize the behavior about QCD in enhancing the success probability of GA, which is only related to the number of searcher items and the scale of the database, regardless of using Cr{\mathcal{C}}_{r}Cr​ or Cl1{\mathcal{C}}_{{l}_{1}}Cl1​​. In the generalized Grover search algorithm (GGA), the QCD for a class of states increases with the required optimal measurement time. In comparison, the quantification of other quantum correlations in GA, such as pairwise entanglement, multipartite entanglement, pairwise discord, and genuine multipartite discord, cannot be directly related to the success probability or the optimal measurement time. Additionally, we do not detect pairwise nonlocality or genuine tripartite nonlocality in GA since Clauser-Horne-Shimony-Holt inequality and Svetlichny's inequality are not violated.
Abstract Coherence plays a very important role in Grover search algorithm (GSA). In this paper, we define the normalization coherence , where C is a coherence measurement. By virtue of the constraint of large N and Shannon's maximum entropy principle, a surprising complementary relationship between the coherence and the success probability of GSA is obtained. Namely, , where C is in terms of the relative entropy of coherence and l 1 norm of coherence, t is the number of the search iterations in GSA. Moreover, the equation holds no matter either in ideal or noisy environments. Considering the number of qubits is limited in the recent noisy intermediate-scale quantum (NISQ) era, some exact numerical calculation experiments are presented for different database sizes N with different types of noises. The results show that the complementarity between the success probability and the coherence almost always holds. This work provides a new perspective to improve the success probability by manipulating its complementary coherence, and vice versa. It has an excellent potential for helping quantum algorithms design in the NISQ era.
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.
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.
We have investigated the quantum phase transition employing the quantum renormalization-group method while, in most of the previous literature, entanglement (concurrence) has been barely demonstrated. However, it is now well known that entanglement is not the only signature of quantum correlations and a variety of computable measures have been developed to characterize quantum correlations in the composite systems. As an illustration, two cases are elaborated: a one-dimensional anisotropic (i) XXZXXZXXZ model and (ii) an XYXYXY model, with various measures of quantum correlations, including quantum discord, geometric discord, measurement-induced disturbance, measurement-induced nonlocality, and violation of Bell inequalities [e.g., Clauser-Horne-Shimony-Holt (CHSH) inequality]. We have proved that all of these correlation measures can effectively detect the quantum critical points associated with quantum phase transitions after several iterations of the renormalization in both cases. Nonetheless, it is shown that some of their dynamical behaviors are not totally similar with entanglement and, even when concurrence vanishes, there still exists some kind of quantum correlation which is not captured by entanglement. Intriguingly, CHSH inequality can never be violated in the whole iteration procedure, which indicates that block-block entanglement cannot revealed by the CHSH inequality. Moreover, the nonanalytic and scaling behaviors of Bell violation have also been discussed in detail. As a by-product, we verify that measurement-induced disturbance is exactly equal to the quantum discord measured by ${\ensuremath{\sigma}}_{z}$ for general X\mathsf{X}X-structured states.
Coherence is one of the most basic concepts and resources in quantum information. To clear the role coherence plays on the essential operator level in Grover's search algorithm, here we discuss the coherence dynamics of the state after each basic operator is applyied. As it is known, Grover's search algorithm repeats the application of Grover operator GGG, which can be decomposed into $G={H}^{\ensuremath{\bigotimes}n}P{H}^{\ensuremath{\bigotimes}n}O$, where HHH is Hadamard operator, PPP is the condition phase-shift operator, and OOO is the oracle operator. First, we show that OOO and PPP are incoherent operators while ${H}^{\ensuremath{\bigotimes}n}$ is coherent. Second, we prove that the amount of the operator coherence of the first ${H}^{\ensuremath{\bigotimes}n}$ and the operator coherence produced or depleted by ${H}^{\ensuremath{\bigotimes}n}$ depends not only on the size of the database and the success probability, but also on target states. Moreover, the amount of operator coherence is larger when the superposition state of targets is entangled rather than product. Third, we show that the two ${H}^{\ensuremath{\bigotimes}n}$ have different effects on coherence that one produces coherence and the other depletes coherence, and the depletion plays a major role. Therefore, the coherence is vibrating during the search process and the overall effect is that coherence is in depletion.
The question of which resources drive the advantages in quantum algorithms has long been a fundamental challenge. While entanglement and coherence are critical to many quantum algorithms, our results indicate that they do not fully explain the quantum advantage achieved by the Grover search algorithm. By introducing a generalized Grover search algorithm, we demonstrate that the success probability depends not only on the querying number of oracles but also on the coherence fraction, which quantifies the fidelity between an arbitrary initial quantum state and the equal superposition state. Additionally, we explore the role of the coherence fraction in the quantum minimization algorithm, which offers a framework for solving complex problems in quantum machine learning. These findings offer insights into the origins of quantum advantage and open pathways for the development of new quantum algorithms.