Quantum algorithms revisited

Abstract

Introduction Quantum computation is based on two quantum phenomena: quantum interference and quantum entanglement. Entanglement allows one to encode data into non-trivial multi-particle superpositions of some preselected basis states, and quantum interference, which is a dynamical process, allows one to evolve initial quantum states (inputs) into final states (outputs) modifying intermediate multi-particle superpositions in some prescribed way. Multi-particle quantum interference, unlike single particle interference, does not have any classical analogue and can be viewed as an inherently quantum process. It is natural to think of quantum computations as multi-particle processes (just as classical computations are processes involving several "particles" or bits). It turns out that viewing quantum computation as multi-particle interferometry leads to a simple and a unifying picture of known quantum algorithms. In this language quantum computers are basically mult