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:1302.6005

Non-classical Correlations in the Quantum Search Algorithm

Shantanav Chakraborty, Satyabrata Adhikari

Published Feb 25, 2013• 2 citations
arXivHTMLPDF

Abstract

Entanglement lies at the heart of quantum mechanics and has no classical analogue. It is central to the speed up achieved by quantum algorithms over their classical counterparts. The Grover's search algorithm is one such algorithm which enables us to achieve a quadratic speed up over any known classical algorithm that searches for an element in an unstructured database. Here, we analyse and quantify the effects of entanglement in the generalized version of this algorithm for two qubits. By 'generalized', it is meant that the use of any arbitrary single qubit unitary gate is permitted to create superposed states. Our analysis has been firstly on a noise free environment and secondly in the presence of noise. In the absence of noise, we establish a relation between the concurrence and the amplitude of the final state thereby showing the explicit effects of entanglement on the same. Moreover, the effects of noisy channels, namely amplitude and phase damping channels are studied. We investigate the amount of quantum correlation in the states obtained after the phase inversion stage of the algorithm followed by interaction of those states with the noisy environment. The quantum correlations are quantified by geometric discord. It has been revealed that the states generated after the effect of amplitude damping on the phase inverted states of the quantum search algorithm possess non-zero quantum correlation even when entanglement is absent. However, this is absent in the phase damping scenario.

DOI
10.48550/arxiv.1302.6005

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

Correlations in the Grover search

Jian Cui, Heng Fan

The Grover search is a well-known quantum algorithm that outperforms any classical search algorithm. It is known that quantum correlations such as entanglement are responsible for the power of some quantum information protocols. But entanglement is not the only kind of quantum correlations. Other quantum correlations such as quantum discord are also useful to capture some important properties of the nonclassical correlation. Also there is no well-accepted and clear distinction between quantum correlations and classical correlations. In this paper, we systematically investigate several kinds of correlations including both quantum and classical in the whole process of the Grover search algorithm. These correlations are the concurrence, entanglement of formation, quantum discord, classical correlation and mutual information. The behaviors of quantum discord, classical correlation and mutual information are almost the same while the concurrence is different in the qubit–qubit case. For the qubit partition 1: n case, the behaviors of all correlations are qualitative the same. When the search is over, all kinds of correlations are zero, we argue that this is necessary for the final step in the search.

arXiv:0904.2703•Journal of Physics A Mathematical and Theoretical•Jan 4, 2010•124 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

Effects of initial states on the quantum correlations in the generalized Grover search algorithm*

Zhenyu Chen, Tianhui Qiu, Wenbin Zhang +1 more

We investigate the correlations between two qubits in the Grover search algorithm with arbitrary initial states by numerical simulation. Using a set of suitable bases, we construct the reduced density matrix and give the numerical expression of correlations relating to the iterations. For different initial states, we obtain the concurrence and quantum discord compared with the success probability in the algorithm. The results show that the initial states affect the correlations and the limit point of the correlations in the searching process. However, the initial states do not influence the whole cyclical trend.

Chinese Physics B•May 27, 2021•2 citations

Noise Analysis of Grover's Quantum Search Algorithm

For searching an item in unstructured databases, Grover's quantum search algorithm offers quadratic speedup overclassical search algorithms. This paper reports 2 to 5 quantum-bit (Qubit) implementations of Grover's search algorithmusing the phase-flip method for oracle function realization without any extra ancilla qubit. A comprehensive estimation andanalysis of the theoretical and physical accuracies of the algorithm have been presented. The impact of increasing qubits onaccuracy has been computed and analyzed. The metrics delineated for comparison are the number of qubits and gates, depthof the circuit, execution time, and theoretical/physical accuracy. The results revealed a greater disparity between theoreticaland physical accuracy using a higher number of qubits perceived to be caused by noisy qubits utilized in computations. Thenovelty of the work is the investigation of variations caused by the noise in the accuracy and execution time of Grover'ssearch algorithm. The results indicate that because of noise, the accuracy of 2- and 3- qubit implementations declined by14.49% and 33.86%, whereas the execution time increased by 50% and 80%; respectively.

Indian Journal of Pure & Applied Physics•Jan 1, 2023•5 citations

Invariance of success probability in Grover's quantum search under local noise with memory

Sheikh Parvez Mandal, Ahana Ghoshal, Chirag Srivastava +1 more

We analyze the robustness of Grover's quantum search algorithm performed by a quantum register under a possibly time-correlated noise acting locally on the qubits. We model the noise as originating from an arbitrary but fixed unitary evolution $U$ of some noisy qubits. The noise can occur with some probability in the interval between any pair of consecutive noiseless Grover evolutions. Although each run of the algorithm is a unitary process, the noise model leads to decoherence when all possible runs are considered. We derive a set of unitary $U$'s, called good noises, for which the success probability of the algorithm at any given time remains unchanged with varying nontrivial total number $m$ of noisy qubits in the register. The result holds irrespective of the presence of any time correlations in the noise. We show that only when $U$ is either of the Pauli matrices ${\ensuremath{\sigma}}_{x}$ and ${\ensuremath{\sigma}}_{z}$ (which give rise to $m$-qubit bit-flip and phase-damping channels, respectively, in the time-correlation-less case), the algorithm's success probability stays unchanged when increasing or decreasing $m$. In contrast, when $U$ is the Pauli matrix ${\ensuremath{\sigma}}_{y}$ (giving rise to $m$-qubit bit-phase flip channel in the time-correlation-less case), the success probability at all times stays unaltered as long as the parity (even or odd) of the total number $m$ remains the same. This asymmetry between the Pauli operators stems from the inherent symmetry-breaking existing within the Grover circuit. We further show that the positions of the noisy sites are irrelevant in the case of any of the Pauli noises. The results are illustrated in the cases of time-correlated and time-correlation-less noise. We find that the former case leads to a better performance of the noisy algorithm. We also discuss physical scenarios where our chosen noise model is of relevance.

arXiv:2112.02640•Physical Review A•Feb 21, 2023•4 citations
Entanglement lies at the heart of quantum mechanics and has no classical analogue. It is central to the speed up achieved by quantum algorithms over their classical counterparts. The Grover's search algorithm is one such algorithm which enables us to achieve a quadratic speed up over any known classical algorithm that searches for an element in an unstructured database. Here, we analyse and quantify the effects of entanglement in the generalized version of this algorithm for two qubits. By 'generalized', it is meant that the use of any arbitrary single qubit unitary gate is permitted to create superposed states. Our analysis has been firstly on a noise free environment and secondly in the presence of noise. In the absence of noise, we establish a relation between the concurrence and the amplitude of the final state thereby showing the explicit effects of entanglement on the same. Moreover, the effects of noisy channels, namely amplitude and phase damping channels are studied. We investigate the amount of quantum correlation in the states obtained after the phase inversion stage of the algorithm followed by interaction of those states with the noisy environment. The quantum correlations are quantified by geometric discord. It has been revealed that the states generated after the effect of amplitude damping on the phase inverted states of the quantum search algorithm possess non-zero quantum correlation even when entanglement is absent. However, this is absent in the phase damping scenario.
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 Grover search is a well-known quantum algorithm that outperforms any classical search algorithm. It is known that quantum correlations such as entanglement are responsible for the power of some quantum information protocols. But entanglement is not the only kind of quantum correlations. Other quantum correlations such as quantum discord are also useful to capture some important properties of the nonclassical correlation. Also there is no well-accepted and clear distinction between quantum correlations and classical correlations. In this paper, we systematically investigate several kinds of correlations including both quantum and classical in the whole process of the Grover search algorithm. These correlations are the concurrence, entanglement of formation, quantum discord, classical correlation and mutual information. The behaviors of quantum discord, classical correlation and mutual information are almost the same while the concurrence is different in the qubit–qubit case. For the qubit partition 1: n case, the behaviors of all correlations are qualitative the same. When the search is over, all kinds of correlations are zero, we argue that this is necessary for the final step in the search.
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.
We investigate the correlations between two qubits in the Grover search algorithm with arbitrary initial states by numerical simulation. Using a set of suitable bases, we construct the reduced density matrix and give the numerical expression of correlations relating to the iterations. For different initial states, we obtain the concurrence and quantum discord compared with the success probability in the algorithm. The results show that the initial states affect the correlations and the limit point of the correlations in the searching process. However, the initial states do not influence the whole cyclical trend.
For searching an item in unstructured databases, Grover's quantum search algorithm offers quadratic speedup overclassical search algorithms. This paper reports 2 to 5 quantum-bit (Qubit) implementations of Grover's search algorithmusing the phase-flip method for oracle function realization without any extra ancilla qubit. A comprehensive estimation andanalysis of the theoretical and physical accuracies of the algorithm have been presented. The impact of increasing qubits onaccuracy has been computed and analyzed. The metrics delineated for comparison are the number of qubits and gates, depthof the circuit, execution time, and theoretical/physical accuracy. The results revealed a greater disparity between theoreticaland physical accuracy using a higher number of qubits perceived to be caused by noisy qubits utilized in computations. Thenovelty of the work is the investigation of variations caused by the noise in the accuracy and execution time of Grover'ssearch algorithm. The results indicate that because of noise, the accuracy of 2- and 3- qubit implementations declined by14.49% and 33.86%, whereas the execution time increased by 50% and 80%; respectively.
We analyze the robustness of Grover's quantum search algorithm performed by a quantum register under a possibly time-correlated noise acting locally on the qubits. We model the noise as originating from an arbitrary but fixed unitary evolution UUU of some noisy qubits. The noise can occur with some probability in the interval between any pair of consecutive noiseless Grover evolutions. Although each run of the algorithm is a unitary process, the noise model leads to decoherence when all possible runs are considered. We derive a set of unitary UUU's, called good noises, for which the success probability of the algorithm at any given time remains unchanged with varying nontrivial total number mmm of noisy qubits in the register. The result holds irrespective of the presence of any time correlations in the noise. We show that only when UUU is either of the Pauli matrices ${\ensuremath{\sigma}}_{x}$ and ${\ensuremath{\sigma}}_{z}$ (which give rise to mmm-qubit bit-flip and phase-damping channels, respectively, in the time-correlation-less case), the algorithm's success probability stays unchanged when increasing or decreasing mmm. In contrast, when UUU is the Pauli matrix ${\ensuremath{\sigma}}_{y}$ (giving rise to mmm-qubit bit-phase flip channel in the time-correlation-less case), the success probability at all times stays unaltered as long as the parity (even or odd) of the total number mmm remains the same. This asymmetry between the Pauli operators stems from the inherent symmetry-breaking existing within the Grover circuit. We further show that the positions of the noisy sites are irrelevant in the case of any of the Pauli noises. The results are illustrated in the cases of time-correlated and time-correlation-less noise. We find that the former case leads to a better performance of the noisy algorithm. We also discuss physical scenarios where our chosen noise model is of relevance.