UC Berkeley

While the exponential complexity of quantum systems is the basis of counterintuitive phenomena such as quantum computing, it also represents a fundamental challenge: how can we, classical beings, study, understand, and control quantum systems that are exponentially more powerful than ourselves? In this dissertation, we present classical methods to approach two such issues.

Firstly, we discuss the testing of quantum devices, particularly special-purpose quantum computers. We propose a simple classical model for quantum annealers, arguably the most intensely explored class of special-purpose quantum computers. The model provides a benchmark against which to compare the quantum annealer, in what may be called a "quantum Turing test," to determine whether the quantum annealer exhibits algorithmically significant quantum behavior. An application of the test reveals that the input-output behavior of the benchmark agrees with published data from the D-Wave One quantum annealer on random instances of its native problem on 108 qubits, and closely matches the reported performance of D-Wave 2X on special instances devised to exercise quantum tunneling. In other words, the machine does not pass the quantum Turing test with respect to these inputs. A more detailed analysis of the new classical model yields further algorithmic insights into the nature of quantum annealing.

Secondly, we show that commuting stoquastic quantum k-SAT, an interesting variant of the local Hamiltonian problem, is in NP for any k=O(log n). The result follows from a study of the computational complexity of tensor network nonzero testing, a fundamental problem in quantum Hamiltonian complexity. We show that the problem in its most general form is computationally very hard, i.e., not contained in the polynomial hierarchy unless the hierarchy collapses. On the other hand, we are able to identify two "easy" special cases of tensor network nonzero testing, namely nonnegative tensors and injective tensors, which may be useful in certain contexts. Indeed, our main result follows by exhibiting a direct connection between the special case of nonnegative tensor networks and commuting stoquastic quantum k-SAT.