Synthesis of Quantum Superpositions by Quantum Computation

Abstract

The quantum search algorithm can be looked at as a technique for synthesizing a particular kind of superposition—one whose amplitude is concentrated in a single basis state. This basis state is defined by a binary function $f\left(\overline{x}\right)$ that is nonzero in this desired basis state and zero everywhere else. This paper extends the quantum search algorithm to an algorithm that can create an arbitrarily specified superposition on a space of size $N$ in $O\left(\sqrt{N}\right)$ steps. The superposition is specified by a complex valued function $f\left(\overline{x}\right)$ that specifies the desired amplitude of the system in basis state $\overline{x}$.