Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2411.14697

Quantum Advantage via Solving Multivariate Quadratics

Pierre Briaud, Riddhi Ghosal, Aayush Jain, Paul Lou, Amit Sahai

Published Nov 22, 2024• 0 citations
arXivHTMLPDF

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) multivariate quadratic equations over the finite field $\mathbb{F}_2$ drawn from a specified distribution. In particular, we design a distribution of degree-2 polynomials $\{p_i(x_1,\ldots,x_n)\}_{i\in [m]}$ for $m

DOI
10.48550/arxiv.2411.14697

Related papers

Quantum Advantage via Solving Multivariate Polynomials

Pierre Briaud, Itai Dinur, Riddhi Ghosal +3 more

In this work, we propose a new way to (non-interactively, verifiably) demonstrate quantum advantage by solving the average-case 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 \ge 2\), we design a distribution of degree up to \(d\) polynomials \(\{p_i(x_1,\ldots,x_n)\}_{i\in[m]}\) for \(m \lt n\) over \(\mathbb{F}_2\) for which we show that there is an 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 \gt 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.

arXiv:2509.07276•Society for Industrial and Applied Mathematics eBooks•Jan 1, 2026•0 citations

Fast Quantum Algorithm for Solving Multivariate Quadratic Equations

Jean‐Charles Faugère, Kelsey Horan, Delaram Kahrobaei +3 more

In August 2015 the cryptographic world was shaken by a sudden and surprising announcement by the US National Security Agency NSA concerning plans to transition to post-quantum algorithms. Since this announcement post-quantum cryptography has become a topic of primary interest for several standardization bodies. The transition from the currently deployed public-key algorithms to post-quantum algorithms has been found to be challenging in many aspects. In particular the problem of evaluating the quantum-bit security of such post-quantum cryptosystems remains vastly open. Of course this question is of primarily concern in the process of standardizing the post-quantum cryptosystems. In this paper we consider the quantum security of the problem of solving a system of {\it $m$ Boolean multivariate quadratic equations in $n$ variables} (\MQb); a central problem in post-quantum cryptography. When $n=m$, under a natural algebraic assumption, we present a Las-Vegas quantum algorithm solving \MQb{} that requires the evaluation of, on average, $O(2^{0.462n})$ quantum gates. To our knowledge this is the fastest algorithm for solving \MQb{}.

•Aug 27, 2019•2 citations

Fast Quantum Algorithm for Solving Multivariate Quadratic Equations

Jean‐Charles Faugère, Kelsey Horan, Delaram Kahrobaei +3 more

In August 2015 the cryptographic world was shaken by a sudden and surprising announcement by the US National Security Agency NSA concerning plans to transition to post-quantum algorithms. Since this announcement post-quantum cryptography has become a topic of primary interest for several standardization bodies. The transition from the currently deployed public-key algorithms to post-quantum algorithms has been found to be challenging in many aspects. In particular the problem of evaluating the quantum-bit security of such post-quantum cryptosystems remains vastly open. Of course this question is of primarily concern in the process of standardizing the post-quantum cryptosystems. In this paper we consider the quantum security of the problem of solving a system of {\it $m$ Boolean multivariate quadratic equations in $n$ variables} (\MQb); a central problem in post-quantum cryptography. When $n=m$, under a natural algebraic assumption, we present a Las-Vegas quantum algorithm solving \MQb{} that requires the evaluation of, on average, $O(2^{0.462n})$ quantum gates. To our knowledge this is the fastest algorithm for solving \MQb{}.

arXiv:1712.07211•Dec 19, 2017•22 citations

Quantum algorithm for multivariate polynomial interpolation

Jianxin Chen, Andrew M. Childs, Shih-Han Hung

How many quantum queries are required to determine the coefficients of a degree- d polynomial in n variables? We present and analyse quantum algorithms for this multivariate polynomial interpolation problem over the fields F q , R and C . We show that k C and 2 k C queries suffice to achieve probability 1 for C and R , respectively, where k C = ⌈ ( 1 / ( n + 1 ) ) ( n + d d ) ⌉ except for d =2 and four other special cases. For F q , we show that ⌈( d /( n + d ))( n + d d ) ⌉ queries suffice to achieve probability approaching 1 for large field order q . The classical query complexity of this problem is ( n + d d ) , so our result provides a speed-up by a factor of n +1, ( n +1)/2 and ( n + d )/ d for C , R and F q

arXiv:1701.03990•Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences•Jan 1, 2018•8 citations

Solving systems of Boolean multivariate equations with quantum annealing

Sergi Ramos-Calderer, Carlos Bravo-Prieto, Ruge Lin +4 more

Polynomial systems over the binary field have important applications, especially in symmetric and asymmetric cryptanalysis, multivariate-based postquantum cryptography, coding theory, and computer algebra. In this paper, we study the quantum annealing model for solving Boolean systems of multivariate equations of degree 2, usually referred to as the multivariate quadratic problem. We present different methodologies to embed the problem into a Hamiltonian that can be solved by available quantum annealing platforms. In particular, we provide three embedding options, and we highlight their differences in terms of quantum resources. Moreover, we design a machine-agnostic algorithm that adopts an iterative approach to better solve the problem Hamiltonian by repeatedly reducing the search space. Finally, we use D-Wave devices to successfully implement our methodologies on several instances of the multivariate quadratic problem.

arXiv:2111.13224•Physical Review Research•Feb 7, 2022•9 citations

Asymptotically Faster Quantum Algorithms to Solve Multivariate Quadratic Equations

Daniel J. Bernstein, Bo‐Yin Yang

Lecture notes in computer science•Jan 1, 2018•20 citations
In this work, we propose a new way to (non-interactively, verifiably) demonstrate Quantum Advantage by solving the average-case NP\mathsf{NP}NP search problem of finding a solution to a system of (underdetermined) multivariate quadratic equations over the finite field F2\mathbb{F}_2F2​ drawn from a specified distribution. In particular, we design a distribution of degree-2 polynomials {pi(x1,…,xn)}i∈[m]\{p_i(x_1,\ldots,x_n)\}_{i\in [m]}{pi​(x1​,…,xn​)}i∈[m]​ for $m
In this work, we propose a new way to (non-interactively, verifiably) demonstrate quantum advantage by solving the average-case NP search problem of finding a solution to a system of (underdetermined) constant degree multivariate equations over the finite field F2\mathbb{F}_2F2​ drawn from a specified distribution. In particular, for any d≥2d \ge 2d≥2, we design a distribution of degree up to ddd polynomials {pi(x1,…,xn)}i∈[m]\{p_i(x_1,\ldots,x_n)\}_{i\in[m]}{pi​(x1​,…,xn​)}i∈[m]​ for m<nm \lt nm<n over F2\mathbb{F}_2F2​ for which we show that there is an expected polynomial-time quantum algorithm that provably simultaneously solves {pi(x1,…,xn)=yi}i∈[m]\{p_i(x_1,\ldots,x_n) = y_i\}_{i\in[m]}{pi​(x1​,…,xn​)=yi​}i∈[m]​ for a random vector (y1,…,ym)(y_1,\ldots,y_m)(y1​,…,ym​). On the other hand, while solutions exist with high probability, we conjecture that for constant d>2d \gt 2d>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.
In August 2015 the cryptographic world was shaken by a sudden and surprising announcement by the US National Security Agency NSA concerning plans to transition to post-quantum algorithms. Since this announcement post-quantum cryptography has become a topic of primary interest for several standardization bodies. The transition from the currently deployed public-key algorithms to post-quantum algorithms has been found to be challenging in many aspects. In particular the problem of evaluating the quantum-bit security of such post-quantum cryptosystems remains vastly open. Of course this question is of primarily concern in the process of standardizing the post-quantum cryptosystems. In this paper we consider the quantum security of the problem of solving a system of {\it mmm Boolean multivariate quadratic equations in nnn variables} (\MQb); a central problem in post-quantum cryptography. When n=mn=mn=m, under a natural algebraic assumption, we present a Las-Vegas quantum algorithm solving \MQb{} that requires the evaluation of, on average, O(20.462n)O(2^{0.462n})O(20.462n) quantum gates. To our knowledge this is the fastest algorithm for solving \MQb{}.
In August 2015 the cryptographic world was shaken by a sudden and surprising announcement by the US National Security Agency NSA concerning plans to transition to post-quantum algorithms. Since this announcement post-quantum cryptography has become a topic of primary interest for several standardization bodies. The transition from the currently deployed public-key algorithms to post-quantum algorithms has been found to be challenging in many aspects. In particular the problem of evaluating the quantum-bit security of such post-quantum cryptosystems remains vastly open. Of course this question is of primarily concern in the process of standardizing the post-quantum cryptosystems. In this paper we consider the quantum security of the problem of solving a system of {\it mmm Boolean multivariate quadratic equations in nnn variables} (\MQb); a central problem in post-quantum cryptography. When n=mn=mn=m, under a natural algebraic assumption, we present a Las-Vegas quantum algorithm solving \MQb{} that requires the evaluation of, on average, O(20.462n)O(2^{0.462n})O(20.462n) quantum gates. To our knowledge this is the fastest algorithm for solving \MQb{}.
How many quantum queries are required to determine the coefficients of a degree- d polynomial in n variables? We present and analyse quantum algorithms for this multivariate polynomial interpolation problem over the fields F q , R and C . We show that k C and 2 k C queries suffice to achieve probability 1 for C and R , respectively, where k C = ⌈ ( 1 / ( n + 1 ) ) ( n + d d ) ⌉ except for d =2 and four other special cases. For F q , we show that ⌈( d /( n + d ))( n + d d ) ⌉ queries suffice to achieve probability approaching 1 for large field order q . The classical query complexity of this problem is ( n + d d ) , so our result provides a speed-up by a factor of n +1, ( n +1)/2 and ( n + d )/ d for C , R and F q
Polynomial systems over the binary field have important applications, especially in symmetric and asymmetric cryptanalysis, multivariate-based postquantum cryptography, coding theory, and computer algebra. In this paper, we study the quantum annealing model for solving Boolean systems of multivariate equations of degree 2, usually referred to as the multivariate quadratic problem. We present different methodologies to embed the problem into a Hamiltonian that can be solved by available quantum annealing platforms. In particular, we provide three embedding options, and we highlight their differences in terms of quantum resources. Moreover, we design a machine-agnostic algorithm that adopts an iterative approach to better solve the problem Hamiltonian by repeatedly reducing the search space. Finally, we use D-Wave devices to successfully implement our methodologies on several instances of the multivariate quadratic problem.