Conference

We address the problem of testing the dimensionality of classical and quantum systems in a ‘black-box’ scenario. Imagine two uncharacterized devices. The first one allows an experimentalist to prepare a physical system in various ways. The second one allows the experimentalist to perform some measurement on the system. After collecting enough statistics, the experimentalist obtains a ‘data table’, featuring the probability distribution of the measurement outcomes for each choice of preparation (of the system) and of measurement. Here, we develop a general formalism to assess the minimal dimensionality of classical and quantum systems necessary to reproduce a given data table. To illustrate these ideas, we provide simple examples of classical and quantum ‘dimension witnesses’. In general quantum systems are more economical than classical ones in terms of dimensionality, in the sense that there exist data tables obtainable from quantum systems of dimension d which can only be generated from classical systems of dimension strictly greater than d. By drawing connections to communication complexity one can find data tables for which this classical/quantum separation is dramatic. Finally, these ideas can also be used to demonstrate security of one-way QKD in a semi-device-independent scenario, in which devices are uncharacterized, but only assumed to produce quantum systems of a given dimension.

A seminal work by Cleve, Høyer, Toner and Watrous (quant-ph/0404076) proposed a close connection between quantum nonlocality and computational complexity theory by considering nonlocal games and multi-prover interactive proof systems with entangled provers. It opened up the whole area of study of the computational nature of nonlocality. Since then, understanding nonlocality has been one of the major goals in computational complexity theory in the quantum setting. This talk gives a survey of this exciting area.

In this talk, I'll survey various "foils" of BQP (Bounded-Error Quantum Polynomial-Time) that have been proposed: that is, changes to the quantum model of computation that make it either more or less powerful. Possible topics include: postselected quantum computing, quantum computing with nonlinear Schrodinger equation, quantum computing with non-unitary linear transformations, quantum computing with hidden variables, linear-optical quantum computing, quantum computing with restricted gate sets, quantum computing with separable mixed states, quantum computing over finite fields, and more depending on audience interest.