Quantum versus classical resources in computational complexity
Jordi Rudo Weggemans

Abstract:
This dissertation studies the interplay between quantum and classical computational resources through the lens of computational complexity theory. It is structured in three parts, each addressing a different aspect of this topic.

Part I considers low-energy states of quantum systems, which play an important role in quantum many-body physics and quantum chemistry. We study the complexity of estimating ground and excited state energies of local Hamiltonians, given access to a guiding state promised to have non-negligible overlap with the relevant eigenspace. In Chapter 3, we formalize access models for such guiding states and study some of their properties and relations. In Chapter 4, we show that, for certain physically motivated 2-local Hamiltonians, this task is BQP-complete for a large range of input parameter settings. If the guiding state is only promised to exist, we show that the problem becomes QCMA-complete. Under standard complexity-theoretic assumptions, these results establish a well-defined, practically motivated setting in which quantum computers are provably superpolynomially more efficient than classical ones. In Chapter 5, we ask whether approximate descriptions of ground states can be obtained given QMA oracle access. In the fully general setting, this would correspond to finding a near-optimal quantum witness for any problem in QMA. Whilst this is known not to be possible relative to an oracle, we prove that it is possible to compute classical approximations of all low-locality reduced density matrices of a near-optimal witness, using a classical polynomial-time algorithm with such oracle access.

Part II focuses on quantum probabilistically checkable proof (QPCP) systems. In Chapter 6, we define a general class of QPCPs, allowing adaptivity and multiple unentangled provers. We show, via quantum reductions, that they are equivalent to constant-gap local Hamiltonian problems. As a consequence, we prove that adaptivity does not increase verifier power in this model, and that constant-query multi-prover QPCPs for QMA(2) imply QMA= QMA(2). In Chapter 7, we study quantum–classical PCPs (QCPCPs), where a quantum verifier has either classical or quantum query access to a classical proof. We prove that any constant quantum-query QCPCP with inverse-polynomial promise gap can be simulated by a constant-classical-query QCPCP with constant promise gap, and that the corresponding class of problems lies in BQ·NP, the class of all promise problems that have a quantum reduction to 3-SAT. This gives strong evidence that the power of QCMA cannot be captured by a quantum–classical PCP.

Part III explores alternative complexity measures, namely unitary query complexity and sample complexity. In Chapter 8, we develop a general technique for proving lower bounds on unitary query complexity using reductions to unitary channel discrimination, which also apply in the presence of quantum advice or proofs. As a direct corollary of our technique, we show that there exist quantum oracles relative to which QMA(2) ̸⊃SBQP and QMA/qpoly ̸⊃SBQP. In Chapter 9, we introduce and study a sample-to-sample task called complement sampling. We show that classically, this task requires an exponential number of classical samples, whilst a quantum computer can solve it using only a single quantum sample—resulting in the largest possible separation between classical and quantum sample complexity. We also argue that, under standard cryptographic assumptions, the task is efficiently verifiable, classically hard, and feasible on near-term quantum devices, providing a new path to “quantum resource advantage”.