Quantum Advantage via Solving Multivariate Quadratics

Pierre Briaud, Riddhi Ghosal, Aayush Jain +2

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…