Complexity 5

Abstract: BosonSampling and Random Circuit Sampling are important both as a theoretical tool for separating quantum and classical computation, and as an experimental means of demonstrating quantum speedups. Prior works have shown that average-case hardness of sampling follows from certain unproven conjectures about the hardness of computing output probabilities, such as the Permanent-of-Gaussians Conjecture (PGC), which states that $e^{-n\log{n}-n-O(\log n)}$ additive-error estimates to the output probability of most random BosonSampling experiments are $\#P$-hard. Prior works have only shown weaker average-case hardness results that do not imply sampling hardness. Proving these conjectures has become a central question in quantum complexity. In this work, we show that $e^{-n\log n-n-O(n^\delta)}$ additive-error estimates to output probabilities of most random BosonSampling experiments are $\#P$-hard for any $\delta>0$, exponentially improving on prior work. In the process, we circumvent all known barrier results for proving PGC. The remaining hurdle to prove PGC is now “merely” to show that the $O(n^\delta)$ in the exponent can be improved to $O(\log n).$ We also obtain an analogous result for Random Circuit Sampling. We then show, for the first time, a hardness of average-case classical sampling result for BosonSampling, under an anticoncentration conjecture. Specifically, we prove the impossibility of multiplicative-error sampling from random BosonSampling experiments with probability $1-2^{-\tilde{\mathstrut O}(N^{1/3})}$ for input size $N$, unless the Polynomial Hierarchy collapses. This exponentially improves upon the state-of-the-art. To do this, we introduce new proof techniques which tolerate exponential loss in the worst-to-average-case reduction. This opens the possibility to show the hardness of average-case sampling without ever proving PGC.

Abstract: We provide a framework for average-case quantum complexity by showing that glassiness obstructs a natural family of quantum algorithms. Glassiness --- a phenomenon in physics characterized by a disordered, slow-mixing phase --- is known to imply hardness for stable classical algorithms; for example, constant-time Langevin dynamics or message-passing fail for random $k$-SAT and max-cut problems in a glassy parameter regime. We present comparable results in the quantum setting with the following contributions. \begin{itemize}[rightmargin=7em] \item \emph{Quantum optimal transport view of glassiness.} We show that the standard notion of quantum glassiness in physics implies that the Gibbs state is decomposed into clusters extensively separated in quantum Wasserstein distance. We prove this implies lower bounds on the quantum Wasserstein complexity of channels from non-glassy to glassy states. \item \emph{Structural argument for hardness.} We define \emph{stable quantum algorithms} in terms of Lipschitz temperature dependence. We prove that constant-time local Lindbladian evolution and shallow variational algorithms are stable and hence fail to capture the clustered geometry of the Gibbs state, yielding a geometrically interpretable algorithmic obstruction. Contrary to prior Lindbladian runtime lower bounds that only apply to evolution from worst-case initial states, our results hold even when starting from the maximally mixed state. \end{itemize} At a technical level, our techniques (based on channel complexity) differ significantly from classical probabilistic approaches due to the sign problem in the absence of a known eigenbasis. This allows our average-case hardness results to apply to non-commuting, non-stoquastic quantum Hamiltonians. As an example, we show the average-case hardness of random 3-local Hamiltonians: the ensemble of all 3-local Pauli strings with independent Gaussian coefficients. To obtain this result, we compute the full replica symmetry breaking solution of the general $p$-local Pauli Hamiltonian ensemble via the replica trick, a non-rigorous but widely used method in statistical physics. The system's phase diagram is richer than its classical (Ising $p$-spin) and fermionic (SYK) analogues, which either always or never have a glassy phase; instead, the Pauli ensemble has a glassy phase only below some constant value of $p$, confirming the phase diagram predicted by prior finite-size numerical analyses.