Quantum Information

Quantum information theory has two equivalent mathematical conjectures concerning quantum channels, which are also equivalent to other important conjectures concerning the entanglement. In this talk I explain these conjectures and introduce recent results.

It is a fundamental property of quantum mechanics that non-orthogonal pure states cannot be distinguished with certainty, which leads to the following problem: Given a state picked at random from some ensemble, what is the maximum probability of success of determining which state we actually have? I will discuss two recently obtained analytic lower bounds on this optimal probability. An interesting case to which these bounds can be applied is that of ensembles consisting of states that are themselves picked at random. In this case, I will show that powerful results from random matrix theory may be used to give a strong lower bound on the probability of success, in the regime where the ratio of the number of states in the ensemble to the dimension of the states is constant. I will also briefly discuss applications to quantum computation (the oracle identification problem) and to the study of generic entanglement.

Ancillary state construction is a necessary component of quantum computing. Ancillae are required both for error correction and for performing universal computation in a fault-tolerant way. Computation to an arbitrary accuracy, however, is effectively achieved by increasing the number of qubits in order to suppress the variance in the expected number of errors. Thus, it is important to be able to construct very large ancillary states. Concatenated quantum coding provides a means of constructing ancillae of any size, but, this fact aside, concatenation is not a particularly efficient form of coding. More efficient codes exist, but these codes lack the substructure of concatenated codes that enables fault-tolerant preparation of large ancillae. In this talk I will discuss the advantages of coding in large blocks, both from the perspective of efficiency and analysis, and I will describe my progress in developing construction procedures for moderately large ancillae.

We explore the role of rotational symmetry of quantum key distribution (QKD) protocols in their security. Specifically, in the first part of the talk, we consider a generalized QKD protocol with discrete rotational symmetry. Note that, before our work, each QKD protocol seems to have a different security proof. Given that the techniques of those proofs are similar, it will be interesting to have a unified proof for QKD protocols with symmetry (e.g., the BB84 protocol and the SARG04 protocol). This is exactly what we achieve in our work. We show that rotational symmetry plays an important role in the unified security proof of QKD protocols with symmetry, leading to simple and structural security relations. In the second part, we consider a QKD protocol that does not possess rotational symmetry and analyze its security. Interestingly, even without any rotational symmetry, this protocol can still be proven secure. However, the security relation is not as simple as those in the first part, due to the lack of symmetry. Therefore, although rotational symmetry is not required in a QKD protocol to ensure its security, rotational symmetry does provide significant simplification in the security analysis, leading to simple security relations.

In this talk, I will show how to efficiently generate graph states based on realistic linear optics (with imperfect photon detectors and source), how to do scalable quantum computation with probabilistic atom photon interactions, and how to simulate strongly correlated many-body physics with ultracold atomic gas.

I will explain how a quantum circuit together with measurement apparatuses and EPR sources can be fully verified without any reference to some other trusted set of quantum devices. Our main assumption is that the physical system we are working with consists of several identifiable sub-systems, on which we can apply some given gates locally. To achieve our goal we define the notions of simulation and equivalence. The concept of simulation refers to producing the correct probabilities when measuring physical systems. The notion of equivalence is used to enable the efficient testing of the composition of quantum operations. Unlike simulation, which refers to measured quantities (i.e., probabilities of outcomes), equivalence relates mathematical objects like states, subspaces or gates. Using these two concepts, we prove that if a system satisfies some simulation conditions, then it is equivalent to the one it is supposed to implement. In addition, with our formalism, we can show that these statements are robust, and the degree of robustness can be made explicit. Finally, we design a test for any quantum circuit whose complexity is linear in the number of gates and qubits, and polynomial in the required precision. Joint work with Frederic Magniez, Dominic Mayers and Harold Ollivier.

Complexity class MA is a class of yes/no problems for which the answer `yes\' has a short certificate that can be efficiently checked by a classical randomized algorithm. We prove that MA has a natural complete problem: stoquastic k-SAT. This is a quantum-mechanical analogue of the satisfiability problem such that k-bit clauses are replaced by k-qubit projectors with non-negative matrix elements. Complexity class AM is a generalization of MA in which the certificate may include a short conversation between Prover and Verifier. We prove that AM also has a natural complete problem: stoquastic Local Hamiltonian with a quenched disorder. The problem is to evaluate expectation value of the ground state energy of disordered local Hamiltonian with non-positive matrix elements.

We describe a protocol for distilling maximally entangled bipartite states between random pairs of parties (``random entanglement'') from those sharing a tripartite W state, and show that this may be done at a higher rate than distillation of bipartite entanglement between specified pairs of parties (``specified entanglement''). Specifically, the optimal distillation rate for specified entanglement for the W has been previously shown to be the asymptotic entanglement of assistance of 0.92 EPR pairs per W, while our protocol can distill 1 EPR pair per W between random pairs of parties, which we conjecture to be optimal. We further extend this to a more general class of W-like states and show by increasing the number of parties in the protocol that there exist states with fixed lower-bounded distillable random entanglement for arbitrarily small specified entanglement. [Work done in collaboration with Benjamin Fortescue. Preprint available at http://arxiv.org/abs/quant-ph/0607126 ]

Entanglement is one of the most studied features of quantum mechanics and in particular quantum information. Yet its role in quantum information is still not clearly understood. Results such as (R. Josza and N. Linden, Proc. Roy. Soc. Lond. A 459, 2011 (2003)) show that entanglement is necessary, but stabilizer states and the Gottesman-Knill theorem (for example) imply that it is far from sufficient. I will discuss three aspects of entanglement. First, a quantum circuit with a "vanishingly small" amount of entanglement that admits an apparent exponential speed-up over the classical case. Second, I will discuss techniques for lower-bounding the amount of entanglement in bipartite quantum states. Finally, I will discuss the role of entanglement in quantum metrology. Specifically, I will show that entangling ancillas can make no difference to the accuracy of a quantum parameter estimation, regardless of the nature of the coupling Hamiltonian. I will conclude by discussing strategies for improving the scaling of quantum parameter estimation.

Traditional quantum state tomography requires a number of measurements that grows exponentially with the number of qubits n. But using ideas from computational learning theory, I'll show that "for most practical purposes" one can learn a quantum state using a number of measurements that grows only linearly with n. I'll discuss applications of this result in experimental physics and quantum computing theory, as well as possible implications for the foundations of quantum mechanics. quant-ph/0608142

In this talk I will present several new results from joint work with Dmitry Gavinsky, Oded Regev and Ronald de Wolf, relating to the model of one-way communication and the simultaneous model of communication. I will describe several separations between various resources (entanglement versus event coin, quantum communication versus classical communication), showing in particular that quantum communication cannot simulate a public coin and that entanglement can be much more powerful than a public coin, even if communication is quantum. I will also present a characterization of the quantum fingerprinting technique.