Quantum computing for accelerating cross-correlations intensive applications in signal processing

Erik Franken; Kohr Holger; Valentina Caprara Vivoli; Yuchen Deng

REVIEW 3 major objections 5 minor 21 references

Quantum computing for accelerating cross-correlations intensive applications in signal processing

T0 review · 3 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

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

Pith's one-line read This paper claims two quantum algorithms—one for cross-correlation via Quantum Amplitude Estimation, one for EMML—and says the EMML version is quadratically faster than the classical analog.

desk verdict A genuinely new QAE-based approach to cross-correlations, but both central claims — storing all correlations and a quadratic EMML speedup — are unsupported as written. read the letter →

arxiv 1908.09519 v2 pith:XDW6QZWG submitted 2019-08-26 quant-ph

Valentina Caprara Vivoli , Yuchen Deng , Kohr Holger , Erik Franken This is my paper · ORCID

classification quant-ph MSC 81P6894A12 PACS 03.67.Lx

keywords quantumamplitudeestimationcross-correlationexpectationmaximizationmaximumlikelihoodalgorithmsignalprocessingtemplatematchingconvolutionimage

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

The paper tries to establish that cross-correlation, a workhorse of signal and image processing, can be computed on a quantum computer by encoding data arrays as probability distributions and applying Quantum Amplitude Estimation (QAE), rather than by trying to replace the fast Fourier transform with a quantum Fourier transform. With that encoding, the cross-correlation value $C_l$ appears as the sine-squared of an angle estimated by QAE, and the authors argue the cost is $O(\sqrt{N})$ for arrays of length $N$. The same construction is extended to the expectation-maximization maximum-likelihood (EMML) update, where each new pixel value is written as $\sin^2\theta_{j,k}$; the paper claims this gives a quadratic speed-up over the classical $O(N^2\log N)$. The payoff, if the claims hold, is a quantum route into template matching, drift correction, tilt-series alignment, and other correlation-based image-processing tasks.

What carries the argument

The load-bearing object is Quantum Amplitude Estimation (QAE) fed by a Grover operator whose marked subspace is defined by a shift-equality condition. For the cross-correlation circuit, the operator is $Q = A S_0 A^{-1} S_{j_A \ominus j'_B = l}$, and the marked condition forces the amplitude to be exactly $\sqrt{C_l}$; QAE then phase-kicks that amplitude into a register. The crucial trick is to store the input arrays as probabilities (non-negative weights) rather than as amplitudes, so the correlation of two arrays becomes the probability of a condition, not an amplitude overlap subject to quantum interference. In the EMML circuit the same operator is promoted to two dimensions, with a template array and two shifted copies of the data array, so that the new pixel value $x^{t+1}_{j,k}$ is the sine-squared of the estimated angle.

What would settle it

Simulate the Section 3 circuit for two small arrays with known, distinct cross-correlation values and measure the shift register together with the value register after the inverse QFT; if reconstructing all $N$ values of $C_l$ requires one QAE run per shift $l$ ($N$ runs total) rather than a single run, then the end-to-end complexity is not $O(\sqrt{N})$.

Watch

Extended reading notes

Core claim

The central claim is that cross-correlations can be computed—and stored in a quantum register—using QAE instead of the QFT. The authors encode two real, non-negative, normalized arrays $A$ and $B$ as amplitudes over index registers, then build a Grover operator $Q$ whose reflection marks pairs $(j,j')$ satisfying $j_A\ominus j'_B = l$. When QAE is applied, the value register ends up holding an estimate of the angle $\theta_l$ with $\sin^2\theta_l = \sum_j x^A_{l\oplus j}x^B_j = C_l$, the $l$-th cross-correlation. Because $C_l$ is a probability of the marked subspace, the paper argues that the usual quantum-mechanical obstruction to correlation disappears; the number of QAE steps needed scales as $1/\sin\theta_l$, and with typical values $C_l \approx 1/N$ the paper sets $M=\alpha\sqrt{N}$ and quotes an $O(\sqrt{N})$ complexity. For EMML, the same probability trick turns the maximization step into a single QAE per pixel: $x^{t+1}_{j,k}=\sin^2\theta_{j,k}$, with complexity $O(N)$ against the classical $O(N^2\log N)$. The authors close by noting the method also computes convolutions and can be extended to complex data by splitting real and imaginary parts.

Load-bearing premise

The speed-up assumes that one run of Quantum Amplitude Estimation over the superposition of all shifts yields the individual cross-correlation value $C_l$ for every shift $l$, but the circuit as written leaves the shift register entangled with the value register, so reading all $N$ values would require roughly $N$ repetitions.

Editorial extensions

If this is right

If the cross-correlation algorithm works as stated, template matching and shift detection between two $N$-sample signals can be handed to a quantum subroutine that returns the correlation values in a quantum register in $O(\sqrt{N})$ QAE iterations.
If the EMML update is correct, each iteration of expectation-maximization maximum likelihood runs in $O(N)$ per pixel rather than $O(N^2\log N)$, a quadratic gain for single-particle reconstruction and related iterative image restoration.
Because convolution is a correlation with one array reversed, the same circuit computes convolutions, extending the result to convolution-based signal processing.
The complex-data extension stated in the paper implies that complex-valued correlations can be assembled from four real-valued quantum correlations without changing the asymptotic cost.

Reading between the lines

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

A concrete test that goes beyond the paper: count the total number of measurements needed to recover the full vector $(C_0,\dots,C_{N-1})$ from the circuit of Section 3. If the shift register must be measured to label which $C_l$ was sampled, the reported $O(\sqrt{N})$ is the cost per value, not per full cross-correlation, and the end-to-end improvement disappears.
The probability-encoding trick suggests a general recipe: any pairwise sum of products of non-negative numbers can be written as the probability of a condition on two registers and estimated by QAE. That would cover convolution layers in neural networks, as the paper hints, but also other kernel sums such as weighted template overlaps.
A natural numerical check of the EMML claim is to run the circuit on $N=4$ or $8$ arrays in a simulator and compare the measured angles against the classically computed $x^{t+1}_{j,k}$; small-$N$ deviations would reveal whether the normalized-data assumption (probability weights summing to $1$) distorts the correlation values in noisy, low-amplitude image data.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

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

Colleague,

This paper's core idea is real: instead of the usual QFT-based attempt, they encode data in probabilities and use Quantum Amplitude Estimation to compute cross-correlations. That is not in the prior work they cite, so the novelty is genuine. The QAE eigenvector algebra in Sections 3.2 and 4.2 is mostly correct as far as it goes. This is not a crackpot paper; it reads like a plausible construction with a couple of load-bearing gaps.

The first gap is the cross-correlation readout. Equation (12) leaves the shift register entangled with the phase registers, and the paper never says how to separate them. Measuring gives one random shift with a noisy estimate. Getting all N correlations costs O(N) repetitions, so the claimed O(√N) complexity does not apply to the stated task. Calling the output a "stored" quantum array is not enough; without a readout that yields the values, the algorithm is incomplete.

The second gap is worse. Section 4.2 claims a quadratic speedup over the classical O(N² log N) EMML update. But one run of their circuit outputs a single pixel x^{t+1}_{j,k} — see Eq. (20) and Algorithm steps 5–6. A full update needs all N² pixels, so it takes N² executions. Each execution uses M = αN controlled-G operations, giving O(N³) per update. Compared to O(N² log N) by FFT, that is a slowdown, not a speedup. The classical baseline they compare against computes all correlations at once; the quantum object they count is per-pixel. Apples to oranges.

There are smaller issues: no error analysis for the QAE estimates, which is significant because the target probabilities are ~1/N or ~1/N²; the affine normalization x_j = a x'_j + b changes the cross-correlation in a way that is hand-waved; and the real, non-negative, sum-to-one restriction is acknowledged but not examined.

Bottom line: this is a decent first idea, but the central claims do not hold up. The math that is there is mostly right; the algorithmic conclusions do not follow. I would not send it to referees as submitted. It needs a fundamental rethink of the output model — the approach might work for sampling correlations, but not as a full computation. I would not cite it.

—

Referee Report

3 major / 5 minor

Summary. The manuscript proposes two quantum algorithms based on Quantum Amplitude Estimation (QAE). The first algorithm encodes two nonnegative, normalized data arrays in quantum amplitudes, creates a superposition over cyclic shifts, and claims to compute and store all discrete cross-correlation values C_l in O(√N) time. The second algorithm adapts this construction to one iteration of the expectation maximization maximum likelihood (EMML) update, and claims a complexity of O(N) per update, which the authors describe as a quadratic improvement over the classical O(N^2 log N) FFT-based computation. The paper contains circuit diagrams, operator definitions, and eigenstate decompositions for both algorithms.

Significance. If the claimed speedups were valid, the paper would open a new application area for quantum computing in signal and image processing, with potential impact on template matching, drift correction, and cryo-EM reconstruction. The paper also states its main limitation clearly: the algorithms apply only to real, nonnegative data. The derivations are direct overlap calculations with no fitted parameters, so circularity is not a concern here. However, the two central claims are not supported: the cross-correlation algorithm does not specify a readout procedure that yields all N values in one shot, and the EMML complexity comparison compares a per-pixel quantum cost with a full-image classical cost. These issues are load-bearing for the advertised speedups.

major comments (3)

[Section 3.2, Eq. (12)] The output state in Eq. (12) leaves the shift register |l> entangled with the phase register |Mθ_l/π>. A single projective measurement therefore yields one random shift l together with an estimate of C_l, not the full array of N cross-correlation values. The manuscript gives no measurement, post-processing, or repeated-sampling strategy that would separate the registers and extract all C_l values, so the claimed O(√N) complexity for computing all cross-correlations is unsupported; extracting all N values would require on the order of N repetitions.
[Section 4.2, Eqs. (15)-(20), Algorithm steps 5-6] The EMML circuit estimates exactly one new pixel value x^{t+1}_{j,k} for a fixed index (j,k) because the shift operator S_{j,k} is applied to the second copy for that fixed (j,k) and the final measurement yields a single angle Θ_{j,k}. Since the full update in Eq. (13) requires all N^2 values x^{t+1}_{j,k}, one full EMML update needs N^2 executions. With M = αN controlled-G operations per execution, the total cost per update is O(N) · N^2 = O(N^3), not O(N). Comparing this with the classical O(N^2 log N) FFT cost for the full 2D cross-correlation compares a per-pixel cost with a full-image cost, so the claimed quadratic speed-up in the abstract and in Section 4.2 is invalid.
[Sections 3.2 and 4.2] No error analysis is provided for the QAE estimates. For cross-correlation values C_l of order 1/N, the angle θ_l is of order 1/√N, and the choice M = α√N gives a phase-estimation error of order 1/M ~ 1/(α√N), which is comparable to θ_l itself; the relative error of the estimated cross-correlation is therefore of order one. Similarly, for pixel values of order 1/N^2 in the 2D EMML setting, the choice M = αN yields relative errors of order one. A rigorous bound on the estimation error is needed to justify either complexity claim as stated.

minor comments (5)

[Section 3.1, Eq. (5)] The encoding operators should read AA|0> = Σ √(x_A^j)|j> and AB|0> = Σ √(x_B^j)|j>; as printed, the states Σ x_j|j> are not normalized under the stated condition Σ x_j = 1.
[Section 3.2] The statement 'Since ⟨C_l⟩ = 1/N' is an average over shifts; individual C_l can be much smaller or even zero, so the choice M = α√N is not a worst-case guarantee for the estimation error.
[Section 3, Algorithm] The algorithm for cross-correlation computation has no measurement or classical output step; as written, it prepares a quantum state rather than outputting the cross-correlation values, so the phrase 'computing and storing' should be clarified.
[Section 3] The affine rescaling x_j = a x'_j + b changes the cross-correlation by additive and multiplicative terms that depend on a and b; the manuscript should provide the explicit inverse transformation for C_j instead of only stating that the result can be scaled back.
[Section 4] The notation for the new pixel value is inconsistent: the text uses x^{t+1}_j in one place and x^{t+1}_{j,k} elsewhere; the 2D index should be used consistently throughout.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the algorithms directly compute the advertised quantities via quantum amplitude estimation, with no fitted parameters or self-citation load-bearing steps.

full rationale

The paper's derivation chain is self-contained rather than circular. The cross-correlation algorithm encodes the data arrays into amplitudes, defines a Grover operator whose eigenvalue phases satisfy sin^2(theta_l) = C_l, and then uses quantum amplitude estimation to read out those phases. The target quantity C_l is literally the probability amplitude overlap defined by the encoded data, so estimating it is a direct computation, not a prediction from fitted parameters. Similarly, the EMML algorithm defines sin^2(theta_{j,k}) = x^{t+1}_{j,k} in Eq. (16) and then estimates that angle with QAE; again the quantity is a function of the input and template arrays, not an input smuggled in as an output. No parameters are fitted to a subset of data and then called predictions. There are no self-citations; the cited works are standard external references such as Brassard et al. for QAE and Dempster et al. for EMML, and the authors' own previous work is not invoked as load-bearing support. The substantive weaknesses identified by readers—such as the entangled shift register in Eq. (12) lacking a clear measurement separation, and the complexity comparison in Section 4.2 comparing one pixel estimate against the full N^2 classical computation—are correctness or complexity-analysis concerns, not circularity. They do not involve the derivation reducing to its inputs by construction. Therefore the appropriate circularity score is 0.

Assumptions & free parameters 2 free parameters · 3 assumptions · 0 invented entities

The central claims rest on standard QAE plus three unstated assumptions: unit-cost state preparation, recoverable normalization, and parallel readout of superposition-based estimates. The last is the most fragile and is not justified in the text.

free parameters (2)

QAE precision register size M = M = alpha * sqrt(N) for cross-correlation; M = alpha * N for EMML
M determines the number of Grover iterations and hence the estimation precision. The paper chooses alpha much less than N arbitrarily and does not relate alpha to the desired accuracy, so the precision of the estimated cross-correlations is uncharacterized.
Normalization constants a and b = chosen per dataset
Used to make data non-negative and sum to 1; the paper states recovery is possible but does not give the explicit inversion formula.

assumptions (3)

domain assumption Amplitude encoding operators A_A, A_B, A_I, A_T have unit cost.
Sections 3 and 4 state 'For simplicity we assume that the complexity of these operators is 1'. In practice, preparing arbitrary amplitude-encoded states requires O(N) gates or QRAM, which would eliminate the claimed speedup.
domain assumption The data can be linearly transformed to satisfy x_j >= 0 and sum x_j = 1 without changing the cross-correlation topology.
Section 3 states the transform x_j = a * x'_j + b and claims C_j can be scaled back, but the effect on the computed cross-correlations is only asserted, not derived.
ad hoc to paper The QAE applied to a superposition over shifts yields individual cross-correlation estimates.
Section 3.2, Eq. (12) leaves the phase register entangled with the shift register; the paper never explains how to extract all C_l, and a direct measurement samples a random l.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Quantum computing for accelerating cross-correlations intensive applications in signal processing." pith.science (2026). https://pith.science/paper/XDW6QZWG

@misc{pith2026190809519,
  author       = {Pith},
  title        = {Pith review of: Quantum computing for accelerating cross-correlations intensive applications in signal processing},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/XDW6QZWG}},
  note         = {Machine review of arXiv:1908.09519}
}

read the original abstract

Despite their importance as subfields of mathematics and engineering, signal and image processing have not received much attention in the field of quantum computation. Cross-correlations are instrumental to all the aforementioned fields. In this article we help fill this void by providing two quantum algorithms, one for computing and storing cross-correlations, and one for implementing the expectation maximization maximum likelihood algorithm. In addition we show that the quantum expectation maximization maximum likelihood algorithm has a quadratic speed-up compared to the classical analog.

Figures

Figures reproduced from arXiv: 1908.09519 by the authors.

**Figure 2.** Quantum circuit for the calculation of a new [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

21 extracted references · 20 canonical work pages

[1]

Saxton, J

W.O. Saxton, J. Frank, Ultramicroscopy 2, 219-227 (1976)

work page 1976
[2]

Zhang, E

S. Zhang, E. Palovcak, J.-P. Armache, Y. Cheng, and D. Agard, Nature Methods 30, 331-332 (2017)

work page 2017
[3]

Electron Tomography

J. Frank et al., "Electron Tomography", Chap.6, Springer (1992)

work page 1992
[4]

Koster, and W

A. Koster, and W. Deruijter, Ultramicroscopy 40(2), 89-107 (1992)

work page 1992
[5]

C.Best, S.Nickell, andW.Baumeister, Meth- ods in cell biology79, 615-638 (2007)

work page 2007
[6]

Dempster, N.M

A.P. Dempster, N.M. Laird, D.B. Rubin, J. Royal Stat. Soc. Series B,39 1, 1-38 (1977)

work page 1977
[7]

Sigworth, Journal of Structural Biology 122, 328-339 (1998)

F. Sigworth, Journal of Structural Biology 122, 328-339 (1998)

work page 1998
[8]

S.Scheres, Journal of Structural Biology,180, 519-530 (2012)

work page 2012

Show all 21 references

[9]

Cooley, P.A.W

J.W. Cooley, P.A.W. Lewis, and P.D. Welch, Proceedings of the IEEE55, 10 (1967)

1967
[10]

Quantum algorithm zoo

S. Jordan, "Quantum algorithm zoo", NIST, 22 April 2011. [Online]. Available: https://math.nist.gov/quantum/zoo/

2011
[11]

Lomont, arXiv:quant-ph/0309070 (2003)

C. Lomont, arXiv:quant-ph/0309070 (2003)

2003 arXiv
[12]

Coppersmith, IBM Research Report RC19642 (1994)

D. Coppersmith, IBM Research Report RC19642 (1994)

1994
[13]

F. Yan, A. Iliyasu and S. Venegas-Andraca, Quantum information processing, 15, 1-35 (2016)

2016
[14]

Brassard, P

G. Brassard, P. Hoyer, M. Mosca and A. Tapp, Quantum Computation and Quantum Information, AMS Contemporary Mathemat- ics, 305, 53-74 (2002)

2002
[15]

Terhal and J

B. Terhal and J. Smolin, Phys. Rev. A58, 1822 (1998)

1998
[16]

Quantum Counterfeit Coin Problems

K. Iwama, H. Nishimura, R. Raymond, and J. Teruyama, "Quantum Counterfeit Coin Problems", Proceedings of 21st International 6 Symposium on Algorithms and Computation (ISAAC2010), LNCS 6506, 73-84 (2010)

2010
[17]

Sundberg, Scandinavian Journal of Statistics 1, 49-58 (1974)

R. Sundberg, Scandinavian Journal of Statistics 1, 49-58 (1974)

1974
[18]

Sundberg, Commun

R. Sundberg, Commun. Stat. Simul. Com- put. 5, 55-64 (1976)

1976
[19]

LeCun, Y

Y. LeCun, Y. Bengio, and G. Hinton, Nature 521, 436 (2015)

2015
[20]

The handbook of brain theory and neural networks

Y. LeCun and Y. Bengio, "The handbook of brain theory and neural networks" 3361, 10 (1995)

1995
[21]

Advances in Neural Information Pro- cessing Systems

A. Krizhevsky, I. Sutskever, and G. E. Hin- ton, "Advances in Neural Information Pro- cessing Systems" (2012) 7

2012

Pith tools

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

[1] [1]

Saxton, J

W.O. Saxton, J. Frank, Ultramicroscopy 2, 219-227 (1976)

work page 1976

[2] [2]

Zhang, E

S. Zhang, E. Palovcak, J.-P. Armache, Y. Cheng, and D. Agard, Nature Methods 30, 331-332 (2017)

work page 2017

[3] [3]

Electron Tomography

J. Frank et al., "Electron Tomography", Chap.6, Springer (1992)

work page 1992

[4] [4]

Koster, and W

A. Koster, and W. Deruijter, Ultramicroscopy 40(2), 89-107 (1992)

work page 1992

[5] [5]

C.Best, S.Nickell, andW.Baumeister, Meth- ods in cell biology79, 615-638 (2007)

work page 2007

[6] [6]

Dempster, N.M

A.P. Dempster, N.M. Laird, D.B. Rubin, J. Royal Stat. Soc. Series B,39 1, 1-38 (1977)

work page 1977

[7] [7]

Sigworth, Journal of Structural Biology 122, 328-339 (1998)

F. Sigworth, Journal of Structural Biology 122, 328-339 (1998)

work page 1998

[8] [8]

S.Scheres, Journal of Structural Biology,180, 519-530 (2012)

work page 2012