{"id":"df76e478-4111-4fe2-a8e5-dfb7e4e7b764","arxiv_id":"1908.09519","paper_version":2,"verdict":"REJECT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":2,"one_line_summary":"The paper presents QAE-based circuits for cross-correlation and EMML, but the claimed speedup relies on an unsupported readout procedure and an invalid comparison with classical FFT-based processing.","lead":"This paper proposes two quantum algorithms, one for cross-correlation computation and one for expectation-maximization maximum-likelihood estimation, both built on Quantum Amplitude Estimation. The authors claim a quadratic speedup, but the circuits as written compute only one output value per run and provide no way to read out all cross-correlation values.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The claimed quadratic speed-up for EMML rests on an invalid per-pixel vs full-image complexity comparison: one run outputs one pixel, so a full update costs O(N^3), not O(N).","rationale":"This is a good-faith reading. The paper tries to use QAE to turn correlation values into phase/probability outputs and to accelerate EMML. The strongest unambiguous claim is the quadratic speed-up stated in the abstract and Section 4.2. The load-bearing condition for that claim is that the quantum circuit's cost is for the same output as the classical O(N^2 log N) comparison. Section 4 and the algorithm box show it is not: the circuit is built around a chosen (j,k) shift and measures one new-data value. Repeating for all pixels multiplies the cost by N^2. This is an internal accounting inconsistency, not a disagreement with consensus, so it does not require outside assumptions. The reader's extraction objection to the cross-correlation algorithm is also real, but it is less decisive for the paper's advertised speed-up: even granting the QAE block, the EMML comparison fails. For that reason I partially agree with the reader's weakest assumption and keep a reject verdict. No formal verification or reproducible code is provided, so there is no independent support that would rescue the complexity claim. The test above is a simple audit of the number of runs; it settles the concern.","tokens_in":7623,"tokens_out":6781,"duration_ms":74756,"concrete_test":"Check the algorithm's own accounting: count the number of executions of the EMML circuit needed to produce the full array {x^{t+1}_{j,k}} for all j,k in {0,...,N-1}^2. The circuit in Section 4 and Algorithm steps 1-6 is executed once per (j,k), because the shift operator S_{j,k} and the measurement step fix a single pixel. Multiply by the M = alpha N controlled-G operations per execution to get alpha N^3. Then compare alpha N^3 with the classical FFT cost N^2 log_2 N for the same full update (e.g., N=1024, alpha=1: ~1.07e9 vs ~1.05e7). If the paper cannot provide a procedure that outputs all N^2 pixels without N^2 runs, the O(N) full-update claim is refuted.","verdict_should_be":"REJECT","load_bearing_attack":"Section 4.2 claims: \"The complexity of the algorithm is O(N), that is roughly a quadratical improvement respect to the classical complexity O(N^2 log N).\" This comparison is not between the same objects. The described quantum circuit (Fig. 2, Section 4) estimates one value x^{t+1}_{j,k}: operator S_{j,k} is applied to the second copy for fixed (j,k) (Eq. 15), the QAE output in Eq. (20) has |M theta_{j,k}/pi> in the new-data register, and Algorithm steps 5-6 measure Theta_{j,k} and compute sin^2(pi Theta_{j,k}/M) = x^{t+1}_{j,k}. Thus one execution yields exactly one pixel. The full EMML update in Eq. (13) requires all N^2 values x^{t+1}_{j,k}; obtaining them requires N^2 executions. Each execution uses M = alpha N controlled-G operations (Section 4.2), so the total cost per full update is O(N) * N^2 = O(N^3). The classical baseline O(N^2 log N) is for computing the full 2-D cross-correlation/convolution (all N^2 shifts) using FFT. A correct comparison is O(N^3) vs O(N^2 log N) per update, which is worse, not quadratically better. Even if every amplitude-estimation step is individually correct, the central speed-up claim fails.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":7968,"tokens_out":5966,"duration_ms":65325,"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":[{"comment":"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":"Section 3.2, Eq. (12)"},{"comment":"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.","section":"Section 4.2, Eqs. (15)-(20), Algorithm steps 5-6"},{"comment":"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.","section":"Sections 3.2 and 4.2"}],"minor_comments":[{"comment":"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":"Section 3.1, Eq. (5)"},{"comment":"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":"Section 3.2"},{"comment":"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":"Section 3, Algorithm"},{"comment":"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":"Section 3"},{"comment":"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.","section":"Section 4"}],"recommendation":"reject","confidential_remarks":"The central speed-up claims are invalid as presented: the cross-correlation algorithm lacks a readout that produces all N values in a single run, and the EMML algorithm estimates one pixel per execution, making the full update O(N^3) rather than O(N). These are not local presentation issues; correcting them would require changing the algorithms' output model and complexity statements, which is beyond a revision of this manuscript."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThis 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.\n\nThe 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.\n\nThe 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.\n\nThere 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.\n\nBottom 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.\n\n—","headline":"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.","tokens_in":8457,"tokens_out":4857,"would_cite":false,"duration_ms":50225,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":false},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["81P68","94A12"],"pacs":["03.67.Lx"],"model":"deepseek-v4-flash","headline":"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.","keywords":["quantum amplitude estimation","cross-correlation","expectation maximization maximum likelihood","quantum algorithm","signal processing","template matching","convolution","image processing"],"falsifier":"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})$.","tokens_in":7451,"feed_emoji":"⚛️","tokens_out":8506,"duration_ms":79726,"temperature":0.7,"pith_summary":"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.","feed_headline":"Claimed: quadratic speed-up for quantum signal processing","feed_subtitle":"Two QAE-based algorithms target the cross-correlation and expectation-maximization steps behind image alignment and drift correction.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the Quantum Amplitude Estimation primitive whose controlled-Grover phase kick produces the angle estimates that encode $C_l$.","marker":"[14]"},{"why":"Provides the FFT-based classical cross-correlation baseline with $O(N\\log N)$ complexity that the quantum algorithm is designed to beat.","marker":"[9]"},{"why":"Defines the EMML algorithm whose maximization step the paper rewrites as a single QAE per pixel value.","marker":"[6]"},{"why":"Represents the earlier claim that convolution and correlation cannot be computed by quantum means, which the paper positions itself against.","marker":"[11]"},{"why":"Supplies the quantum Fourier transform used inside QAE to read out the estimated angle.","marker":"[12]"}],"fun_headline_variants":["Quadratic speed-up claimed for quantum cross-correlation algorithm","Quantum cross-correlation algorithm promises quadratic speed-up","QAE-based quantum processing targets quadratic speed-up","Quantum algorithm for cross-correlation offers quadratic speed-up"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Quadratic speed-up claimed for quantum cross-correlation algorithm","Quantum cross-correlation algorithm promises quadratic speed-up","QAE-based quantum processing targets quadratic speed-up","Quantum algorithm for cross-correlation offers quadratic speed-up"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000749,"raw_usage":{"total_tokens":3314,"prompt_tokens":905,"completion_tokens":2409,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":521,"completion_tokens_details":{"reasoning_tokens":2347}},"tokens_in":521,"tokens_out":2409,"duration_ms":17241,"temperature":1.0,"reasoning_tokens":2347,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T11:10:16.150547+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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})$.","supporting_citations":[{"cited_title":"Brassard, P","cited_arxiv_id":null,"evidence_quote":"Supplies the Quantum Amplitude Estimation primitive whose controlled-Grover phase kick produces the angle estimates that encode $C_l$."},{"cited_title":"Cooley, P.A.W","cited_arxiv_id":null,"evidence_quote":"Provides the FFT-based classical cross-correlation baseline with $O(N\\log N)$ complexity that the quantum algorithm is designed to beat."},{"cited_title":"Dempster, N.M","cited_arxiv_id":null,"evidence_quote":"Defines the EMML algorithm whose maximization step the paper rewrites as a single QAE per pixel value."},{"cited_title":"Quantum convolution and quantum correlation algorithms are physically impossible","cited_arxiv_id":"quant-ph/0309070","evidence_quote":"Represents the earlier claim that convolution and correlation cannot be computed by quantum means, which the paper positions itself against."},{"cited_title":"Coppersmith, IBM Research Report RC19642 (1994)","cited_arxiv_id":null,"evidence_quote":"Supplies the quantum Fourier transform used inside QAE to read out the estimated angle."}],"review_version":1}