Quantum Information

We use a Bayesian approach to optimally solve problems in noisy binary search. We deal with two variants: 1. Each comparison can be erroneous with some probability 1 - p. 2. At each stage k comparisons can be performed in parallel and a noisy answer is returned. We present a (classic) algorithm which optimally solves both variants together, up to an additive term of O(log log (n)), and prove matching information theoretic lower bounds. We use the algorithm with the results of Farhi et al. (FGGS99)presenting a quantum search algorithm in an ordered list of expected complexity less than log(n)/3, and some improved quantum lower bounds on noisy search, and search with an error probability. Joint work with Michael Ben-Or.

Roughly speaking, the more Alice is entangled with Bob, the harder it is for her to send her state to Charlie. In particular, it will be shown that the squashed entanglement, a well known entanglement measure, gives the fastest rate at which a quantum state can be sent between two parties who share arbitrary side information. Likewise, the entanglement of formation and entanglement cost is shown to be the fastest rate at which a quantum state can be sent when the parties have access to side-information which is maximally correlated. A further restriction on the type of side-information implies that the rate of state transmission is given by the quantum mutual information. This suggests a new paradigm for understanding entanglement and other correlations in terms of quantum Shannon theroy. Different types of side-information correspond to different types of correlations with the squashed entanglement and the mutual information being two extremes. Furthermore, there is a dual paradigm: if one distributes the side-information as aliciously as possible so as to make the sending of the state as difficult as possible, one finds maximum rates which give interpretations to known quantities as well as new ones.

Do ideas about information and reality inspire fruitful new approaches to the hardest problems of modern physics? What can we learn about the paradoxes of quantum mechanics, the beginning of the universe and our understanding of black holes by thinking about the very essence of information? The answers to these questions are surprising and enlightening, but also controversial. The topic of information within physics has involved some of the 20th century\'s greatest scientists in long-running intellectual battles that continue to the present day. In this special debate, hosted by the CBC\'s Bob McDonald of \'Quirks and Quarks\', you will enjoy a lively discussion between four prominent physicists who have thought long and hard about these questions. information, quantum mechanics, quantum cryptology, entropy, everything computes, properties equals information, uncertainty principle, quantum computer, hologram, black hole, event horizon, coherence, Schrodinger, interference and predictability, quantum state, teleportation, entanglement

One of the most significant questions in quantum information is about the origin of the computational power of the quantum computer; namely, from which feature of quantum mechanics and how does the quantum computer obtain its superior computational potential compared with the classical computer? In my talk, I address this open question more concisely through the study of measurement-based quantum computer, in which all the quantum resource is attributed to entanglement since computation is carried through its consumption by local measurements. I also show a simple model of the phase transition of quantum computer occurring at some threshold, below which the quantum computer comes to allow an efficient classical simulation in accordance with an exponential drop in the amount of entanglement.

Quantum fields in the Minkowski vacuum are entangled with respect to local field modes. This entanglement can be swapped to spatially separated quantum systems using standard local couplings. A single, inertial field detector in the exponentially expanding (de Sitter) vacuum responds as if it were bathed in thermal radiation in a Minkowski universe. Using two inertial detectors, interactions with the field in the thermal case will entangle certain detector pairs that would not become entangled in the corresponding de Sitter case.The two universes can thus be distinguished by their entangling power.

First, a brief description of Bell\'s theorem will be given. It states states that there is no classical-like (local realistic) description of all quantum predictions. Next, a plausible class of non-local realistic models will be presented which is incompatible with quantum mechanics, as first shown by Leggett. Experiments confirming the incompatibility will be described. Finally, it will be argued that quantum mechanics can be seen as a theory of systems with limited information resources.

We attempt at characterizing the correlations present in the quantum computational model DQC1, introduced by Knill and Laflamme [Phys. Rev. Lett. 81, 5672 (1998)]. The model involves a collection of qubits in the completely mixed state coupled to a single control qubit that has nonzero purity. Although there is little or no entanglement between two parts of this system, it provides an exponential speedup in certain problems. On the contrary, we find that the quantum discord across the most natural split is nonzero for typical instances of the DQC1 ciruit. Nonzero values of discord indicate the presence of nonclassical correlations. We propose quantum discord as figure of merit for characterizing the resources present in this computational model. This might be a complementary measure for counting resources in quantum information science.

A class of operations distinct to entangled states shared between more than two parties is their conversion to entangled states shared between fewer parties. The extent to which these can be achieved in the regime of local operations and classical communication provides an operational characterisation of multiparty states, for example in the \"entanglement of assistance\" and related quantities. I will give a brief overview of this topic and discuss our results showing qualitatively different behaviour when the parties receiving the final state are not chosen beforehand.

We will compare quantum phase estimation from the point of view of quantum computation and quantum metrology. In the simplest cases, the former can be simplified to a sequential (unentangled) protocol, while the latter is parallel (entangled). We show that both protocols can be formally related with circuit identities and that they respond in exactly the same way to decoherence. We present sequential protocols for optimal estimation and frame synchronization in DQC1. Finally, we introduce new estimation protocols based on nonlinear Hamiltonians. We show that both optimal input states and product states with separable measurements improve the scaling of linear Hamiltonians. We will comment on the effect of decoherence in nonlinear protocols, and the role of entanglement in nonlinear protocols with product states.

Renner\'s global quantum de Finetti theorem establishes that if the state of a quantum system is invariant under permutations of its systems, then almost all of its subsystems are almost in the same state and independent of each other. Motivated by this result, we show that the most straightforward classical analogue of Renner\'s theorem is false. Joint work with Matthias Christandl (Cambridge).

The one clean qubit model is a model of quantum computation in which all but one qubit starts in the maximally mixed state. One clean qubit computers are believed to be strictly weaker than standard quantum computers, but still capable of solving some classically intractable problems. I\'ll discuss my recent work in collaboration with Peter Shor which shows that evaluating a certain approximation to the Jones polynomial at a fifth root of unity for the trace closure of a braid is a complete problem for the one clean qubit complexity class.

We give a convenient representation for any map which is covariant with respect to an irreducible representation of SU(2), and use this representation to analyze the evolution of a quantum directional reference frame when it is exploited as a resource for performing quantum operations. We introduce the moments of a quantum reference frame, which serve as a complete description of its properties as a frame, and investigate how many times a quantum directional reference frame represented by a spin-j system can be used to perform a certain quantum operation with a given probability of success. We provide a considerable generalization of previous results on degradation of reference frame, from which follows a classification of the dynamics of spin-j system under the repeated action of any covariant map with respect to SU(2). Joint work with Lana Sheridan, Martin Laforest and Stephen Bartlett