An Introduction to Quantum Computing, Without the Physics

Understand

This paper is a gentle but rigorous introduction to quantum computing intended for discrete mathematicians.

• Starting from a small set of assumptions on the behavior of quantum computing devices, we analyze their main characteristics, stressing the differences with classical computers, and finally describe two well-known algorithms (Simon's algorithm and Grover's algorithm) using the formalism developed in previous sections.
• This paper does not touch on the physics of the devices, and therefore does not require any notion of quantum mechanics.
• Numerical examples on an implementation of Grover's algorithm using open-source software are provided.