June 12, 2012

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) =x^{a} 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 x^{0} mod n = 1, so x^{r} 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).