On provable quantum advantages in combinatorial optimization and distribution learning

This dissertation investigates the fundamental computational capabilities of quantum algorithms with respect to combinatorial optimization and distribution learning. We establish rigorous quantum advantages over classical algorithms for such problems under both widely accepted cryptographic assumptions and unconditionally. First, we demonstrate a super-polynomial quantum advantage for approximating solutions to combinatorial optimization problems, explicitly constructing advantage-bearing instances of Integer Linear Programming. Our proofs build upon approximation hardness results that instantiate a connection between the representation-independent hardness of learning and approximation hardness, as captured by Occam’s razor within computational learning theory. We show that the instances we construct can be efficiently approximated by quantum algorithms utilizing Shor’s factoring algorithm, yet remain classically intractable unless standard cryptographic assumptions fail. Second, we fill a previously open gap by proving a super-polynomial quantum advantage for learning the density function of probability distributions, complementing prior results established for generative distribution learning. We show that the hardness of density modeling can be established under weaker cryptographic assumptions involving pseudorandom functions. The quantum advantage for density modeling fundamentally arises from Shor’s algorithm for computing discrete logarithms. Moreover, we explicitly articulate known connections between Boolean function learning hardness and distribution learning hardness using established constructions. Third, addressing practical constraints of near-term quantum devices, we establish an unconditional quantum advantage for generative distribution learning using shallow, constant-depth quantum circuits. We find that shallow quantum circuits pose a superior class of hypotheses compared to classical counterparts. This result underscores the potential of near-term quantum hardware by highlighting the unique computational capabilities enabled by quantum entanglement and non-local correlations, offered even by constrained devices. Collectively, these contributions deepen our understanding of quantum computational advantages for combinatorial optimization and distribution learning, clarifying their foundations and pointing toward promising avenues for future exploration.