Quantum Advantage via Solving Multivariate Polynomials

Understand

In this work, we propose a new way to (non-interactively, verifiably) demonstrate quantum advantage by solving the average-case $\mathsf{NP}$ search problem of finding a solution to a system of (underdetermined) constant degree multivariate equations over the finite field $\mathbb{F}_2$ drawn from a specified distribution.

• In particular, for any $d \geq 2$, we design a distribution of degree up to $d$ polynomials $\{p_i(x_1,\ldots,x_n)\}_{i\in [m]}$ for $m<n$ over $\mathbb{F}_2$ for which we show that there is a expected polynomial-time quantum algorithm that provably simultaneously solves $\{p_i(x_1,\ldots,x_n)=y_i\}_{i\in [m]}$ for a random vector $(y_1,\ldots,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.