arXiv:2002.11094

Quantum algorithms for exponential sums and the evaluation of the Riemann zeta function

Sandeep Tyagi

Published Feb 25, 2020• 0 citations

Abstract

We give quantum algorithms for estimating weighted exponential sums $S(f,w,N)= \sum_{k=0}^{N-1} w_k e^{2 πi f(k)}$, with $w_k \ge 0$, $\sum_k w_k =1$, and $N=2^{n}$ exponentially large. Under two explicit oracle assumptions -- efficiently computable prefix sums for the weights, enabling Grover--Rudolph state preparation, and a fixed-point circuit for $f$ -- amplitude estimation yields $S$ to additive error $\varepsilon$ with $O(\varepsilon^{-1}\log(1/γ))$ oracle uses and $\operatorname{polylog}(N)$ gates per use; all bounds are full gate complexities, and the saving over classical sampling is quadratic in $1/\varepsilon$. Applying this to the Riemann--Siegel formula, we prove that $ζ(σ+it)$ in the critical strip can be estimated to accuracy $δ$ with $\widetilde O(t^{(1-σ)/2}\, δ^{-1})$ gates, hence $\widetilde O(t^{1/4}\, δ^{-1})$ on the critical line, where $\widetilde O$ suppresses factors polylogarithmic in $t/δ$. At fixed accuracy this improves on the $t^{1/2}$ Riemann--Siegel cost and on the best rigorous classical algorithm's $t^{4/13+o(1)}$; the quantum algorithm is advantageous precisely when $δ\gg t^{-3/52}$, which covers the accuracy needed to locate and count zeros. We show that a $\operatorname{polylog}(t)$ algorithm does not follow from these techniques -- undoing the normalization costs the $\ell^{1}$ mass $\sum_{k\le N} k^{-σ} = Θ(t^{(1-σ)/2})$ of the main sum -- and that Hiary-type block decompositions cannot improve the quantum query complexity. We also give an estimator for the magnitude of the amplitude sum $\lvert \sum_k a_k \rvert$ of any efficiently preparable state, and review the required amplitude- and phase-estimation subroutines.

DOI: 10.48550/arxiv.2002.11094

Related papers

Optimal algorithmic complexity of inference in quantum kernel methods

Elies Gil-Fuster, Seongwook Shin, Sofiene Jerbi +2 more

quant-pharXiv:2604.15214Apr 17, 20260 citations

Amortized classical baselines for bulk evaluation of the Riemann zeta function, and their omission from a quantum speedup claim

Papanokechi

Aug 6, 20260 citations

Quantum Approximate Counting with Bernoulli Oracles

Chengshen Gao, Yongzhen Xu, Lvzhou Li

quant-pharXiv:2609.07604Sep 8, 20260 citations

Quantum algorithms for weighted constrained sampling and weighted model counting

Fabrizio Riguzzi

arXiv:2407.12816Quantum Machine IntelligenceNov 5, 20242 citations

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

Yota Maeda, Hiroshi Yano

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.

quant-pharXiv:2608.23929Aug 26, 20260 citations

Quantum Weighted Model Counting

Fabrizio Riguzzi

arXiv:1910.13530Oct 22, 20190 citations

arXiv:2002.11094

Quantum algorithms for exponential sums and the evaluation of the Riemann zeta function

Sandeep Tyagi

Published Feb 25, 2020• 0 citations

arXiv HTML PDF

Abstract

We give quantum algorithms for estimating weighted exponential sums

S(f,w,N)= \sum_{k=0}^{N-1} w_k e^{2 πi f(k)}

, with

w_k \ge 0

\sum_k w_k =1

, and

N=2^{n}

exponentially large. Under two explicit oracle assumptions -- efficiently computable prefix sums for the weights, enabling Grover--Rudolph state preparation, and a fixed-point circuit for

f

-- amplitude estimation yields

S

to additive error

\varepsilon

with

O(\varepsilon^{-1}\log(1/γ))

oracle uses and

\operatorname{polylog}(N)

gates per use; all bounds are full gate complexities, and the saving over classical sampling is quadratic in

1/\varepsilon

. Applying this to the Riemann--Siegel formula, we prove that

ζ(σ+it)

in the critical strip can be estimated to accuracy

δ

with

\widetilde O(t^{(1-σ)/2}\, δ^{-1})

gates, hence

\widetilde O(t^{1/4}\, δ^{-1})

on the critical line, where

\widetilde O

suppresses factors polylogarithmic in

t/δ

. At fixed accuracy this improves on the

t^{1/2}

Riemann--Siegel cost and on the best rigorous classical algorithm's

t^{4/13+o(1)}

; the quantum algorithm is advantageous precisely when

δ\gg t^{-3/52}

, which covers the accuracy needed to locate and count zeros. We show that a

\operatorname{polylog}(t)

algorithm does not follow from these techniques -- undoing the normalization costs the

\ell^{1}

mass

\sum_{k\le N} k^{-σ} = Θ(t^{(1-σ)/2})

of the main sum -- and that Hiary-type block decompositions cannot improve the quantum query complexity. We also give an estimator for the magnitude of the amplitude sum

\lvert \sum_k a_k \rvert

of any efficiently preparable state, and review the required amplitude- and phase-estimation subroutines.

DOI: 10.48550/arxiv.2002.11094

Related papers

Optimal algorithmic complexity of inference in quantum kernel methods

Elies Gil-Fuster, Seongwook Shin, Sofiene Jerbi +2 more

Quantum kernel methods are among the leading candidates for achieving quantum advantage in supervised learning. A key bottleneck is the cost of inference: evaluating a trained model on new data requires estimating a weighted sum $\sum_{i=1}^N α_i k(x,x_i)$ of $N$ kernel values to additive precision $\varepsilon$ , where $α$ is the vector of trained coefficients. The standard approach estimates each term independently via sampling, yielding a query complexity of $O(N\lVertα\rVert_2^2/\varepsilon^2)$ . In this work, we identify two independent axes for improvement: (1) How individual kernel values are estimated (sampling versus quantum amplitude estimation), and (2) how the sum is approximated (term-by-term versus via a single observable), and systematically analyze all combinations thereof. The query-optimal combination, encoding the full inference sum as the expectation value of a single observable and applying quantum amplitude estimation, achieves a query complexity of $O(\lVertα\rVert_1/\varepsilon)$ , removing the dependence on $N$ from the query count and yielding a quadratic improvement in both $\lVertα\rVert_1$ and $\varepsilon$ . We prove a matching lower bound of $Ω(\lVertα\rVert_1/\varepsilon)$ , establishing query-optimality of our approach up to logarithmic factors. Beyond query complexity, we also analyze how these improvements translate into gate costs and show that the query-optimal strategy is not always optimal in practice from the perspective of gate complexity. Our results provide both a query-optimal algorithm and a practically optimal choice of strategy depending on hardware capabilities, along with a complete landscape of intermediate methods to guide practitioners. All algorithms require only amplitude estimation as a subroutine and are thus natural candidates for early-fault-tolerant implementations.Quantum kernel methods are among the leading candidates for achieving quantum advantage in supervised learning. A key bottleneck is the cost of inference: evaluating a trained model on new data requires estimating a weighted sum $\sum_{i=1}^N α_i k(x,x_i)$ of $N$ kernel values to additive precision $\varepsilon$, where $α$ is the vector of trained coefficients. The standard approach estimates each term independently via sampling, yielding a query complexity of $O(N\lVertα\rVert_2^2/\varepsilon^2)$. In this work, we identify two independent axes for improvement: (1) How individual kernel values are estimated (sampling versus quantum amplitude estimation), and (2) how the sum is approximated (term-by-term versus via a single observable), and systematically analyze all combinations thereof. The query-optimal combination, encoding the full inference sum as the expectation value of a single observable and applying quantum amplitude estimation, achieves a query complexity of $O(\lVertα\rVert_1/\varepsilon)$, removing the dependence on $N$ from the query count and yielding a quadratic improvement in both $\lVertα\rVert_1$ and $\varepsilon$. We prove a matching lower bound of $Ω(\lVertα\rVert_1/\varepsilon)$, establishing query-optimality of our approach up to logarithmic factors. Beyond query complexity, we also analyze how these improvements translate into gate costs and show that the query-optimal strategy is not always optimal in practice from the perspective of gate complexity. Our results provide both a query-optimal algorithm and a practically optimal choice of strategy depending on hardware capabilities, along with a complete landscape of intermediate methods to guide practitioners. All algorithms require only amplitude estimation as a subroutine and are thus natural candidates for early-fault-tolerant implementations.

quant-pharXiv:2604.15214Apr 17, 20260 citations

Amortized classical baselines for bulk evaluation of the Riemann zeta function, and their omission from a quantum speedup claim

Papanokechi

Wei et al. (Nat. Commun., 2026; preprint arXiv:2511.11199v1) report a quantum algorithm for ζ(½+it) and compare its cost against direct Riemann–Siegel summation. This note examines that comparison. The speedup claim is correct against the baselines the paper names, and correct for a single isolated evaluation. It is, however, applied to locating and verifying zeros, which is a bulk task, and the classical state of the art for bulk evaluation is amortized. Odlyzko–Schönhage (1988) amortizes to T^ε per point, for every ε > 0, over blocks of length T^(1/2) after one precomputation, where the quantum method offers no amortization mechanism at all and pays its per-point cost every time; Hiary's amortized method (Math. Comp., 2011) reaches the same T^(1/4) exponent classically fifteen years earlier. Neither is cited in the preprint's 47-item reference list — a finding scoped to arXiv:2511.11199v1 and to that version only, for reasons given below. The Hiary paper the preprint does cite is the later Annals method, not the amortized one. Odlyzko–Schönhage is present in the source bibliography database but uncited, one of 16 uncited entries of 65, a set that also contains Riemann (1859); no intent is inferred. One argument is developed and one is withdrawn. The withdrawn one is a precision penalty. A measurement made for this note over 6200 Gram points spanning six decades of height finds |Z| height-flat (fitted slope −0.00005941, R² = 0.000333), so the sampling resolution δ is a large constant factor, not an asymptotic penalty. What survives is practical rather than asymptotic and rests on a single datum, the most extreme value in the sources obtained here; no distribution for that tail is stated in any of them, so the datum is not an upper bound on the precision required. The argument that carries the weight is categorical rather than complexity-theoretic: amplitude estimation returns confidence intervals, whereas rigorous verification of the Riemann Hypothesis to a given height requires certified enclosures. Platt–Trudgian's accounting of their 3×10¹² computation supports this, attributing a 725× cost of rigour to interval arithmetic and sampling rate and explicitly not to precision. Separately, the paper's correspondence theorem is shown to hold at every zero in the strip, not only on the critical line; this is a statement about the construction, which is therefore coextensive with the Riemann Hypothesis rather than evidence bearing on it. Nothing here bears on the hypothesis itself, and nothing here disputes the physics. Every claim is traced to a hashed artifact and classified by the strength of its warrant. The bibliography findings are scoped to arXiv:2511.11199v1: the published record is an Accelerated Article Preview carrying no reference list, and the published version is known to differ from v1, so a recheck is registered against the edited version when it appears. Three blockers are left open and stated rather than closed — the unavailable published reference list, the absent tail distribution, and what actually sets the operative resolution for sign-change-based verification, given that precision was demonstrably not the binding classical constraint. An appendix registers one pre-specified, falsifiable prediction about quantum block-amortized cost.Wei et al. (Nat. Commun., 2026; preprint arXiv:2511.11199v1) report a quantum algorithm for ζ(½+it) and compare its cost against direct Riemann–Siegel summation. This note examines that comparison. The speedup claim is correct against the baselines the paper names, and correct for a single isolated evaluation. It is, however, applied to locating and verifying zeros, which is a bulk task, and the classical state of the art for bulk evaluation is amortized. Odlyzko–Schönhage (1988) amortizes to T^ε per point, for every ε > 0, over blocks of length T^(1/2) after one precomputation, where the quantum method offers no amortization mechanism at all and pays its per-point cost every time; Hiary's amortized method (Math. Comp., 2011) reaches the same T^(1/4) exponent classically fifteen years earlier. Neither is cited in the preprint's 47-item reference list — a finding scoped to arXiv:2511.11199v1 and to that version only, for reasons given below. The Hiary paper the preprint does cite is the later Annals method, not the amortized one. Odlyzko–Schönhage is present in the source bibliography database but uncited, one of 16 uncited entries of 65, a set that also contains Riemann (1859); no intent is inferred. One argument is developed and one is withdrawn. The withdrawn one is a precision penalty. A measurement made for this note over 6200 Gram points spanning six decades of height finds |Z| height-flat (fitted slope −0.00005941, R² = 0.000333), so the sampling resolution δ is a large constant factor, not an asymptotic penalty. What survives is practical rather than asymptotic and rests on a single datum, the most extreme value in the sources obtained here; no distribution for that tail is stated in any of them, so the datum is not an upper bound on the precision required. The argument that carries the weight is categorical rather than complexity-theoretic: amplitude estimation returns confidence intervals, whereas rigorous verification of the Riemann Hypothesis to a given height requires certified enclosures. Platt–Trudgian's accounting of their 3×10¹² computation supports this, attributing a 725× cost of rigour to interval arithmetic and sampling rate and explicitly not to precision. Separately, the paper's correspondence theorem is shown to hold at every zero in the strip, not only on the critical line; this is a statement about the construction, which is therefore coextensive with the Riemann Hypothesis rather than evidence bearing on it. Nothing here bears on the hypothesis itself, and nothing here disputes the physics. Every claim is traced to a hashed artifact and classified by the strength of its warrant. The bibliography findings are scoped to arXiv:2511.11199v1: the published record is an Accelerated Article Preview carrying no reference list, and the published version is known to differ from v1, so a recheck is registered against the edited version when it appears. Three blockers are left open and stated rather than closed — the unavailable published reference list, the absent tail distribution, and what actually sets the operative resolution for sign-change-based verification, given that precision was demonstrably not the binding classical constraint. An appendix registers one pre-specified, falsifiable prediction about quantum block-amortized cost.

Aug 6, 20260 citations

Quantum Approximate Counting with Bernoulli Oracles

Chengshen Gao, Yongzhen Xu, Lvzhou Li

Quantum counting is a fundamental quantum algorithm that estimates the fraction of marked elements using a membership oracle, achieving a quadratic speedup over classical sampling. The membership oracle, however, assumes exact labeling of each element, but this assumption fails when the labels are inherently probabilistic. We study quantum counting with \emph{Bernoulli oracles}, where given $m$ Bernoulli distributions with unknown biases $p_1,\dots,p_m$ and a gap parameter $Δ$ , the goal is to estimate the fraction $ρ$ of \emph{positive} distributions ( $p_i\ge1/2+Δ$ ) to within additive error $ε$ . We prove an upper bound of $\tilde{O}\!\big(\frac{\sqrtρ}{Δε}+\frac{1}{Δ\sqrtε}\big)$ queries, achieving a quadratic speedup over the classical sample complexity. % of $Θ(ρ/Δ^2ε^2)$ . Our algorithm first uses the Quantum Singular Value Transformation (QSVT) to coherently amplify the bias gap without collapsing the superposition over distributions, and then applies two-stage adaptive amplitude estimation. We complement this upper bound with a near-matching lower bound of $Ω(\sqrtρ/(Δε))$ via a new composition theorem for the quantum adversary method in the Boolean-over-average-case direction. For the special case of a constant gap $Δ=Θ(1)$ , which corresponds to the bounded-error oracle where each query returns the correct label with constant probability, our bounds specialize to $\tilde{O}\big(\frac{\sqrtρ}ε+\frac{1}{\sqrtε}\big)$ and $Ω(\frac{\sqrtρ}ε)$ , thereby characterizing the query complexity of quantum counting with bounded-error oracles.Quantum counting is a fundamental quantum algorithm that estimates the fraction of marked elements using a membership oracle, achieving a quadratic speedup over classical sampling. The membership oracle, however, assumes exact labeling of each element, but this assumption fails when the labels are inherently probabilistic. We study quantum counting with \emph{Bernoulli oracles}, where given $m$ Bernoulli distributions with unknown biases $p_1,\dots,p_m$ and a gap parameter $Δ$, the goal is to estimate the fraction $ρ$ of \emph{positive} distributions ($p_i\ge1/2+Δ$) to within additive error $ε$. We prove an upper bound of $\tilde{O}\!\big(\frac{\sqrtρ}{Δε}+\frac{1}{Δ\sqrtε}\big)$ queries, achieving a quadratic speedup over the classical sample complexity. % of $Θ(ρ/Δ^2ε^2)$. Our algorithm first uses the Quantum Singular Value Transformation (QSVT) to coherently amplify the bias gap without collapsing the superposition over distributions, and then applies two-stage adaptive amplitude estimation. We complement this upper bound with a near-matching lower bound of $Ω(\sqrtρ/(Δε))$ via a new composition theorem for the quantum adversary method in the Boolean-over-average-case direction. For the special case of a constant gap $Δ=Θ(1)$, which corresponds to the bounded-error oracle where each query returns the correct label with constant probability, our bounds specialize to $\tilde{O}\big(\frac{\sqrtρ}ε+\frac{1}{\sqrtε}\big)$ and $Ω(\frac{\sqrtρ}ε)$, thereby characterizing the query complexity of quantum counting with bounded-error oracles.

quant-pharXiv:2609.07604Sep 8, 20260 citations

Quantum algorithms for weighted constrained sampling and weighted model counting

Fabrizio Riguzzi

Abstract We consider the problems of weighted constrained sampling and weighted model counting, where we are given a propositional formula and a weight for each world. The first problem consists of sampling worlds with a probability proportional to their weight given that the formula is satisfied. The latter is the problem of computing the sum of the weights of the models of the formula. Both have applications in many fields such as probabilistic reasoning, graphical models, statistical physics, statistics, and hardware verification. In this article, we propose quantum weighted constrained sampling (QWCS) and quantum weighted model counting (QWMC), two quantum algorithms for performing weighted constrained sampling and weighted model counting, respectively. Both are based on the quantum search/quantum model counting algorithms that are modified to take into account the weights. In the black box model of computation, where we can only query an oracle for evaluating the Boolean function given an assignment, QWCS requires $O(2^{\frac{n}{2}}+1/\sqrt{\text {WMC}})$ O ( 2 n 2 + 1 / WMC ) oracle calls, where n is the number of Boolean variables and $\text {WMC}$ WMC is the normalized between 0 and 1 weighted model count of the formula, while a classical algorithm has a complexity of $\Omega (1/\text {WMC})$ Ω ( 1 / WMC ) . QWMC takes $\Theta (2^{\frac{n}{2}})$ Θ ( 2 n 2 ) oracle calss, while classically the best complexity is $\Theta (2^n)$ Θ ( 2 n ) , thus achieving a quadratic speedup.Abstract We consider the problems of weighted constrained sampling and weighted model counting, where we are given a propositional formula and a weight for each world. The first problem consists of sampling worlds with a probability proportional to their weight given that the formula is satisfied. The latter is the problem of computing the sum of the weights of the models of the formula. Both have applications in many fields such as probabilistic reasoning, graphical models, statistical physics, statistics, and hardware verification. In this article, we propose quantum weighted constrained sampling (QWCS) and quantum weighted model counting (QWMC), two quantum algorithms for performing weighted constrained sampling and weighted model counting, respectively. Both are based on the quantum search/quantum model counting algorithms that are modified to take into account the weights. In the black box model of computation, where we can only query an oracle for evaluating the Boolean function given an assignment, QWCS requires $$O(2^{\frac{n}{2}}+1/\sqrt{\text {WMC}})$$ O ( 2 n 2 + 1 / WMC ) oracle calls, where n is the number of Boolean variables and $$\text {WMC}$$ WMC is the normalized between 0 and 1 weighted model count of the formula, while a classical algorithm has a complexity of $$\Omega (1/\text {WMC})$$ Ω ( 1 / WMC ) . QWMC takes $$\Theta (2^{\frac{n}{2}})$$ Θ ( 2 n 2 ) oracle calss, while classically the best complexity is $$\Theta (2^n)$$ Θ ( 2 n ) , thus achieving a quadratic speedup.

arXiv:2407.12816Quantum Machine IntelligenceNov 5, 20242 citations

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

Yota Maeda, Hiroshi Yano

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.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.

quant-pharXiv:2608.23929Aug 26, 20260 citations

Quantum Weighted Model Counting

Fabrizio Riguzzi

In Weighted Model Counting (WMC) we assign weights to Boolean literals and we want to compute the sum of the weights of the models of a Boolean function where the weight of a model is the product of the weights of its literals. WMC was shown to be particularly effective for performing inference in graphical models, with a complexity of $O(n2^w)$ where $n$ is the number of variables and $w$ is the treewidth. In this paper, we propose a quantum algorithm for performing WMC, Quantum WMC (QWMC), that modifies the quantum model counting algorithm to take into account the weights. In turn, the model counting algorithm uses the algorithms of quantum search, phase estimation and Fourier transform. In the black box model of computation, where we can only query an oracle for evaluating the Boolean function given an assignment, QWMC solves the problem approximately with a complexity of $Θ(2^{\frac{n}{2}})$ oracle calls while classically the best complexity is $Θ(2^n)$ , thus achieving a quadratic speedup.In Weighted Model Counting (WMC) we assign weights to Boolean literals and we want to compute the sum of the weights of the models of a Boolean function where the weight of a model is the product of the weights of its literals. WMC was shown to be particularly effective for performing inference in graphical models, with a complexity of $O(n2^w)$ where $n$ is the number of variables and $w$ is the treewidth. In this paper, we propose a quantum algorithm for performing WMC, Quantum WMC (QWMC), that modifies the quantum model counting algorithm to take into account the weights. In turn, the model counting algorithm uses the algorithms of quantum search, phase estimation and Fourier transform. In the black box model of computation, where we can only query an oracle for evaluating the Boolean function given an assignment, QWMC solves the problem approximately with a complexity of $Θ(2^{\frac{n}{2}})$ oracle calls while classically the best complexity is $Θ(2^n)$, thus achieving a quadratic speedup.

arXiv:1910.13530Oct 22, 20190 citations

We give quantum algorithms for estimating weighted exponential sums

S(f,w,N)= \sum_{k=0}^{N-1} w_k e^{2 πi f(k)}

, with

w_k \ge 0

\sum_k w_k =1

, and

N=2^{n}

exponentially large. Under two explicit oracle assumptions -- efficiently computable prefix sums for the weights, enabling Grover--Rudolph state preparation, and a fixed-point circuit for

f

-- amplitude estimation yields

S

to additive error

\varepsilon

with

O(\varepsilon^{-1}\log(1/γ))

oracle uses and

\operatorname{polylog}(N)

gates per use; all bounds are full gate complexities, and the saving over classical sampling is quadratic in

1/\varepsilon

. Applying this to the Riemann--Siegel formula, we prove that

ζ(σ+it)

in the critical strip can be estimated to accuracy

δ

with

\widetilde O(t^{(1-σ)/2}\, δ^{-1})

gates, hence

\widetilde O(t^{1/4}\, δ^{-1})

on the critical line, where

\widetilde O

suppresses factors polylogarithmic in

t/δ

. At fixed accuracy this improves on the

t^{1/2}

Riemann--Siegel cost and on the best rigorous classical algorithm's

t^{4/13+o(1)}

; the quantum algorithm is advantageous precisely when

δ\gg t^{-3/52}

, which covers the accuracy needed to locate and count zeros. We show that a

\operatorname{polylog}(t)

algorithm does not follow from these techniques -- undoing the normalization costs the

\ell^{1}

mass

\sum_{k\le N} k^{-σ} = Θ(t^{(1-σ)/2})

of the main sum -- and that Hiary-type block decompositions cannot improve the quantum query complexity. We also give an estimator for the magnitude of the amplitude sum

\lvert \sum_k a_k \rvert

of any efficiently preparable state, and review the required amplitude- and phase-estimation subroutines.

\sum_{i=1}^N α_i k(x,x_i)

N

kernel values to additive precision

\varepsilon

, where

α

is the vector of trained coefficients. The standard approach estimates each term independently via sampling, yielding a query complexity of

O(N\lVertα\rVert_2^2/\varepsilon^2)

. In this work, we identify two independent axes for improvement: (1) How individual kernel values are estimated (sampling versus quantum amplitude estimation), and (2) how the sum is approximated (term-by-term versus via a single observable), and systematically analyze all combinations thereof. The query-optimal combination, encoding the full inference sum as the expectation value of a single observable and applying quantum amplitude estimation, achieves a query complexity of

O(\lVertα\rVert_1/\varepsilon)

, removing the dependence on

N

from the query count and yielding a quadratic improvement in both

\lVertα\rVert_1

and

\varepsilon

. We prove a matching lower bound of

Ω(\lVertα\rVert_1/\varepsilon)

, establishing query-optimality of our approach up to logarithmic factors. Beyond query complexity, we also analyze how these improvements translate into gate costs and show that the query-optimal strategy is not always optimal in practice from the perspective of gate complexity. Our results provide both a query-optimal algorithm and a practically optimal choice of strategy depending on hardware capabilities, along with a complete landscape of intermediate methods to guide practitioners. All algorithms require only amplitude estimation as a subroutine and are thus natural candidates for early-fault-tolerant implementations.

m

Bernoulli distributions with unknown biases

p_1,\dots,p_m

and a gap parameter

Δ

, the goal is to estimate the fraction

ρ

of \emph{positive} distributions (

p_i\ge1/2+Δ

) to within additive error

ε

. We prove an upper bound of

\tilde{O}\!\big(\frac{\sqrtρ}{Δε}+\frac{1}{Δ\sqrtε}\big)

queries, achieving a quadratic speedup over the classical sample complexity. % of

Θ(ρ/Δ^2ε^2)

. Our algorithm first uses the Quantum Singular Value Transformation (QSVT) to coherently amplify the bias gap without collapsing the superposition over distributions, and then applies two-stage adaptive amplitude estimation. We complement this upper bound with a near-matching lower bound of

Ω(\sqrtρ/(Δε))

via a new composition theorem for the quantum adversary method in the Boolean-over-average-case direction. For the special case of a constant gap

Δ=Θ(1)

, which corresponds to the bounded-error oracle where each query returns the correct label with constant probability, our bounds specialize to

\tilde{O}\big(\frac{\sqrtρ}ε+\frac{1}{\sqrtε}\big)

and

Ω(\frac{\sqrtρ}ε)

, thereby characterizing the query complexity of quantum counting with bounded-error oracles.

O(2^{\frac{n}{2}}+1/\sqrt{\text {WMC}})

O ( 2 n 2 + 1 / WMC ) oracle calls, where n is the number of Boolean variables and

\text {WMC}

WMC is the normalized between 0 and 1 weighted model count of the formula, while a classical algorithm has a complexity of

\Omega (1/\text {WMC})

Ω ( 1 / WMC ) . QWMC takes

\Theta (2^{\frac{n}{2}})

Θ ( 2 n 2 ) oracle calss, while classically the best complexity is

\Theta (2^n)

Θ ( 2 n ) , thus achieving a quadratic speedup.

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.

O(n2^w)

where

n

is the number of variables and

w

is the treewidth. In this paper, we propose a quantum algorithm for performing WMC, Quantum WMC (QWMC), that modifies the quantum model counting algorithm to take into account the weights. In turn, the model counting algorithm uses the algorithms of quantum search, phase estimation and Fourier transform. In the black box model of computation, where we can only query an oracle for evaluating the Boolean function given an assignment, QWMC solves the problem approximately with a complexity of

Θ(2^{\frac{n}{2}})

oracle calls while classically the best complexity is

Θ(2^n)

, thus achieving a quadratic speedup.