Quantum Advantage via Solving Multivariate Polynomials

In this work, we propose a new way to (non-interactively, verifiably) demonstrate quantum advantage by solving the average-case NP search problem of finding a solution to a system of (underdetermined) constant degree multivariate equations over the finite field F 2 drawn from a specified distribution. In particular, for any d ≥ 2, we design a distribution of degree up to d polynomials p i (x 1 , . . . , x n ) i∈[m] for m < n over F 2 for which we show that there is a expected polynomial-time quantum algorithm that provably simultaneously solves p i (x 1 , . . . , x n ) = y i i∈[m] for a random vector (y 1 , . . . , y m ). On the other hand, while solutions exist with high probability, we conjecture that for constant d > 2, it is classically hard to find one based on a thorough review of existing classical cryptanalysis. Our work thus posits that degree three functions are enough to instantiate the random oracle to obtain non-relativized quantum advantage.

Our approach begins with the breakthrough Yamakawa-Zhandry (FOCS 2022) quantum algorithmic framework. In our work, we demonstrate that this quantum algorithmic framework extends to the setting of multivariate polynomial systems.

Our key technical contribution is a new analysis on the Fourier spectra of distributions induced by a general family of distributions over F 2 multivariate polynomials-those that satisfy 2-wise independence and shift-invariance. This family of distributions includes the distribution of uniform random degree at most d polynomials for any constant d ≥ 2. Our analysis opens up potentially new directions for quantum cryptanalysis of other multivariate systems.