Project Highlights

Project #1: Quantum Algorithms and Complexity Theory We have shown that a particular graph traversal problem can be solved exponentially faster on a quantum computer than on a classical computer. What is remarkable about this result is that the algorithm is based on a continuous time quantum walk, thus employing a different technique from previous quantum algorithms based on quantum Fourier transforms. We have presented a few simple problems in which quantum computing without entanglement is better than anything classically achievable (in terms of the reliability of the outcome after a fixed number of oracle calls). This demonstrates that entanglement is not essential for quantum computing. We have shown that the quantum Fourier transform can be computed exactly for any modulus. Previously, such exact computations were known only for smooth modulii (i.e., those with small prime factors). We have shown that quantum searching can be applied in a context where bit-queries are subject to errors within some (constant) bound. The loss of efficiency is only a constant factor, an improvement over previous methods where the loss in efficiency is by a logarithmic factor. As a corollary, optimal quantum upper bounds can be obtained for the problem of evaluating constant-depth AND-OR trees. We have shown that deterministic quantum computing with a single bit can determine whether the classical limit of a quantum system is chaotic or integrable using O(N) physical resources, where N is the dimension of the Hilbert space of the system under study. This is a square root improvement over all known classical procedures. We have discovered a simple multi-party distributed problem which can be used to circumvent the detection loophole in experimental tests of non-locality. Project #2: Quantum Information Security We have defined and investigated the notion of authentication for messages composed of quantum states. A non-interactive scheme that enables a sender to both encrypt and authenticate (with unconditional security) based on a classical private key has been obtained. We have also shown that, unlike in the classical case, any scheme to authenticate quantum messages must also encrypt them. We have investigated an extension of secure multi-party computing tasks to computation with quantum inputs and circuits, showing that these tasks can be solved (information-theoretically) provided that the number of dishonest players is less than one sixth of the total. The protocols employ a sub-protocol for verifiable quantum secret sharing, which is interesting in its own right. We have presented two polarization-based protocols for quantum key distribution. The protocols encode key bits in noiseless subspaces or subsystems, and so can function over a quantum channel subjected to an arbitrary degree of collective noise, as occurs, for instance, due to rotation of polarizations in an optical fiber. These offer practical and realistic alternatives to existing schemes for quantum key distribution over optical fibers without resorting to interferometry or two-way quantum communication, thereby circumventing, respectively, the need for high precision timing and the threat of Trojan horse attacks. We have shown that the so-called superselection rules in physics do not affect the validity of the impossibility proofs pertaining to bit commitment and coin flipping. Project #3: Theory of Quantum Information Implementations Noiseless subsystems offer a general and efficient method for protecting quantum information in the presence of noise that has symmetry properties. A paradigmatic class of error models displaying non-trivial symmetries emerges under collective noise behavior, which implies a permutationally-invariant interaction between the system and the environment. We have described experiments that demonstrate the preservation of a bit of quantum information encoded in a three qubit noiseless subsystem for general collective noise. A complete set of input states is used to determine the super-operator for the implemented one-qubit process and to confirm that the fidelity of entanglement is improved for a large, non-commutative set of engineered errors. To date, this is the largest set of error operators that has been successfully corrected for by any quantum code.