Michael H. Freedman,
David A. Meyer,
Nolan R. Wallach
and Jeb Willenbring
Probably the single most important result in quantum information processing is Shor's factoring algorithm; certainly this motivated much of the current interest in the subject. The search for quantum algorithms which reduce the computational complexity of other problems has had very limited success (simulation of quantum systems and `database search' are commonly thought to be the most significant), however, which can be at least partly attributed to the absence of a deep understanding of why quantum algorithms work. Interference is definitely important, and in most cases, entanglement; we are studying each of these quantum phenomena in our work on this project.
In an attempt to investigate which problems may be amenable to more efficient solution by quantum algorithms, in [1] we introduced the idea of quantum games where two players Picard and Q take alternate turns. Picard plays probabilistically (classically); we showed by a very simple example involving flipping a penny that there are games for which Q has a quantum strategy which is superior to any classical strategy. This work seems to have motivated discussion of quantum game theoretic directions for quantum information protocols in ARO's Research Roadmap for Quantum Communication and Quantum Memory and was reported in Physics News Update, Physical Review Focus, The Economist, The Daily Telegraph, Science News and Scientific American [2]. In [3] we expand on the analogy between Picard's moves and random problem instances and Q's strategy and a quantum algorithm - and emphasize the crucial role of interference.
Entanglement plays an important role not only in quantum algorithms, but throughout quantum information processing. Except in the two factor pure state situation, however, it is not yet completely understood. Our approach to this problem is to characterize the entanglement of n qubits by the invariants of the action of the product of n copies of SU(2), i.e., as those properties of the state which are unchanged by local unitary transformations. In general it is a difficult problem to compute a complete algebraically independent set of such invariants. We have made progress on some small n instances of the problem. In [4] we prove some q-analogs of a theorem of Kostant-Rallis which give graded multiplicity formulae for representations of a subgroup of a semi-simple linear algebraic group defined as the fixed points of a regular involution. In their simplest non-trivial application, these formulae give the Hilbert series for so(4,C) = sl(2,C) x sl(2,C) invariants of M4(C). That is, they give the degrees of a set of SU(2) x SU(2) invariants of two qubit mixed states - an important step towards a complete characterization of entanglement in this situation. We have also begun investigating maximally entangled multiqubit states - those for which partial traces over subsets of the qubits give reduced density matrices with maximal entropy. Using the current implementation of the symbolic algebra package GROEBNER we showed that there is no maximally entangled 4 qubit state.
An especially important application of entanglement (and maximally entangled states) is in quantum error correcting codes (QECCs). These will be required in any physical quantum computer, particularly in the noisy solid state implementations which seem most likely to scale to multiple qubits . . . once a few qubits can be controlled successfully. We have investigated QECCs for the lattice architectures most natural for solid state implementation. These topological QECCs have stabilizers (`parity check operations') which are local, involving only a bounded number of qubits. In [5] we observe that a single qubit can be encoded in the first Z2-homology cycle of a lattice on RP2 and show that (one of) the smallest such code(s) is equivalent to Shor's original 9 qubit code. Furthermore, we show that arbitrary numbers of qubits can be encoded on planar lattices with boundary. The cost of local stabilizers in topological QECCs is the necessarily large number n of encoding qubits - proportional to the area of the surface. The number of correctable errors scales, in contrast, as the size d of the homology cycle encoding a qubit. In two dimensions, Loewner's theorem implies a bound on the number of correctable errors: d < const. n1/2. Results of Gromov on systolic freedom in higher dimensions - whence sizes of minimal nontrivial cycles scale with anomalously large dimensions - suggested an investigation of the Z2-systolic freedom which would lead to topological QECCs with better parameters. Preliminary results showing that Z2-systolic freedom does, in fact, exist in three dimensions are described in [6].
Kitaev showed that universal quantum computation is possible using defects in topological QECCs as computational tokens and braiding moves as gate operations. The continuous version of this scenario is quantum field computation, first proposed in [7]. The fact that #P-hard information is contained in the Jones polynomial which is computed by Witten's topological quantum field theory (TQFT) suggests that this might be a more powerful computational model than standard quantum computation. This idea was reported in Science and in The Notices of the AMS [8], and is explored further in [9], where the importance of measurement precision is emphasized: Realistic measurements have only finite precision, and this bound must be included when the computational power of physical systems is determined.
This observation turns out to have a significant impact on the last area we have investigated as part of this project: the fundamental theorems on hidden variable models for quantum mechanics. These are interesting not because the foundations of quantum mechanics deserve scrutiny, but because they provide the original proofs of separations between classical and quantum information processing capacity. In [10] we show, however, that the finite precision of physical measurement nullifies Kochen-Specker (KS) type proofs of the non-existence of noncontextual hidden variable models. Thus no quantum-over-classical advantage for information processing can be derived from the KS theorem. The continuous version of the KS theorem is Gleason's theorem. We investigate the extent to which Gleason type theorems hold when measurements are distributed, e.g., restricted to individual qubits. In [11] we determine conditions on distributed measurements which do and do not rule out hidden variable models, i.e., for which there is or is not a separation between classical and quantum information processing.
To summarize, in this project we have made some progress in elucidating the roles played by both interference and entanglement in quantum algorithms. This progress came from general considerations and also from investigating specific distributed models: lattice quantum computation (which is particularly relevant for solid state implementations) and geometrical quantum field computation. We anticipate that future development along these lines will lead to new quantum algorithms as well as techniques for distributed quantum communication.
Wednesday 22 August 2001
ITP Program on Quantum Information: Entanglement, Decoherence and Chaos
Michael H. Freedman
``Quantum loop gasses and Chern Simons theory''
[details]
Wednesday 13 June 2001
MSRI Summer Graduate Program Modern Signal Processing
David A. Meyer
``Applications of quantum transforms''
[details]
Wednesday 13 June 2001
MSRI Summer Graduate Program Modern Signal Processing
David A. Meyer
``Introduction to quantum transforms''
[details]
Thursday 12 April 2001
UCLA Condensed Matter Journal Club
Michael H. Freedman
``A two-dimensional antiferromagnet which `knows' Chern-Simons theory''
[details]
Monday 19 February 2001
AAAS Annual Meeting
Michael H. Freedman
``A topological model of quantum computation''
[details]
Wednesday 10 January 2001
NIST Physics Laboratory seminar
David A. Meyer
``Quantum lattice algorithms''
Tuesday 9 January 2001
NIST Physics Laboratory seminar
David A. Meyer
``Quantum search algorithms''
[details]
Tuesday 5 December 2000
MSRI Workshop on Subfactors and Algebraic Aspects of Quantum Field Theory
Michael H. Freedman
``Anyons in mathematics, computer science and physics''
[details]
Monday 23 October 2000
DARPA Quantum Information Science and Technology (QuIST) Workshop
David A. Meyer
``Quantum algorithms''
[details]
Wednesday 18 October 2000
Quantum Computation for Physical Modeling (QCPM) Workshop 2000
David A. Meyer
``Physical quantum algorithms''
[details]
Monday 18 September 2000
Berkeley Quantum Computation and Information Seminar
David A. Meyer
``Quantum Parrondo games''
[details]
Wednesday 6 September 2000
SPAWAR Systems Center Technical Lecture
David A. Meyer
``Introduction to quantum algorithms''
Thursday 31 August 2000
Quantum Computing Program Review
David A. Meyer
[details]
Wednesday 23 August 2000
9th International Conference on Discrete Simulation of Fluid Dynamics
David A. Meyer
``Parrondo games as lattice gas automata''
[details]
Tuesday 15 August 2000
Influence of Physics on Topology Conference
Michael H. Freedman
[details]
Tuesday 8 August 2000
Mathematical Challenges of the 21st Century
Michael H. Freedman
``Quantum computation and modular functors''
[details]
Friday 19 May 2000
Second Annual SQuInt Workshop
David A. Meyer
``Quantum search algorithms''
[details]
Thursday 18 May 2000
UCLA Mathematics Colloquium
Nolan R. Wallach
``Introduction to quantum computing''
[details]
Friday 21 April 2000
UCSB Lecture Series on Quantum Computation
David A. Meyer
``Quantum search algorithms''
[details]
Thursday 6 April 2000
UCSB Lecture Series on Quantum Computation
Michael H. Freedman
``Quantum computation and the localization of modular functors''
[details]
Saturday 1 April 2000
AMS 2000 Spring Eastern Sectional Meeting
David A. Meyer
``Quantum games and quantum algorithms''
[details]
Thursday 10 February 2000
MSRI Mathematics of Quantum Computation Workshop
Nolan R. Wallach
``Extrema for entropy of n-qubit states and quantum error correcting codes''
[details]
Tuesday 8 February 2000
MSRI Mathematics of Quantum Computation Workshop
Michael H. Freedman
``A topological modular functor which is universal for quantum computation''
[details]
Monday 24 January 2000
NSA seminar, Fort Meade, MD
Jeb Willenbring
``On some q-analogs of a theorem of Kostant-Rallis''
Thursday 20 January 2000
2000 Joint Mathematics Meetings
Special Session on Quantum Computation and Information
Nolan R. Wallach
``Measures of entanglement''
[details]
Wednesday 19 January 2000
2000 Joint Mathematics Meetings
Special Session on Quantum Computation and Information
David A. Meyer
``Quantum games and quantum algorithms''
[details]
Friday 29 October 1999
NSF Workshop on Quantum Information Science
Michael H. Freedman
``Quantum field theories and quantum computing''
[details]
Tuesday 26 October 1999
University of Washington Mathematics Department Colloquium
Michael H. Freedman
``Computer science in the early universe''
[details]
Wednesday 15 September 1999
Virginia Tech Mathematics Department Algebra Seminar
Nolan R. Wallach
``Entanglement in quantum computing''
[details]
Tuesday 14 September 1999
Virginia Tech Mathematics Department Colloquium
Nolan R. Wallach
``Quantum computing''
[details]
Thursday 2 September 1999
ARO Program Review
David A. Meyer
``Distributed quantum algorithms''
Tuesday 20 July 1999
Isaac Newton Institute Workshop on Quantum Computation and Algorithms
David A. Meyer
``Finite precision measurement nullifies the Kochen-Specker theorem''
[details]
Thursday 27 May 1999
Berkeley Computer Science Department theory seminar
Michael H. Freedman
``Computer science in the early universe''
[details]