Quantum mechanics redefines information and its fundamental properties. Researchers at Perimeter Institute work to understand the properties of quantum information and study which information processing tasks are feasible, and which are infeasible or impossible. This includes research in quantum cryptography, which studies the trade-off between information extraction and disturbance, and its applications. It also includes research in quantum error correction, which involves the study of methods for protecting information against decoherence. Another important side of the field is studying the application of quantum information techniques and insights to other areas of physics, including quantum foundations and condensed matter.
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.
How should we think about quantum computing? The usual answer to this question is based on ideas inspired by computer science, such as qubits, quantum gates, and quantum circuits. In this talk I will explain an alternate geometric approach to quantum computation. In the geometric approach, an optimal quantum computation corresponds to "free falling" along the minimal geodesics of a certain Riemannian manifold. This reformulation opens up the possibility of using tools from geometry to understand the strengths and weaknesses of quantum computation, and perhaps to understand what makes certain physical operations difficult (or easy) to synthesize.
In order to predict the future state of a quantum system, we generally do not need to know the past state of the entire universe, but only the state of a finite neighborhood of the system. This locality is best expressed as a restriction on how information "flows" between systems. In this talk I will describe some recent work, inspired by quantum cellular automata, about the information strucutre of local quantum dynamics. Issues to be discussed include the definition of "locality", some characterization theorems, connections between classical and quantum locality for reversible maps, the relation between local and global dynamics, and the dissection of CNOT.
In this talk, I will outline a quantum generalization of causal networks that are used to analyze complex probabilistic inference problems involving large numbers of correlated random variables. I will review the framework of classical causal networks and the graph theoretical constructions that are abstracted from them, including entailed conditional independence, d-separation and Markov equivalence. I will show how to generalize the definition of causal networks to the quantum case, such that the same graph theoretic constructions apply, and give an explicit representation of the states supported on the graph as the Gibbs states of certain classes of Hamiltonians.
Adiabatic Quantum Computation is not only a possibly more robust alternative to standard quantum computation. Since it considers a continuous-time evolution of the system, it also provides a natural bridge towards studying the dynamics of interacting many-particle quantum systems, quantum phase transitions and other issues in fundamental physics. After a brief review of adiabatic quantum computation, I will show our recent results on the dynamics of entanglement and fidelity for the search and Deutsch algorithms including several variations and optimization. I will show how these studies led to suggesting an alternative definition of entanglement and compare the results, and discuss possible implications for considering entanglement a resource. I will conclude with an outlook on further applications and extensions of adiabatic quantum computation.
It is somewhat surprising, but problems in quantum computing lead to problems in algebraic graph theory. I will discuss some instances that I am familiar with, and note a commmon thread.