We give new evidence that quantum computers--moreover, rudimentary quantum computers
built entirely out of linear-optical elements--cannot be efficiently simulated by classical …

We examine the number of queries to input variables that a quantum algorithm requires to
compute Boolean functions on {0, 1} N in the black-box model. We show that the exponential …

We discuss several complexity measures for Boolean functions: certificate complexity,
sensitivity, block sensitivity, and the degree of a representing or approximating polynomial …

The NLTS (No Low-Energy Trivial State) conjecture of Freedman and Hastings posits that
there exist families of Hamiltonians with all low energy states of non-trivial complexity (with …

We propose a new method for proving lower bounds on quantum query algorithms. Instead
of a classical adversary that runs the algorithm with one input and then modifies the input we …

We present two new quantum algorithms that either find a triangle (a copy of K_3) in an
undirected graph G on n nodes, or reject if G is triangle free. The first algorithm uses …

We prove that the entanglement entropy of the ground state of a locally gapped frustration-
free 2D lattice spin system satisfies an area law with respect to a vertical bipartition of the …

This paper proves that several interactive proof systems are zero-knowledge against
general quantum attacks. This includes the well-known Goldreich-Micali-Wigderson …

Quantum algorithms hold the promise of solving certain computational problems
dramatically faster than their classical counterparts. The latest generation of quantum …

Quantum algorithms for graph problems are considered, both in the adjacency matrix model
and in an adjacency list-like array model. We give almost tight lower and upper bounds for …