2026 Theses Doctoral

Quantum query complexity, with advice

Bostanci, Can H.

The goal of this thesis is to understand whether quantum states are inherently more useful than classical strings when used as auxiliary information, including proofs and advice. One way to formalize this question is to compare oracle models in which a quantum verifier receives either a quantum proof or a classical proof. Over the past twenty years, a number of works have made progress toward answering this question, but all have fallen short of the “gold standard,” a classical oracle separation.

This thesis describes an alternative approach to the problem of comparing quantum and classical proofs and proves the first classical oracle separation between the corresponding complexity classes. It also proves the first classical oracle separation between bounded-error quantum polynomial time with quantum advice and bounded-error quantum polynomial time with classical advice. Our approach exploits the “reusability,” or “clonability,” of a classical witness to transform a hypothetical verifier with a classical proof into an algorithm that achieves a “too-good-to-be-true” success probability for a family of sampling tasks. We use this perspective to prove two classical oracle separations between quantum and classical proofs.

1. Our first oracle separation is based on a natural extension of the “Forrelation” problem, originally used by Aaronson and Ambainis to demonstrate an exponential query complexity advantage for quantum algorithms over classical ones. We introduce the “spectral Forrelation” problem and prove an oracle separation using a novel compressed-oracle technique.

2. Our second oracle separation is based on the “code intersection” problem studied by Yamakawa and Zhandry. We connect this candidate separation to near-optimal list recoverability of codes. Using recent coding-theory results, we prove that a code intersection oracle instantiated with multiplicity codes yields a separation.