Richard Feynman the Nobel prize-winning physicist in 1982 was the first person that thought up the idea of a 'quantum computer'. Based on his idea, a quantum computer uses the effects of quantum mechanics to its advantage. [1] For a while after that, the notion of a quantum computer was only a theoretical interest but invention of an algorithm to factor large numbers on a quantum computer, by Peter Shor has bought the idea to everybody's attention. A quantum computer would be able to crack codes much more quicker than any ordinary or classical computer could. In fact a quantum computer capable of performing Shor's algorithm would be able to break current cryptography techniques in a matter of seconds. With the motivation provided by this algorithm, the topic of quantum computing has gathered momentum and researchers around the world are racing to be the first to create a practical quantum computer.
Shor's algorithm hinges on a result from number theory. Here is the result, the function f(a) =xa mod n is a periodic function, where x is an integer coprime to n. In the context of Shor's algorithm n will be the number we wish to factor. When two numbers are coprime it means that their greatest common divisor is 1. Calculating this function for an exponential number of a's would take exponential time on a classical computer. Shor's algorithm utilizes quantum parallelism to perform the exponential number of operations in one step. Since f(a) is a periodic function, it has some period r. We know that x0 mod n = 1, so xr mode n = 1, and x(2r) mod n =1 and so on since the function is periodic. Given this information and through the following algebraic manipulation:
and if r is an even number
We can see that the product (x(r/2) -1)(x(r/2) +1 ) is an integer multiple of n, the number to be factored. So long as x(r/2) is not equal to ±1, then at least one of (x(r/2) -1), (x(r/2) + 1) must have a nontrivial factor in common with n. So by computing gcd(x(r/2) -1, n), and gcd(x(r/2) +1, n), we will obtain a factor of n, where gcd is the greatest common denominator function. [2]
As we know a bit, the most fundamental building block in the classical model of a computer can only exist in one of two distinct states, a 0 or a 1. The rules are changed in a quantum computer. [3] In a quantum computer we define a quantum bit or a qubit, which not only can exist in the classical 0 and 1 states, it can also be in a coherent superposition of both. When a qubit is in this state it can be considered as existing in two universes, as a 0 in one universe and as a 1 in the other one. An operation on such a qubit actually acts on both values at the same time. The main point being that by performing the single operation on the qubit, we have performed the operation on two different values. Likewise, a two-qubit system would perform the operation on 4 values, and a three-qubit system would perform on eight values. Increasing the number of qubits exponentially increases the 'quantum parallelism' that we can obtain with the system. It is possible to use this parallelism to solve certain problems in a fraction of the time taken by a classical computer by having the correct type of algorithm.
As we said a quantum computer with a particular number of qubits is fundamentally different from a classical computer composed of the same number of classical bits. For example, to represent the state of an n-qubit system on a classical computer would require the storage of 2n complex coefficients. While this fact may seem to indicate that qubits can hold exponentially more information than their classical counterparts. But we should be careful that the qubits are only in a probabilistic superposition of all of their states. It means when the final state of the qubits is measured, they will be found only in one of the possible configurations they were in before the measurement. Moreover, it is incorrect to think of the qubits as only being in one particular state before measurement since the fact that they were in a superposition of states before the measurement was made directly affects the possible outcomes of the computation. [4]
Designing a quantum computer is not even similar to a classical computer design. A new type of technology is required to build a quantum computer. A new technology which enables 'qubits' to exist as coherent superpositions of 0 and 1 states. The best method to achiev this goal is still unknown, but many methods are being experimented with and are proving to have varying degrees of success.
Below we are going to talk about some examples of achievement of the qubit and some research that people have done to make it happen.
L. DiCarlo et al. created the first rudimentary solid-state quantum processor. The two-qubit superconducting chip was able to run elementary algorithms. Each of the two artificial atoms (or qubits) were made up of a billion aluminum atoms but they acted like a single one that could occupy two different energy states. [5] Another example of an achievement of the qubit is the 'quantum dot'. Quantum dot is basically a single electron trapped inside a cage of atoms. The way that it works is that when the dot is exposed to a pulse of laser light of precisely the right wavelength and duration, the electron is raised to an excited state. A second burst of laser light causes the electron to fall back to its ground state. The ground and excited states of the electron can be considered as the 0 and 1 states of the qubit and the application of the laser light can be thought as a controlled NOT function as it knocks the qubit from 0 to 1 or from 1 to 0. Now if the pulse of laser light is only half the duration of that required for the NOT function, as a result the electron is placed in a superposition of both ground and excited states instantaneously, this being the corresponding of the coherent state of the qubit. More complex logic functions can be modeled using quantum dots arranged in pairs. It would therefore seem that quantum dots are a suitable candidate for building a quantum computer. [6] A. Balandin et al. presented a quantum dot structure fabricated by lithographic positioning, which can be used as a prototype of the quantum dot register for quantum computing. The parameters of their fabricated quantum dot structure are very close to the ones required for two possible embodiments of a quantum computer. [7] Matteo Mariantoni et al. proved that a quantum computer can be made with a Von Neumann architecture ( separation of RAM). They have demonstrated a quantum central processing unit that exchanges data with a quantum random-access memory integrated on a chip, with instructions stored on a classical computer. They have tested their quantum machine by executing codes that involve seven quantum elements: Two superconducting qubits coupled through a quantum bus, two quantum memories, and two zeroing registers. [8]
Quantum computation is about using quantum physics to compute mathematics. It's parallel computation, but more than just parallel, it can produce effects that are harder to get in classic computers. It has some continuous properties also. There are several known quantum algorithms that show better efficiency than their classic counterparts. The recent works have given quantum computing a promising future. Researchers believe that the quantum computers could be a reality if the current pace of advancement continues. The optimist will point out that the problems being experienced by researchers appear to be technical rather than fundamental.
© Rahim Esfandyarpour. The author grants permission to copy, distribute and display this work in unaltered form, with attribution to the author, for noncommercial purposes only. All other rights, including commercial rights, are reserved to the author.
[1] D. Deutsch et al. "Quantum Computation", Physics World, 5, No. 6, 57 (1992).
[2] P. W. Shor, " Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer", SIAM J. Comput. 26, 1484 (1997).
[3] "Two-Bit Heroes", The Economist, 13 Jan 96.
[4] D. P. DiVincenzo, "Quantum Computation", Science 270, 255 (1995)
[5] L. Dicarlo et al., "Demonstration of Two-Qubit Algorithms With a Superconducting Quantum Processor," Nature 460, 240 (2009).
[6] J. Brown, "Quantum Revolution for Computing", New Scientist, No. 1944, p. 21, 24 Sep 94.
[7] M. Mariantoni et al., "Implementing the Quantum von Neumann Architecture with Superconducting Circuits," Science 334, 61 (2011).
[8] A. Balandin, G. Jin and K. L. Wang, "Issues of Practical Realization of a Quantum Dot Register for Quantum Computing ", J. Electronic Mat. 29, 549 (2000).