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

Loss of the quadratic speedup in Grover search under local and coherent noise

Imama Tul Birrah Khan, Muhammad Faryad

Published Nov 12, 2026• 0 citations
arXivHTMLPDF

Abstract

Grover's algorithm searches an unstructured database with a number of oracle queries that grows only as the square root of its size. Noise erodes this advantage, and we ask, analytically, how quickly. When a depolarizing channel acts on the whole register after every gate layer, it commutes with the gates, and the noisy state is the noiseless one with a coherent weight that decays geometrically with depth. The Grover rotation is not slowed. Its weight decays, the best stopping point moves earlier, and the expected query cost keeps its square-root scaling only while the accumulated noise over the circuit stays small. For independent errors on the qubits we show that the ideal Grover operator freezes any amplitude pushed out of the two-dimensional search plane. This gives the exact effect of a single error: phase flips do most damage early in the search, bit flips late, and combined errors at any time. For large databases it also reduces the noisy search to Bloch-type equations for the part of the state that stays in the plane, in which the algorithm is a rotation and the noise appears as leakage and dephasing. We derive the rates for bit-flip, phase-flip, depolarizing, and amplitude-damping noise and solve the equations. Local noise acts, to leading order, like a global channel strengthened by the number of qubits, so the tolerable error per qubit falls faster than the inverse square root of the database size by one power of the register size. For coherent errors in the rotation angle we bound the success probability by a band that widens linearly with depth. Our results recover, in closed form, scalings found earlier for particular noise models, and they explain why some errors are more harmful than others.

DOI
10.48550/arxiv.2611.16398

Related papers

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

Using quantum switches to mitigate noise in Grover’s search algorithm

Suryansh Srivastava, Arun Kumar Pati, Indranil Chakrabarty +1 more

Abstract Grover’s quantum search algorithm promises a quadratic speedup for unstructured search over its classical counterpart. But this advantage is affected by noise acting on the search space. Here, we show that a quantum switch can act as a resource to mitigate the effects of noise. In this scenario, the noise is modeled by a depolarizing channel, which coherently acts on the entire quantum register. We show that a quantum switch can significantly reduce the error in Grover’s search algorithm. We consider the success probability of finding the marked item as the sole quantifier of diminishing the effect of noise in the search space in the presence of quantum switch. We propose two frameworks for the application of quantum switches. In the first framework, we apply the superposition of channel’s orders in the form of a switch and do a post-selection at every iteration of the applications of the Grover operator. In the second framework, we delay this measurement and post-selection until the very end. The number of post selections is minimal in the second scenario, and hence the noise reduction can be attributed more to the presence of quantum switch. We illustrate with an example of significant advantage in the success probability of Grover’s algorithm using quantum switch.

arXiv:2401.05866•Journal of Physics A Mathematical and Theoretical•Dec 13, 2024•8 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

Practical Guide to Quantum Computing: Grover's Algorithm # 4

Mikhail Pavlov

Abstract This guide is based on the IBM Quantum course Phase Estimation and Factoring and focuses on Grover’s algorithm, a quantum algorithm for unstructured search problems that provides a quadratic speedup over classical approaches. In an unstructured search problem, we are given a function (often represented as an oracle) that marks one or more “correct” solutions among NNN possible candidates. A classical algorithm requires on the order of O(N)O(N)O(N) evaluations in the worst case. In contrast, Grover’s algorithm finds a solution using only O(N)O(\sqrt{N})O(N) oracle queries. This quadratic improvement implies: The quantum algorithm requires roughly the square root of the number of operations needed classically. Any classical algorithm for unstructured search must have cost at least quadratic relative to Grover’s quantum procedure. Core Idea of the Algorithm Grover’s algorithm relies on: Preparation of a uniform superposition (typically using Hadamard gates). An oracle that marks valid solutions via phase inversion. The Grover diffusion operator, which amplifies the probability amplitude of the marked states through interference. By repeatedly applying the Grover operator, the amplitude of the desired solution grows while others diminish, allowing measurement to reveal the correct answer with high probability. Practical Considerations Despite its theoretical elegance and wide applicability, the quadratic speedup of Grover’s algorithm is unlikely to yield near-term practical advantage. Modern classical hardware operates at extremely high clock rates and is vastly more mature than current quantum devices. For problem sizes accessible to today’s quantum computers, classical systems remain dominant. However, history shows that even sub-quadratic classical improvements — such as: Fast Fourier Transform (FFT) Efficient sorting algorithms like quicksort and mergesort have had transformative practical impact. The crucial distinction is that Grover’s algorithm depends on fundamentally different hardware — quantum processors — which are still in early development. Long-Term Perspective As quantum hardware advances in qubit count, coherence time, and error correction, Grover’s quadratic advantage may become practically significant for: Cryptographic key search Optimization heuristics Combinatorial search problems Amplitude amplification subroutines in broader quantum algorithms Through hands-on experimentation on IBM Q, this lesson demonstrates how theoretical amplitude amplification translates into executable quantum circuits, reinforcing the relationship between interference, probability amplitudes, and computational complexity.

•Mar 4, 2026•0 citations

Quantum Search without Global Diffusion

John Burke, Ciaran McGoldrick

Quantum search is among the most important algorithms in quantum computing. At its core is quantum amplitude amplification, a technique that achieves a quadratic speedup over classical search by combining two global reflections: the oracle, which marks the target, and the diffusion operator, which reflects about the initial state. We show that this speedup can be preserved when the oracle is the only global operator, with all other operations acting locally on non-overlapping partitions of the search register. We present a recursive construction that, when the initial and target states both decompose as tensor products over these chosen partitions, admits an exact closed-form solution for the algorithm's dynamics. This is enabled by an intriguing degeneracy in the principal angles between successive reflections, which collapse to just two distinct values governed by a single recursively defined angle. Applied to unstructured search, a problem that naturally satisfies the tensor decomposition, the approach retains the $O(\sqrt{N})$ oracle complexity of Grover search when each partition contains at least $\log_2(\log_2 N)$ qubits. On an 18-qubit search problem, partitioning into two stages reduces the non-oracle circuit depth by as much as 51%-96% relative to Grover, requiring up to 9% additional oracle calls. For larger problem sizes this oracle overhead rapidly diminishes, and valuable depth reductions persist when the oracle circuit is substantially deeper than the diffusion operator. More broadly, these results show that a global diffusion operator is not necessary to achieve the quadratic speedup in quantum search, offering a new perspective on this foundational algorithm. Moreover, the scalar reduction at the heart of our analysis inspires and motivates new directions and innovations in quantum algorithm design and evaluation.

quant-pharXiv:2604.15435•Apr 20, 2026•2 citations

The Quadratic Leap: How Grover's Algorithm is Redefining Core Problems in Computer Science and Engineering

Palaganti Venkata Nagendra Sai Sandeep

Grover's algorithm stands as a cornerstone of quantum computing, offering a theoretical quadratic speedup for unstructured search problems. This allows for finding a target item in an unsorted database of N entries in approximately the square root of N steps, a significant improvement over classical algorithms which require a number of operations on the order of N in the worst case. This speedup becomes particularly compelling for very large datasets, where classical exhaustive search becomes computationally intractable. The algorithm achieves this by leveraging fundamental quantum mechanical principles, primarily superposition and interference. It operates by preparing qubits in a uniform superposition of all possible states, then iteratively applying a quantum oracle to mark the desired state by flipping its phase, followed by a diffusion operator that amplifies the probability of the marked state. Despite its theoretical promise, real-world implementation faces substantial challenges stemming from Noisy Intermediate-Scale Quantum (NISQ) hardware, which is characterized by high error rates and short coherence times. Consequently, achieving a true, scalable quantum advantage remains a future endeavor, contingent on significant hardware advancements. Nevertheless, Grover's algorithm holds significant potential across diverse fields, including enhancing brute-force attacks on cryptographic systems, accelerating solutions for optimization problems, and speeding up search processes in machine learning and unstructured database queries.

•Aug 2, 2025•2 citations
Grover's algorithm searches an unstructured database with a number of oracle queries that grows only as the square root of its size. Noise erodes this advantage, and we ask, analytically, how quickly. When a depolarizing channel acts on the whole register after every gate layer, it commutes with the gates, and the noisy state is the noiseless one with a coherent weight that decays geometrically with depth. The Grover rotation is not slowed. Its weight decays, the best stopping point moves earlier, and the expected query cost keeps its square-root scaling only while the accumulated noise over the circuit stays small. For independent errors on the qubits we show that the ideal Grover operator freezes any amplitude pushed out of the two-dimensional search plane. This gives the exact effect of a single error: phase flips do most damage early in the search, bit flips late, and combined errors at any time. For large databases it also reduces the noisy search to Bloch-type equations for the part of the state that stays in the plane, in which the algorithm is a rotation and the noise appears as leakage and dephasing. We derive the rates for bit-flip, phase-flip, depolarizing, and amplitude-damping noise and solve the equations. Local noise acts, to leading order, like a global channel strengthened by the number of qubits, so the tolerable error per qubit falls faster than the inverse square root of the database size by one power of the register size. For coherent errors in the rotation angle we bound the success probability by a band that widens linearly with depth. Our results recover, in closed form, scalings found earlier for particular noise models, and they explain why some errors are more harmful than others.
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.
Abstract Grover’s quantum search algorithm promises a quadratic speedup for unstructured search over its classical counterpart. But this advantage is affected by noise acting on the search space. Here, we show that a quantum switch can act as a resource to mitigate the effects of noise. In this scenario, the noise is modeled by a depolarizing channel, which coherently acts on the entire quantum register. We show that a quantum switch can significantly reduce the error in Grover’s search algorithm. We consider the success probability of finding the marked item as the sole quantifier of diminishing the effect of noise in the search space in the presence of quantum switch. We propose two frameworks for the application of quantum switches. In the first framework, we apply the superposition of channel’s orders in the form of a switch and do a post-selection at every iteration of the applications of the Grover operator. In the second framework, we delay this measurement and post-selection until the very end. The number of post selections is minimal in the second scenario, and hence the noise reduction can be attributed more to the presence of quantum switch. We illustrate with an example of significant advantage in the success probability of Grover’s algorithm using quantum switch.
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.
Abstract This guide is based on the IBM Quantum course Phase Estimation and Factoring and focuses on Grover’s algorithm, a quantum algorithm for unstructured search problems that provides a quadratic speedup over classical approaches. In an unstructured search problem, we are given a function (often represented as an oracle) that marks one or more “correct” solutions among NNN possible candidates. A classical algorithm requires on the order of O(N)O(N)O(N) evaluations in the worst case. In contrast, Grover’s algorithm finds a solution using only O(N)O(\sqrt{N})O(N) oracle queries. This quadratic improvement implies: The quantum algorithm requires roughly the square root of the number of operations needed classically. Any classical algorithm for unstructured search must have cost at least quadratic relative to Grover’s quantum procedure. Core Idea of the Algorithm Grover’s algorithm relies on: Preparation of a uniform superposition (typically using Hadamard gates). An oracle that marks valid solutions via phase inversion. The Grover diffusion operator, which amplifies the probability amplitude of the marked states through interference. By repeatedly applying the Grover operator, the amplitude of the desired solution grows while others diminish, allowing measurement to reveal the correct answer with high probability. Practical Considerations Despite its theoretical elegance and wide applicability, the quadratic speedup of Grover’s algorithm is unlikely to yield near-term practical advantage. Modern classical hardware operates at extremely high clock rates and is vastly more mature than current quantum devices. For problem sizes accessible to today’s quantum computers, classical systems remain dominant. However, history shows that even sub-quadratic classical improvements — such as: Fast Fourier Transform (FFT) Efficient sorting algorithms like quicksort and mergesort have had transformative practical impact. The crucial distinction is that Grover’s algorithm depends on fundamentally different hardware — quantum processors — which are still in early development. Long-Term Perspective As quantum hardware advances in qubit count, coherence time, and error correction, Grover’s quadratic advantage may become practically significant for: Cryptographic key search Optimization heuristics Combinatorial search problems Amplitude amplification subroutines in broader quantum algorithms Through hands-on experimentation on IBM Q, this lesson demonstrates how theoretical amplitude amplification translates into executable quantum circuits, reinforcing the relationship between interference, probability amplitudes, and computational complexity.
Quantum search is among the most important algorithms in quantum computing. At its core is quantum amplitude amplification, a technique that achieves a quadratic speedup over classical search by combining two global reflections: the oracle, which marks the target, and the diffusion operator, which reflects about the initial state. We show that this speedup can be preserved when the oracle is the only global operator, with all other operations acting locally on non-overlapping partitions of the search register. We present a recursive construction that, when the initial and target states both decompose as tensor products over these chosen partitions, admits an exact closed-form solution for the algorithm's dynamics. This is enabled by an intriguing degeneracy in the principal angles between successive reflections, which collapse to just two distinct values governed by a single recursively defined angle. Applied to unstructured search, a problem that naturally satisfies the tensor decomposition, the approach retains the O(N)O(\sqrt{N})O(N​) oracle complexity of Grover search when each partition contains at least log⁡2(log⁡2N)\log_2(\log_2 N)log2​(log2​N) qubits. On an 18-qubit search problem, partitioning into two stages reduces the non-oracle circuit depth by as much as 51%-96% relative to Grover, requiring up to 9% additional oracle calls. For larger problem sizes this oracle overhead rapidly diminishes, and valuable depth reductions persist when the oracle circuit is substantially deeper than the diffusion operator. More broadly, these results show that a global diffusion operator is not necessary to achieve the quadratic speedup in quantum search, offering a new perspective on this foundational algorithm. Moreover, the scalar reduction at the heart of our analysis inspires and motivates new directions and innovations in quantum algorithm design and evaluation.
Grover's algorithm stands as a cornerstone of quantum computing, offering a theoretical quadratic speedup for unstructured search problems. This allows for finding a target item in an unsorted database of N entries in approximately the square root of N steps, a significant improvement over classical algorithms which require a number of operations on the order of N in the worst case. This speedup becomes particularly compelling for very large datasets, where classical exhaustive search becomes computationally intractable. The algorithm achieves this by leveraging fundamental quantum mechanical principles, primarily superposition and interference. It operates by preparing qubits in a uniform superposition of all possible states, then iteratively applying a quantum oracle to mark the desired state by flipping its phase, followed by a diffusion operator that amplifies the probability of the marked state. Despite its theoretical promise, real-world implementation faces substantial challenges stemming from Noisy Intermediate-Scale Quantum (NISQ) hardware, which is characterized by high error rates and short coherence times. Consequently, achieving a true, scalable quantum advantage remains a future endeavor, contingent on significant hardware advancements. Nevertheless, Grover's algorithm holds significant potential across diverse fields, including enhancing brute-force attacks on cryptographic systems, accelerating solutions for optimization problems, and speeding up search processes in machine learning and unstructured database queries.