Quantum computing · Theory (AI-assisted)
Loss of the quadratic speedup in Grover search under local and coherent noise
arXiv:2611.16398v1 ↗PDF ↗Submitted 12 November 2026
- Question
- Grover search needs about \(\pi\sqrt N/4\) iterations, and every one gives noise a chance to act. Earlier results are spread over different noise models, error placements and figures of merit, and are mostly thresholds rather than explicit success probabilities. How fast does each kind of noise erase the quadratic speedup, and why are some errors worse than others?
- Result
- With a depolarizing channel on the whole register after every gate layer, the noisy state is exactly the noiseless one weighted by \((1-p_g)^{3r+1}\) plus a maximally mixed part. The rotation is not slowed; the best stopping point moves earlier, and the expected query count keeps its \(\sqrt N\) scaling only while \(p_g\sqrt N\) is small, becoming about \(2p_gN\) beyond. For independent errors on the qubits, amplitude pushed out of the two-dimensional search plane is frozen, so a phase flip does most damage early and a bit flip late. For large \(N\) the noisy search reduces to Bloch-type equations in which local noise acts like a global channel of rate \(c\,np\), with \(c=5/8\) for bit or phase flips and \(3/4\) for depolarizing noise, so the tolerable error per qubit and layer falls as \(1/(n\sqrt N)\). Bounded coherent angle errors give a band of outcomes whose width grows linearly with depth.
The paper in detail
Write \(\ket s=\cos\alpha\ket{w^\perp}+\sin\alpha\ket w\) with \(\sin\alpha=1/\sqrt N\). Each iteration, oracle then diffusion, rotates the state by \(2\alpha\) in the plane of \(\ket{w^\perp}\) and \(\ket w\), so after \(r\) iterations the success probability is \(\sin^2[(2r+1)\alpha]\). The noise model puts a channel on every qubit after the initial Hadamard layer and after the oracle, the first Hadamard layer and the reflection \(U_0\) of each iteration, giving \(3r+1\) noisy layers. This covers gate errors and idle decoherence in one placement.
A global depolarizing channel commutes with every unitary, since it only mixes in the identity. All \(3r+1\) channels can therefore be moved to the end, and \[P_r=(1-p_g)^{3r+1}\sin^2[(2r+1)\alpha]+\frac{1-(1-p_g)^{3r+1}}{N}.\] For weak noise the peak success is about \(e^{-3\pi p_g\sqrt N/4}\) and the optimal iteration count moves earlier by \(3p_g(N-1)/8\). For \(p_g\sqrt N\gg1\) the optimum is \(r^*\approx2/(3p_g)-1/2\), independent of \(N\), and the expected query cost \(r/P_r\) is about \((3e/4)p_gN\approx2p_gN\). That is linear in \(N\), the scaling that lower bounds for a depolarizing oracle allow.
Local noise breaks the commutation, but the geometry still helps: on everything orthogonal to the search plane the Grover operator is just \(-1\). Amplitude an error pushes out of the plane is never amplified and only rarely returns, so it is lost. A phase flip keeps the marked component and scatters the rest, while a bit flip does the opposite. One error when the state sits at angle \(\theta\) leaves success about \(\sin^4\theta\) for a phase flip and \(\cos^4\theta\) for a bit flip. Averaged over a run, each costs \(5/8\) of the success probability, and a \(Y\) error costs all of it. Errors between the diffusion's Hadamard layers are seen with \(X\) and \(Z\) exchanged.
For large \(N\) the in-plane density matrix \(\bigl(\begin{smallmatrix}A&C\\C&B\end{smallmatrix}\bigr)\) obeys \(\dot A=-2\omega C-\gamma_AA\), \(\dot B=2\omega C-\gamma_BB\), \(\dot C=\omega(A-B)-\gamma_CC\), with \(\omega=2\alpha\) and rates read off by counting which errors remove which component: \((2np,np,3np)\) for bit flips, \((np,2np,3np)\) for phase flips and \((2np,2np,3np)\) for depolarizing noise. At the noiseless optimum, success decays as \(\exp[-(\bar\gamma+\kappa/2)\pi\sqrt N/4]\), with \(\bar\gamma\) the mean population decay and \(\kappa\) the extra dephasing. Amplitude damping is the gentlest channel and depends on the number of ones in the marked label.
For coherent errors each oracle may misplace the angle by up to \(\delta\) and each diffusion by up to \(\Delta\), so after \(r\) iterations the angle lies in an interval of width \(2r(\delta+\Delta)\). At the optimum the worst-case error probability is about \([\tfrac{\pi}{4}\sqrt N(\delta+\Delta)]^2\). For \(N=16\) and \(\delta+\Delta=0.06\) rad, the error is at most 0.14 at the first optimum (\(r=3\)) but anywhere between 0 and 0.35 at the second (\(r=9\)). The authors suggest extending the analysis to correlated and time-dependent errors and to other amplitude-amplification algorithms.
Transferable methods
Moving a commuting channel through the circuit
Global depolarizing noise is the one model where every noisy layer commutes with every gate. Collecting all channels at the end gives an exact success probability, from which the optimal stopping point and query cost follow by elementary calculus.
Because \(U(I/N)U^\dagger=I/N\), the channel \(\mathcal E(\rho)=(1-p)\rho+pI/N\) satisfies \(\mathcal E(U\rho U^\dagger)=U\mathcal E(\rho)U^\dagger\). Each of the \(3r+1\) channels multiplies the pure part by \(\lambda=1-p\) and moves the lost weight into \(I/N\), giving Eq. (30).
Editorial derivation of the strong-noise optimum: before the rotation completes, \(\sin[(2r+1)\alpha]\approx(2r+1)\alpha\), so maximise \(f(r)=\lambda^{3r+1}(2r+1)^2/N\). Setting \(\frac{d}{dr}\ln f=3\ln\lambda+\frac{4}{2r+1}=0\) gives \(2r+1=\frac{4}{3p}\), hence \(r^*=\frac{2}{3p}-\frac12\) and \[P^*\approx e^{-2}\Bigl(\frac{4}{3p}\Bigr)^2\frac1N=\frac{16}{9e^2}\,\frac{1}{p^2N}.\]
Editorial checks: direct density-matrix simulation of the six-qubit circuit with the global channel (\(p_g=0.01\)) matches Eq. (30) to six digits at \(r=1,3,6\). For \(n=22\), \(p_g=0.002\) (\(p_g\sqrt N\approx4.1\)), numerical optimisation gives \(r^*=321\) against 333, \(P^*=0.0138\) against 0.0143, and minimum expected cost \(1.720\times10^4\) queries against \((3e/4)p_gN=1.710\times10^4\). For \(n=10\), \(p_g=10^{-4}\), the shift of the optimum is \(-0.0384\) against \(-3p_g(N-1)/8=-0.0384\).
How to reuse it
Whenever the noise model is invariant under the circuit's unitaries, such as global depolarizing noise or a twirled channel, push all channels to the end: the output becomes the ideal state times a survival weight, and optimisation over depth is a one-variable problem.
The frozen complement and the Grover-plane equations
Local errors leave the two-dimensional plane, which seemed to require the full \(2^n\)-dimensional dynamics. The observation that the Grover operator acts as \(-1\) outside the plane means escaped amplitude stays out and can be dropped, which leaves a three-variable linear system.
For \(\ket\chi\perp\ket{w^\perp},\ket w\), the oracle leaves \(\ket\chi\) unchanged and the diffusion \(2\ket s\bra s-I\) sends it to \(-\ket\chi\), so \(G\ket\chi=-\ket\chi\). Projected onto the plane, \(Z_k\) keeps \(\ket w\bra w\) and shrinks the \(\ket{w^\perp}\) part to \(-1/(N-1)\), while \(X_k\) keeps the \(\ket{w^\perp}\) part up to \(O(1/N)\) and couples to \(\ket w\) only at order \(1/\sqrt N\). Per layer, \(A\) survives with probability \((1-p_z-p_y)^n\), \(B\) with \((1-p_x-p_y)^n\) and \(C\) with \((1-p)^n\). Summing one direct and two Hadamard-conjugated layers per iteration gives the rates of Table 1.
With \(\bar\gamma=(\gamma_A+\gamma_B)/2\) and \(\kappa=(\gamma_C-\bar\gamma)/2\), the effective decay at the optimum is \(\bar\gamma+\kappa/2\): \(\tfrac{15}{8}np=3\cdot\tfrac58np\) for bit or phase flips and \(\tfrac94np=3\cdot\tfrac34np\) for depolarizing noise. These are the single-error costs \(5/8\) and \(3/4\) times three layers, and the budget \(p\lesssim1/(c\,n\sqrt N)\) follows (editorial arithmetic from Table 1).
Editorial check by exact density-matrix simulation with \(p=0.003\) per qubit and layer at the noiseless optimum. For \(n=8\) (\(r=12\)) the exact success probabilities are 0.591 (bit flip), 0.564 (phase flip) and 0.518 (depolarizing), against 0.588, 0.581 and 0.523 from the Grover-plane equations; for \(n=6\) the gaps are similar. The phase-flip case shows the largest deviation, about 0.02, and bit-flip noise is indeed slightly less harmful than phase-flip noise, as the paper states.
How to reuse it
For any algorithm confined to a small invariant subspace by an operator that is trivial on its complement, local noise can be modelled as leakage plus dephasing of that subspace. Counting which Pauli errors remove which component gives the rates without simulating the full register.
Context & limitations
Why it matters. The closed forms give a first noise budget for any routine built on amplitude amplification, recover earlier scalings (Azuma's 5/8, the local-depolarizing threshold of Cohn and co-workers, the \(1/\sqrt N\) tolerance to systematic phase errors) and explain the extra factor of \(n\) for local noise: it counts the qubits that can each fail.
Limitations. The oracle and the diffusion reflection are each treated as one noisy layer; compiled into elementary gates, both have depth growing with \(n\), which would tighten the budget further. The Grover-plane equations drop terms of order \(1/\sqrt N\) and returns into the plane of order \(1/n\); in an editorial exact simulation at 6 and 8 qubits they were within 0.02 of the true success probability. The coherent-error result is a worst-case band, not a distribution. The authors state that Claude (Anthropic) was used to revise the text, check the derivations and develop and extend the analytical results, and to write the plotting code.