Brent Kraczek and Dr. Jean-Francois Van Huele, Physics and Astronomy
Quantum computation is a recent idea of how to use quantum mechanics to improve computer performance. Although a full quantum computer has not yet been built, a few algorithms have been developed which take advantage of different aspects of quantum mechanics. David Deutsch, one of the founders of quantum computation, claims that “classical computation” is based on the mathematics allowed by classical physics–what we experience in everyday life; quantum computation is based on the mathematics allowed by quantum mechanics [1]. My research centers on understanding the differences between classical and quantum computation through one such algorithm, Shor’s prime factorization algorithm [2,3]. This included an in-depth study of the algorithm and programming and running a simulation in C++ for use on a classical computer.
Two distinct quantum properties allow increased performance: superposition and entanglement. All elementary exist in specific states (solutions of quantum differential equations), or in a superposition of those states. A superposition is not an average; quantum particles can simultaneously exist in multiple states (including being in two places at once). When the particle is measured, however, the measurement yields only one of those states, and the knowledge of what other states it was in is lost forever. For example, a photon can have either vertical or horizontal polarization, which are distinct quantum states. Most photons are in a superposition of both states, with specific probabilities of being measured in each state. When the photon is passed through a horizontal polarization filter, it will either pass through (meaning it is measured to be horizontally polarized) or it will not (vertically polarized), dependent on the probability of measuring that state.
Through physical interaction this photon can be entangled (correlated) with another so their polarizations must be opposite. When one of the photons’ polarization is measured, it is once again found to be either horizontal or vertical. The other photon, when measured, will, with 100% probability be found in the other polarization state.
In a quantum computer the memory register consists of many quantum particles that can be in one of two states, or a superposition of the two. By labeling one state as 0 and the other as 1, these particles take the place of bits in a classical computer. The different quantum bits, or qubits represent data, similar to a classical computer, but with a twist. While a classical register of three bits can represent any one of the numbers from 0 to 7, three entangled qubits can be in a super-position of any or all the possible values from 0 to 7. Furthermore, an operation performed on the quantum register would operate on each of the possible values simultaneously. With a register of N qubits this allows the computer to perform up to 2^N operations for the price of one.
This ability to perform exponentially many computations lasts until a measurement is made, so quantum algorithms are designed to raise the probabilities of correct answers, while lowering the probabilities of incorrect answers to zero. Just as with the entangled, polarized photons, the user gets only one of the values out of the computer while the other values are lost. Shor’s algorithm takes advantage of several well known tricks from number theory, and combines them with a single quantum element, a quantum discrete fourier transform, to out-perform the best know classical algorithms. The function f(a) = y^a mod N (where y and N are coprime integers and a {1, 2, 3, . . . }) is periodic, with period r. The greatest common denominators of y^(r/2) ± 1 and N are factors 173 of N, with a high probability of being not equal to 1 or N. A classical computer can quickly handle all of these calculations, except finding the period of f, which is done using the inefficient classical discrete fourier transform.
Although the quantum discrete fourier transform is efficient, any classical simulation cannot be since classical computer bits can neither be entangled, nor represent a superposition of solutions. The quantum discrete fourier transform performs on single, or sets of 2, qubits at a time. Since the entangled qubits are in a superpostion of all possible solutions, the computer only needs to operate on each distinct set of qubits once. To simulate this my program uses an array containing the complex probability amplitude of each possible state represented by a specified number of qubits. Operations are performed by multiplying the array by matrices. While a quantum register would have l qubits representing 2^l possible states, my program requires 2^l complex values (each of which uses 8 bytes) representing the probability of measuring that specific state–exponential slowdown from the quantum computer. The transformation is performed by a series of matrix multiplications which operate on each of the possible states. Given current memory constraints my simulation is presently capable of factoring numbers as high as 27. Indications are that by changing my simulation and using for-loops rather than matrices I can significantly increase this possibility, but will not match classical performance.
The real value of the simulation lies in the process of development and its ability to aid in further study of entanglement, rather than in its ability to factor numbers. In programming the simulation I had to understand every aspect of the algorithm, including learning various aspects of the number theory and the nature of the discrete fourier transform. Through this I know exactly where the shortcomings of the classical simulation are, and how quantum computation makes up for these. In the future the simulation will be used to look more closely at the properties of entanglement and how these affect the performance of a quantum computer. As it stands, my simulation follows the steps a quantum computer would to quickly factor a large number and can be used to study other aspects of quantum computation.
References
- Deutsch, D, “Quantum Theory, the Church-Turing principle and the universal quantum computer,” Proc. Roy. Soc. Lond. Vol. A400, pp. 96-117 (1985)
- Shor, P., “Algorithms for quantum computation: Discrete logarithms and factoring.” Proc. 35th Annual Symposium on FOCS, pages 124-34. IEEE Computer Society Press, 1994
- Ekert, A. and R. Jozsa, “Quantum computation and Shor’s factoring algorithm”, Rev. Mod. Physics, Vol. 68, pp. 733-53 (1996)
- Barenco, A., “Quantum physics and computers,” Contemp. Phys., Vol. 37, pp. 375-89 (1996).