The Crown Jewels of Quantum Algorithms

Scott Aaronson

One of the crown jewels of complexity theory is Valiant's theorem that computing the permanent of an n × n matrix is # P -hard. Here we show that, by using the model of linear-optical quantum computing —and in particular, a universality theorem owing to Knill, Laflamme and Milburn—one can give a different and arguably more intuitive proof of this theorem.

Stefano Bonzio, Paola Verrucchi

Tzvetan S. Metodi, Arvin I. Faruque, Frederic T. Chong

Tony Guénault

Superfluidity is the jewel in the crown of low temperature physics. When temperatures are low enough, every substance in thermal equilibrium must become ordered. Since some materials remain fluid to the lowest temperatures, it is a fascinating question as to how this ordering can take place. One possibility is the formation of a superfluid state, a

Richard Cleve, ARTUR K. EKERT, Leah Henderson +2 more

Andreas Blühm, Ion Nechita

In this work, we establish the connection between the study of free spectrahedra and the compatibility of quantum measurements with an arbitrary number of outcomes. This generalizes previous results by the authors for measurements with two outcomes. Free spectrahedra arise from matricial relaxations of linear matrix inequalities. A particular free spectrahedron which we define in this work is the matrix jewel. We find that the compatibility of arbitrary measurements corresponds to the inclusion of the matrix jewel into a free spectrahedron defined by the effect operators of the measurements under study. We subsequently use this connection to bound the set of (asymmetric) inclusion constants for the matrix jewel using results from quantum information theory and symmetrization. The latter translate to new lower bounds on the compatibility of quantum measurements. Among the techniques we employ are approximate quantum cloning and mutually unbiased bases.