Subscriber
Index
Quantum computing | thinfilmmfg.com
Subscriber
Index
Quantum computing |
Quantum computers have garnered substantial interest recently, largely because of Shor's finding that quantum algorithms can factor large numbers that would be intractable for binary logic algorithms. Shor's result attacks the security of public key encryption and has inspired dire predictions about the death of encryption and therefore of e-commerce. Yet quantum computers are, at present, purely theoretical constructs, several decades away from real world implementation.
Lost in all the noise is a far more profound observation: two of the central scientific ideas of the twentieth century, quantum mechanics and computing, can be linked to build a physics of information processing. This new field creates a completely new approach to computation and helps physicists study some of the most baffling behavior in quantum mechanics. This article outlines the concepts underlying quantum computation and explains some of their implications. It is necessarily superficial. More detailed analyses are listed in the References section.
The roots of information theory lie with the abstract mathematicians David Hilbert and Kurt Gödel. Most mathematics focuses on proving propositions. Is the square of the hypotenuse of a right triangle equal to the sum of the squares of its sides? Are prime numbers evenly distributed among the positive integers? Hilbert focused on the nature of mathematics itself. Can all mathematical propositions be proven or disproven? Hilbert felt that they could, which would imply that mathematics is complete, in the sense that it contains all the information necessary to discuss the structure of mathematics.
Hilbert's conjecture, made around 1900, stood until 1931. In 1931 Gödel's Incompleteness Theorem showed that any consistent system of number theory that is complete enough to be useful can be used to construct propositions that cannot be proven or disproven within the system.
In the proof of his theorem, Gödel invented a method for converting mathematical propositions to strings of numbers. This coding scheme allowed him to create meta-statements, or statements about statements of number theory. In effect, he created the number theory equivalent of the Epimenides Paradox. Epimenides, a Cretan, said, "All Cretans are liars." If the statement is true, then Epimenides is lying, and therefore the statement cannot be true.
Gödel's version of the paradox is, "This statement cannot be proven within the context of number theory," written as a string of symbols using Gödel's encoding scheme. The Incompleteness Theorem also showed that a similar paradox can be constructed in any consistent number theoretical system that is powerful enough to allow meta-statements at all.
Once Gödel established that undecidable propositions exist, attention shifted to methods for finding them. Alan Turing, in 1936, showed that a coding scheme could be used to translate mathematical steps like "add A and B" or "check to see if A > B" into a string of binary symbols on paper tape. He envisioned a machine which would obey the instructions on any paper tape given to it. More precisely, a Turing machine reads one binary symbol at a time. Depending on that symbol and the machine's internal state, the machine rewrites its internal state to a new value, writes a symbol to the current location on the tape, and moves the tape one step forward or back. A Turing machine is completely specified by its initial state and its responses to all possible inputs. It would be possible to build a whole room full of Turing machines, each with a set of input-output responses appropriate to a specific computational problem.
Turing also showed that a universal Turing machine existed and could simulate the action of any single purpose machine. The central result of computer science, the Church-Turing Principle, states that every computable function can be computed by a universal Turing machine. Computable functions include tasks like word processing, statistical process control, and network communications.
Turing initially proposed his machine as a means to automate mathematical proofs, and in particular to identify undecidable mathematical propositions. A proposition can be written as an algorithm, a series of instructions to a Turing machine. For example, consider a procedure which tests to see if an odd number is the sum of two primes. If it is, the algorithm adds two and checks the next odd number in sequence. If not, the algorithm halts and delivers the last number checked as its result. Determining whether this algorithm will halt, without actually running it, is equivalent to proving or disproving Goldbach's Conjecture. (The Conjecture states that every odd number can be written as the sum of two primes.)
Turing asserted the existence of an algorithm to determine whether any Turing machine would halt on any input. This algorithm, TH(x), halts if and only if the algorithm x does not. Applying TH to itself, leads to a contradiction similar to the Epimenides Paradox: TH(TH) halts if and only if TH does not halt. Thus, Turing showed that there is no general purpose way to determine if a given algorithm will halt.
To summarize the discussion so far, Gödel's Incompleteness Theorem showed that all axiomatic number theory systems are incomplete. He introduced a method for coding mathematical statements as symbols, allowing the construction of unprovable metastatements.
Turing then introduced the idea of a machine which could process such symbolic statements. Turing's machine is also "incomplete" in Gödel's sense. It is possible to construct an algorithm which Turing's machine cannot compute.
Stripped to its essence, a Turing machine takes an initial state, applies an operation, and returns a new state. Quantum mechanics can be described in similar terms. The fundamental postulates of quantum mechanics are given here without justification; see any quantum mechanics textbook for more details. They are:
If a quantum system is viewed as an information processor, then the state vector represents the initial state of the system. Operators change this state, with a result defined by Schrödinger's Equation and the properties of the operators. The field of quantum computing asks: given a suitable library of operators, can a quantum system serve as a computer in the sense of the Church-Turing Principle? Deutsch phrased the principle this way: "Every finitely realizable physical system can be simulated arbitrarily closely by a universal model computing machine operating by finite means."
The Deutsch statement suggests that a system operating on quantum states can simulate behavior that is beyond the reach of classical computers operating on binary logic bits. Quantum computing is the theoretical and experimental study of such systems.
The Einstein-Podolski-Rosen (EPR) Paradox, an important quantum mechanical thought experiment, provides a ready example of non-classical behavior.
The EPR experiment assumes a pair of electrons A and B, prepared in a state where their spins sum to zero. The two particles fly apart in opposite directions. An experiment then measures the spins of each particle along a different axis. The spins of the two particles still sum to zero. Moreover, the relationship between the two measurements can be predicted from the orientations of the two axes of measurement. Phrased another way, the second electron not only "knows" the spin state of the first, but "knows" the angle at which that spin is being measured, even though the two particles are widely separated. No classical computer could accomplish this task.
This "entanglement" between the states of electrons A and B lies at the heart of quantum computing. One of the implications of Schrödinger's equation is that a quantum system simultaneously inhabits all the possible states in its probability distribution. If the system is limited to two states, such as an electron which can have spin up or spin down, then it can be viewed as a logical "bit" which has the values 1 and 0 simultaneously. Such a system is called a qubit.
Entanglement of particles means that we can at least theoretically prepare a system which combines the states of arbitrarily many qubits. In practice, entangling pairs of qubits is sufficient.
A quantum gate acts on an entangled qubit pair much as a binary logic gate acts on a pair of binary numbers. The difference is that the qubit pair contains all four possible states (both spins up, both spins down, A up and B down, and B up with A down). In effect, the gate has performed the same action on four different input states. Entangling n qubits allows the gate to act on 2n input states simultaneously.
A series of quantum gates, like a series of binary gates, can theoretically perform any calculation. Moreover, the massively parallel computation allowed by superposition of states puts many otherwise intractable problems, like factoring large primes, within reach.
Actually implementing a quantum computer is another matter. The superposition of states is fragile. Any measurement, any coupling between qubits and their environment, will terminate the calculation. Several different qubit implementation schemes have been proposed, ranging from trapped ions to nuclear spin states. To date, systems with up to seven qubits have been reported. Commercially important computations will require thousands of qubits.
Quantum computers offer a new model for universal computation, using physical systems to simulate physical systems. It remains to be seen whether and how paradoxes like Gödel's sentence and the halting problem will manifest themselves in the quantum computing domain.
Viewing a quantum state vector as a unit of information, and perturbations of that vector as logical manipulations, allows physicists to study quantum interactions which would otherwise be extremely complicated. Even small numbers of qubits can be used to test the resulting conclusions. Qubits give physicists a new and powerful tool for studying the consequences of behavior like entanglement.
Quantum computing is a very young field. Businesses tied to classical computing have nothing to fear for years and probably decades to come. In the short term, though, qubits offer a way to relate the structure of information to the structure of matter itself.
For an accessible introduction to Gödel, Turing, and the foundations of information processing, see Douglas R. Hofstadter's book, Gödel, Escher, Bach: An Eternal Golden Braid. (Basic Books, 1999)
For an undergraduate level introduction to quantum mechanics, see the textbook Molecular Quantum Mechanics, by P. W. Atkins and R. S. Friedman (Oxford University Press, 1999).
For a technical review of quantum computation, see Andrew Steane's paper, "Quantum computing." Available online at http://www.arXiv.org/abs/Quant-ph/9708022
David Deutsch discussed the universal quantum computer in "Quantum theory, the Church-Turing principle, and the universal quantum computer," Proc. Royal Soc. London A, vol. 400, pp97-117 (1985).
Peter Shor's paper explaining the use of quantum computers for factorization is "Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer," in Proc. 35th Annual Symp. On Foundations of Computer Sci. Santa Fe, IEEE Computer Society Press; Available online at http://www.arXiv.org/abs/quant-ph/9508027
| This site is Copyright ©2001 by Thin Film Manufacturing. All Rights Reserved |