What is a quantum computer?

It is tempting to say that a quantum computer is one whose operation is governed by the laws of quantum mechanics. But since the laws of quantum mechanics govern the behavior of all physical phenomena, this temptation must be resisted. Your laptop operates under the laws of quantum mechanics, but it is not a quantum computer. A quantum computer is one whose operation exploits certain very special transformations of its internal state, whose description is the primary subject of this book. The laws of quantum mechanics allow these peculiar transformations to take place under very carefully controlled conditions.

In a quantum computer the physical systems that encode the individual logical bits must have no physical interactions whatever that are not under the complete control of the program. All other interactions, however irrelevant they might be in an ordinary computer – which we shall call classical – introduce potentially catastrophic disruptions into the operation of a quantum computer. Such damaging encounters can include interactions with the external environment, such as air molecules bouncing off the physical systems that represent bits, or the absorption of minute amounts of ambient radiant thermal energy. There can even be disruptive interactions between the computationally relevant features of the physical systems that represent bits and other features of those same systems that are associated with computationally irrelevant aspects of their internal structure.

A set of positive integers less than N constitutes a group under multiplication modulo N if the set (a) contains 1, (b) contains the modulo-N inverse of any of its members, and (c) contains the the modulo-N products of all pairs of its members. A subset of a group meeting conditions (a)–(c) is called a subgroup. The number of members of a group is called the order of the group. An important result of the elementary theory of finite groups (Lagrang's theorem) is that the order of any of its subgroups is a divisor of the order of the group itself. This is established in the next three paragraphs.

If S is any subset of a group G (not necessarily a subgroup) and a is any member of G (which might or might not be in S), define aS (called a coset of S) to be the set of all members of G of the form g = as, where s is any member of S. (Throughout this appendix equality will be taken to mean equality modulo N.) Distinct members of S give rise to distinct members of aS, for if s and s′ are in S and as = as′, then multiplying both sides by the inverse of a gives s = s′. So any coset aS has the same number of members as S itself.

The miracle of quantum error correction

Correcting errors might sound like a dreary practical problem, of little aesthetic or conceptual interest. But aside from being of crucial importance for the feasibility of quantum computation, it is also one of the most beautiful and surprising parts of the subject. The surprise is that error correction is possible at all, since the only way to detect errors is to make measurements, but measurement gates disruptively alter the states of the measured Qbits, apparently making things even worse. “Quantum error correction” would seem to be an oxymoron. The beauty lies in the ingenious ways that people have found to get around this apparently insuperable obstacle.

The discovery in 1995 of quantum error correction by Peter Shor and, independently, Andrew Steane had an enormous impact on the prospects for actual quantum computation. It changed the dream of building a quantum computer capable of useful computation from a clearly unattainable vision to a program that poses an enormous but not necessarily insuperable technological challenge.

Error correction is not a major issue for classical computation. In a classical computer the physical systems that embody individual bits – the Cbits – are immense on the atomic scale. The two states of a Cbit representing 0 and 1 are so grossly different that the probability is infinitesimal for flipping from one to the other as a result of thermal fluctuations, mechanical vibrations, or other irrelevant extraneous interactions.

It was almost three quarters of a century after the discovery of quantum mechanics, and half a century after the birth of information theory and the arrival of large-scale digital computation, that people finally realized that quantum physics profoundly alters the character of information processing and digital computation. For physicists this development offers an exquisitely different way of using and thinking about the quantum theory. For computer scientists it presents a surprising demonstration that the abstract structure of computation cannot be divorced from the physics governing the instrument that performs the computation. Quantum mechanics provides new computational paradigms that had not been imagined prior to the 1980s and whose power was not fully appreciated until the mid 1990s.

In writing this introduction to quantum computer science I have kept in mind readers from several disciplines. Primarily I am addressing computer scientists, electrical engineers, or mathematicians who may know little or nothing about quantum physics (or any other kind of physics) but who wish to acquire enough facility in the subject to be able to follow the new developments in quantum computation, judge for themselves how revolutionary they may be, and perhaps choose to participate in the further development of quantum computer science. Not the least of the surprising things about quantum computation is that remarkably little background in quantum mechanics has to be acquired to understand and work with its applications to information processing.

The nature of the search

Suppose you know that exactly one n-bit integer satisfies a certain condition, and suppose you have a black-boxed subroutine that acts on the N = 2n different n-bit integers, outputting 1 if the integer satisfies the condition and 0 otherwise. In the absence of any other information, to find the special integer you can do no better with a classical computer than to apply the subroutine repeatedly to different random numbers until you hit on the special one. If you apply it to M different integers the probability of your finding the special number is M/N. You must test ½N different integers to have a 50% chance of success.

If, however, you have a quantum computer with a subroutine that performs such a test, then you can find the special integer with a probability that is very close to 1 when N is large, using a method that calls the subroutine a number of times no greater than.

This very general capability of quantum computers was discovered by Lov Grover, and goes under the name of Grover's search algorithm. Shor's period-finding algorithm and Grover's search algorithm, together with their various modifications and extensions, constitute the two masterpieces of quantum-computational software.

One can think of Grover's black-boxed subroutine in various ways. The subroutine might perform a mathematical calculation to determine whether the input integer is the special one. Here is a simple example.

As a further exercise in the use of circuit diagrams, we rederive the properties of the 7-Qbit error-correcting code, using the method developed in Chapter 5 to establish that the circuit in Figure 5.11 gives the 5-Qbit codewords.

We start with the observation that the seven mutually commuting operators Mi, Ni (i = 0, 1, 2) in (5.42), and in (5.49), each with eigenvalues ±1, have a set of 27 nondegenerate eigenvectors that form an orthonormal basis for the entire seven-dimensional codeword space. In particular the two codeword states and are the unique eigen states of all the Mi and Ni with eigenvalues 1, and of with eigenvalues 1 and –1, respectively.

It follows from this that if a circuit produces a state |Ψ〉 that is invariant under all the Mi and Ni then |Ψ〉 must be a superposition of the codeword states and, and if |Ψ〉 is additionally an eigenstate of then, to within factors eiϕ of modulus 1, |Ψ〉 must be or depending on whether the eigenvalue is 1 or –1.

Figure O.1 shows that the state |Ψ〉 produced by the circuit in Figure 5.10 is indeed invariant under M0 = X0X4X5X6. This figure demonstrates that when M0 is brought to the left through all the gates in the circuit it acts directly as Z0 on the input state on the left, which is invariant under Z0.

The general computational process

A suitably programmed quantum computer should act on a number x to produce another number f(x) for some specified function f. Appropriately interpreted, with an accuracy that increases with increasing k, we can treat such numbers as non-negative integers less than 2k. Each integer is represented in the quantum computer by the corresponding computational-basis state of k Qbits.

If we specify the numbers x as n-bit integers and the numbers f(x) as m-bit integers, then we shall need at least n + m Qbits: a set of n-Qbits, called the input register, to represent x, and another set of m-Qbits, called the output register, to represent f(x). Qbits being a scarce commodity, you might wonder why we need separate registers for input and output. One important reason is that if f(x) assigns the same value to different values of x, as many interesting functions do, then the computation cannot be inverted if its only effect is to transform the contents of a single register from x to f(x). Having separate registers for input and output is standard practice in the classical theory of reversible computation. Since quantum computers must operate reversibly to perform their magic (except for measurement gates), they are generally designed to operate with both input and output registers. We shall find that this dual-register architecture can also be usefully exploited by a quantum computer in some strikingly nonclassical ways.