Effects of Noisy Oracle on Search Algorithm Complexity

Abstract

Grover's algorithm provides a quadratic speed-up over classical algorithms for unstructured database or library searches. This paper examines the robustness of Grover's search algorithm to a random phase error in the oracle and analyzes the complexity of the search process as a function of the scaling of the oracle error with database or library size. Both the discrete- and continuous-time implementations of the search algorithm are investigated. It is shown that unless the oracle phase error scales as O(N^(-1/4)), neither the discrete- nor the continuous-time implementation of Grover's algorithm is scalably robust to this error in the absence of error correction.

16 pages, 4 figures, submitted to Phys. Rev. A

References in corpus (1)

• The effect of unitary noise on Grover's quantum search algorithm

Cited by in corpus (38)

• Adiabatic Quantum Computation in Open Systems
• Internal Consistency of Fault-Tolerant Quantum Error Correction in Light of Rigorous Derivations of the Quantum Markovian Limit
• Strengths and weaknesses of weak-strong cluster problems: A detailed overview of state-of-the-art classical heuristics vs quantum approaches
• Noise resistance of adiabatic quantum computation using random matrix theory
• Decoherence in a scalable adiabatic quantum computer
• Efficient Grover search with Rydberg blockade
• Non-ergodic delocalized states for efficient population transfer within a narrow band of the energy landscape
• Noise effect on Grover algorithm
• Non-Markovian decoherence in the adiabatic quantum search algorithm
• Noise effects in the quantum search algorithm from the computational complexity point of view
• Adiabatic Quantum Search in Open Systems
• Grover search under localized dephasing
• Central limit theorem for reducible and irreducible open quantum walks
• Quantum computation speedup limits from quantum metrological precision bounds
• Short-depth circuits for efficient expectation value estimation
• Adiabatic quantum optimization in presence of discrete noise: Reducing the problem dimensionality
• Environment-assisted analog quantum search
• A Benchmarking Study of Quantum Algorithms for Combinatorial Optimization
• Complementarity between Success Probability and Coherence in Grover Search Algorithm
• Fault Models for Quantum Mechanical Switching Networks
• Sensitivity of quantum speedup by quantum annealing to a noisy oracle
• Fault-ignorant Quantum Search
• Effect of qubit losses on Grover's quantum search algorithm
• Simulation of Grover's quantum search algorithm in a Ising nuclear spin chain quantum computer with first and second nearest neighbour couplings
• Subspace projection method for unstructured searches with noisy quantum oracles using a signal-based quantum emulation device
• Decoherence in Search Algorithms
• Self-protected adiabatic quantum computation
• Robust quantum minimum finding with an application to hypothesis selection
• Two Notes on Grover's Search: Programming and Discriminating
• Quantum Dissipative Search via Lindbladians
• Quantum algorithm for unstructured search of ranked targets
• Phases and phase transition in Grover's algorithm with systematic noise
• Performance of Grover's search algorithm with diagonalizable collective noises
• Tunable Tradeoff between Quantum and Classical Computation via Nonunitary Zeno-like Dynamics
• Correcting for Potential Barriers in Quantum Walk Search
• Multi-Armed Bandits and Quantum Channel Oracles
• A note on the runtime of a faulty Hamiltonian oracle
• Noise Effects on the Wilczek-Zee Geometric Phase