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.

Entanglement is one of the most fundamental and yet most elusive properties of quantum mechanics. Not only does entanglement play a central role in quantum information science, it also provides an increasingly prominent bridging notion across different subfields of Physics --- including quantum foundations, quantum gravity, quantum statistical mechanics, and beyond. Arguably, the property of a state being entangled or not is by no means unambiguously defined. Rather, it depends strongly on how we decide to regard the whole as composed of its part or, more generally, on the restricted ways in which we are able to observe and control the system at hand. Acknowledging the implications of such an operationally constrained point of view naturally has led to a notion of 'generalized entanglement,' which is directly based on quantum observables and offers added flexibility in a variety of contexts. In this talk, I will survey some of the main accomplishments of the generalized entanglement program to date, with an eye toward recent developments and open problems.

Black holes are regions of space with gravity so strong that nothing can escape from them, not even light. This isn't science fiction - there's even a gigantic black hole at the center of our galaxy. It's hard to imagine a more effective way to irrevocably erase and destroy a computer's hard drive than to drop it into a nice big black hole. But is the information on that drive really gone forever? Paradoxically, there's a good chance that not only does the information come back, it comes back in the blink of an eye. This surprise return of the information is based on the same principles that might someday make reliable quantum computers a reality. In fact, engineers are already exploiting these principles to help distribute software and stream video over the internet. And that's where the tornadoes come in...

We study the entanglement dynamics and relaxation properties of a system of two interacting qubits in the two cases (I) two independent bosonic baths and (II) one common bath, at temperature $T$. The entanglement dynamics is studied in terms of the concurrence C(t) between the two spins and of the von Neumann entropy S(t) with respect to the bath, as a function of time. We prove that the system does thermalize. In the case (II) of a single bath, the existence of a decoherence-free (DFS) subspace makes entanglement dynamics very rich. We show that when the system is initially in a state with a component in the DFS the relaxation time is surprisingly long, showing the existence of semi-decoherence free subspaces. The equilibrium state in this case is not the Gibbs state. The entanglement dynamics for the single bath case is also studied as a function of temperature, coupling strength with the environment and strength of tunneling coupling. The case of the mixed state is finally shown and discussed.

In topological quantum computation the geometric details of a particle trajectory become irrelevant; only the topology matters. This is one reason for the inherent fault tolerance of topological quantum computation. I will speak about a model in which this idea is taken one step further. Even the topology is irrelevant. The computation is determined solely by the permutation of the particles. Unlike topological quantum computation, which requires anyons confined to two dimensions, permutational quantum computations can in principle be performed by permuting a set of ordinary spin-1/2 particles with definite total angular momentum in three dimensions. The resulting model of computation appears to be intermediate in power between classical computation (P) and standard quantum computation (BQP). The model may be equivalently defined in terms of spin networks, which are an important concept in loop quantum gravity.