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

Higher-order perturbation theory for decoherence in Grover’s algorithm

Hiroo Azuma

Published Oct 4, 2005• 6 citations
arXivHTMLPDF

Abstract

In this paper, we study decoherence in Grover's quantum search algorithm using a perturbative method. We assume that each two-state system (qubit) that belongs to a register suffers a phase-flip error (${\ensuremath{\sigma}}_{z}$ error) with probability $p$ independently at every step in the algorithm, where $0\ensuremath{\leqslant}p\ensuremath{\leqslant}1$. Considering an $n$-qubit density operator to which Grover's iterative operation is applied $M$ times, we expand it in powers of $2Mnp$ and derive its matrix element order by order under the large-$n$ limit. [In this large-$n$ limit, we assume $p$ is small enough, so that $2Mnp$ can take any real positive value or zero. We regard $x\ensuremath{\equiv}2Mnp$ $(\ensuremath{\geqslant}0)$ as a perturbative parameter.] We obtain recurrence relations between terms in the perturbative expansion. By these relations, we compute higher orders of the perturbation efficiently, so that we extend the range of the perturbative parameter that provides a reliable analysis. Calculating the matrix element numerically by this method, we derive the maximum value of the perturbative parameter $x$ at which the algorithm finds a correct item with a given threshold of probability ${P}_{\mathrm{th}}$ or more. (We refer to this maximum value of $x$ as ${x}_{\mathrm{c}}$, a critical point of $x$.) We obtain a curve of ${x}_{\mathrm{c}}$ as a function of ${P}_{\mathrm{th}}$ by repeating this numerical calculation for many points of ${P}_{\mathrm{th}}$ and find the following facts: a tangent of the obtained curve at ${P}_{\mathrm{th}}=1$ is given by $x=(8∕5)(1\ensuremath{-}{P}_{\mathrm{th}})$, and we have ${x}_{\mathrm{c}}>\ensuremath{-}(8∕5){\mathrm{log}}_{e}\phantom{\rule{0.2em}{0ex}}{P}_{\mathrm{th}}$ near ${P}_{\mathrm{th}}=0$.

DOI
10.1103/physreva.72.042305

Related papers

Decoherence in Grover’s quantum algorithm: Perturbative approach

Hiroo Azuma

In this paper, we study decoherence in Grover's quantum searching algorithm using a perturbative method. We assume that each two-state system (qubit) suffers ${\ensuremath{\sigma}}_{z}$ error with probability $p(0<~p<~1)$ independently at every step in the algorithm. Considering an n-qubit density operator to which Grover's operation is applied M times, we expand it in powers of $2Mnp$ and derive its matrix element order by order under the $\stackrel{\ensuremath{\rightarrow}}{n}\ensuremath{\infty}$ limit. (In this large-n limit, we assume p is small enough, so that $2Mnp(>~0)$ can take any real positive value or $0.)$ This approach gives us an interpretation about creation of new modes caused by ${\ensuremath{\sigma}}_{z}$ error and an asymptotic form of an arbitrary-order correction. Calculating the matrix element up to the fifth-order term numerically, we investigate a region of $2Mnp$ (perturbative parameter), where the algorithm finds the correct item with a threshold of probability ${P}_{\mathrm{th}}$ or more. It satisfies $2Mnp<(8/5)(1\ensuremath{-}{P}_{\mathrm{th}})$ around $2Mnp\ensuremath{\simeq}0$ and ${P}_{\mathrm{th}}\ensuremath{\simeq}1,$ and this linear relation is applied to a wide range of ${P}_{\mathrm{th}}$ approximately. This observation is similar to a result obtained by Bernstein and Vazirani concerning accuracy of quantum gates for general algorithms. We cannot investigate a quantum-to-classical phase transition of the algorithm, because it is outside the reliable domain of our perturbation theory.

arXiv:quant-ph/0110101•Physical Review A•Apr 1, 2002•27 citations

A classical limit of Grover’s algorithm induced by dephasing: Coherence versus entanglement

Kazuo Fujikawa, C. H. Oh, Koichiro Umetsu

A new approach to the classical limit of Grover’s algorithm is discussed by assuming a very rapid dephasing of a system between consecutive Grover’s unitary operations, which drives pure quantum states to decohered mixed states. One can identify a specific element among [Formula: see text] unsorted elements by a probability of the order of unity after [Formula: see text] steps of classical amplification, which is realized by a combination of Grover’s unitary operation and rapid dephasing, in contrast to [Formula: see text] steps in quantum mechanical amplification. The initial two-state system with enormously unbalanced existence probabilities, which is realized by a chosen specific state and a superposition of all the rest of the states among [Formula: see text] unsorted states, is crucial in the present analysis of classical amplification. This analysis illustrates Grover’s algorithm in extremely noisy circumstances. A similar increase from [Formula: see text] to [Formula: see text] steps due to the loss of quantum coherence takes place in the analog model of Farhi and Gutmann where the entanglement does not play an obvious role. This supports a view that entanglement is crucial in quantum computation to describe quantum states by a set of qubits, but the actual speedup of the quantum computation is based on quantum coherence.

arXiv:1804.10082•Modern Physics Letters A•Mar 1, 2019•6 citations

Exact results on Quantum search algorithm

Saptarshi Roy Chowdhury, Swarupananda Pradhan

We generalize Grover algorithm with two arbitrary phases in a density matrix set up. We give exact analytic expressions for the success probability after arbitrary number of iteration of the generalized Grover operator as a function of number of iterations, two phase angles (α, \{beta}) and parameter ξ introduced in the off diagonal terms of the density matrix in a sense to capture the coherence present in the initial quantum register. We extend Li and Li's idea and show for the phase matching condition α = -\{beta} = 0.35π with two iterations and ξ = 1, we can achieve success probability >= 0.8 only with a knowledge about the lower bound of λ = 0.166 where λ is the ratio of marked to total number states in the database. Finally we quantify success probability of the algorithm with decrease in coherence of the initial quantum state against modest noise in this simple model.

arXiv:2207.09762•Jul 20, 2022•0 citations

Grover's search algorithm for nnn qubits with optimal number of iterations

Simanraj Sadana

The success probability of a search of $M$ targets from a database of size $N$, using Grover's search algorithm depends critically on the number of iterations of the composite operation of the oracle followed by Grover's diffusion operation. Although the required number of iterations scales as $\mathcal{O}(\sqrt{N})$ for large $N$, the asymptote is not a good indicator of the optimal number of iterations when $\sqrt{M/N}$ is not small. A scheme for the determination of the exact number of iterations, subject to a threshold set for the success probability of the search (probability of detecting the target state(s)), is crucial for the efficacy of the algorithm. In this work, a general scheme for the construction of $n$-qubit Grover's search algorithm with $1 \leq M \leq N$ target states is presented, along with the procedure to find the optimal number of iterations for a successful search. It is also shown that for given $N$ and $M$, there is an upper-bound on the success probability of the algorithm.

arXiv:2011.04051•Nov 8, 2020•1 citation

Higher-order perturbation theory for decoherence in Grover's algorithm (9 pages)

Hiroo Azuma

Physical Review A•Jan 1, 2005•1 citation

Quantum search algorithm in unstructured database

A. D. Kozhukhivskyi

Grover's quantum algorithm was developed to solve the problem of searching an unstructured database for a certain unique element. In general, this problem can be formulated as follows: an unstructured database consists of elements and contains one unique element that has a certain property that can be tested with polynomial complexity, and which must be found with minimal time and complexity. Classical methods require querying the database to find the desired element, while Grover's algorithm allows you to perform only approximately steps, which are iterations of the procedure, to the database and be sure that the resulting element will be exactly the desired element with a probability close to 1. As in quantum algorithms aimed at cryptanalysis of symmetric transformations, Grover's algorithm repeats the procedure (Grover's iteration) to increase the probability of obtaining the correct result. Similarly to such algorithms in Grover's method, when iterations are continued after reaching the required number of iterations, the probability of obtaining the correct result decreases. This is due to the fact that during the execution of Grover's iteration, a rotation is performed in the complex space. Thus, each iteration, making a turn, brings the register closer and closer to the desired state, but at a certain point a maximum closeness is reached, at which the continued use of iterations will lead to a turn past the desired state, which will move the state of the system away from the desired state. The database for this algorithm can be any search space consisting of a certain number of elements. So, for example, it can be applied to find a secret key for a symmetric cryptograms formation or to find a collision for a hashing function.

Scientific Notes of the State University of Telecommunications•Jan 1, 2022•1 citation
In this paper, we study decoherence in Grover's quantum search algorithm using a perturbative method. We assume that each two-state system (qubit) that belongs to a register suffers a phase-flip error (\ensuremathσz{\ensuremath{\sigma}}_{z}\ensuremathσz​ error) with probability ppp independently at every step in the algorithm, where 0\ensuremath⩽p\ensuremath⩽10\ensuremath{\leqslant}p\ensuremath{\leqslant}10\ensuremath⩽p\ensuremath⩽1. Considering an nnn-qubit density operator to which Grover's iterative operation is applied MMM times, we expand it in powers of 2Mnp2Mnp2Mnp and derive its matrix element order by order under the large-nnn limit. [In this large-nnn limit, we assume ppp is small enough, so that 2Mnp2Mnp2Mnp can take any real positive value or zero. We regard x\ensuremath≡2Mnpx\ensuremath{\equiv}2Mnpx\ensuremath≡2Mnp (\ensuremath⩾0)(\ensuremath{\geqslant}0)(\ensuremath⩾0) as a perturbative parameter.] We obtain recurrence relations between terms in the perturbative expansion. By these relations, we compute higher orders of the perturbation efficiently, so that we extend the range of the perturbative parameter that provides a reliable analysis. Calculating the matrix element numerically by this method, we derive the maximum value of the perturbative parameter xxx at which the algorithm finds a correct item with a given threshold of probability Pth{P}_{\mathrm{th}}Pth​ or more. (We refer to this maximum value of xxx as xc{x}_{\mathrm{c}}xc​, a critical point of xxx.) We obtain a curve of xc{x}_{\mathrm{c}}xc​ as a function of Pth{P}_{\mathrm{th}}Pth​ by repeating this numerical calculation for many points of Pth{P}_{\mathrm{th}}Pth​ and find the following facts: a tangent of the obtained curve at Pth=1{P}_{\mathrm{th}}=1Pth​=1 is given by x=(8∕5)(1\ensuremath−Pth)x=(8∕5)(1\ensuremath{-}{P}_{\mathrm{th}})x=(8∕5)(1\ensuremath−Pth​), and we have xc>\ensuremath−(8∕5)logePth{x}_{\mathrm{c}}>\ensuremath{-}(8∕5){\mathrm{log}}_{e}\phantom{\rule{0.2em}{0ex}}{P}_{\mathrm{th}}xc​>\ensuremath−(8∕5)loge​Pth​ near Pth=0{P}_{\mathrm{th}}=0Pth​=0.
In this paper, we study decoherence in Grover's quantum searching algorithm using a perturbative method. We assume that each two-state system (qubit) suffers ${\ensuremath{\sigma}}_{z}$ error with probability p(0< p< 1)p(0<~p<~1)p(0< p< 1) independently at every step in the algorithm. Considering an n-qubit density operator to which Grover's operation is applied M times, we expand it in powers of 2Mnp2Mnp2Mnp and derive its matrix element order by order under the $\stackrel{\ensuremath{\rightarrow}}{n}\ensuremath{\infty}$ limit. (In this large-n limit, we assume p is small enough, so that 2Mnp(> 0)2Mnp(>~0)2Mnp(> 0) can take any real positive value or 0.)0.)0.) This approach gives us an interpretation about creation of new modes caused by ${\ensuremath{\sigma}}_{z}$ error and an asymptotic form of an arbitrary-order correction. Calculating the matrix element up to the fifth-order term numerically, we investigate a region of 2Mnp2Mnp2Mnp (perturbative parameter), where the algorithm finds the correct item with a threshold of probability Pth{P}_{\mathrm{th}}Pth​ or more. It satisfies $2Mnp<(8/5)(1\ensuremath{-}{P}_{\mathrm{th}})$ around $2Mnp\ensuremath{\simeq}0$ and ${P}_{\mathrm{th}}\ensuremath{\simeq}1,$ and this linear relation is applied to a wide range of Pth{P}_{\mathrm{th}}Pth​ approximately. This observation is similar to a result obtained by Bernstein and Vazirani concerning accuracy of quantum gates for general algorithms. We cannot investigate a quantum-to-classical phase transition of the algorithm, because it is outside the reliable domain of our perturbation theory.
A new approach to the classical limit of Grover’s algorithm is discussed by assuming a very rapid dephasing of a system between consecutive Grover’s unitary operations, which drives pure quantum states to decohered mixed states. One can identify a specific element among [Formula: see text] unsorted elements by a probability of the order of unity after [Formula: see text] steps of classical amplification, which is realized by a combination of Grover’s unitary operation and rapid dephasing, in contrast to [Formula: see text] steps in quantum mechanical amplification. The initial two-state system with enormously unbalanced existence probabilities, which is realized by a chosen specific state and a superposition of all the rest of the states among [Formula: see text] unsorted states, is crucial in the present analysis of classical amplification. This analysis illustrates Grover’s algorithm in extremely noisy circumstances. A similar increase from [Formula: see text] to [Formula: see text] steps due to the loss of quantum coherence takes place in the analog model of Farhi and Gutmann where the entanglement does not play an obvious role. This supports a view that entanglement is crucial in quantum computation to describe quantum states by a set of qubits, but the actual speedup of the quantum computation is based on quantum coherence.
We generalize Grover algorithm with two arbitrary phases in a density matrix set up. We give exact analytic expressions for the success probability after arbitrary number of iteration of the generalized Grover operator as a function of number of iterations, two phase angles (α, \{beta}) and parameter ξ introduced in the off diagonal terms of the density matrix in a sense to capture the coherence present in the initial quantum register. We extend Li and Li's idea and show for the phase matching condition α = -\{beta} = 0.35π with two iterations and ξ = 1, we can achieve success probability >= 0.8 only with a knowledge about the lower bound of λ = 0.166 where λ is the ratio of marked to total number states in the database. Finally we quantify success probability of the algorithm with decrease in coherence of the initial quantum state against modest noise in this simple model.
The success probability of a search of MMM targets from a database of size NNN, using Grover's search algorithm depends critically on the number of iterations of the composite operation of the oracle followed by Grover's diffusion operation. Although the required number of iterations scales as O(N)\mathcal{O}(\sqrt{N})O(N​) for large NNN, the asymptote is not a good indicator of the optimal number of iterations when M/N\sqrt{M/N}M/N​ is not small. A scheme for the determination of the exact number of iterations, subject to a threshold set for the success probability of the search (probability of detecting the target state(s)), is crucial for the efficacy of the algorithm. In this work, a general scheme for the construction of nnn-qubit Grover's search algorithm with 1≤M≤N1 \leq M \leq N1≤M≤N target states is presented, along with the procedure to find the optimal number of iterations for a successful search. It is also shown that for given NNN and MMM, there is an upper-bound on the success probability of the algorithm.
Grover's quantum algorithm was developed to solve the problem of searching an unstructured database for a certain unique element. In general, this problem can be formulated as follows: an unstructured database consists of elements and contains one unique element that has a certain property that can be tested with polynomial complexity, and which must be found with minimal time and complexity. Classical methods require querying the database to find the desired element, while Grover's algorithm allows you to perform only approximately steps, which are iterations of the procedure, to the database and be sure that the resulting element will be exactly the desired element with a probability close to 1. As in quantum algorithms aimed at cryptanalysis of symmetric transformations, Grover's algorithm repeats the procedure (Grover's iteration) to increase the probability of obtaining the correct result. Similarly to such algorithms in Grover's method, when iterations are continued after reaching the required number of iterations, the probability of obtaining the correct result decreases. This is due to the fact that during the execution of Grover's iteration, a rotation is performed in the complex space. Thus, each iteration, making a turn, brings the register closer and closer to the desired state, but at a certain point a maximum closeness is reached, at which the continued use of iterations will lead to a turn past the desired state, which will move the state of the system away from the desired state. The database for this algorithm can be any search space consisting of a certain number of elements. So, for example, it can be applied to find a secret key for a symmetric cryptograms formation or to find a collision for a hashing function.