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:2509.07276 · Society for Industrial and Applied Mathematics eBooks

Quantum Advantage via Solving Multivariate Polynomials

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

Published Jan 1, 2026• 10 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1137/1.9781611978971.52

Related papers

Quantum Advantage via Solving Multivariate Quadratics

Pierre Briaud, Riddhi Ghosal, Aayush Jain +2 more

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

arXiv:2411.14697•Nov 22, 2024•1 citation

Verifiable Quantum Advantage without Structure

Takashi Yamakawa, Mark Zhandry

We show the following hold, unconditionally unless otherwise stated, relative to a random oracle: — There are NP search problems solvable by quantum polynomial-time (QPT) machines but not classical probabilistic polynomial-time (PPT) machines. — There exist functions that are one-way, and even collision resistant, against classical adversaries but are easily inverted quantumly. Similar counterexamples exist for digital signatures and CPA-secure public key encryption (the latter requiring the assumption of a classically CPA-secure encryption scheme). Interestingly, the counterexample does not necessarily extend to the case of other cryptographic objects such as PRGs. — There are unconditional publicly verifiable proofs of quantumness with the minimal rounds of interaction: for uniform adversaries, the proofs are non-interactive, whereas for non-uniform adversaries the proofs are two message public coin. — Our results do not appear to contradict the Aaronson-Ambanis conjecture. Assuming this conjecture, there exist publicly verifiable certifiable randomness, again with the minimal rounds of interaction. By replacing the random oracle with a concrete cryptographic hash function such as SHA2, we obtain plausible Minicrypt instantiations of the above results. Previous analogous results all required substantial structure, either in terms of highly structured oracles and/or algebraic assumptions in Cryptomania and beyond.

arXiv:2204.02063•Journal of the ACM•Apr 22, 2024•64 citations

Quantum Advantage in Tolerant Junta Testing

Avishay Tal, Weiqiang Yuan

We establish the first super-polynomial quantum advantage for the tolerant junta testing problem in the adaptive setting. Specifically, we show that within a certain parameter regime, tolerant $k$-junta testing with high precision can be solved using $\mathrm{poly}(k)$ quantum queries, whereas any classical algorithm requires at least $k^{Ω(\log k)}$ queries. The problem of tolerant $k$-junta testing is as follows: given parameters $(k, ε_1, ε_2)$, with $0\le ε_1<ε_2 \le 1/2$, and black-box access to a Boolean function $f$ (defined on $n$ variables), distinguish whether $f$ is $ε_1$-close to some $k$-junta or $ε_2$-far from every $k$-junta. We show the quantum advantage for a range of parameters close to $1/2$, for example, $ε_1 = 1/2-1/k$ and $ε_2 = 1/2-1/(2k^2)$. The (non-adaptive) quantum tester we use was given by a recent work of Bao, Liu, Yao, Ye, and Zhang (SOSA 2026). We slightly adapt their analysis to show that it holds in the above parameter regime. On the other hand, our classical lower bound requires substantial new ideas. Inspired by the lower bound techniques of Chen and Patel (FOCS 2023), we introduce a new hard distribution of ``yes'' instances (i.e., instances with distance at most $ε_1$ to $k$-juntas) that is based on planting an ``approximate-junta'' as follows: we randomly pick $k$ out of $n$ coordinates, and for each fixing of the $k$ coordinates, the $2^{n-k}$ values in the restricted subcube are drawn randomly except for the set of points in an error-correcting code on which we place the same random bit. We show that this distribution is much closer to $k$-juntas than the uniform distribution, but on the other hand, they are indistinguishable with respect to any classical algorithm making $k^{o(\log k)}$ queries.

cs.CCCross-listedarXiv:2606.23194•Leibniz international proceedings in informatics•Jun 23, 2026•1 citation

Verifiable Quantum Advantage without Structure

Takashi Yamakawa, Mark Zhandry

We show the following hold, unconditionally unless otherwise stated, relative to a random oracle with probability 1: •There are NP search problems solvable by BQP machines but not BPP machines.•There exist functions that are one-way, and even collision resistant, against classical adversaries but are easily inverted quantumly. Similar separations hold for digital signatures and CPA-secure public key encryption (the latter requiring the assumption of a classically CPA-secure encryption scheme). Interestingly, the separation does not necessarily extend to the case of other cryptographic objects such as PRGs.•There are unconditional publicly verifiable proofs of quantumness with the minimal rounds of interaction: for uniform adversaries, the proofs are non-interactive, whereas for non-uniform adversaries the proofs are two message public coin.•Our results do not appear to contradict the Aaronson-Ambanis conjecture. Assuming this conjecture, there exist publicly verifiable certifiable randomness, again with the minimal rounds of interaction.By replacing the random oracle with a concrete cryptographic hash function such as SHA2, we obtain plausible Minicrypt instantiations of the above results. Previous analogous results all required substantial structure, either in terms of highly structured oracles and/or algebraic assumptions in Cryptomania and beyond.

Annual Symposium on Foundations of Computer Science•Oct 1, 2022•54 citations

Founding Quantum Cryptography on Quantum Advantage, or, Towards Cryptography from #P Hardness

Dakshita Khurana, Kabir Tomer

Recent oracle separations [Kretschmer, TQC'21, Kretschmer et. al., STOC'23] have raised the tantalizing possibility of building quantum cryptography from sources of hardness that persist even if the polynomial hierarchy collapses. We realize this possibility by building quantum bit commitments and secure computation from unrelativized, well-studied mathematical problems that are conjectured to be hard for $\mathsf{P^{\#P}}$ -- such as approximating the permanents of complex Gaussian matrices, or approximating the output probabilities of random quantum circuits. Indeed, we show that as long as any one of the conjectures underlying sampling-based quantum advantage (e.g., BosonSampling, Random Circuit Sampling, IQP, etc.) is true, quantum cryptography can be based on the extremely mild assumption that $\mathsf{P^{\#P}} \not\subseteq \mathsf{(io)BQP/qpoly}$. We prove that the following hardness assumptions are equivalent. (1) The hardness of approximating the probability assigned to a randomly chosen string in the support of certain efficiently sampleable distributions (upto inverse polynomial multiplicative error).(2) The existence of one-way puzzles, where a quantum sampler outputs a pair of classical strings -- a puzzle and its key -- and where the hardness lies in finding the key corresponding to a random puzzle. These are known to imply quantum bit commitments [Khurana and Tomer, STOC'24]. (3) The existence of state puzzles, or one-way state synthesis, where it is hard to synthesize a secret quantum state given a public classical identifier. These capture the hardness of search problems with quantum inputs (secrets) and classical outputs (challenges). These are the first constructions of quantum cryptographic primitives (one-way puzzles, quantum bit commitments, state puzzles) from concrete, well-founded mathematical assumptions that do not imply the existence of classical cryptography.

arXiv:2409.15248•ACM Symposium on Theory of Computing (STOC)•Jun 15, 2025•20 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•10 citations
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.
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
We show the following hold, unconditionally unless otherwise stated, relative to a random oracle: — There are NP search problems solvable by quantum polynomial-time (QPT) machines but not classical probabilistic polynomial-time (PPT) machines. — There exist functions that are one-way, and even collision resistant, against classical adversaries but are easily inverted quantumly. Similar counterexamples exist for digital signatures and CPA-secure public key encryption (the latter requiring the assumption of a classically CPA-secure encryption scheme). Interestingly, the counterexample does not necessarily extend to the case of other cryptographic objects such as PRGs. — There are unconditional publicly verifiable proofs of quantumness with the minimal rounds of interaction: for uniform adversaries, the proofs are non-interactive, whereas for non-uniform adversaries the proofs are two message public coin. — Our results do not appear to contradict the Aaronson-Ambanis conjecture. Assuming this conjecture, there exist publicly verifiable certifiable randomness, again with the minimal rounds of interaction. By replacing the random oracle with a concrete cryptographic hash function such as SHA2, we obtain plausible Minicrypt instantiations of the above results. Previous analogous results all required substantial structure, either in terms of highly structured oracles and/or algebraic assumptions in Cryptomania and beyond.
We establish the first super-polynomial quantum advantage for the tolerant junta testing problem in the adaptive setting. Specifically, we show that within a certain parameter regime, tolerant kkk-junta testing with high precision can be solved using poly(k)\mathrm{poly}(k)poly(k) quantum queries, whereas any classical algorithm requires at least kΩ(log⁡k)k^{Ω(\log k)}kΩ(logk) queries. The problem of tolerant kkk-junta testing is as follows: given parameters (k,ε1,ε2)(k, ε_1, ε_2)(k,ε1​,ε2​), with 0≤ε1<ε2≤1/20\le ε_1<ε_2 \le 1/20≤ε1​<ε2​≤1/2, and black-box access to a Boolean function fff (defined on nnn variables), distinguish whether fff is ε1ε_1ε1​-close to some kkk-junta or ε2ε_2ε2​-far from every kkk-junta. We show the quantum advantage for a range of parameters close to 1/21/21/2, for example, ε1=1/2−1/kε_1 = 1/2-1/kε1​=1/2−1/k and ε2=1/2−1/(2k2)ε_2 = 1/2-1/(2k^2)ε2​=1/2−1/(2k2). The (non-adaptive) quantum tester we use was given by a recent work of Bao, Liu, Yao, Ye, and Zhang (SOSA 2026). We slightly adapt their analysis to show that it holds in the above parameter regime. On the other hand, our classical lower bound requires substantial new ideas. Inspired by the lower bound techniques of Chen and Patel (FOCS 2023), we introduce a new hard distribution of ``yes'' instances (i.e., instances with distance at most ε1ε_1ε1​ to kkk-juntas) that is based on planting an ``approximate-junta'' as follows: we randomly pick kkk out of nnn coordinates, and for each fixing of the kkk coordinates, the 2n−k2^{n-k}2n−k values in the restricted subcube are drawn randomly except for the set of points in an error-correcting code on which we place the same random bit. We show that this distribution is much closer to kkk-juntas than the uniform distribution, but on the other hand, they are indistinguishable with respect to any classical algorithm making ko(log⁡k)k^{o(\log k)}ko(logk) queries.
We show the following hold, unconditionally unless otherwise stated, relative to a random oracle with probability 1: •There are NP search problems solvable by BQP machines but not BPP machines.•There exist functions that are one-way, and even collision resistant, against classical adversaries but are easily inverted quantumly. Similar separations hold for digital signatures and CPA-secure public key encryption (the latter requiring the assumption of a classically CPA-secure encryption scheme). Interestingly, the separation does not necessarily extend to the case of other cryptographic objects such as PRGs.•There are unconditional publicly verifiable proofs of quantumness with the minimal rounds of interaction: for uniform adversaries, the proofs are non-interactive, whereas for non-uniform adversaries the proofs are two message public coin.•Our results do not appear to contradict the Aaronson-Ambanis conjecture. Assuming this conjecture, there exist publicly verifiable certifiable randomness, again with the minimal rounds of interaction.By replacing the random oracle with a concrete cryptographic hash function such as SHA2, we obtain plausible Minicrypt instantiations of the above results. Previous analogous results all required substantial structure, either in terms of highly structured oracles and/or algebraic assumptions in Cryptomania and beyond.
Recent oracle separations [Kretschmer, TQC'21, Kretschmer et. al., STOC'23] have raised the tantalizing possibility of building quantum cryptography from sources of hardness that persist even if the polynomial hierarchy collapses. We realize this possibility by building quantum bit commitments and secure computation from unrelativized, well-studied mathematical problems that are conjectured to be hard for P#P\mathsf{P^{\#P}}P#P -- such as approximating the permanents of complex Gaussian matrices, or approximating the output probabilities of random quantum circuits. Indeed, we show that as long as any one of the conjectures underlying sampling-based quantum advantage (e.g., BosonSampling, Random Circuit Sampling, IQP, etc.) is true, quantum cryptography can be based on the extremely mild assumption that P#P⊈(io)BQP/qpoly\mathsf{P^{\#P}} \not\subseteq \mathsf{(io)BQP/qpoly}P#P⊆(io)BQP/qpoly. We prove that the following hardness assumptions are equivalent. (1) The hardness of approximating the probability assigned to a randomly chosen string in the support of certain efficiently sampleable distributions (upto inverse polynomial multiplicative error).(2) The existence of one-way puzzles, where a quantum sampler outputs a pair of classical strings -- a puzzle and its key -- and where the hardness lies in finding the key corresponding to a random puzzle. These are known to imply quantum bit commitments [Khurana and Tomer, STOC'24]. (3) The existence of state puzzles, or one-way state synthesis, where it is hard to synthesize a secret quantum state given a public classical identifier. These capture the hardness of search problems with quantum inputs (secrets) and classical outputs (challenges). These are the first constructions of quantum cryptographic primitives (one-way puzzles, quantum bit commitments, state puzzles) from concrete, well-founded mathematical assumptions that do not imply the existence of classical cryptography.
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.