Quantum Advantage via Solving Multivariate Quadratics
Pierre Briaud, Riddhi Ghosal, Aayush Jain, Paul Lou, Amit Sahai · arXiv (Cornell University) · 2024
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) multivariate quadratic equations over the finite field $\mathbb{F}_2$ drawn from a specified distribution. In particular, we design a distribution of degree-2 polynomials $\{p_i(x_1,\ldots,x_n)\}_{i\in [m]}$ for $m