{"ID":2873661,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.07276","arxiv_id":"2509.07276","title":"Quantum Advantage via Solving Multivariate Polynomials","abstract":"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\u003cn$ 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 \u003e 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 $\\mathbb{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 \\geq 2$. Our analysis opens up potentially new directions for quantum cryptanalysis of other multivariate systems.","short_abstract":"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 distribut...","url_abs":"https://arxiv.org/abs/2509.07276","url_pdf":"https://arxiv.org/pdf/2509.07276v1","authors":"[\"Pierre Briaud\",\"Itai Dinur\",\"Riddhi Ghosal\",\"Aayush Jain\",\"Paul Lou\",\"Amit Sahai\"]","published":"2025-09-08T23:19:20Z","proceeding":"quant-ph","tasks":"[\"quant-ph\",\"cs.CR\"]","methods":"[]","has_code":false}