Perimeter Institute Quantum Discussions

Coin flipping by telephone (Blum \'81) is one of the most basic cryptographic tasks of two-party secure computation. In a quantum setting, it is possible to realize (weak) coin flipping with information theoretic security. Quantum coin flipping has been a longstanding open problem, and its solution uses an innovative formalism developed by Alexei Kitaev for mapping quantum games into convex optimization problems. The optimizations are carried out over duals to the cone of operator monotone functions, though the mapped problem can also be described in a very simple language that involves moving points in the plane. Time permitting, I will discuss both Kitaev\'s formalism, and the solution that leads to quantum weak coin flipping with arbitrarily small bias.

Decoherence attempts to explain the emergent classical behaviour of a quantum system interacting with its quantum environment. In order to formalize this mechanism we introduce the idea that the information preserved in an open quantum evolution (or channel) can be characterized in terms of observables of the initial system. We use this approach to show that information which is broadcast into many parts of the environment can be encoded in a single observable. This supports a model of decoherence where the pointer observable can be an arbitrary positive operator-valued measure (POVM). This generalization makes it possible to characterize the emergence of a realistic classical phase-space. In addition, this model clarifies the relations among the information preserved in the system, the information flowing from the system to the environment (measurement), and the establishment of correlations between the system and the environment.

I should like to show how particular mathematical properties can limit our metaphysical choices, by discussing old and new theorems within the statistical-model framework of Mielnik, Foulis & Randall, and Holevo, and what these theorems have to say about possible metaphysical models of quantum mechanics. Time permitting, I should also like to show how metaphysical assumptions lead to particular mathematical choices, by discussing how the assumption of space as a relational concept leads to a not widely known frame-invariant formulation of classical point-particle mechanics by Föppl and Zanstra, and related research topics in continuum mechanics and general relativity.

The \\\"frequency comb\\\" defined by the eigenmodes of an optical resonator is a naturally large set of exquisitely well defined quantum systems, such as in the broadband mode-locked lasers which have redefined time/frequency metrology and ultra precise measurements in recent years. High coherence can therefore be expected in the quantum version of the frequency comb, in which nonlinear interactions couple different cavity modes, as can be modeled by different forms of graph states. We show that is possible to thereby generate states of interest to quantum metrology and computing, such as multipartite entangled cluster and Greenberger-Horne-Zeilinger states.

We construct a simple translationally invariant, nearest-neighbor Hamiltonian on a chain of 10-dimensional qudits that makes it possible to realize universal quantum computing without any external control during the computational process, requiring only initial product state preparation. Both the quantum circuit and its input are encoded in an initial canonical basis state of the qudit chain. The computational process is then carried out by the autonomous Hamiltonian time evolution. After a time greater than a polynomial in the size of the quantum circuit has passed, the result of the computation can be obtained with high probability by measuring a few qudits in the computational basis. This result also implies that there cannot exist efficient classical simulation methods for generic translationally invariant nearest-neighbor Hamiltonians on qudit chains, unless quantum computers can be efficiently simulated by classical computers (or, put in complexity theoretic terms, unless BPP=BQP). This is joint work with Daniel Nagaj.

The renormalization group (RG) is one of the conceptual pillars of statistical mechanics and quantum field theory, and a key theoretical element in the modern formulation of critical phenomena and phase transitions. RG transformations are also the basis of numerical approaches to the study of low energy properties and emergent phenomena in quantum many-body systems. In this colloquium I will introduce the notion of \\\"entanglement renormalization\\\" and use it to define a coarse-graining transformation for quantum systems on a lattice [G.Vidal, Phys. Rev. Lett. 99, 220405 (2007)]. The resulting real-space RG approach is able to numerically address 1D and 2D lattice systems with thousands of quantum spins using only very modest computational resources. From the theoretical point of view, entanglement renormalization sheds new light into the structure of correlations in the ground state of extended quantum systems. I will discuss how it leads to a novel, efficient representation for the ground state of a system at a quantum critical point or with topological order.

In this talk, we will investigate the distinguishability of quantum operations from both discrete and continuous point of view. In the discrete case, the main topic is how we can identify quantum measurement apparatuses by considering the patterns of measurement outcomes. In the continuous case, we will focus on the efficiency of parameter estimation of quantum operations. We will discuss several methods that can achieve Heisenberg Limit and prove in some other cases the impossibility of breaking the Standard Quantum Limit. The general treatment of estimation of quantum operations also allows an investigation of the effect of noise on estimation efficiency.

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.

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.