Quantum Advantage via Solving Multivariate Polynomials

Pierre Briaud, Itai Dinur, Riddhi Ghosal +3

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 t…