A classical limit of Grover's algorithm induced by dephasing: Coherence vs entanglement

Abstract

A new approach to the classical limit of Grover's algorithm is discussed by assuming a very rapid dephasing of a system between consecutive Grover's unitary operations, which drives pure quantum states to decohered mixed states. One can identify a specific element among $N$ unsorted elements by a probability of the order of unity after $k\sim N$ steps of classical amplification, which is realized by a combination of Grover's unitary operation and rapid dephasing, in contrast to $k\sim \pi \sqrt{N}/4$ steps in quantum mechanical amplification. The initial two-state system with enormously unbalanced existence probabilities, which is realized by a chosen specific state and a superposition of all the rest of states among $N$ unsorted states, is crucial in the present analysis of classical amplification. This analysis illustrates Grover's algorithm in extremely noisy circumstances. A similar increase from $k\sim \sqrt{N}$ to $k\sim N$ steps due to the loss of quantum coherence takes place in the {\em analog} model of Farhi and Gutmann where the entanglement does not play an obvious role. This supports a view that entanglement is crucial in quantum computation to describe quantum states by a set of qubits, but the actual speedup of the quantum computation is based on quantum coherence.

arXiv comment15 pages. Substantially modified with an additional author and the change of the title. This version is going to be published in Mod. Phys. Lett. A

References in corpus (15)

• Quantum Annealing in the Transverse Ising Model
• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
• Strengths and Weaknesses of Quantum Computing
• Tight bounds on quantum searching
• Grover's quantum searching algorithm is optimal
• Quantum computers can search rapidly by using almost any transformation
• Sophisticated quantum search without entanglement
• Implementation of quantum search algorithm using classical Fourier optics
• Grover's search algorithm: An optical approach
• Quantum search without entanglement
• Grover's Quantum Search Algorithm for an Arbitrary Initial Mixed State
• Noise effect on Grover algorithm
• Microwave Experiments Simulating Quantum Search and Directed Transport in Artificial Graphene
• Decoherence on Grover's quantum algorithm: perturbative approach
• Noise effects in the quantum search algorithm from the computational complexity point of view

Cited by in corpus (1)

• Quantum resources in Harrow-Hassidim-Lloyd algorithm