Abstract
Quantum computing is evolving so quickly that forces us to revisit, rewrite,
and update the basis of the theory. Basic Quantum Algorithms revisits the first
quantum algorithms. It started in 1985 with Deutsch trying to evaluate a
function at two domain points simultaneously. Then, Deutsch and Jozsa created
in 1992 a quantum algorithm that determines whether a Boolean function is
constant or balanced. In the next year, Bernstein and Vazirani realized that
the same algorithm can be used to find a specific Boolean function in the set
of linear Boolean functions. In 1994, Simon presented a new 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. In the same year,
Shor created two new quantum algorithms for factoring integers and calculating
discrete logarithms, threatening the cryptography methods widely used nowadays.
In 1995, Kitaev described an alternative version for Shor's algorithms that
proved useful in many other applications. In the following year, Grover created
a quantum search algorithm quadratically faster than its classical counterpart.
In this work, all those remarkable algorithms are described in detail with a
focus on the circuit model.
Users
Please
log in to take part in the discussion (add own reviews or comments).