Introducció matemàtica a la computació quàntica

Abstract

The purpose of this expository article is to phrase the essential notions of quantum computation in purely mathematical terms. In particular we will define the notions of q-computation, q-measurement, q-procedure, q-computer and q-algorithm, and each of them will be illustrated with several examples. In addition to some low level q-algorithms, we discuss in detail a good sample of the most relevant discovered in the last years. These include q-algorithms for the Fourier transform, for telling which alternative occurs for a Boolean function that is known to be constant or balanced (Deutsch), for database searching (Grover), for estimating the phase of an eigenvalue of a unitary operator (Kitaev), for finding the multiplicative order of an integer modulo another integer (Shor) and for factoring an integer (Shor). The possible physical realizations of the model, and its potential use to obtain gains with respect to classical algorithms (sometimes even exponential gains), are analyzed in terms of a standard axiomatic formulation of (finite dimensional) quantum theory.