From: greg@math.ucdavis.edu (Greg Kuperberg) Subject: This week in the mathematics arXiv (31 Jan - 4 Feb) Date: 6 Feb 2000 14:00:02 -0600 Newsgroups: sci.math.research Summary: [missing] [deletia --djr] Recently Mike Freedman (the topologist and Fields Medalist) cross-listed two articles from the quant-ph archive (Quantum Physics) to the mathematics archive, quant-ph/0001071 and quant-ph/0001108. Mike, as some of you may have heard, had an epiphany a few years ago and switched from geometric topology to quantum computation. For me the switch was very fortuitous, since I also got interested in quantum computation a year and a half ago, and since his current interest and his old expertise lead him to quantum algebra and topology, which is my main area. For those of you who still don't know what quantum computation is, many people believe that the current form of computation, as realized by existing computers and as modelled by Turing machines and abstracted digital circuits, does not fully exploit the laws of physics, and that a quantum-mechanical computer could in principle be much faster for certain computational problems. In particular the best non-quantum algorithms for factoring a number with N digits requires exponential time (exponential in N^1/4 I think), but there is a simple quantum factoring algorithm, due to Peter Shor, that works in polynomial time. quant-ph/0001071 shows that you can effectively simulate a unitary topological a unitary 3-dimensional topological quantum field theory, such as the one associated to the Jones-Witten-Reshetikhin-Turaev invariants, with a quantum computer. quant-ph/0001108 has the converse result, that you can one such TQFT (the Chern-Simons theory at a fifth root of unity) to simulate general quantum computation. Actually I found a similar result to that of the second article independently, but unfortunately I haven't yet written it up. This idea is important because it could lead to an improvement in the fault-tolerance constant, the minimum necessary fidelity of the gates or components of a quantum computer. At the moment quantum devices are not nearly good enough for quantum computation; their fidelity is close to 0, while what is needed is fidelity close to 1! Anyway I'd like to quote one sentence from quant-ph/0001071 which expresses one of my thoughts: There is a marked analogy between the development of the QCM [the quantum circuit model] from 1982 Feynman [Fey] to the present, and the development of recursive function theory in 1930's and 1940's. At the close of the earlier period, "Church's thesis" proclaimed the uniqueness of all models of (classical) calculation: recursive function theory, Turing machine, \lambda-calculus, etc.... The present paper can be viewed as supporting a similar status for QCM as the inherently quantum mechanical model of calculation. I would say something more general: There is a marked parallel between the whole field of quantum computation today and the field of computer science from Turing's first paper to the construction of ENIAC. It was really hard to think about computers when they didn't exist. Progress was very slow and academia responded relatively conservatively. Then, as now with quantum computation, much of the impetus came from government projects and industry rather than from universities. "This week in the mathematics archive" may be freely redistributed with attribution and without modification. [deletia --djr] -- /\ Greg Kuperberg (UC Davis) / \ \ / Visit the Math Archive Front at http://front.math.ucdavis.edu/ \/ * From A-hat to Z(G), ABC to ZFC * ============================================================================== From: greg@math.ucdavis.edu (Greg Kuperberg) Subject: This week in the mathematics arXiv (14 Feb - 18 Feb) Date: 20 Feb 2000 01:43:24 -0800 Newsgroups: sci.math.research [deletia --djr] Last week I mentioned a quantum computation algorithm, Grover's algorithm, which can exhaustively search a combinatorial search space of size O(N) in time O(sqrt(N)). I assumed that we have a Boolean-valued function f and that we want to find the unique x in the search space such that f(x) is true. Taking the simplifying assumption that f is computed by an inaccessible "black box" that returns the value in polynomial time, the result is clearly classically impossible. The best you can do classically is to guess randomly, which takes expected time N/2. Since we can't prove that P != NP, we can't prove that the black box model is valid, but most people think that it is for suitable f. This week I'll try to explain Grover's algorithm. It will be clear that its trick has nothing to do with the deep complexity theory of the P vs. NP question. In (reversible, finite) quantum statistics, you have a basis of independent states, which in the case of a quantum computer with K qubits of memory is the set of 2^K bit strings. As with classical probability theory, you consider the vector space of formal linear combinations of these states, but in quantum statistics the coefficients are complex rather than real. Moreover, probabilities are given by taking the L^2 norm rather than the L^1 norm. For example, if a 2-qubit quantum computer is in the state |psi> = (|00> + 2|01> + 2|10>)/3 then the total probability is 1, as it should be, while the probability that the first qubit is in the state 0 is 5/9. (Here |psi> is Dirac's notation for a vector, also called a state or a wave function, in a quantum state space.) An allowed reversible evolution of the system is a linear transformation that conserves probability. Since probability is given by the L^2 norm that means unitary operators; in classical probability theory it would have been stochastic operators. A quantum gate is a unitary operator that involves only a small number of qubits; in other words an operator O that factors as G tensor I, where G is a unitary operator on the state space C^2^{tensor k} of k qubits, and I is the identity operator on the state space C^2^{tensor K-k} of the remaining K-k qubits. It is a theorem that 2-qubit gates are enough for universal quantum computation. There is more variety in quantum unary gates than in classical ones. There is a NOT gate X|0> = |1> , X|1> = |0> as before, but there is also the phase flip gate Z|0> = |0> , Z|1> = -|1> and there is the Hadamard gate H|0> = (|0>+|1>)/sqrt(2) = |+> H|1> = (|0>-|1>)/sqrt(2) = |-> Actually I like to think of the Hadamard gate as a change of description rather than as an explicit operation. Namely |+> and |-> are equivalent to |0> and |1>. Any computation that can be done in the |0>,|1> basis can also be done in the |+>,|-> basis, either by explicitly conjugating with Hadamard gates or implicitly by executing all steps in the computation in the second basis rather than the first one. (There is also a 0-ary gate which multiplies every state by the same phase e^(i*theta). One of the precepts of quantum statistics is that this operation changes nothing. It is a physically irrelevant change of description.) Grover's algorithm for a search space of size N = 2^K requires a quantum computer with K qubits, the guessing memory, plus extra space for simple computations and to compute f. You need to compute f reversibly, i.e. without ever erasing scratch memory so that you can undo every gate used to compute f to bring the computer back to its original state. This can be done in polynomial time if f can be computed in polynomial time irreversibly. Initially in Grover's algorithm the guessing memory is in the state |h> = |++...+> and the rest is in some convenient known state. At each stage you do the following two steps: 1) Put a spare qubit q in the state |1> if the guessing memory is in the state |h> = |++....+> and |0> if it is in an orthogonal state, then apply the phase flip gate Z to q, then undo the computation of q. 2) Put a spare qubit q in the state |1> if f(x) is true, and |0> if it is in an orthogonal state, where x is the bits of the quantum memory in the |0>,|1> basis. Then apply the gate Z to q, then undo the computation of q. Step (1) reflects the state space of the guessing memory; it negates the line spanned by |h> and fixes the orthogonal hyperplane. Likewise step (2) negates the line spanned by |x>, where x is the solution to the question f(x) = TRUE, and fixes the orthogonal hyperplane. (It is a subtlety, but really perfectly legitimate, that the second step can be performed quickly even though x is not known a priori.) The two steps together rotate the state space of the quantum memory in the plane spanned by |x> and |h>. Since x is some bit string of length K and |h> is the normalized sum of all 0-1 bit strings, the angle theta between them satisfies cos(theta) = = 2^(-K/2) Thus the rotation is by an angle very close to 180 degrees; the discrepancy is to first order 2^(-K/2) radians. It follows that if you iterate Grover's algorithm roughly pi/2*2^(K/2) times, the computer evolves from its initial state |h> to a state very close to |x>. At this point the computer has the correct answer in its memory with probability close to 1. You can then stop the computation and measure the memory to learn the answer. Recalling that the size of the search space is N = 2^K, the algorithm requires pi/2*sqrt(N) iterations, or pi*sqrt(N) evaluations of f. So that's Grover's algorithm. It can be generalized in various ways. For example if there are s solutions to f(x) = TRUE, it works in time O(sqrt(N/s)). It can be combined with heuristic depth-first tree searches, there is a protocol if the number of solutions is unknown, etc. I see a resemblance between the behavior of the quantum algorithm and the behavior of the classical brute-force search algorithm in its statistical formulation. Namely in the brute-force search algorithm the computer begins in the flat distribution on all bit strings . The computer then iteratively computes f(x); it stops if f(x) = TRUE and otherwise it renews the flat distribution . Thus if you run the brute-force search for a fixed time, the evolution of its state is given by a stochastic map that exponentially diminishes the state while fixing the state . In the quantum algorithm slow exponential decay from to is replaced by slow rotation from |h> to |x>. You could call Grover's algorithm "coherent guessing". Finally one old criticism of Grover's algorithm, as well as quantum factoring and all other interesting quantum algorithms, is that it is really an impossibly accurate analog computation. It turns out that this criticism, while important, can be answered for all quantum algorithms uniformly. The accuracy problem for quantum computers is analogous to the reliability problem for components of digital computers. One solution to both problems is error correction and fault-tolerant computation. A good reference for both Grover's algorithm and for quantum error correction is Steane's review article which I mentioned before [quant-ph/9708022]. "This week in the mathematics archive" may be freely redistributed with attribution and without modification. [deletia --djr] -- /\ Greg Kuperberg (UC Davis) / \ \ / Visit the Math Archive Front at http://front.math.ucdavis.edu/ \/ * The best things in life are free *