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.10986 · Advanced Quantum Technologies

Efficient Quantum Algorithm for Weighted Partial Sums and Numerical Integration

Alok Shukla, Prakash Vedula

Published Jul 1, 2025• 1 citation
arXivHTMLPDF

Abstract

Abstract A quantum algorithm is presented for efficiently computing partial sums and specific weighted partial sums of quantum state amplitudes. Computation of partial sums has important applications, including numerical integration, cumulative probability distributions, and probabilistic modeling. The proposed quantum algorithm uses a custom unitary construction to achieve the desired partial sums with gate complexity and circuit depth of , where represents the number of terms in the partial sum. For cases where is a power of two, the unitary construction is straightforward; however, for arbitrary , an efficient quantum algorithm is developed to create the required unitary matrix. Computational examples for evaluation of certain partial sums and numerical integration based on the proposed algorithm are provided. The algorithm is also extended to evaluate partial sums of even or odd components and more complex weighted sums over specified intervals.

DOI
10.1002/qute.202500084

Related papers

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

Sandeep Tyagi

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.

arXiv:2002.11094•Feb 25, 2020•0 citations

Efficient quantum algorithm for all quantum wavelet transforms

Mohsen Bagherimehrab, Alán Aspuru‐Guzik

Abstract Wavelet transforms are widely used in various fields of science and engineering as a mathematical tool with features that reveal information ignored by the Fourier transform. Unlike the Fourier transform, which is unique, a wavelet transform is specified by a sequence of numbers associated with the type of wavelet used and an order parameter specifying the length of the sequence. While the quantum Fourier transform, a quantum analog of the classical Fourier transform, has been pivotal in quantum computing, prior works on quantum wavelet transforms (QWTs) were limited to the second and fourth order of a particular wavelet, the Daubechies wavelet. Here we develop a simple yet efficient quantum algorithm for executing any wavelet transform on a quantum computer. Our approach is to decompose the kernel matrix of a wavelet transform as a linear combination of unitaries (LCU) that are compilable by easy-to-implement modular quantum arithmetic operations and use the LCU technique to construct a probabilistic procedure to implement a QWT with a known success probability. We then use properties of wavelets to make this approach deterministic by a few executions of the amplitude amplification strategy. We extend our approach to a multilevel wavelet transform and a generalized version, the packet wavelet transform, establishing computational complexities in terms of three parameters: the wavelet order M , the dimension N of the transformation matrix, and the transformation level d . We show the cost is logarithmic in N , linear in d and superlinear in M . Moreover, we show the cost is independent of M for practical applications. Our proposed QWTs could be used in quantum computing algorithms in a similar manner to their well-established counterpart, the quantum Fourier transform.

arXiv:2309.09350•Quantum Science and Technology•Apr 11, 2024•21 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.

arXiv:2407.12816•Quantum Machine Intelligence•Nov 5, 2024•2 citations

A general quantum algorithm for numerical integration

Guoqiang Shu, Zheng Shan, Jinchen Xu +2 more

Quantum algorithms have shown their superiority in many application fields. However, a general quantum algorithm for numerical integration, an indispensable tool for processing sophisticated science and engineering issues, is still missing. Here, we first proposed a quantum integration algorithm suitable for any continuous functions that can be approximated by polynomials. More impressively, the algorithm achieves quantum encoding of any integrable functions through polynomial approximation, then constructs a quantum oracle to mark the number of points in the integration area and finally converts the statistical results into the phase angle in the amplitude of the superposition state. The quantum algorithm introduced in this work exhibits quadratic acceleration over the classical integration algorithms by reducing computational complexity from O(N) to O(√N). Our work addresses the crucial impediments for improving the generality of quantum integration algorithm, which provides a meaningful guidance for expanding the superiority of quantum computing.

Scientific Reports•May 7, 2024•7 citations

Pfaffian Circuits

Jason Morton

It remains an open question whether the apparent additional power of quantum computation derives inherently from quantum mechanics, or merely from the flexibility obtained by "lifting" Boolean functions to linear operators and evaluating their composition cleverly. Holographic algorithms provide a useful avenue for exploring this question. We describe a new, simplified construction of holographic algorithms in terms of Pfaffian circuits. Novel proofs of some key results are provided, and we extend the approach of [34] to nonsymmetric, odd, and homogenized signatures, circuits, and various models of execution flow. This shows our approach is as powerful as the matchgate approach. Holographic algorithms provide in general $O(n^{ω_p})$ time algorithms, where $ω_p$ is the order of Pfaffian evaluation in the ring of interest (with $1.19 \leq ω_p \leq 3$ depending on the ring) and $n$ is the number of inclusions of variables into clauses. Our approach often requires just the evaluation of an $n \times n$ Pfaffian, and at most needs an additional two rows per gate, whereas the matchgate approach is quartic in the arity of the largest gate. We give examples (even before any change of basis) including efficient algorithms for certain lattice path problems and an $O(n^{ω_p})$ algorithm for evaluation of Tutte polynomials of lattice path matroids. Finally we comment on some of the geometric considerations in analyzing Pfaffian circuits under arbitrary basis change. Connections are made to the sum-product algorithm, classical simulation of quantum computation, and SLOCC equivalent entangled states.

arXiv:1101.0129•Dec 30, 2010•9 citations

Efficient Quantum Algorithms for Estimating Gauss Sums

Wim van Dam, G. Seroussi

We present an efficient quantum algorithm for estimating Gauss sums over finite fields and finite rings. This is a natural problem as the description of a Gauss sum can be done without reference to a black box function. With a reduction from the discrete logarithm problem to Gauss sum estimation we also give evidence that this problem is hard for classical algorithms. The workings of the quantum algorithm rely on the interaction between the additive characters of the Fourier transform and the multiplicative characters of the Gauss sum.

arXiv:quant-ph/0207131•Jul 23, 2002•67 citations
Abstract A quantum algorithm is presented for efficiently computing partial sums and specific weighted partial sums of quantum state amplitudes. Computation of partial sums has important applications, including numerical integration, cumulative probability distributions, and probabilistic modeling. The proposed quantum algorithm uses a custom unitary construction to achieve the desired partial sums with gate complexity and circuit depth of , where represents the number of terms in the partial sum. For cases where is a power of two, the unitary construction is straightforward; however, for arbitrary , an efficient quantum algorithm is developed to create the required unitary matrix. Computational examples for evaluation of certain partial sums and numerical integration based on the proposed algorithm are provided. The algorithm is also extended to evaluate partial sums of even or odd components and more complex weighted sums over specified intervals.
We give quantum algorithms for estimating weighted exponential sums S(f,w,N)=∑k=0N−1wke2πif(k)S(f,w,N)= \sum_{k=0}^{N-1} w_k e^{2 πi f(k)}S(f,w,N)=∑k=0N−1​wk​e2πif(k), with wk≥0w_k \ge 0wk​≥0, ∑kwk=1\sum_k w_k =1∑k​wk​=1, and N=2nN=2^{n}N=2n 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 fff -- amplitude estimation yields SSS to additive error ε\varepsilonε with O(ε−1log⁡(1/γ))O(\varepsilon^{-1}\log(1/γ))O(ε−1log(1/γ)) oracle uses and polylog⁡(N)\operatorname{polylog}(N)polylog(N) gates per use; all bounds are full gate complexities, and the saving over classical sampling is quadratic in 1/ε1/\varepsilon1/ε. Applying this to the Riemann--Siegel formula, we prove that ζ(σ+it)ζ(σ+it)ζ(σ+it) in the critical strip can be estimated to accuracy δδδ with O~(t(1−σ)/2 δ−1)\widetilde O(t^{(1-σ)/2}\, δ^{-1})O(t(1−σ)/2δ−1) gates, hence O~(t1/4 δ−1)\widetilde O(t^{1/4}\, δ^{-1})O(t1/4δ−1) on the critical line, where O~\widetilde OO suppresses factors polylogarithmic in t/δt/δt/δ. At fixed accuracy this improves on the t1/2t^{1/2}t1/2 Riemann--Siegel cost and on the best rigorous classical algorithm's t4/13+o(1)t^{4/13+o(1)}t4/13+o(1); the quantum algorithm is advantageous precisely when δ≫t−3/52δ\gg t^{-3/52}δ≫t−3/52, which covers the accuracy needed to locate and count zeros. We show that a polylog⁡(t)\operatorname{polylog}(t)polylog(t) algorithm does not follow from these techniques -- undoing the normalization costs the ℓ1\ell^{1}ℓ1 mass ∑k≤Nk−σ=Θ(t(1−σ)/2)\sum_{k\le N} k^{-σ} = Θ(t^{(1-σ)/2})∑k≤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 ∣∑kak∣\lvert \sum_k a_k \rvert∣∑k​ak​∣ of any efficiently preparable state, and review the required amplitude- and phase-estimation subroutines.
Abstract Wavelet transforms are widely used in various fields of science and engineering as a mathematical tool with features that reveal information ignored by the Fourier transform. Unlike the Fourier transform, which is unique, a wavelet transform is specified by a sequence of numbers associated with the type of wavelet used and an order parameter specifying the length of the sequence. While the quantum Fourier transform, a quantum analog of the classical Fourier transform, has been pivotal in quantum computing, prior works on quantum wavelet transforms (QWTs) were limited to the second and fourth order of a particular wavelet, the Daubechies wavelet. Here we develop a simple yet efficient quantum algorithm for executing any wavelet transform on a quantum computer. Our approach is to decompose the kernel matrix of a wavelet transform as a linear combination of unitaries (LCU) that are compilable by easy-to-implement modular quantum arithmetic operations and use the LCU technique to construct a probabilistic procedure to implement a QWT with a known success probability. We then use properties of wavelets to make this approach deterministic by a few executions of the amplitude amplification strategy. We extend our approach to a multilevel wavelet transform and a generalized version, the packet wavelet transform, establishing computational complexities in terms of three parameters: the wavelet order M , the dimension N of the transformation matrix, and the transformation level d . We show the cost is logarithmic in N , linear in d and superlinear in M . Moreover, we show the cost is independent of M for practical applications. Our proposed QWTs could be used in quantum computing algorithms in a similar manner to their well-established counterpart, the quantum Fourier transform.
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(2n2+1/WMC)O(2^{\frac{n}{2}}+1/\sqrt{\text {WMC}})O(22n​+1/WMC​) O ( 2 n 2 + 1 / WMC ) oracle calls, where n is the number of Boolean variables and WMC\text {WMC}WMC WMC is the normalized between 0 and 1 weighted model count of the formula, while a classical algorithm has a complexity of Ω(1/WMC)\Omega (1/\text {WMC})Ω(1/WMC) Ω ( 1 / WMC ) . QWMC takes Θ(2n2)\Theta (2^{\frac{n}{2}})Θ(22n​) Θ ( 2 n 2 ) oracle calss, while classically the best complexity is Θ(2n)\Theta (2^n)Θ(2n) Θ ( 2 n ) , thus achieving a quadratic speedup.
Quantum algorithms have shown their superiority in many application fields. However, a general quantum algorithm for numerical integration, an indispensable tool for processing sophisticated science and engineering issues, is still missing. Here, we first proposed a quantum integration algorithm suitable for any continuous functions that can be approximated by polynomials. More impressively, the algorithm achieves quantum encoding of any integrable functions through polynomial approximation, then constructs a quantum oracle to mark the number of points in the integration area and finally converts the statistical results into the phase angle in the amplitude of the superposition state. The quantum algorithm introduced in this work exhibits quadratic acceleration over the classical integration algorithms by reducing computational complexity from O(N) to O(√N). Our work addresses the crucial impediments for improving the generality of quantum integration algorithm, which provides a meaningful guidance for expanding the superiority of quantum computing.
It remains an open question whether the apparent additional power of quantum computation derives inherently from quantum mechanics, or merely from the flexibility obtained by "lifting" Boolean functions to linear operators and evaluating their composition cleverly. Holographic algorithms provide a useful avenue for exploring this question. We describe a new, simplified construction of holographic algorithms in terms of Pfaffian circuits. Novel proofs of some key results are provided, and we extend the approach of [34] to nonsymmetric, odd, and homogenized signatures, circuits, and various models of execution flow. This shows our approach is as powerful as the matchgate approach. Holographic algorithms provide in general O(nωp)O(n^{ω_p})O(nωp​) time algorithms, where ωpω_pωp​ is the order of Pfaffian evaluation in the ring of interest (with 1.19≤ωp≤31.19 \leq ω_p \leq 31.19≤ωp​≤3 depending on the ring) and nnn is the number of inclusions of variables into clauses. Our approach often requires just the evaluation of an n×nn \times nn×n Pfaffian, and at most needs an additional two rows per gate, whereas the matchgate approach is quartic in the arity of the largest gate. We give examples (even before any change of basis) including efficient algorithms for certain lattice path problems and an O(nωp)O(n^{ω_p})O(nωp​) algorithm for evaluation of Tutte polynomials of lattice path matroids. Finally we comment on some of the geometric considerations in analyzing Pfaffian circuits under arbitrary basis change. Connections are made to the sum-product algorithm, classical simulation of quantum computation, and SLOCC equivalent entangled states.
We present an efficient quantum algorithm for estimating Gauss sums over finite fields and finite rings. This is a natural problem as the description of a Gauss sum can be done without reference to a black box function. With a reduction from the discrete logarithm problem to Gauss sum estimation we also give evidence that this problem is hard for classical algorithms. The workings of the quantum algorithm rely on the interaction between the additive characters of the Fourier transform and the multiplicative characters of the Gauss sum.