An introduction to quantum computing, without the physics

Abstract

This paper is a gentle but rigorous introduction to quantum computing intended for dis- crete mathematicians. Starting from a small set of assumptions on the behavior of quan- tum computing devices, we analyze their main characteristics, stressing the differences with classical computers, and finally describe two well-known algorithms (Simon's algo- rithm 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 no- tion of quantum mechanics. Numerical examples based on an implementation of Grover's algorithm using open-source software are provided.