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

Addendum to "Quantum Search with Noisy Oracle"

Ansis Rosmanis

Published May 20, 2024• 4 citations
arXivHTMLPDF

Abstract

In this note, I generalize the techniques of my recent work (arXiv:2309.14944) and show that, even if just a single known qubit of query registers is affected by the depolarizing noise of rate p, quantum search among n elements cannot be done any faster than in O(np) queries. This holds both when the affected qubit is one of the log(n) index qubits and when it is the target qubit.

DOI
10.48550/arxiv.2405.11973

Related papers

Quantum Search with Noisy Oracle

Ansis Rosmanis

We consider quantum search algorithms that have access to a noisy oracle that, for every oracle call, with probability $p>0$ completely depolarizes the query registers, while otherwise working properly. Previous results had not ruled out quantum $\mathrm{O}(\sqrt{n})$-query algorithms in this setting, even for constant $p$. We show that, for all $p\le 0.99$, the quantum noisy-query complexity of the unstructured search is $\tildeΘ(\max\{np,\sqrt{n}\})$. The lower bound $Ω(\max\{np,\sqrt n\})$ holds also for the dephasing noise and even when, for every oracle call, the algorithm is provided with a flag indicating whether the error has occurred.

arXiv:2309.14944•Sep 26, 2023•17 citations

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

Imama Tul Birrah Khan, Muhammad Faryad

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.

arXiv:2611.16398•Nov 12, 2026•0 citations

Oracle Distillation

Ruohan Shen, Soonwon Choi

Learning and sensing are among the most promising applications of quantum technology, often with provable quantum advantages. In any realistic experiment, however, noise threatens to erase these advantages as the problem size grows. We introduce oracle distillation, a procedure that distills many queries to a noisy oracle into a single high-fidelity oracle. Here the oracle, an unknown unitary from a known family, models the interface through which a quantum device learns about an unknown system. We construct an explicit protocol that distills any Boolean oracle, both under adversarial noise that corrupts a constant fraction of the input qubits and under i.i.d. depolarizing noise at a constant rate on every qubit. At the heart of the protocol is the weak query, in which the device deliberately queries the oracle only weakly, trading response strength for the ability to correct errors. Our protocol is near-optimal among all protocols that distill the oracle while keeping its errors correctable, revealing a fundamental tension between these two requirements. An important implication of the protocol is a threshold theorem: every Boolean oracle problem whose quantum advantage is polynomial in the domain size, including Grover search, $k$-forrelation, and Simon's problem, retains a quantum advantage whenever the per-qubit depolarizing rate is below a constant threshold. In particular, the quadratic quantum advantage of Grover search, long believed fragile under noise, survives nearly intact at low error rates even when almost every query involves errors on one or more qubits. We further extend the protocol to fractional and continuous-time Boolean oracles. Quantum error correction can thus protect not only prescribed operations but also unknown dynamics. Our results make a large family of quantum advantages in learning robust against noise and open a path toward robust computational sensing.

quant-pharXiv:2609.31596•Sep 28, 2026•1 citation

Grover search under localized dephasing

Daniel Reitzner, Mark S. Hillery

Decoherence in quantum searches, and in the Grover search, in particular, has already been extensively studied, leading very quickly to the loss of the quadratic speedup over the classical case, when searching for some target (marked) element within a set of size $N$. The noise models used were, however, almost always global. In this paper, we study Grover search under the influence of localized partially dephasing noise of rate $p$. We find that, in the case when the size $k$ of the affected subspace is much smaller than $N$ and the target is unaffected by the noise, namely when $kp\ensuremath{\ll}\sqrt{N}$, the quadratic speedup is retained. Once these restrictions are not met, the quadratic speedup is lost. If the target is affected by the noise, the noise rate needs to scale as $1/\sqrt{N}$ to keep the speedup. We also observe an intermediate region, where if $k\ensuremath{\sim}{N}^{\ensuremath{\mu}}$ and the target is unaffected, the speedup seems to obey ${N}^{\ensuremath{\mu}}$, which for $\ensuremath{\mu}>0.5$ is worse than the quantum, but better than the classical case. We also put obtained results for quantum searches into perspective of quantum walks and searches on graphs.

arXiv:1712.06558•Physical Review A•Jan 23, 2019•20 citations

Faster quantum searching with almost any diffusion operator

Avatar Tulsi

Grover's search algorithm drives a quantum system from an initial state $|s\ensuremath{\rangle}$ to a desired final state $|t\ensuremath{\rangle}$ by using selective phase inversions of these two states. Earlier, we studied a generalization of Grover's algorithm that relaxes the assumption of the efficient implementation of ${I}_{s}$, the selective phase inversion of the initial state, also known as a diffusion operator. This assumption is known to become a serious handicap in cases of physical interest. Our general search algorithm works with almost any diffusion operator ${D}_{s}$ with the only restriction of having $|s\ensuremath{\rangle}$ as one of its eigenstates. The price that we pay for using any operator is an increase in the number of oracle queries by a factor of $O(B)$, where $B$ is a characteristic of the eigenspectrum of ${D}_{s}$ and can be large in some situations. Here we show that by using a quantum Fourier transform, we can regain the optimal query complexity of Grover's algorithm without losing the freedom of using any diffusion operator for quantum searching. However, the total number of operators required by the algorithm is still $O(B)$ times more than that of Grover's algorithm. So our algorithm offers an advantage only if the oracle operator is computationally more expensive than the diffusion operator, which is true in most search problems.

arXiv:1503.05712•Physical Review A•May 7, 2015•11 citations

Quantum search degeneration under amplitude noise in queries to the oracle

Alexey E. Rastegin, Anzhelika M. Shemet

arXiv:2111.14333•Quantum Information Processing•Apr 27, 2022•8 citations
In this note, I generalize the techniques of my recent work (arXiv:2309.14944) and show that, even if just a single known qubit of query registers is affected by the depolarizing noise of rate p, quantum search among n elements cannot be done any faster than in O(np) queries. This holds both when the affected qubit is one of the log(n) index qubits and when it is the target qubit.
We consider quantum search algorithms that have access to a noisy oracle that, for every oracle call, with probability p>0p>0p>0 completely depolarizes the query registers, while otherwise working properly. Previous results had not ruled out quantum O(n)\mathrm{O}(\sqrt{n})O(n​)-query algorithms in this setting, even for constant ppp. We show that, for all p≤0.99p\le 0.99p≤0.99, the quantum noisy-query complexity of the unstructured search is Θ~(max⁡{np,n})\tildeΘ(\max\{np,\sqrt{n}\})Θ~(max{np,n​}). The lower bound Ω(max⁡{np,n})Ω(\max\{np,\sqrt n\})Ω(max{np,n​}) holds also for the dephasing noise and even when, for every oracle call, the algorithm is provided with a flag indicating whether the error has occurred.
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.
Learning and sensing are among the most promising applications of quantum technology, often with provable quantum advantages. In any realistic experiment, however, noise threatens to erase these advantages as the problem size grows. We introduce oracle distillation, a procedure that distills many queries to a noisy oracle into a single high-fidelity oracle. Here the oracle, an unknown unitary from a known family, models the interface through which a quantum device learns about an unknown system. We construct an explicit protocol that distills any Boolean oracle, both under adversarial noise that corrupts a constant fraction of the input qubits and under i.i.d. depolarizing noise at a constant rate on every qubit. At the heart of the protocol is the weak query, in which the device deliberately queries the oracle only weakly, trading response strength for the ability to correct errors. Our protocol is near-optimal among all protocols that distill the oracle while keeping its errors correctable, revealing a fundamental tension between these two requirements. An important implication of the protocol is a threshold theorem: every Boolean oracle problem whose quantum advantage is polynomial in the domain size, including Grover search, kkk-forrelation, and Simon's problem, retains a quantum advantage whenever the per-qubit depolarizing rate is below a constant threshold. In particular, the quadratic quantum advantage of Grover search, long believed fragile under noise, survives nearly intact at low error rates even when almost every query involves errors on one or more qubits. We further extend the protocol to fractional and continuous-time Boolean oracles. Quantum error correction can thus protect not only prescribed operations but also unknown dynamics. Our results make a large family of quantum advantages in learning robust against noise and open a path toward robust computational sensing.
Decoherence in quantum searches, and in the Grover search, in particular, has already been extensively studied, leading very quickly to the loss of the quadratic speedup over the classical case, when searching for some target (marked) element within a set of size NNN. The noise models used were, however, almost always global. In this paper, we study Grover search under the influence of localized partially dephasing noise of rate ppp. We find that, in the case when the size kkk of the affected subspace is much smaller than NNN and the target is unaffected by the noise, namely when $kp\ensuremath{\ll}\sqrt{N}$, the quadratic speedup is retained. Once these restrictions are not met, the quadratic speedup is lost. If the target is affected by the noise, the noise rate needs to scale as 1/N1/\sqrt{N}1/N​ to keep the speedup. We also observe an intermediate region, where if $k\ensuremath{\sim}{N}^{\ensuremath{\mu}}$ and the target is unaffected, the speedup seems to obey ${N}^{\ensuremath{\mu}}$, which for $\ensuremath{\mu}>0.5$ is worse than the quantum, but better than the classical case. We also put obtained results for quantum searches into perspective of quantum walks and searches on graphs.
Grover's search algorithm drives a quantum system from an initial state $|s\ensuremath{\rangle}$ to a desired final state $|t\ensuremath{\rangle}$ by using selective phase inversions of these two states. Earlier, we studied a generalization of Grover's algorithm that relaxes the assumption of the efficient implementation of Is{I}_{s}Is​, the selective phase inversion of the initial state, also known as a diffusion operator. This assumption is known to become a serious handicap in cases of physical interest. Our general search algorithm works with almost any diffusion operator Ds{D}_{s}Ds​ with the only restriction of having $|s\ensuremath{\rangle}$ as one of its eigenstates. The price that we pay for using any operator is an increase in the number of oracle queries by a factor of O(B)O(B)O(B), where BBB is a characteristic of the eigenspectrum of Ds{D}_{s}Ds​ and can be large in some situations. Here we show that by using a quantum Fourier transform, we can regain the optimal query complexity of Grover's algorithm without losing the freedom of using any diffusion operator for quantum searching. However, the total number of operators required by the algorithm is still O(B)O(B)O(B) times more than that of Grover's algorithm. So our algorithm offers an advantage only if the oracle operator is computationally more expensive than the diffusion operator, which is true in most search problems.