Perimeter Institute Quantum Discussions

I discuss a technique - the quantum adversary upper bound - that uses the structure of quantum algorithms to gain insight into the quantum query complexity of Boolean functions. Using this bound, I show that there must exist an algorithm for a certain Boolean formula that uses a constant number of queries. Since the method is non-constructive, it does not give information about the form of the algorithm. After describing the technique and applying it to a class of functions, I will outline quantum algorithms that match the non-constructive bound.

We show that if the ground state energy problem of a
classical spin model is NP-hard, then there exists a choice parameters of the
model such that its low energy spectrum coincides with the spectrum of
\emph{any} other model, and, furthermore, the corresponding eigenstates match
on a subset of its spins. This implies that all spin physics, for example all
possible universality classes, arise in a single model. The latter property was
recently introduced and called ``Hamiltonian completeness'', and it was shown

Transversal
implementations of encoded unitary gates are highly desirable for
fault-tolerant quantum computation.  It is known, however, that
transversal gates alone cannot be computationally universal.  I will show
that the limitation on universality can be circumvented using only
fault-tolerant error correction, which is already required anyway.  This
result applies to ``triorthogonal'' stabilizer codes, which were recently
introduced by Bravyi and Haah for state distillation.  I will show that

Expressions of several information theoretic quantities involve an optimization over auxiliary quantum registers. Entanglement-assisted version of some classical communication problems provides examples of such expressions. Evaluating these expressions requires bounds on the dimension of these auxiliary registers. In the classical case such a bound can usually be obtained based on the