Efficient quantum algorithm for weighted partial sums and numerical integration

Alok Shukla; Prakash Vedula

REVIEW 3 major objections 4 minor 22 references

Efficient quantum algorithm for weighted partial sums and numerical integration

T0 review · 3 major / 4 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A quantum circuit of O(log M) gates embeds any M-term partial sum of a state's amplitudes into the |0> amplitude.

desk verdict Thin but checkable idea — invert their own uniform-superposition circuit so the partial sum lands in the |0⟩ amplitude — and the worked numerical-integration example is wrong as printed: S_12(|v⟩)×√12 ≈ 3.08, not 0.544. read the letter →

arxiv 2411.10986 v1 pith:HCMCGGUP submitted 2024-11-17 quant-ph

Alok Shukla , Prakash Vedula This is my paper · ORCID

classification quant-ph MSC 81P6865D32 PACS 03.67.Ac

keywords quantumalgorithmpartialsumsnumericalintegrationuniformsuperpositionamplitudeencodingcircuitdepthweighted

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper claims that any partial sum of the first M amplitudes of a quantum state can be computed by a quantum circuit whose gate count and depth grow only logarithmically in M, provided the input state is already available. The key move is to construct a unitary whose first row is the uniform vector with M ones followed by zeros, so that the partial sum (up to a known normalization) lands in the amplitude of |0>. For M a power of two this is a row of Hadamards; for arbitrary M the paper gives a construction that reverses a uniform-superposition preparation algorithm, using controlled rotations whose angles come from the binary expansion of M. The authors show the same gadget yields weighted partial sums, even/odd sums, and midpoint-rule numerical integration, and they argue the O(log M) cost compares favorably with Monte Carlo integration approaches.

What carries the argument

The central object is the unitary matrix U whose first row is the uniform partial-sum pattern chi = [1 ... 1 0 ... 0]/sqrt(M). It is constructed as the inverse of the uniform-superposition-preparation circuit that the authors previously gave for arbitrary M; the binary decomposition of M fixes the positions and angles of controlled-Hadamard and controlled-RY gates. Acting on |f>, this unitary transfers S_M/sqrt(M) into the amplitude of the basis state |0>.

What would settle it

Apply Algorithm 1 for a non-power-of-two M (e.g., M=13 on four qubits) to each computational basis state |k> in simulation, and verify that the amplitude of |0> in the output equals 1/sqrt(M) for k<M and 0 for k>=M; any deviation from this first-row pattern disproves the central construction.

Watch

Extended reading notes

Core claim

The central discovery is that the partial sum S_M = sum_{k=0}^{M-1} f_k of a normalized vector f can be recovered as the amplitude of |0> after applying a unitary U whose first row is [1 ... 1 0 ... 0]/$\sqrt$(M). The construction is explicit: decompose M into powers of two, then run the reverse of the authors' uniform-superposition-preparation circuit, with controlled-Hadamard gates and RY rotations whose angles satisfy cos($\theta$/2) = $\sqrt$($2^{{l_j}}$/(M - M_{j-1})) and a final rotation with cos(theta_0/2) = $\sqrt$(M_0/M). This yields U with gate count and depth O(log_2 M) for arbitrary M, not just powers of two. The same circuit family, with the rotation angles freed, produces weighted partial sums with arbitrary weight vectors; applying the unitary to a subset of qubits gives even or odd partial sums and other structured weighted sums.

Load-bearing premise

The O(log M) complexity claim assumes the input quantum state is already prepared; if preparing that state is expensive, the overall computation is not O(log M).

Editorial extensions

If this is right

Partial sums, and hence numerical integrals via midpoint rules with weights, can be embedded in a quantum amplitude in O(log M) circuit depth, so they can be chained into later quantum processing without mid-circuit measurement.
Weighted partial sums with independently chosen real weights (subject to normalization) can be generated by the same construction, enabling computation of cumulative probabilities, moving averages, and weighted integrals over intervals.
Even and odd partial sums, and more generally weighted sums over strided index sets, follow by applying the gadget to a subset of qubits, with the same logarithmic scaling.
If the input state is prepared beforehand, the O(log M) gate count beats the O(N) cost of classical Monte Carlo summation over N points, as the paper compares against existing integration algorithms.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

If state preparation is included, the end-to-end complexity is dominated by preparation and, for classical output, amplitude estimation; so the O(log M) claim does not by itself translate to an end-to-end speedup for producing a classical number.
The gate count is l_k + 2k for the binary expansion, which is O(log M) but with a constant that grows with the number of 1-bits in M, so circuits for M with many 1-bits have larger constant factors.
The same inverse-preparation trick might apply to non-uniform target rows: any state-preparation circuit that produces a target superposition with a known control structure can be reversed to build a unitary with a desired first row, potentially yielding other integral transforms at logarithmic depth.
A natural testable extension is to use this gadget inside amplitude-estimation loops for Monte Carlo integration where the integrand is encoded in the amplitudes of a prepared state; the logarithmic-depth partial-sum box would reduce the cost per sample compared with coherently summing on a larger register.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Two things worth knowing. The actual new idea is thin but checkable: the inverse of their own uniform-superposition circuit [22] has first row [1…1 0…0]/√M, and applying that inverse to |f⟩ puts the partial sum into the |0⟩ amplitude. The overlap identity behind it is standard linear algebra; the contribution is a qubit-efficient, O(log M)-depth way to compute that overlap without a swap test. Algorithm 2's weighted generalization is a reasonable extension, and the paper is honest that state preparation is out of scope and that classical extraction needs amplitude estimation on top. The complexity claim is conditional but stated fairly.

The soft spots, in order of severity. First, the numerical integration example in Section 7.1.2 is miscalculated. With the paper's own definition, S_12(|v⟩)×√12 equals Σ_{k=0}^{11} sin((2k+1)π/32)/‖ev‖ ≈ 8.708/√8 ≈ 3.08, not 0.544262837. The printed value is the unnormalized midpoint sum times 1/16 — the ordinary midpoint rule with Δx = 1/16 — so the stated extraction formula is missing a factor of ‖ev‖/16. The number happens to approximate the true integral, but not via the equation printed. This is a concrete error in the paper's headline application and it has to be fixed.

Second, correctness of the main construction is delegated to the authors' own [22] with "can be easily verified." That is heavy self-reliance, though not circular — nothing is fit to a target. Still, a referee should insist the key lemma be stated and proved in this paper, or at least given a real proof sketch. Third, novelty is narrow: it is a new application of an existing primitive, not a new principle, and the payoff is capped by amplitude-estimation cost when a classical number is needed.

On balance, the core construction is plausible and probably correct, the paper is honest about its assumptions, and the error, while embarrassing, is local. It deserves a serious referee — this is a revise-and-resubmit, not a desk reject. I would not cite it as-is, and I would want [22]'s correctness checked and the example fixed before trusting the integration claim.

Referee Report

3 major / 4 minor

Summary. The paper proposes a quantum algorithm that, given a normalized n-qubit state |f⟩ and an integer M ≤ 2^n, constructs a unitary U whose first row is (1/√M)(1,...,1,0,...,0), so that the amplitude of |0⟩ after applying U to |f⟩ equals (1/√M)∑_{k=0}^{M-1} f_k. For M = 2^r the construction is simply Hadamards; for arbitrary M it gives a sequence of controlled-Hadamard and controlled-RY gates adapted from the authors' earlier uniform-superposition algorithm [22]. Algorithms 1 and 2 are stated with claimed gate complexity and circuit depth O(log_2 M), and applications are given to partial sums, cumulative distributions, weighted sums, and numerical integration.

Significance. If the unitary construction is correct, the paper's approach is a useful way to embed a partial sum in an amplitude with logarithmic-depth circuits, avoiding the overhead of a swap-test inner product and allowing downstream quantum processing. The paper has clear strengths: explicit circuits are given (Figs. 1–3), the power-of-two case is cleanly separated from the general case, and the text honestly acknowledges in Section 7 that state preparation and classical amplitude estimation are outside the advertised O(log M) cost. However, the correctness of the arbitrary-M case is largely inherited from the authors' own prior work [22] rather than proved here, and the numerical examples contain concrete normalization errors, including a miscalculated integration result. These issues are local and fixable, but they are load-bearing for the paper's demonstrations.

major comments (3)

[7.1.2] The numerical-integration example is miscalculated as printed. With v_k = sin((2k+1)π/32)/∥ev∥ and ∥ev∥ = √8, the quantity S_12(|v⟩)×√12 equals (1/√8)∑_{k=0}^{11} sin((2k+1)π/32) ≈ 3.078, not 0.544262837. The quoted value instead equals (1/16)∑_{k=0}^{11} sin((2k+1)π/32), i.e., the unnormalized midpoint sum times Δx. Thus the extraction formula S_M(|v⟩)×√M stated in Section 7 is not the formula actually used in the example. The demonstration must be corrected, for example by explicitly including the missing factor ∥ev∥/16 or by redefining what is being approximated.
[3] The correctness of Algorithm 1 for arbitrary M is not proved in this paper. Section 3 asserts that the circuit generated by lines 6–16 is the inverse of Algorithm 1 in [22] and says this 'can be easily verified', but no verification or induction is supplied. Since [22] is the authors' own prior work and this unitary property is the central algorithmic claim, the paper should provide a self-contained proof (e.g., an induction on the binary decomposition of M) that the control structure and rotation angles in lines 6–16 produce the first row (1/√M)(1,...,1,0,...,0). As written, the proof is an appeal to another paper.
[7.1.1] The partial-sum example for M = 13 contains a normalization error. The state |v⟩ has amplitude 1/√8 on both |12⟩ and |13⟩, so the sum of the first 13 components is 1 + 1/√2 + 1/√2 = 1 + √2, whereas the text gives 1 + 1/√2 + 1/√8. Consequently the displayed c_0 = (1/√13)(1+1/√2+1/√8) does not equal the partial sum defined by Eq. (1.1). This does not invalidate the general algorithm, but it means the example does not illustrate the stated formula correctly.

minor comments (4)

[4] The summation bounds in Eq. (4.2) and Eq. (4.3) are garbled; for example, the first summation should run from j = S_{k-1} to S_k - 1, not as printed. Please rewrite these equations with unambiguous indices.
[8] The expression ⟨0|U⊗I|f⟩ is a vector in the second register, not a scalar equal to S_E. The intended identity should be written using a partial inner product or explicit coefficients.
[4] The heading 'comutation of weighted partial sums' contains a typo; it should read 'computation'.
[7] The abstract and introduction should state explicitly that the O(log M) cost excludes input state preparation and classical amplitude estimation, as Section 7 later acknowledges, to avoid overstatement.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the unitary construction is the inverse of a distinct uniform-superposition preparation result; the paper's main issues are a deferred proof and an inconsistent numerical example, not circular reasoning.

full rationale

The only candidate for circularity is Section 3, where Algorithm 1's unitary U is justified by saying: 'the unitary operator U corresponding to these steps is precisely the inverse of the unitary matrix U† corresponding to the quantum circuit generated by the efficient algorithm for preparation of uniform superposition state presented in [22] ... This can be easily verified.' This is a self-citation and the local proof is deferred, but it is not circular: [22] is a separate, parameter-free construction of uniform superposition states, and the target partial sum S_M does not appear among its assumptions. The desired amplitude ef0 = (1/sqrt(M)) sum_{j=0}^{M-1} f_j follows from the explicitly constructed first row [1 ... 1 0 ... 0]/sqrt(M) by matrix multiplication (Section 3, Eqs. (3.1)-(3.3)); it is not a fitted parameter relabeled as a prediction. Algorithm 2 likewise builds weighted sums from user-chosen weights; Eq. (4.2) is the definition of the output the circuit is designed to produce, not an independent prediction recovered from the circuit. The strongest non-circular issues are: (i) the correctness proof for arbitrary M effectively inherits [22] instead of proving the inverse-circuit identity in detail; and (ii) the Section 7.1.2 numerical-integration example is inconsistent with its own stated normalization: with v = ev/||ev|| and ||ev|| = sqrt(8), S_12(|v⟩)×sqrt(12) = sum_{k=0}^{11} sin((2k+1)pi/32)/sqrt(8) ≈ 3.078, not 0.5442628374252914; the displayed value is the unnormalized midpoint sum times Delta x. That is a correctness/typo issue, not circularity. The Section 7 state-preparation limitation is explicitly acknowledged. No circular reduction of the central claim was found; absent a circular step, the score is 0.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The central claim rests on the prior uniform-superposition algorithm [22], on the availability of the input state, and on standard linear algebra and amplitude estimation. No parameters are fitted to data; Algorithm 2's weights are user inputs rather than fitted constants.

assumptions (4)

domain assumption Algorithm 1 of [22] prepares a uniform superposition over the first M computational basis states with O(log M) gates and depth.
Section 3 states U is 'precisely the inverse' of Algorithm 1 in [22] and delegates correctness to that paper; no independent proof is given in this preprint.
domain assumption The input state |f> is normalized and available without counting preparation cost.
Stated in Section 7: 'We assume that the quantum state |v> is already available.' Also assumed in Eq. (1.1) with sum |f_k|^2 = 1.
standard math The amplitude of |0> after a unitary equals the inner product of the first row of that unitary with the input vector.
Used throughout Sections 3 and 5; standard linear algebra.
standard math Amplitude estimation can extract the |0> amplitude with error epsilon using resources scaling as 1/epsilon (or similar), and this cost is separate from the unitary construction.
Invoked in the introduction and Section 6 via references [17-21].

how reviews work

0 comments

Cite this review

Pith. "Pith review of Efficient quantum algorithm for weighted partial sums and numerical integration." pith.science (2026). https://pith.science/paper/HCMCGGUP

@misc{pith2026241110986,
  author       = {Pith},
  title        = {Pith review of: Efficient quantum algorithm for weighted partial sums and numerical integration},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/HCMCGGUP}},
  note         = {Machine review of arXiv:2411.10986}
}

abstract

This paper presents a quantum algorithm 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 $O(\log_2 M)$, where $M$ represents the number of terms in the partial sum. For cases where $M$ is a power of two, the unitary construction is straightforward; however, for arbitrary $M$, we develop an efficient quantum algorithm to create the required unitary matrix. Computational examples for evaluation certain partial sums and numerical integration based on our proposed algorithm are provided. We also extend the algorithm to evaluate partial sums of even or odd components and more complex weighted sums over specified intervals.

Figures

Figures reproduced from arXiv: 2411.10986 by the authors.

**Figure 1.** Quantum circuits created by Algorithm 1 for computing the partial sums for M = 13, n = 4 (left) and M = 42, n = 6 (right). 3 Discussion on the correctness of Algorithm 1 We now present a more detailed explanation of the steps in Algorithm 1 and discuss the reasoning behind its correctness. Since the desired partial weighted sum is produced as the amplitude fe0 = 1 √ M PM−1 j=0 fj corresponding to the |0⟩ state of |f… view at source ↗

**Figure 2.** Quantum circuit for creating the state |v⟩ = 1 √ 64 (|0⟩ + |1⟩ + |2⟩ + |3⟩ + |4⟩ + |5⟩ + |6⟩ + |7⟩) + 1 √ 32 (|8⟩ + |9⟩ + |10⟩ + |11⟩) + 1 √ 8 (|12⟩ + |13⟩) + 1 √ 2 (|14⟩). 7.1.1 Computational example: partial sums Let us consider a normalized vector |v⟩ where the length N = 2n . In this example, let N = 16, i.e., n = 4, and the vector |v⟩ is given as: |v⟩ = X 15 k=0 vk |k⟩ = 1 √ 64 (|0⟩ + |1⟩ + |2⟩ + |3⟩ + |4⟩ + |5… view at source ↗

**Figure 3.** Quantum circuits created by Algorithm 1 for computing the partial sums for [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

22 extracted references · 10 canonical work pages

[22]

An e fficient quantum algorithm for preparation of uniform quan- tum superposition states

Alok Shukla and Prakash Vedula. An e fficient quantum algorithm for preparation of uniform quan- tum superposition states. Quantum Information Processing, 23(2):38, 2024. 14

work page 2024
[1]

A hybrid classical-quantum algorithm for solution of nonlinear ordinary differential equations

Alok Shukla and Prakash Vedula. A hybrid classical-quantum algorithm for solution of nonlinear ordinary differential equations. Applied Mathematics and Computation, 442:127708, 2023

2023
[2]

Solving nonlinear di fferential equations with differentiable quantum circuits

Oleksandr Kyriienko, Annie E Paine, and Vincent E Elfving. Solving nonlinear di fferential equations with differentiable quantum circuits. Physical Review A, 103(5):052416, 2021. 12

work page 2021
[3]

Quantum spectral methods for di fferential equations

Andrew M Childs and Jin-Peng Liu. Quantum spectral methods for di fferential equations. Communications in Mathematical Physics, 375(2):1427–1457, 2020

2020
[4]

A review on quantum approximate optimization algorithm and its variants

Kostas Blekos, Dean Brand, Andrea Ceschini, Chiao-Hui Chou, Rui-Hao Li, Komal Pandya, and Alessandro Summer. A review on quantum approximate optimization algorithm and its variants. Physics Reports, 1068:1–66, 2024

2024
[5]

Trajectory optimization using quantum computing

Alok Shukla and Prakash Vedula. Trajectory optimization using quantum computing. Journal of Global Optimization, 75(1):199–225, 2019

work page 2019
[6]

A quantum approach for optimal control

Hirmay Sandesara, Alok Shukla, and Prakash Vedula. A quantum approach for optimal control.arXiv preprint arXiv:2407.02864, 2024

work page Pith review arXiv 2024
[7]

Variational quantum algorithms

Marco Cerezo, Andrew Arrasmith, Ryan Babbush, Simon C Benjamin, Suguru Endo, Keisuke Fujii, Jarrod R McClean, Kosuke Mitarai, Xiao Yuan, Lukasz Cincio, et al. Variational quantum algorithms. Nature Reviews Physics, 3(9):625–644, 2021

2021

Show all 22 references

[8]

A hybrid classical-quantum algorithm for digital image processing

Alok Shukla and Prakash Vedula. A hybrid classical-quantum algorithm for digital image processing. Quantum Information Processing, 22(3):19, Dec 2022

2022
[9]

Hybrid classical-quantum image processing via polar walsh basis functions

Mohit Rohida, Alok Shukla, and Prakash Vedula. Hybrid classical-quantum image processing via polar walsh basis functions. Quantum Machine Intelligence, 6(2):72, 2024

2024
[10]

Review of quantum image processing

Zhaobin Wang, Minzhe Xu, and Yaonan Zhang. Review of quantum image processing. Archives of Computational Methods in Engineering, 29(2):737–761, 2022

2022
[11]

A quantum approach for digital signal processing

Alok Shukla and Prakash Vedula. A quantum approach for digital signal processing. The European Physical Journal Plus, 138(12):1–24, 2023

2023
[12]

Quantum Monte Carlo integration: The full advantage in minimal circuit depth

Steven Herbert. Quantum Monte Carlo integration: The full advantage in minimal circuit depth. Quantum, 6:823, 2022

2022
[13]

Quantum coin method for numerical integration

Naoharu H Shimada and Toshiya Hachisuka. Quantum coin method for numerical integration. In Computer graphics forum, volume 39, pages 243–257. Wiley Online Library, 2020

2020
[14]

Quantum integration in Sobolev classes

Stefan Heinrich. Quantum integration in Sobolev classes. Journal of Complexity, 19(1):19–42, 2003

2003
[15]

Fast quantum algorithms for numerical integrals and stochas- tic processes

Daniel S Abrams and Colin P Williams. Fast quantum algorithms for numerical integrals and stochas- tic processes. arXiv preprint quant-ph/9908083, 1999

1999 arXiv
[16]

A general quantum algorithm for numerical integration

Guoqiang Shu, Zheng Shan, Jinchen Xu, Jie Zhao, and Shuya Wang. A general quantum algorithm for numerical integration. Scientific Reports, 14(1):10432, 2024

2024
[17]

Quantum measurements and the abelian stabilizer problem

A Yu Kitaev. Quantum measurements and the abelian stabilizer problem. arXiv preprint quant-ph/9511026, 1995

1995 arXiv
[18]

Quantum amplitude amplification and estimation

Gilles Brassard, Peter Hoyer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and estimation. Contemporary Mathematics, 305:53–74, 2002

2002
[19]

Amplitude estimation without phase estimation.Quantum Information Processing, 19(2):1– 17, 2020

Yohichi Suzuki, Shumpei Uno, Rudy Raymond, Tomoki Tanaka, Tamiya Onodera, and Naoki Ya- mamoto. Amplitude estimation without phase estimation.Quantum Information Processing, 19(2):1– 17, 2020. 13

2020
[20]

Iterative quantum amplitude esti- mation

Dmitry Grinko, Julien Gacon, Christa Zoufal, and Stefan Woerner. Iterative quantum amplitude esti- mation. npj Quantum Information, 7(1):52, 2021

2021
[21]

Low depth algorithms for quantum amplitude estimation

Tudor Giurgica-Tiron, Iordanis Kerenidis, Farrokh Labib, Anupam Prakash, and William Zeng. Low depth algorithms for quantum amplitude estimation. Quantum, 6:745, 2022

2022

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.

[1] [22]

An e fficient quantum algorithm for preparation of uniform quan- tum superposition states

Alok Shukla and Prakash Vedula. An e fficient quantum algorithm for preparation of uniform quan- tum superposition states. Quantum Information Processing, 23(2):38, 2024. 14

work page 2024

[2] [1]

A hybrid classical-quantum algorithm for solution of nonlinear ordinary differential equations

Alok Shukla and Prakash Vedula. A hybrid classical-quantum algorithm for solution of nonlinear ordinary differential equations. Applied Mathematics and Computation, 442:127708, 2023

2023

[3] [2]

Solving nonlinear di fferential equations with differentiable quantum circuits

Oleksandr Kyriienko, Annie E Paine, and Vincent E Elfving. Solving nonlinear di fferential equations with differentiable quantum circuits. Physical Review A, 103(5):052416, 2021. 12

work page 2021

[4] [3]

Quantum spectral methods for di fferential equations

Andrew M Childs and Jin-Peng Liu. Quantum spectral methods for di fferential equations. Communications in Mathematical Physics, 375(2):1427–1457, 2020

2020

[5] [4]

A review on quantum approximate optimization algorithm and its variants

Kostas Blekos, Dean Brand, Andrea Ceschini, Chiao-Hui Chou, Rui-Hao Li, Komal Pandya, and Alessandro Summer. A review on quantum approximate optimization algorithm and its variants. Physics Reports, 1068:1–66, 2024

2024

[6] [5]

Trajectory optimization using quantum computing

Alok Shukla and Prakash Vedula. Trajectory optimization using quantum computing. Journal of Global Optimization, 75(1):199–225, 2019

work page 2019

[7] [6]

A quantum approach for optimal control

Hirmay Sandesara, Alok Shukla, and Prakash Vedula. A quantum approach for optimal control.arXiv preprint arXiv:2407.02864, 2024

work page Pith review arXiv 2024

[8] [7]

Variational quantum algorithms

Marco Cerezo, Andrew Arrasmith, Ryan Babbush, Simon C Benjamin, Suguru Endo, Keisuke Fujii, Jarrod R McClean, Kosuke Mitarai, Xiao Yuan, Lukasz Cincio, et al. Variational quantum algorithms. Nature Reviews Physics, 3(9):625–644, 2021

2021