In this feature, James summarizes an essay written as part of his college work, which was based on a literature review of the field of quantum computing, with particular reference to Shor's quantum factoring algorithm. His aim is to give a flavor of the general theory of quantum computing, its background, recent achievements and possibilities for the future.

Introduction

During the course of the 20th Century, humankind has harnessed the power of information more efficiently than ever before. For the first time, computers have allowed the manipulation and processing of information outside of the human mind. The pace of change in computing technology has also been astounding, moving from gears and relays to the integrated circuits, which can be found in any modern PC. In fact, it has been estimated by Lloyd¹³ that every two years for the past fifty years, computers have become twice as fast while their hardware components have halved in size. If this rate of miniaturization continues, we will soon reach the stage where computer chips will be manufactured on the atomic scale, and the behavior of such circuits will be described by the laws of quantum mechanics, rather than classical physics. Indeed, to a certain extent, the designers of modern computer circuits already take quantum mechanical effects into account.

It was perhaps Richard Feynman⁸ who first pointed out that, rather than being a hindrance, this quantum mechanical behavior of circuits may allow the possibility of completely new computing processes, which would have no classical analogue. Feynman demonstrated that a quantum system could act to provide a simulation of the probabilistically-weighted processes found in nature, and also that for certain problems, it is impossible to obtain an efficient equivalent classical algorithm. This is because such simulations, when run on a classical Turing Machine (TM),¹⁸ involve an exponential growth in the number of computational steps, for a linear increase in the degree of difficulty of the problem.

Consider a problem that is not efficiently computable on a classical computer: the factorization of a number. Intuitively, we can see that there are efficient classical algorithms for multiplication of two numbers, since multiplying, say, 57 by 127 takes less than a minute to calculate using pencil and paper. But the reverse problem, breaking the number 7239 into its two prime factors, will take much longer. In fact, even the best classical factoring algorithms take an exponentially-increasing amount of time to carry out a factorization, and this means that a modern PC would take several billion years to factor a 200 digit number. There may well exist efficient classical factoring algorithms, but unfortunately these are not known at the current time! So, if quantum factoring algorithms can be implemented, this is one reason why quantum computing may be important to us.

Computing: From Classical to Quantum

Classical Computers and Computational Efficiency

Computation can be thought of as a systematic creation of an ‘output,' which, when interpreted in a particular way, has abstract properties specified by an ‘input.' Input and output here are physical entities, and the process is carried out by a physical machine - a computer. The classical theory of computation relies on a theoretical device known as a Turing Machine (TM). Such a machine can be visualized¹⁴ as a device, which is composed of a read/write head and a memory with unlimited storage capacity. Each discrete cell of the memory contains one of a finite set of symbols, and the head can be in any one of a finite set of states. Then, each discrete step of the machine action is determined by two initial conditions - the state of the head and the symbol in the memory cell being looked at by the head. From these initial conditions, the subsequent action of the read/write head is determined in three parts - (i) the next state of the read/write head, (ii) the symbol to be written to the current memory cell, and (iii) the next memory cell to be looked at by the head (i.e. the movement of the head is determined). From this configuration, the computation can be allowed to proceed from an initial state to a final, ‘halting' state, at which stage the computation is complete. This is a general computer - almost all ‘real' computers are simplifications of this. For the most part, the number of possible symbols stored in memory cells is limited to a set of just two - this is the binary system, and the symbols are normally denoted by 0 and 1.

The specification of the set of instructions followed by any computer is called an algorithm - it is essentially just a process that can be mechanically applied time and again. For example, the pencil and paper multiplication method taught in schools is an example of an algorithm. As described in the introduction, there are some algorithms that are faster to carry out than others, and the rigorous method for defining whether an algorithm is fast or slow is to examine its efficiency. We can then define whether an algorithm is generally slow or fast, rather than in application to just one particular problem. For example, it takes longer to multiply 79*229 than it does to factor the number 10, but this does not mean our factoring algorithms are more efficient than our multiplicative algorithms! Since most computers work in binary information, we define the input size to be the number of ‘bits' needed to encode the information (i.e. a number N requires log₂N bits). The execution time is defined as the number of computational steps necessary to solve the problem. For any given input, an efficient algorithm takes a number of computational steps that increase as a polynomial function of the number of input bits: # steps < poly(log₂N), for all inputs N As mentioned before, the execution time of the best classical factoring algorithms still increases as an exponential of log₂N. We can partly see why by considering the most obvious factoring method: dividing N by all numbers up to N^1/2, until the factors are found. This requires O(N^1/2) steps = O(2^{1/2 logN}), which is exponential in log₂N; this quantitatively explains just why factorization is so difficult for a classical computer.

Quantum Computers

The Quantum Turing Machine (QTM), as proposed by Deutsch², is a quantum generalization of the TM system. The basic idea is that - rather than the pair of initial conditions determining a particular action of the read/write head - they determine all possible actions of the head with a given probability. As one might expect, this does not change the range of possible computations that can be carried out on the system (there are certain types of computation that are impossible on a TM/QTM), but it does allow the possibility of operation using quantum parallelism - this means that it is possible to devise quantum algorithms for problems that are efficient, where their classical counterparts are not.

When considering quantum computation, instead of using binary digits, or bits, of information, we now have quantum bits - qubits. These exist in a superposition of states:

Shor's Factoring Algorithm

The Equivalent Problem

Before explaining the details of Shor's algorithm, it is necessary to understand that, rather than using brute force to factor a number, quantum computation is used here to solve an equivalent problem. The main task of the algorithm will be to find the period, r, of the equation:

f(a) = y^a modN [1]
so that f(a+r) = f(a). Here, N is the number to be factored and y is any number coprime to N (that is, the greatest common divisor of y and N, denoted by gcd(y, N), is 1), chosen at random. Mod, short for modulo or modulus, just denotes the remainder left over after dividing by N, e.g.12mod6 = 0, but 13mod6=1 etc. In this section, it will be shown that solving this problem enables us to find the factors of N.

Now, consider the equation:

x² = 1modN [2]
This always has the trivial solutions x= ±1 modN, and, if N is an odd prime, these are the only solutions. But, if N is a product, it can be shown that there are also pairs of non-trivial solutions of the form: x = ±b modN. For example, take N = 35 = 5*7. Then, if x^­2 = 1 mod35, apart from x = ±1 mod35, there are two further solutions, x = ±29 mod35. Now, it is also true that the non-trivial solution, b, gives us some clue as to the factors of N, and in fact one can show that the greatest common divisors of N and b±1 are the non-trivial factors of N.

So, to conclude, if we can find a non-trivial solution x of equation [2], then we can find a non-trivial factor of N. To find such a solution for x, it is necessary to return to equation [1]. Now, we must first define r as the order of y, modN, so that:

y^r modN = 1
We can see that this is the same as our previous definition of r as the period of f(a). If r is even, then let:
x = y^r/2,
which solves equation [1]. Hence, determining the order of y, modN, allows the possibility of finding the factors of N. However, the process is not guaranteed to work, since, if y has an odd order r, or y^r/2 is a trivial solution of equation [2], it will not be possible to find the factors of N. Nonetheless, it can be shown that⁷ if y is chosen at random, the probability of either of these cases occurring is always < 0.5, and usually much smaller, for large N.

Shor's Algorithm

To factor a number N, we choose a quantum computing system with q possible quantum states (which can be thought of as ‘universes' when considering the many universes interpretation), where q is any randomly chosen number between N² and 2N². In direct analogy to classical computation, the system is considered to be composed of an array of L qubits (quantum bits), which will be called register 1, so that q = 2^L. Next, y is chosen coprime to N, as described previously, and all L qubits are set to the state | 0 >. We first want to take this register and put it in a quantum superposition of all the possible integer numbers it can contain.

So, starting with all qubits in a | 0 > state, we can apply a simple unitary transformation, U, to each qubit that creates a superposition of | 0 > and | 1 > states:

U: | 0 > -> (1/2)^1/2 {| 0 > + | 1 >}
For example, if L=2, i.e. we have two qubits in total in our register, then, after this transformation, the register will be in a superposition of all four numbers it can contain:
U: | 0,0 > -> (1/2) { | 0,0 > + | 0,1 > + | 1,0 > + |1,1 >}
Next, the function f(a), y^a modN, is computed, and the result stored in a second register. Now, these two registers are entangled, so that a measurement performed on register 1 will affect register 2, and vice versa. Hence we can describe the system of the two registers combined, as follows:
q-1
(1/q)^1/2 | a > | y^a modN >
a=0
where the coefficient (1/q)^1/2 is just a normalization arising from our operation, U.

At this stage in the algorithm, a measurement of register 2 is carried out. This could result in any one of the possible values stored in register 2 being found; the register is the same as any other quantum system and so must collapse into a single state after any measuring process.

Now, say we measure a value of z. This can clearly be written as z = y^k modN, for some least k. But, since f(a) is a periodic function, we find that this can be written as z = y^{jr + k} modN, where r is the order of y, modN, as already defined, and j is an integer. Hence this measurement has the effect of ‘fixing' the possible values stored in register 1, to:

a = k, k+r, k+2r,…,k + jr,…etc.
Hence, discarding the second register, which we no longer need, the state of the system, post-measurement, is given by:

(1/q)^1/2 of | k+jr > [4]
We cannot find out r from a direct measurement, because such a test will depend upon k, a random translational shift that will change each time the experiment is carried out! Hence, the determination of r is achieved more subtly, by applying a discrete Fourier transform to the register. This has the effect of washing out the random shift, k, while also altering the period, r, to a multiple of (1/r).

Any measurement of register 1 will now give a multiple jq/r. So, after our measurement of the register, lets say we find a value of c, so that c satisfies c/q = j/r. Now, both c and q are known, and so, if gcd(r,j) = 1, then we can determine r by canceling c/q down to an irreducible fraction. It can be shown that the probability that gcd(r,j) = 1 is greater than 1/logr for large r⁷, and so, if we repeat the whole algorithm O(logr) < O(logN) times, we can increase the probability of successfully finding r arbitrarily close to 1. Hence, this is an efficient determination of the period r, which is good, because r is what we need to find the factors of our original number N!

A Much Needed Example!

Conclusions

One very serious implication of Shor's quantum factoring algorithm is in the area of electronic security, since the possibility of factoring large numbers easily would render the widely used RSA (Rivest, Shamir and Adleman) encryption system⁵ useless! Quantum cryptographic methods will probably safeguard information in the future, but it is interesting to think that all of the ‘secret' information floating around today could become readable by anyone on the day the first factoring quantum computer is switched on. There are also other applications in science and industry, both for this and for other quantum computing algorithms, should they be successfully realized. However, the phenomenon of decoherence, in which the environment of a quantum computer interferes with quantum superpositions, causing the whole system to collapse to one state, may seriously inhibit advances in this direction. Some progress has been made in the area of quantum error correction, by which the data lost through decoherence can be recovered, but it still remains to be seen whether a working quantum computer, capable of factoring large numbers, will ever be built.

There are also more fundamental implications, for example in the area of computing theory. For example, not only does Deutsch's Quantum Turing Machine successfully extend the classical TM model, it also links in with fundamental physical theory, thus putting the theory of computing on a far firmer and less ad hoc basis than before. Deutsch has also claimed that the existence of such an algorithm as Shor's is at least partial evidence for the ‘many universes interpretation' of quantum mechanics. However, this evidence is not yet compelling, particularly since Shor's algorithm has never been carried out using the large numbers needed to verify such an argument.

On the whole, it seems clear that the development of Quantum Computing Algorithms has revolutionized our thinking, not only about computation, but also about physics. It certainly is an exciting area. Of course, particular reference has been given here to Shor's algorithm and its applications, but the concepts and even the operations used are very similar for many quantum algorithms. In the laboratory, it seems only a matter of time before experiments progress to the stage where full-scale quantum computation is possible, even commercially - already there has been some success in implementing cut-down versions of Shor's algorithm, using nuclear magnetic resonance technology.⁹ If we ever reach the stage where Shor's and other quantum algorithms can be implemented as successfully as classical computation, we will be in a position to complete specific problems far more quickly than ever before, and maybe even to increase further our understanding of nature and her complicated processes.