Abstract
A quantum algorithm solves computational tasks using fewer
physical resources than the best-known classical algorithm. Of most interest
are those for which an exponential reduction is achieved. The key example is
the phase estimation algorithm, which provides the quantum speedup in Shor's
factoring algorithm and quantum simulation algorithms. To date, fully quantum
experiments of this type have demonstrated only the read-out stage of quantum
algorithms, but not the steps in which input data is read in and processed to
calculate the final quantum state. Indeed, knowing the answer beforehand was
essential.