Classical complexity of random degree-$d$ ($d \ge 3$) polynomial systems over $\mathbb{F}_2$ with dual Reed-Solomon codeword constraints (the Briaud-Dinur-Ghosal-Jain-Lou-Sahai quantum-advantage instances)

The 2025 construction of Briaud, Dinur, Ghosal, Jain, Lou and Sahai (published at SODA 2026) gives an explicit distribution of underdetermined systems of random degree-$d$ ($d\ge 3$) polynomial equations over $\mathbb{F}_2$, constrained so that solutions must be codewords of a dual Reed-Solomon code, together with an expected-polynomial-time quantum algorithm for solving them; classical hardness of these instances is conjectured on the basis of cryptanalysis but unproven. The open problem is to settle the classical complexity of these average-case instances: prove a superpolynomial average-case lower bound (unconditionally or under a standard, explicitly stated assumption), or exhibit a classical polynomial-time algorithm. Either resolution would deliver the first rigorous verdict on the leading proposal for non-relativized, verifiable quantum advantage via an NP search problem.

Background

Since Shor's polynomial-time quantum algorithm for factoring and discrete logarithms, a central question of quantum computation theory has been to exhibit an average-case NP search problem - a problem where one must find a witness satisfying efficiently checkable constraints, with instances drawn from a specified distribution - that quantum computers solve in polynomial time but classical computers provably cannot. Yamakawa and Zhandry achieved a breakthrough of this kind, but only in a relativized model: their problem is defined relative to a random oracle, an idealized uniformly random function accessible only as a black box, so it does not correspond to any explicit computational task. Removing the oracle ('un-relativizing' the result) requires an explicit family of constraints that simultaneously preserves the correctness of the quantum algorithm and resists classical algorithms - two requirements in tension, since explicit structure is precisely what classical algorithms can exploit.

Briaud, Dinur, Ghosal, Jain, Lou and Sahai proposed such an explicit instantiation using systems of multivariate polynomial equations over $\mathbb{F}_2$, the field with two elements. Their instance distribution combines: (1) $m=n^2$ polynomials $p_1,\dots,p_m$ (more generally any polynomial $m$), each drawn independently and uniformly from the inhomogeneous polynomials of degree $d\ge 3$ (a constant) in $n$ variables, each acting on its own disjoint block $x_i\in\mathbb{F}_2^n$ of the $n^3$ variables; and (2) a dense set of linear constraints $\mathbf{H}x=0$, where $\mathbf{H}$ is the binary expansion of a generator matrix over the extension field $\mathbb{F}_{2^n}$ (the field with $2^n$ elements, an $n$-dimensional vector space over $\mathbb{F}_2$) of a Reed-Solomon code. A Reed-Solomon code is the classical error-correcting code whose codewords are evaluations of low-degree univariate polynomials; the low-rate Reed-Solomon code of rate $1-\alpha$ generated by $\mathbf{H}$ admits efficient list decoding, meaning one can efficiently enumerate all codewords within Hamming distance $1/2+\varepsilon$ of any received word (the parameters satisfy the constraint $1-\sqrt{1-\alpha}>1/2+\varepsilon$), and $\mathbf{H}$ is equivalently a parity-check matrix for its dual code of rank $\alpha m$, to which the solutions are constrained. Constraining solutions to be dual Reed-Solomon codewords is exactly what the quantum algorithm exploits: following Regev's quantum reduction technique (introduced to relate lattice problems to quantum algorithms) and the Yamakawa-Zhandry framework, the algorithm prepares a superposition over candidate block solutions, applies a quantum Fourier transform over the code, and performs list decoding of the Reed-Solomon code generated by $\mathbf{H}$ in superposition. Correctness requires only that each block's polynomial distribution be 2-wise independent (any two evaluations of the polynomial are jointly uniform) and shift-invariant (the distribution of values is unchanged when the input is translated by any fixed vector), conditions satisfied by uniform random degree-$d$ polynomials for every constant $d\ge 2$.

Solving random multivariate polynomial systems is the core hard problem of multivariate cryptography, where the hardness of random quadratic systems (the MQ, or Multivariate Quadratics, problem) underlies several post-quantum signature proposals; the standard classical tools are exhaustive-search variants, polynomial-method algorithms, and Gröbner-basis methods, which transform a polynomial system into a triangular form from which solutions can be read off. The proposed instances differ from cryptographic ones in being massively underdetermined - they have fewer equations than variables by a polynomial factor - so prior cryptanalytic analyses do not directly apply. The authors analyze the classical landscape: the best classical algorithm they identify costs $\widetilde{O}(2^{(1-\alpha)n^2})$, where $\alpha\in(7/8+3\varepsilon/4,1)$ is a constant determining the code's rank and $\widetilde{O}$ suppresses polynomial factors, and they give theoretical and experimental evidence that Gröbner-basis solvers remain exponential. Crucially, the same group's earlier quadratic proposal ($d=2$) was broken by their own subsequent analysis: putting quadratic forms into a normal form lets one fix half the variables of each block so that every equation becomes linear, yielding a polynomial-time attack under a plausible solvability assumption. For $d=3$ they prove this specialization route fails: a random degree-3 polynomial stays degree-3 on every affine subspace of co-dimension at most $n-n^{3/4}$ except with probability $2^{-\Omega(n^2)}$. The paper's central conjecture is therefore that degree 3 is the threshold: the stated distribution is solvable in expected quantum polynomial time but classically hard for constant $d>2$, giving the first concrete, non-oracle instantiation of the Yamakawa-Zhandry quantum advantage. A parallel line of work, Decoded Quantum Interferometry (DQI), applies the same decoding-based quantum framework to approximate optimization problems such as max-LINSAT (the problem of assigning values to variables so as to maximize the number of simultaneously satisfied linear equations) and the optimal polynomial intersection problem, which sharpens the interest in pinning down the exact classical complexity of decoding-constrained algebraic systems.

Problem Statement

An instance is sampled as follows. Fix a constant degree $d\ge 3$, constants $\varepsilon\in(0,1/6)$ and $\alpha$ with $7/8+3\varepsilon/4<\alpha<1$, and parameters $n,m$ (the concrete construction takes $m=n^2$). Draw $p_1,\dots,p_m$ independently, each with independent uniform $\mathbb{F}_2$ coefficients on every monomial of degree at most $d$ in its $n$ variables (including the constant term), acting on disjoint blocks $x_1,\dots,x_m\in\mathbb{F}_2^n$. Let $\mathbf{H}$ be the $\mathbb{F}_2$-expansion of an $\mathbb{F}_{2^n}$-generator matrix of a Reed-Solomon code of rate $1-\alpha$ and length $m$ (equivalently, a parity-check matrix for the dual Reed-Solomon code of rank $\alpha m$), so $\mathbf{H}$ is a binary $((1-\alpha)mn)\times mn$ matrix. Given $\mathbf{H}$ and $p_1,\dots,p_m$, the task is to output $y=(y_1,\dots,y_m)\in(\mathbb{F}_2^n)^m$ such that $\mathbf{H}y=0$ and $p_i(y_i)=0$ for all $i\in[m]$.

This task admits an expected-polynomial-time quantum algorithm, and solutions exist with high probability. The open problem is to settle its classical complexity:

1. Prove that no classical randomized polynomial-time algorithm outputs a valid solution with probability non-negligible in $n$ over the instance distribution - unconditionally, or by reduction from an explicitly stated standard worst-case or average-case assumption; or

2. Exhibit such a classical polynomial-time algorithm.

Rigorous intermediate characterizations of the best classical runtime - provable superpolynomial lower bounds against defined classes of classical algorithms, or classical algorithms with provably subexponential runtime $2^{o(m)}$ improving on the analyzed $\widetilde{O}(2^{(1-\alpha)m})$ barrier - are partial resolutions of the same question.

References

1. Pierre Briaud, Itai Dinur, Riddhi Ghosal, Aayush Jain, Paul Lou, Amit Sahai. Quantum Advantage via Solving Multivariate Polynomials. Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, pp. 1383-1423, 2026. DOI: 10.1137/1.9781611978971.52; preprint arXiv:2509.07276, https://arxiv.org/abs/2509.07276
2. Pierre Briaud, Riddhi Ghosal, Aayush Jain, Paul Lou, Amit Sahai. Quantum Advantage via Solving Multivariate Quadratics. arXiv:2411.14697, 2024. https://arxiv.org/abs/2411.14697
3. Takashi Yamakawa, Mark Zhandry. Verifiable Quantum Advantage without Structure. Journal of the ACM 71(3), 2024. DOI: 10.1145/3658665, https://doi.org/10.1145/3658665
4. Oded Regev. Quantum Computation and Lattice Problems. Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2002, pp. 520-529; SIAM Journal on Computing 33(3):738-760, 2004. DOI: 10.1137/S0097539703440678; preprint arXiv:cs/0304005, 2003, https://arxiv.org/abs/cs/0304005
5. Peter W. Shor. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. arXiv:quant-ph/9508027, 1995 (SIAM Journal on Computing 26(5):1484-1509, 1997). DOI: 10.1137/S0097539795293172, https://arxiv.org/abs/quant-ph/9508027
6. Stephen P. Jordan, Noah Shutty, Mary Wootters, Adam Zalcman, Alexander Schmidhuber, Robbie King, Sergei V. Isakov, Tanuj Khattar, Ryan Babbush. Optimization by Decoded Quantum Interferometry. arXiv:2408.08292, 2024. https://arxiv.org/abs/2408.08292
7. Tanuj Khattar, Noah Shutty, Craig Gidney, Adam Zalcman, Noureldin Yosri, Dmitri Maslov, Ryan Babbush, Stephen P. Jordan. Verifiable Quantum Advantage via Optimized DQI Circuits. arXiv:2510.10967, 2025. https://arxiv.org/abs/2510.10967
8. Kunal Marwaha, Bill Fefferman, Alexandru Gheorghiu, Vojtech Havlicek. On the Complexity of Decoded Quantum Interferometry. arXiv:2509.14443, 2025. https://arxiv.org/abs/2509.14443
9. Maximilian J. Kramer, Carsten Schubert, Jens Eisert. Tight inapproximability of max-LINSAT and implications for decoded quantum interferometry. arXiv:2603.04540, 2026. https://arxiv.org/abs/2603.04540
10. Maximilian J. Kramer, Carsten Schubert, Jens Eisert. Approximability limits for bounded-degree max-LINSAT and implications for decoded quantum interferometry. arXiv:2606.13570, 2026. https://arxiv.org/abs/2606.13570
11. Jan Ljubas, Tim Byrnes. Quantum Decoding Algorithms: Quantum Speedups in Optimization. arXiv:2605.00312, 2026. https://arxiv.org/abs/2605.00312
12. Christophe Piveteau, Joseph M. Renes. Efficient and optimal quantum state discrimination via quantum belief propagation. arXiv:2509.19441, 2025. https://arxiv.org/abs/2509.19441
13. Ryan Babbush, Robbie King, Sergio Boixo, William Huggins, Tanuj Khattar, Guang Hao Low, Jarrod R. McClean, Thomas O'Brien, Nicholas C. Rubin. The Grand Challenge of Quantum Applications. arXiv:2511.09124, 2025. https://arxiv.org/abs/2511.09124
14. Dakshita Khurana, Bhaskar Roberts, Avishay Tal. Certified Randomness without Structure Against Shallow-Query Adversaries. arXiv:2608.24832, 2026. https://arxiv.org/abs/2608.24832