Noise effects in the quantum search algorithm from the computational complexity point of view

Abstract

We analyse the resilience of the quantum search algorithm in the presence of quantum noise modelled as trace preserving completely positive maps. We study the influence of noise on computational complexity of the quantum search algorithm. We show that only for small amounts of noise the quantum search algorithm is still more efficient than any classical algorithm.

7 pages, 2 figures

References in corpus (1)

• Noise effect on Grover algorithm

Cited by in corpus (11)

• Qubit flip game on a Heisenberg spin chain
• A Benchmarking Study of Quantum Algorithms for Combinatorial Optimization
• Complementarity between Success Probability and Coherence in Grover Search Algorithm
• Enhancing pseudo-telepathy in the Magic Square game
• A classical limit of Grover's algorithm induced by dephasing: Coherence vs entanglement
• A model for quantum queue
• Concise Quantum Associative Memories with Nonlinear Search Algorithm
• Invariance of success probability in Grover's quantum search under local noise with memory
• Performance of Grover's search algorithm with diagonalizable collective noises
• A note on the runtime of a faulty Hamiltonian oracle
• Search Via quantum walks with intermediate measurements