Reports

The interest in quantum computing originates in the potential of a quan-tum computer to solve certain computational problems much faster than is possible classically. Examples are the factoring of integers (1) or the simulation of quantum systems (2, 3). In these examples, a quantum algorithm is exponentially faster than the best known classical algorithm. According to the extended Church-Turing thesis, all classical computers are equivalent up to polynomial factors (4). Similarly, all proposed mod-els of quantum computation are polynomially equivalent, so that a find-ing of exponential quantum speedup will be model-independent. In other cases, in particular on small devices, or when the quantum speedup is polynomial, defining and detecting quantum speedup becomes more subtle. Denoting the time used by a specific classical device or algorithm to solve a problem of size N by C(N) and the time used on the quantum device by Q(N), we define quantum speedup as the asymptotic behavior of the rati