TQC · 2011

There are two main Grand Challenges for academic research in quantum communication. The first one concerns "device independent QKD", that is an implementation of Quantum Key Distribution that exploits the nonlocal correlation observed in violations of Bell's inequality to realize "self testing QKD apparatuses". The second one aims at futuristic continental scale quantum networks. The latter requires, among others, multimode quantum memories with close to a second memory times, a fascinating challenge. Interestingly, quantum networks also lead us to a refreshing revisit of nonlocality.

Device-independent cryptographic protocols are by definition more secure than their device-dependent counterparts, since they do not rely on any assumptions regarding the internal workings of the apparatus used to implement them. Thus far, the device-independent approach has been successfully applied to problems such as quantum-key distribution and randomness generation, but it is not a priori clear whether it can be applied to protocols in the mistrustful cryptography class, where the parties do not trust one another. In this work we show that for bit-commitment and coin flipping a device-independent treatment is possible.

Quantum Key Distribution (QKD), invented by Bennett and Brassard and Ekert can be considered the first application of quantum information science. We focus on the assumption that an arbitrarily large number M of signals can be exchanged between the legitimate parties (Alice and Bob) and subsequently used for the computation of the final key. Here, we apply a novel proof technique to the BB84 QKD protocol and derive almost tight bounds on the minimum value M required to achieve a given level of security. The technique is based on a formulation of the uncertainty relation in terms of smooth entropies. We demonstrate significant improvements of the finite-key rate over existing results.

Device-independent quantum key distribution aims to provide key distribution schemes whose security is based on the laws of quantum physics but which does not require any assumptions about the internal working of the quantum devices used in the protocol. We provide a general security proof valid for a large class of device-independent quantum key distribution protocols in a model in which the raw key elements are generated by causally independent measurement processes. The validity of this independence condition may be justifiable in a variety of implementations and is necessarily satisfied in a physical realization where the raw key is generated by N separate pairs of devices.

By characterizing codes in terms of "lattice groups" on infinite lattices, we show that they can all be understood in terms of topological charges and string operators. This is true either for subspace or subsystem codes, and it has direct applications for error correction, for example. Subspace codes are directly connected to topologically ordered condensed matter systems. We show that all 2D topological stabilizer codes are equivalent up to local transformations to several copies of one universal phase: Kitaev's topological code.

One of the most basic and intuitive properties of most information measures is that the amount of information carried by a physical system must be bounded by its size. We consider locking, which occurs when classical information encoded into a quantum system can be extracted given access to the cyphertext only with much less probability than expected. We show that locking occurs with high probability in physical systems whose internal dynamics are sufficiently random, with implications for thermodynamics and the black hole information problem. We also generalise locking to the case where the measuring device is allowed to share entanglement with the cyphertext-key compound system.

The quantum relative entropy between two quantum states rho and sigma, S(rho||sigma) = Tr rho(log rho - log sigma), is a non-commutative generalisation of the Kullback-Leibler distance between probability distributions. Because of its strong mathematical connections with von Neumann entropy, and its interpretation as an optimal asymptotic error rate in quantum hypothesis testing (in the context of Stein's lemma) relative entropy is widely used as a (non-symmetric) distance measure between states. One of its drawbacks, however, is that for non-faithful (rank-deficient) states the relative entropy can be infinite. We define the telescopic relative entropy (TRE) and prove sharp upper bounds on it in terms of the trace norm distance.

Finding the consequences of symmetries in dynamics is a subject with broad applications in physics. We are interested to find tools to study the consequences of symmetry which apply to open as well as closed quantum systems. We introduce a different point of view for thinking about asymmetry which is not based on symmetric dynamics; instead it is based on the intuition that a state which breaks symmetry can be thought as a signal which carries information about the group element. Using this point of view we use information measures to build asymmetry measures via the Holevo quantity. We show that for pure states Noether's theorem includes all the possible implications of the symmetry of dynamics, but for mixed states conservation of asymmetry measures imply more constraints than those prescribed by Noether's theorem.

In 1998, Knill and Laflamme proposed that exponential speedups over classical computers could still be possible even if one can only initialize a single qubit into a pure state, with the rest of the qubits in the maximally mixed state. The complexity class thus defined is called DQC1. We show that approximating the Turaev-Viro invariant of a 3-manifold specified as a mapping torus is a complete problem for DQC1. We also use the language of Topological Quantum Field Theories (or TQFTs) to outline the mathematical underpinnings of the relationship between approximating the Jones polynomial of the plat and trace closures, and approximating the Turaev-Viro invariant of Heegaard splittings and mapping tori.

The formula-evaluation problem is defined recursively. We give a quantum algorithm to evaluate formulas over any finite boolean gate set. Provided that the general adversary bound complexities of the input subformulas to any gate differ by at most a constant factor, the algorithm has optimal query complexity. Importantly, after efficient preprocessing, the algorithm is nearly time optimal. The algorithm is derived using the framework relating span programs and quantum algorithms. It corresponds to the composition of the individual span programs for each gate in the formula. We define a new span program complexity measure, the full witness size, allowing quantum algorithms to be based on span programs with free inputs.

Self-testing was introduced by Mayers and Yao. The goal of self-testing is to verify the operation of a group of non-communicating quantum devices using only classical interaction with the devices and without trusting any of them a priori. In this article we describe two different self-tests which verify that a group of devices share a graph state and implement Pauli X and Z measurements on this state. The self-tests can be reinterpreted as Bell inequalities which have a unique strategy that achieves the quantum bound.

One of the essential differences between quantum information processing (QIP) and the classical counterpart is that QIP sometimes involves global operations on unknown input states, namely, arbitrary superpositions of quantum states where their superposition coefficients are unknown. Quantum teleportation and quantum error corrections are typical examples. We call such unknown states. Quantum information cannot be measured (i.e., estimating the unknown coefficients by finite measurements) perfectly and cannot be copied perfectly either. In contrast, classical information in QIP can be encoded in a set of known orthogonal states and can be perfectly measured. Classical information can be also obtained by the result of measurements in QIP. QIP can be analyzed by investigating how input quantum information is transformed to output quantum information due to global operations. In this talk, I present our recent results from investigating the globalness of unitary operations on quantum information in terms of delocalizing power, entanglement cost, and implementation over a butterfly network.

When separated measurements on entangled quantum systems are performed, the theory predicts correlations that cannot be explained by any classical mechanism. All optical demonstrations of such violations have involved discrete degrees of freedom and are plagued by the detection-efficiency loophole. We present a simple method for generating large violations for feasible states using both photon counting and homodyne detections. Our scheme may lead to the first violation of Bell inequalities using continuous-variable measurements and pave the way for a loophole-free Bell test.

Public-key cryptography has proved to be an indispensable tool in the modern information security infrastructure. We prove that an identification scheme based on bounded quantum reference frames is secure against a computationally-unbounded adversary (only restricted by finite cheating strategies), demonstrating for the first time that unconditionally-secure and reusable public-key authentication is possible in principle. To prove security of our protocol, we employ elements of the polynomial method, the theory of estimation of black-box group transformations, and the theory of bounded quantum reference frames. We also use the quantum Fourier transform in a new and rather surprising way.

Quantum key distribution (QKD) is a cryptographic primitive allowing two distant parties, Alice and Bob, to establish a secret key in an untrusted environment controlled by some eavesdropper, Eve. We introduce a new continuous-variable QKD protocol using a continuous but non-Gaussian modulation, allowing for an efficient reconciliation scheme and thus for improved performances. The modulation we consider crucially uses algebraic properties of the octonions, which can be seen as points on the unit sphere in R^8. We establish the security of this protocol against collective attacks, provided that the quantum channel is linear.

We introduce a notion of a learning agent whose interaction with the environment is governed by a simulation-based projection, which allows the agent to project itself into future situations before it takes real action. Projective simulation is based on a random walk through a network of clips, which are elementary patches of episodic memory. The network of clips changes dynamically, both due to new perceptual input and due to certain compositional principles of the simulation process. During simulation, the clips are screened for specific features which trigger factual action of the agent. While the scheme works entirely classically, it also provides a natural route for generalization to quantum-mechanical operation.

PARITY is the oracle (or black-box) problem of determining the parity of an n-bit string by querying positions in the string. We construct an n-r quantum query algorithm that computes the sum correctly with probability min{floor(n/r)/k,1}, for each 1 <= r <= n. This quantum algorithm utilizes the n-r queries sequentially and adaptively, like quantum search algorithms, but in a different way that is not amplitude amplification. We motivate the development of our algorithm by considering the simplest new instances of SUM and conclude by recalling the result of van Dam.

Extracting uniform randomness from a long string x of length n using a two-universal hash function or an extractor may be very inefficient. We show that the bounds given in König-Renner also apply to the case where the sample is chosen bitwise uniformly, instead of (recursively) in blocks. We also prove a new min-entropy sampling theorem using a completely different approach. As corollary we obtain a lower bound for random access codes: for any k-out-of-n random access code where the storage is bounded by m <= (1-epsilon)n, the success probability is at most 2^{-Omega(k)}.

The graph state formalism is an elegant and powerful formalism for quantum information processing. We focus on the application of graph states in MBQC and in particular on the characterisation of graphs that can be used to perform quantum information processing in this context. We introduce a simpler but equivalent combinatorial characterisation using focused gflow and we provide a simple condition of existence of such a flow as the existence of a right inverse to the adjacency matrix of the graph. The main contribution of this work is the weakening of the determinism condition in order to consider the more general class of information preserving evolutions.

In recent years we've seen many developments in the study of strongly correlated quantum systems spurred by insights from the study of entanglement in quantum information theory. In particular, new variational classes manifestly exploiting the entropy/area law have been applied to successfully study a wide range of settings from real-time evolution to finite fermion densities. These developments have been mostly centered in the lattice setting. In this talk I'll describe recent work in generalizing the two most successful variational classes developed, matrix product states and the multiscale entanglement renormalization ansatz, to the quantum field setting by exploiting a continuum limit of their quantum circuit descriptions.

There exist instances of computations involving mixed quantum states where the quantum advantages over the best known classical algorithm cannot be ascribed to quantum entanglement. We present a fundamental role played by quantum discord in quantum information processing. One of our main results is a connection between quantum discord and the strong subadditivity of von Neumann entropy. Our second main result gives an operational interpretation of quantum discord by establishing its role in an important class of quantum information protocols. We show that quantum discord measures how coherently one performs the Mother protocol, and its generalization as the FQSW (Fully quantum Slepian Wolf) protocol, in the presence of decoherence.

We refine recent local unitary entanglement classification for symmetric pure states of n qubits (that is, states invariant under permutations of qubits) using local unitary stabilizer subgroups and Majorana configurations.