Quantum Advantage via Solving Multivariate Polynomials

Pierre Briaud, Itai Dinur, Riddhi Ghosal, Aayush Jain, Paul Lou, Amit Sahai · 2025

Read Quantum Advantage via Solving Multivariate Polynomials by Pierre Briaud, Itai Dinur, Riddhi Ghosal, Aayush Jain, Paul Lou, Amit Sahai (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-07276.txt.

Introduction

Pierre Briaud and 5 co-authors propose a new way in 2025 to demonstrate quantum advantage, the point where a quantum computer beats classical machines on a useful test. Their test is solving systems of multivariate polynomial equations, sets of equations in many unknowns, over the field with two elements. The systems are drawn at random from a set distribution, with fewer equations than unknowns.

A quantum algorithm based on a 2022 breakthrough framework is shown to solve such systems in expected polynomial time. Classical hardness is not proven but conjectured, after a review of known classical attacks, for equations of degree above two. If the conjecture holds, degree-three equations suffice to instantiate a random oracle and gain a strong form of quantum advantage. A verifiable, non-interactive test would give the field a clean public benchmark.

Catalog record

CREATORPierre Briaud, Itai Dinur, Riddhi Ghosal, Aayush Jain, Paul Lou, Amit Sahai
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE153 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-07276

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Quantum Advantage via Solving Multivariate Polynomials Pierre Briaud, Itai Dinur, Riddhi Ghosal, Aayush Jain, Paul Lou, Amit Sahai 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 𝔽 2 \mathbb{F}_{2} drawn from a specified distribution. In particular, for any d ≥ 2 d\geq 2 , we design a distribution of degree up to d d polynomials { p i ​ ( x 1 , … , x n ) } i ∈ [ m ] \{p_{i}(x_{1},\ldots,x_{n})\}_{i\in[m]} for m < n m<n over 𝔽 2 \mathbb{F}_{2} for which we show that there is a expected polynomial-time quantum algorithm that provably simultaneously solves { p i ( x 1 , … , x n ) = y i } i ∈ [ m ] \{p_{i}(x_{1},\ldots,x_{n})=y_{i}\}_{i\in[m]} for a random vector ( y 1 , … , y m ) (y_{1},\ldots,y_{m}) . On the other hand, while solutions exist with high probability, we conjecture that for constant d > 2 d>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 𝔽 2 \mathbb{F}_{2} multivariate polynomials—those that satisfy 2 2 -wise independence and shift-invariance. This family of distributions includes the distribution of uniform random degree at most d d polynomials for any constant d ≥ 2 d\geq 2 . Our analysis opens up potentially new directions for quantum cryptanalysis of other multivariate systems. 1 Introduction Since Shor’s seminal result [ Sho94 ] over three decades ago showing polynomial-time quantum algorithms for factoring and computing discrete logarithms, researchers have been on the hunt for other average-case search problems in \mathsf{NP} that are efficiently solvable by quantum computers but are believed to be hard classically (“quantum supremacy” [ Pre12 ] ). Outside the context of \mathsf{NP} -search problems, quantum advantage has been identified in several other settings [ CHSH69 , BCM+18 , BKVV20 , KMCVY22 , KLVY23 , JSW+24 ] . However, for \mathsf{NP} -search problems, examples have remained fairly elusive: solving Pell’s equation [ Hal07 ] and matrix group membership [ BBS09 ] have efficient quantum algorithms, with both relying on period finding as a crucial tool. Recently, a breakthrough result of Yamakawa and Zhandry [ YZ22 ] obtained the first polynomial-time quantum algorithm for an unstructured relativized \mathsf{NP} search problem in the random oracle model that is hard classically, using a fundamentally different approach. Subsequently, the work of Jordan et al. [ JSW+24 ] used this approach to obtain a quantum algorithm for a combinatorial optimization problem that has an exponential speed-up over known exponential time classical algorithms for that problem, demonstrating a heuristic advantage. In our work, we will crucially build upon this algorithmic framework, albeit in a very different setting. We study (conjectured) classically hard average-case NP search problems in the area of solving systems of multivariate polynomial equations. Such problems have been studied for decades in the field of multivariate cryptography, where the equations are often quadratic [ OSS84 , ON86 , MI88 , Pat95 , Pat96 , Pat97 , KPG99 , KS99 , GC00 , DS05a , DS05b , CCD+08 , BFP13 , VST17 , CSTV17 , Beu22 ] and sometimes cubic [ DPcW14 , BCE+18 , MRP21a , MRP21b ] . Multivariate cryptography has been widely accepted by the cryptographic community as a post-quantum form of cryptography, positing that even quantum algorithms cannot efficiently solve the underlying equations. This belief, however, can be more accurately attributed to the general lack of suitable quantum algorithmic techniques. Indeed, our work provides the first evidence challenging this general belief that classically hard multivariate systems are also quantumly hard, by demonstrating quantum advantage for a family of random multivariate equations with degree at least 3. In this work, we give an efficient polynomial-time quantum algorithm that provably solves certain families of multivariate polynomial systems, which we will shortly describe. The solutions to these equations generally do not have any nice periodic structure to exploit, nor do we discover any such periodic structure to aid our quantum algorithm. As such, our problem stands apart from previous non-oracle-based quantum advantage results for average-case \mathsf{NP} search problems. We conjecture that this problem is hard to solve using classical methods by analyzing standard solvers for multivariate equations and identifying several features of the equations that could be leveraged for cryptanalysis. Note that, due to the differences between our equations and those typically considered in multivariate cryptography, we do not expect a direct impact of our work in this particular area. However, our work still offers a fresh perspective on the quantum solving of structured multivariate equations, which may still be of cryptanalytic interest. Indeed, multivariate systems arise in various cryptanalytic contexts, such as solving the Learning With Errors (LWE) problem via the Arora-Ge approach [ AG11 ] , as well as in cryptanalysis attempts on the AES algorithm [ CP02 ] , among many others. It remains possible that our techniques could prove useful in one of these settings. The Multivariate System. We now describe the simplest concrete multivariate system, among several possible candidates, for which we have an efficient quantum algorithm and for which we conjecture classical hardness. Since the area of multivariate cryptography has typically focused on the finite field of two elements \mathsf{GF}(2)=\mathbb{F}_{2} or low-degree field extensions, this setting will be the focus of this paper. Our multivariate polynomial system over \mathbb{F}_{2} consists of two sets of constraints over n^{3} variables which we denote as \overline{\mathbf{x}}=(x_{1,1},\ldots,x_{n^{2},n}) . We further group these variables into \overline{\mathbf{x}}=(\mathbf{x}_{1},\ldots,\mathbf{x}_{n^{2}})\in\mathbb{F}_{2}^{n^{3}} , where each \mathbf{x}_{i}\in\mathbb{F}_{2}^{n} , where \mathbf{x}_{i}=(x_{i,1},x_{i,2}\dots,x_{i,n}) . 1. The first set of constraints that we impose are n^{2} -many degree three polynomials \{p_{i}\}_{i\in[n^{2}]} . Each polynomial p_{i} is uniformly randomly sampled from the set of inhomogeneous degree three polynomials over the variables in \mathbf{x}_{i} , that is, the n variables \{x_{i,j}\}_{j\in[n]} . 2. We then impose a set of linear constraints that are described by the dual of a Reed-Solomon 1 1 1 We note that any linear code over \mathbb{F}_{2^{n}} that can produce codewords of length n^{2} and allowing for list decoding from distance \frac{1}{2}+\epsilon for any (small) value of \epsilon would suffice for us. We use Reed-Solomon codes just for concreteness. code over an extension field \mathbb{F}_{2^{n}} with a small constant rate (1-\alpha) , where \alpha\in(\frac{7}{8},1) . That is, consider the generating matrix \mathbf{H}\in\mathbb{F}_{2^{n}}^{(1-\alpha)n^{2}\times n^{2}} of this Reed-Solomon code over the extension field \mathbb{F}_{2^{n}} . This generating matrix over \mathbb{F}_{2^{n}} can be converted to a generating matrix \overline{\mathbf{H}}\in\mathbb{F}_{2}^{(1-\alpha)n^{3}\times n^{3}} over the prime field \mathbb{F}_{2} because every \mathbb{F}_{2^{n}} -linear map can be equivalently expressed as a \mathbb{F}_{2} -linear map. Then we impose the linear constraint that \overline{\mathbf{H}}\cdot\overline{\mathbf{x}}=\mathbf{0} ,

Read the complete text