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:2608.23929

Quantum Algorithms and Hardness for Point-Count Approximation over Finite Fields

Yota Maeda, Hiroshi Yano

quant-phcs.CCmath.AGmath.NTSubmitted Aug 25, 2026• Announced Aug 26, 2026• 0 citations
arXivHTMLPDF

Abstract

We study the approximation of the number of solutions of Laurent polynomials over finite fields. For a Laurent polynomial \[f(x)=\sum_{j=1}^{s}a_jx^{u_j}\in \mathbb{F}_q[x_1^{\pm1},\ldots,x_n^{\pm1}], \] let $U$ be its augmented support matrix whose columns are $(1,u_j)$ with rank $ρ$ and $N(f) := \# \{x\in (\mathbb{F}_q^\times)^n \mid f(x)=0\}$ be its torus point count. Our first main result is a quantum algorithm that outputs $\widehat{N}(f)$ satisfying \[ |\widehat{N}(f) - N(f)| \le \varepsilon q^{n+s/2-ρ} \] with success probability $1-δ$. Provided that $ρ$ and $\|U\|_\infty$ are bounded, the algorithm runs in both classical bit and quantum gate complexity $\mathrm{poly}(n, s, \log q, 1/\varepsilon, \log(1/δ))$. It provides finer resolution than relative-error approximations in general settings. To the best of our knowledge, in the explicit finite-field input model considered here, no previous algorithm achieves this additive accuracy with running time polynomial in $\log q$. Van Dam (arXiv:quant-ph/0405081) conjectured the existence of such an algorithm under the assumption of an oracle reflecting the algebraic properties of the polynomial. In contrast, by exploiting a point-counting formula derived from character sums over finite fields, we develop an alternative approach that efficiently approximates the number of points without assuming the existence of such an oracle. As a second main result, we prove that the same approximation problem becomes $\#$P-hard under randomized polynomial-time Turing reductions when the support matrix $U$ varies freely as part of the input. Thus, taken together, our results clarify how the effectiveness of the quantum approach depends on the tradeoff between the accuracy scale and the support parameters of the input polynomial.

Comments
31 pages

Related papers

BQP, Meet NP: Search-To-Decision Reductions and Approximate Counting

Sevag Gharibian, Jonas Kamminga

What is the power of polynomial-time quantum computation with access to an NP oracle? In this work, we focus on two fundamental tasks from the study of Boolean satisfiability (SAT) problems: search-to-decision reductions, and approximate counting. We first show that, in strong contrast to the classical setting where a poly-time Turing machine requires $Θ(n)$ queries to an NP oracle to compute a witness to a given SAT formula, quantumly $Θ(\log n)$ queries suffice. We then show this is tight in the black-box model - any quantum algorithm with "NP-like" query access to a formula requires $Ω(\log n)$ queries to extract a solution with constant probability. Moving to approximate counting of SAT solutions, by exploiting a quantum link between search-to-decision reductions and approximate counting, we show that existing classical approximate counting algorithms are likely optimal. First, we give a lower bound in the "NP-like" black-box query setting: Approximate counting requires $Ω(\log n)$ queries, even on a quantum computer. We then give a "white-box" lower bound (i.e. where the input formula is not hidden in the oracle) - if there exists a randomized poly-time classical or quantum algorithm for approximate counting making $o(log n)$ NP queries, then $\text{BPP}^{\text{NP}[o(n)]}$ contains a $\text{P}^{\text{NP}}$-complete problem if the algorithm is classical and $\text{FBQP}^{\text{NP}[o(n)]}$ contains an $\text{FP}^{\text{NP}}$-complete problem if the algorithm is quantum.

arXiv:2401.03943•Leibniz international proceedings in informatics•Jan 1, 2024•3 citations

Quantum Lower Bound for Approximate Counting Via Laurent Polynomials

Scott Aaronson, Robin Kothari, Kretschmer, William +1 more

We study quantum algorithms that are given access to trusted and untrusted quantum witnesses. We establish strong limitations of such algorithms, via new techniques based on Laurent polynomials (i.e., polynomials with positive and negative integer exponents). Specifically, we resolve the complexity of approximate counting, the problem of multiplicatively estimating the size of a nonempty set $S \subseteq [N]$, in two natural generalizations of quantum query complexity. Our first result holds in the standard Quantum Merlin--Arthur ($\mathsf{QMA}$) setting, in which a quantum algorithm receives an untrusted quantum witness. We show that, if the algorithm makes $T$ quantum queries to $S$, and also receives an (untrusted) $m$-qubit quantum witness, then either $m = Ω(|S|)$ or $T=Ω\bigl(\sqrt{N/\left| S\right| } \bigr)$. This is optimal, matching the straightforward protocols where the witness is either empty, or specifies all the elements of $S$. As a corollary, this resolves the open problem of giving an oracle separation between $\mathsf{SBP}$, the complexity class that captures approximate counting, and $\mathsf{QMA}$. In our second result, we ask what if, in addition to a membership oracle for $S$, a quantum algorithm is also given "QSamples" -- i.e., copies of the state $\left| S\right\rangle = \frac{1}{\sqrt{\left| S\right| }} \sum_{i\in S}|i\rangle$ -- or even access to a unitary transformation that enables QSampling? We show that, even then, the algorithm needs either $Θ\bigl(\sqrt{N/\left| S\right| }\bigr)$ queries or else $Θ\bigl(\min \bigl\{\left| S\right| ^{1/3}, \sqrt{N/\left| S\right| }\bigr\}\bigr)$ QSamples or accesses to the unitary. Our lower bounds in both settings make essential use of Laurent polynomials, but in different ways.

arXiv:1808.02420•Leibniz international proceedings in informatics•Aug 7, 2018•29 citations

Evaluating QAOA expectation values can be as hard as counting optimal solutions

Stuart Hadfield

Evaluating expectation values is a critical task for variational quantum eigensolvers, parameterized quantum circuits, and many other quantum algorithms. We consider the well-studied case of the Quantum Approximate Optimization Algorithm (QAOA) for the MaxCut problem. Recent work of Wang et al. [arXiv:2511.20212] showed this task to be NP-hard in general for any QAOA depth $p\geq 2$, complementing past results showing efficiently computable formulas for $p=1$ with arbitrary problem graphs. We sharpen this dichotomy showing that for $p\geq 2$ exact or exponentially precise cost expectation value evaluation is #P-hard under deterministic polynomial-time Turing reductions. Hardness at $p\geq 2$ is shown to remain even for evaluating single pairwise correlators $\langle Z\otimes Z\rangle $, as well as for highly restricted sets of algorithm parameters. Our proof refines the NP-hardness construction of Wang et al. that recovers the maximum cut value from the largest exponent of a QAOA Laurent polynomial, utilizing a distinct and simpler construction that extracts a value proportional to the total number of maximum cuts, in addition to the optimal cut value. Thus we show that the QAOA expectation value hardness transition from $p=1$ to $p=2$ is not only from tractability to optimization hardness, but to that of counting optimal solutions. As an application we show our results imply analogous hardness results for computing gradients and Hessians of QAOA circuits.

quant-pharXiv:2608.11385•Aug 13, 2026•3 citations

The Computational Complexity of Quantum Determinants

Hung, Shih-Han, En-Jui Kuo

In this work, we study the computational complexity of quantum determinants, a $q$-deformation of matrix permanents: Given a complex number $q$ on the unit circle in the complex plane and an $n\times n$ matrix $X$, the $q$-permanent of $X$ is defined as $$\mathrm{Per}_q(X) = \sum_{σ\in S_n} q^{\ell(σ)}X_{1,σ(1)}\ldots X_{n,σ(n)},$$ where $\ell(σ)$ is the inversion number of permutation $σ$ in the symmetric group $S_n$ on $n$ elements. The function family generalizes determinant and permanent, which correspond to the cases $q=-1$ and $q=1$ respectively. For worst-case hardness, by Liouville's approximation theorem and facts from algebraic number theory, we show that for primitive $m$-th root of unity $q$ for odd prime power $m=p^k$, exactly computing $q$-permanent is $\mathsf{Mod}_p\mathsf{P}$-hard. This implies that an efficient algorithm for computing $q$-permanent results in a collapse of the polynomial hierarchy. Next, we show that computing $q$-permanent can be achieved using an oracle that approximates to within a polynomial multiplicative error and a membership oracle for a finite set of algebraic integers. From this, an efficient approximation algorithm would also imply a collapse of the polynomial hierarchy. By random self-reducibility, computing $q$-permanent remains to be hard for a wide range of distributions satisfying a property called the strong autocorrelation property. Specifically, this is proved via a reduction from $1$-permanent to $q$-permanent for $O(1/n^2)$ points $z$ on the unit circle. Since the family of permanent functions shares common algebraic structure, various techniques developed for the hardness of permanent can be generalized to $q$-permanents.

arXiv:2302.08083•Feb 16, 2023•4 citations

How hard is it to approximate the Jones polynomial?

Greg Kuperberg

Freedman, Kitaev, and Wang [arXiv:quant-ph/0001071], and later Aharonov, Jones, and Landau [arXiv:quant-ph/0511096], established a quantum algorithm to "additively" approximate the Jones polynomial V(L,t) at any principal root of unity t. The strength of this additive approximation depends exponentially on the bridge number of the link presentation. Freedman, Larsen, and Wang [arXiv:math/0103200] established that the approximation is universal for quantum computation at a non-lattice, principal root of unity; and Aharonov and Arad [arXiv:quant-ph/0605181] established a uniform version of this result. In this article, we show that any value-dependent approximation of the Jones polynomial at these non-lattice roots of unity is #P-hard. If given the power to decide whether |V(L,t)| > a or |V(L,t)| < b for fixed constants a > b > 0, there is a polynomial-time algorithm to exactly count the solutions to arbitrary combinatorial equations. In our argument, the result follows fairly directly from the universality result and Aaronson's theorem that PostBQP = PP [arXiv:quant-ph/0412187].

arXiv:0908.0512•Aug 4, 2009•91 citations

Improved Quantum Lower and Upper Bounds for Matrix Scaling

Sander Gribling, Harold A. Nieuwboer

Matrix scaling is a simple to state, yet widely applicable linear-algebraic problem: the goal is to scale the rows and columns of a given non-negative matrix such that the rescaled matrix has prescribed row and column sums. Motivated by recent results on first-order quantum algorithms for matrix scaling, we investigate the possibilities for quantum speedups for classical second-order algorithms, which comprise the state-of-the-art in the classical setting. We first show that there can be essentially no quantum speedup in terms of the input size in the high-precision regime: any quantum algorithm that solves the matrix scaling problem for $n \times n$ matrices with at most $m$ non-zero entries and with $\ell_2$-error $\varepsilon=\widetildeΘ(1/m)$ must make $\widetildeΩ(m)$ queries to the matrix, even when the success probability is exponentially small in $n$. Additionally, we show that for $\varepsilon\in[1/n,1/2]$, any quantum algorithm capable of producing $\frac{\varepsilon}{100}$-$\ell_1$-approximations of the row-sum vector of a (dense) normalized matrix uses $Ω(n/\varepsilon)$ queries, and that there exists a constant $\varepsilon_0>0$ for which this problem takes $Ω(n^{1.5})$ queries. To complement these results we give improved quantum algorithms in the low-precision regime: with quantum graph sparsification and amplitude estimation, a box-constrained Newton method can be sped up in the large-$\varepsilon$ regime, and outperforms previous quantum algorithms. For entrywise-positive matrices, we find an $\varepsilon$-$\ell_1$-scaling in time $\widetilde O(n^{1.5}/\varepsilon^2)$, whereas the best previously known bounds were $\widetilde O(n^2\mathrm{polylog}(1/\varepsilon))$ (classical) and $\widetilde O(n^{1.5}/\varepsilon^3)$ (quantum).

arXiv:2109.15282•Leibniz international proceedings in informatics•Sep 30, 2021•7 citations
We study the approximation of the number of solutions of Laurent polynomials over finite fields. For a Laurent polynomial [f(x)=\sum_{j=1}^{s}a_jx^{u_j}\in \mathbb{F}_q[x_1^{\pm1},\ldots,x_n^{\pm1}], ] let UUU be its augmented support matrix whose columns are (1,uj)(1,u_j)(1,uj​) with rank ρρρ and N(f):=#{x∈(Fq×)n∣f(x)=0}N(f) := \# \{x\in (\mathbb{F}_q^\times)^n \mid f(x)=0\}N(f):=#{x∈(Fq×​)n∣f(x)=0} be its torus point count. Our first main result is a quantum algorithm that outputs N^(f)\widehat{N}(f)N(f) satisfying [ |\widehat{N}(f) - N(f)| \le \varepsilon q^{n+s/2-ρ} ] with success probability 1−δ1-δ1−δ. Provided that ρρρ and ∥U∥∞\|U\|_\infty∥U∥∞​ are bounded, the algorithm runs in both classical bit and quantum gate complexity poly(n,s,log⁡q,1/ε,log⁡(1/δ))\mathrm{poly}(n, s, \log q, 1/\varepsilon, \log(1/δ))poly(n,s,logq,1/ε,log(1/δ)). It provides finer resolution than relative-error approximations in general settings. To the best of our knowledge, in the explicit finite-field input model considered here, no previous algorithm achieves this additive accuracy with running time polynomial in log⁡q\log qlogq. Van Dam (arXiv:quant-ph/0405081) conjectured the existence of such an algorithm under the assumption of an oracle reflecting the algebraic properties of the polynomial. In contrast, by exploiting a point-counting formula derived from character sums over finite fields, we develop an alternative approach that efficiently approximates the number of points without assuming the existence of such an oracle. As a second main result, we prove that the same approximation problem becomes #\##P-hard under randomized polynomial-time Turing reductions when the support matrix UUU varies freely as part of the input. Thus, taken together, our results clarify how the effectiveness of the quantum approach depends on the tradeoff between the accuracy scale and the support parameters of the input polynomial.
What is the power of polynomial-time quantum computation with access to an NP oracle? In this work, we focus on two fundamental tasks from the study of Boolean satisfiability (SAT) problems: search-to-decision reductions, and approximate counting. We first show that, in strong contrast to the classical setting where a poly-time Turing machine requires Θ(n)Θ(n)Θ(n) queries to an NP oracle to compute a witness to a given SAT formula, quantumly Θ(log⁡n)Θ(\log n)Θ(logn) queries suffice. We then show this is tight in the black-box model - any quantum algorithm with "NP-like" query access to a formula requires Ω(log⁡n)Ω(\log n)Ω(logn) queries to extract a solution with constant probability. Moving to approximate counting of SAT solutions, by exploiting a quantum link between search-to-decision reductions and approximate counting, we show that existing classical approximate counting algorithms are likely optimal. First, we give a lower bound in the "NP-like" black-box query setting: Approximate counting requires Ω(log⁡n)Ω(\log n)Ω(logn) queries, even on a quantum computer. We then give a "white-box" lower bound (i.e. where the input formula is not hidden in the oracle) - if there exists a randomized poly-time classical or quantum algorithm for approximate counting making o(logn)o(log n)o(logn) NP queries, then BPPNP[o(n)]\text{BPP}^{\text{NP}[o(n)]}BPPNP[o(n)] contains a PNP\text{P}^{\text{NP}}PNP-complete problem if the algorithm is classical and FBQPNP[o(n)]\text{FBQP}^{\text{NP}[o(n)]}FBQPNP[o(n)] contains an FPNP\text{FP}^{\text{NP}}FPNP-complete problem if the algorithm is quantum.
We study quantum algorithms that are given access to trusted and untrusted quantum witnesses. We establish strong limitations of such algorithms, via new techniques based on Laurent polynomials (i.e., polynomials with positive and negative integer exponents). Specifically, we resolve the complexity of approximate counting, the problem of multiplicatively estimating the size of a nonempty set S⊆[N]S \subseteq [N]S⊆[N], in two natural generalizations of quantum query complexity. Our first result holds in the standard Quantum Merlin--Arthur (QMA\mathsf{QMA}QMA) setting, in which a quantum algorithm receives an untrusted quantum witness. We show that, if the algorithm makes TTT quantum queries to SSS, and also receives an (untrusted) mmm-qubit quantum witness, then either m=Ω(∣S∣)m = Ω(|S|)m=Ω(∣S∣) or T=Ω(N/∣S∣)T=Ω\bigl(\sqrt{N/\left| S\right| } \bigr)T=Ω(N/∣S∣​). This is optimal, matching the straightforward protocols where the witness is either empty, or specifies all the elements of SSS. As a corollary, this resolves the open problem of giving an oracle separation between SBP\mathsf{SBP}SBP, the complexity class that captures approximate counting, and QMA\mathsf{QMA}QMA. In our second result, we ask what if, in addition to a membership oracle for SSS, a quantum algorithm is also given "QSamples" -- i.e., copies of the state ∣S⟩=1∣S∣∑i∈S∣i⟩\left| S\right\rangle = \frac{1}{\sqrt{\left| S\right| }} \sum_{i\in S}|i\rangle∣S⟩=∣S∣​1​∑i∈S​∣i⟩ -- or even access to a unitary transformation that enables QSampling? We show that, even then, the algorithm needs either Θ(N/∣S∣)Θ\bigl(\sqrt{N/\left| S\right| }\bigr)Θ(N/∣S∣​) queries or else Θ(min⁡{∣S∣1/3,N/∣S∣})Θ\bigl(\min \bigl\{\left| S\right| ^{1/3}, \sqrt{N/\left| S\right| }\bigr\}\bigr)Θ(min{∣S∣1/3,N/∣S∣​}) QSamples or accesses to the unitary. Our lower bounds in both settings make essential use of Laurent polynomials, but in different ways.
Evaluating expectation values is a critical task for variational quantum eigensolvers, parameterized quantum circuits, and many other quantum algorithms. We consider the well-studied case of the Quantum Approximate Optimization Algorithm (QAOA) for the MaxCut problem. Recent work of Wang et al. [arXiv:2511.20212] showed this task to be NP-hard in general for any QAOA depth p≥2p\geq 2p≥2, complementing past results showing efficiently computable formulas for p=1p=1p=1 with arbitrary problem graphs. We sharpen this dichotomy showing that for p≥2p\geq 2p≥2 exact or exponentially precise cost expectation value evaluation is #P-hard under deterministic polynomial-time Turing reductions. Hardness at p≥2p\geq 2p≥2 is shown to remain even for evaluating single pairwise correlators $\langle Z\otimes Z\rangle $, as well as for highly restricted sets of algorithm parameters. Our proof refines the NP-hardness construction of Wang et al. that recovers the maximum cut value from the largest exponent of a QAOA Laurent polynomial, utilizing a distinct and simpler construction that extracts a value proportional to the total number of maximum cuts, in addition to the optimal cut value. Thus we show that the QAOA expectation value hardness transition from p=1p=1p=1 to p=2p=2p=2 is not only from tractability to optimization hardness, but to that of counting optimal solutions. As an application we show our results imply analogous hardness results for computing gradients and Hessians of QAOA circuits.
In this work, we study the computational complexity of quantum determinants, a qqq-deformation of matrix permanents: Given a complex number qqq on the unit circle in the complex plane and an n×nn\times nn×n matrix XXX, the qqq-permanent of XXX is defined as Perq(X)=∑σ∈Snqℓ(σ)X1,σ(1)…Xn,σ(n),\mathrm{Per}_q(X) = \sum_{σ\in S_n} q^{\ell(σ)}X_{1,σ(1)}\ldots X_{n,σ(n)},Perq​(X)=∑σ∈Sn​​qℓ(σ)X1,σ(1)​…Xn,σ(n)​, where ℓ(σ)\ell(σ)ℓ(σ) is the inversion number of permutation σσσ in the symmetric group SnS_nSn​ on nnn elements. The function family generalizes determinant and permanent, which correspond to the cases q=−1q=-1q=−1 and q=1q=1q=1 respectively. For worst-case hardness, by Liouville's approximation theorem and facts from algebraic number theory, we show that for primitive mmm-th root of unity qqq for odd prime power m=pkm=p^km=pk, exactly computing qqq-permanent is ModpP\mathsf{Mod}_p\mathsf{P}Modp​P-hard. This implies that an efficient algorithm for computing qqq-permanent results in a collapse of the polynomial hierarchy. Next, we show that computing qqq-permanent can be achieved using an oracle that approximates to within a polynomial multiplicative error and a membership oracle for a finite set of algebraic integers. From this, an efficient approximation algorithm would also imply a collapse of the polynomial hierarchy. By random self-reducibility, computing qqq-permanent remains to be hard for a wide range of distributions satisfying a property called the strong autocorrelation property. Specifically, this is proved via a reduction from 111-permanent to qqq-permanent for O(1/n2)O(1/n^2)O(1/n2) points zzz on the unit circle. Since the family of permanent functions shares common algebraic structure, various techniques developed for the hardness of permanent can be generalized to qqq-permanents.
Freedman, Kitaev, and Wang [arXiv:quant-ph/0001071], and later Aharonov, Jones, and Landau [arXiv:quant-ph/0511096], established a quantum algorithm to "additively" approximate the Jones polynomial V(L,t) at any principal root of unity t. The strength of this additive approximation depends exponentially on the bridge number of the link presentation. Freedman, Larsen, and Wang [arXiv:math/0103200] established that the approximation is universal for quantum computation at a non-lattice, principal root of unity; and Aharonov and Arad [arXiv:quant-ph/0605181] established a uniform version of this result. In this article, we show that any value-dependent approximation of the Jones polynomial at these non-lattice roots of unity is #P-hard. If given the power to decide whether |V(L,t)| > a or |V(L,t)| < b for fixed constants a > b > 0, there is a polynomial-time algorithm to exactly count the solutions to arbitrary combinatorial equations. In our argument, the result follows fairly directly from the universality result and Aaronson's theorem that PostBQP = PP [arXiv:quant-ph/0412187].
Matrix scaling is a simple to state, yet widely applicable linear-algebraic problem: the goal is to scale the rows and columns of a given non-negative matrix such that the rescaled matrix has prescribed row and column sums. Motivated by recent results on first-order quantum algorithms for matrix scaling, we investigate the possibilities for quantum speedups for classical second-order algorithms, which comprise the state-of-the-art in the classical setting. We first show that there can be essentially no quantum speedup in terms of the input size in the high-precision regime: any quantum algorithm that solves the matrix scaling problem for n×nn \times nn×n matrices with at most mmm non-zero entries and with ℓ2\ell_2ℓ2​-error ε=Θ~(1/m)\varepsilon=\widetildeΘ(1/m)ε=Θ(1/m) must make Ω~(m)\widetildeΩ(m)Ω(m) queries to the matrix, even when the success probability is exponentially small in nnn. Additionally, we show that for ε∈[1/n,1/2]\varepsilon\in[1/n,1/2]ε∈[1/n,1/2], any quantum algorithm capable of producing ε100\frac{\varepsilon}{100}100ε​-ℓ1\ell_1ℓ1​-approximations of the row-sum vector of a (dense) normalized matrix uses Ω(n/ε)Ω(n/\varepsilon)Ω(n/ε) queries, and that there exists a constant ε0>0\varepsilon_0>0ε0​>0 for which this problem takes Ω(n1.5)Ω(n^{1.5})Ω(n1.5) queries. To complement these results we give improved quantum algorithms in the low-precision regime: with quantum graph sparsification and amplitude estimation, a box-constrained Newton method can be sped up in the large-ε\varepsilonε regime, and outperforms previous quantum algorithms. For entrywise-positive matrices, we find an ε\varepsilonε-ℓ1\ell_1ℓ1​-scaling in time O~(n1.5/ε2)\widetilde O(n^{1.5}/\varepsilon^2)O(n1.5/ε2), whereas the best previously known bounds were O~(n2polylog(1/ε))\widetilde O(n^2\mathrm{polylog}(1/\varepsilon))O(n2polylog(1/ε)) (classical) and O~(n1.5/ε3)\widetilde O(n^{1.5}/\varepsilon^3)O(n1.5/ε3) (quantum).