Narrow Results

We consider a probabilistic quantum implementation of a variation of the Pocklington–Lehmer N - 1 primality test using Shor's algorithm. O (log³ N loglog N logloglog N) elementary q-bit operations are required to determine the primality of a number N, making it (asymptotically) the fastest known primality test. Thus, the potential power of quantum mechanical computers is once again revealed.

The minimal time, T^Shor, in which a one-way quantum computer can execute Shor's algorithm is derived. In the absence of an external magnetic field, this quantity diverges at very small temperatures. This result coincides with that of Anders et al. obtained simultaneously to ours but using thermodynamical arguments. Such divergence contradicts the common belief that it is possible to do quantum computation at low temperatures. It is shown that in the presence of a weak external magnetic field, T^Shor becomes a quantized quantity which vanishes at zero temperature. Decoherence is not a problem because T^Shor/τ_dec < 10^-9, where τ_dec is decoherence time.

The prime factorization can be efficiently solved on a quantum computer. This result was given by Shor in 1994. In the first half of this article, a review of Shor's algorithm with mathematical setups is given. In the second half of this article, the prime number theorem which is an essential tool to understand the distribution of prime numbers is given.