Basic Quantum Algorithms
This is an incremental review of early quantum algorithms, primarily for researchers and students in quantum computing.
The paper revisits foundational quantum algorithms, detailing their development from 1985 to 2009, including Shor's algorithms for integer factoring and discrete logarithms that threaten cryptography, and Grover's search algorithm offering quadratic speedup over classical methods.
Quantum computing is evolving so rapidly that it forces us to revisit, rewrite, and update the foundations of the theory. \emph{Basic Quantum Algorithms} revisits the earliest quantum algorithms. The journey began in 1985 with Deutsch attempting to evaluate a function at two domain points simultaneously. Then, in 1992, Deutsch and Jozsa created a quantum algorithm that determines whether a Boolean function is constant or balanced. The following year, Bernstein and Vazirani realized that essentially the same algorithm could be used to identify a specific Boolean function within a set of linear Boolean functions. In 1994, Simon introduced a novel quantum algorithm that determines whether a function is one-to-one or two-to-one exponentially faster than any classical algorithm for the same problem. That same year, Shor developed two groundbreaking quantum algorithms for integer factoring and calculating discrete logarithms, posing a threat to widely used cryptographic methods. In 1995, Kitaev proposed an alternative formulation based on phase estimation that proved valuable in numerous applications. The following year, Grover devised a quantum search algorithm that is quadratically faster than its classical counterpart. More than a decade later, Harrow, Hassidim, and Lloyd proposed a quantum algorithm for solving systems of linear equations, now known as the HHL algorithm. With an emphasis on the circuit model, this work provides a detailed description of all these remarkable algorithms.