Quantum Information

Work on formulating general probabilistic theories in an operational context has tended to concentrate on the probabilistic aspects (convex cones and so on) while remaining relatively naive about how the operational structure is built up (combining operations to form composite systems, and so on). In particular, an unsophisticated notion of a background time is usually taken for granted. It pays to be more careful about these matters for two reasons. First, by getting the foundations of the operational structure correct it can be easier to prove theorems. And second, if we want to construct new theories (such as a theory of Quantum Gravity) we need to start out with a sufficiently general operational structure before we introduce probabilities. I will present an operational structure which is sufficient to provide a foundation for the probabilistic concepts necessary to formulate quantum theory. According to Bob Coecke, this operational structure corresponds to a symmetric monoidal category. I will then discuss a more general operational framework (which I call Object Oriented Operationalism) which provides a foundation for a more general probabilistic framework which may be sufficient to formulate a theory of Quantum Gravity. This more general operational structure does not admit an obvious category theoretic formulation.

I will rephrase the question, "What is a quantal reality?" as "What is a quantal history?" (the word history having here the same meaning as in the phrase sum-over-histories). The answer I will propose modifies the rules of logical inference in order to resolve a contradiction between the idea of reality as a single history and the principle that events of zero measure cannot happen (the Kochen-Specker paradox being a classic expression of this contradiction). The so-called measurement problem is then solved if macroscopic events satisfy classical logic, and this can in principle be decided by a calculation. The resulting conception of reality involves neither multiple worlds nor external observers. It is therefore suitable for quantum gravity in general and causal sets in particular.

A fully general strong converse for channel coding states that when the rate of sending classical information exceeds the capacity of a quantum channel, the probability of correctly decoding goes to zero exponentially in the number of channel uses, even when we allow code states which are entangled across several uses of the channel. Such a statement was previously only known for classical channels and the quantum identity channel. By relating the problem to the additivity of minimum output entropies, we show that a strong converse holds for a large class of channels, including all unital qubit channels, the d-dimensional depolarizing channel and the Werner-Holevo channel. This further justifies the interpretation of the classical capacity as a sharp threshold for information-transmission. Joint work with Robert Koenig.

Quantum random walks have received much interest due to their non- intuitive dynamics, which may hold a key to radically new quantum algorithms. What remains a major challenge is a physical realization that is experimentally viable, readily scalable, and not limited to specific connectivity criteria. In this seminar, I will present an implementation scheme for quantum walking on arbitrarily complex graphs. This scheme is particularly elegant since the walker is not required to physically step between the nodes; only flipping coins is sufficient. In addition, by taking advantage of the inherent structure of the CS decomposition of unitary matrices, we are able to implement all coin operations necessary for each step of the walk simultaneously. This scheme can be physically realized using a variety of quantum systems, such as cold atoms trapped inside an optical lattice or electrons inside coupled quantum dots.

Solving linear systems of equations is a common problem that arises both on its own and as a subroutine in more complex problems: given a matrix A and a vector b, find a vector x such that Ax=b. Often, one does not need to know the solution x itself, but rather an approximation of the expectation value of some operator associated with x, e.g., x'Mx for some matrix M. In this case, when A is sparse and well-conditioned, with largest dimension N, the best known classical algorithms can find x and estimate x'Mx in O(N * poly(log(N))) time. In this talk I'll describe a quantum algorithm for solving linear sets of equations that runs in poly(log N) time, an exponential improvement over the best classical algorithm. This talk is based on my paper arXiv:0811.3171v2, which was written with Avinatan Hassidim and Seth Lloyd.