{"id":"c2937ac5-c9cd-47d4-819e-cc0d99c63ce2","arxiv_id":"2507.19658","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"Convolution is reformulated as a doubly block-Toeplitz matrix product estimated by SWAP-test inner products, but the claimed quantum speedup is not established.","lead":"This paper proposes a quantum algorithm that turns convolution into a sparse matrix multiplication and estimates the outputs with a SWAP test. It claims low circuit depth and logarithmic scaling, but the end-to-end advantage is not derived.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Sampling cost is omitted from the complexity comparison: Eq. 17's 1/(HWC) suppression makes readout require polynomially many shots, so the advertised logarithmic scaling under sparsity is unsupported.","rationale":"The paper's strongest claim, stated in the abstract and Section 3.3, is that sparse-image convolution can be performed with logarithmic scaling in input size and shallow circuit depth. The operational content is K~X = Y in Eq. 8, with readout through Eqs. 16–17. For that claim to hold, the number of circuit executions needed to extract Y must be bounded by something polylogarithmic in HWC. The paper does not provide such a bound. Equation 17 shows that any fixed output position appears with probability suppressed by the ambient dimension HWC, so binomial sampling to fixed precision requires Ω(HWC/ε²) shots for one position, and the full output tensor can only be worse. The reader's weakest-assumption statement identifies exactly this gap in Eqs. 16 and 17, and my reading agrees. I additionally note that Eq. 16's normalization is internally inconsistent, which reinforces the conclusion that the sampling analysis was not carried through. The paper does contain a legitimate reformulation of convolution as a doubly block-Toeplitz matrix product, and the discussion of sparsity-aware QRAM state preparation is reasonable, but those pieces do not remove the readout bottleneck. A routine that samples positions with probability proportional to convolution values is not the same as computing the convolution tensor, and the paper itself concedes that reconstructing the full output requires repeated measurements without quantifying the repetition. The verdict of REJECT is therefore appropriate.","tokens_in":16101,"tokens_out":8447,"duration_ms":96459,"concrete_test":"Instrument Eqs. 16–17 as a shot-counting model: for a concrete instance (e.g., H=W=32, C=3, R=S=3, M=64, N=1, ε=0.01), count the number of circuit executions needed to estimate every entry of Y to additive error ε using binomial confidence intervals from the probabilities in Eq. 17. Then repeat with the corrected normalization 1/√(EFM·N). If the total shot count scales as Ω(EFM·N·HWC/ε²) under Eq. 17, or as Ω(EFM·N/ε²) under the corrected normalization, rather than polylog(HWC), the logarithmic-scaling claim is falsified.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central efficiency claim—'scales logarithmically with input size under sparsity'—rests on Table 2, which lists QRAM complexity, circuit depth, preprocessing time, and state-preparation cost but no measurement cost. The actual readout scheme in §3.2 superposes all output positions, and Eq. 17 gives P0(p,q) = P_pq/(HWC) = (1 + ⟨Kp|Xq⟩)/(2HWC). The written state in Eq. 16 is not normalized: a uniform superposition over (p,q) ∈ [EFM]×[N] should carry 1/√(EFM·N), not 1/√(HWC). After the natural correction, each output pair appears with probability roughly 1/(EFM·N) per trial. Estimating the inner products to additive error ε from binary counts then requires Ω(EFM·N/ε²) total shots for the full output tensor; if Eq. 17's HWC denominator is kept, the requirement grows by an additional factor of HWC. In either case the shot count is polynomial in the number of output positions, not polylogarithmic in input size. The O~(√nnz(x)) QRAM complexity and O~(1) circuit depth in Table 2 describe only one circuit execution, not the cost of actually producing the convolution output. The variational extension is only sketched and does not supply a different readout mechanism. Because no amplitude-estimation or alternative measurement strategy is provided, the sampling bottleneck is load-bearing and the central claim fails as stated.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a quantum algorithm for convolution based on a doubly block-Toeplitz (DBT) reformulation of the convolution kernel, sparse QRAM state preparation, and an inner-product estimation circuit. The central operational claim is Eq. (8), K~ X = Y, where the rows of K~ encode kernel windows and X is the flattened input. The authors claim logarithmic scaling with input size under sparsity, low circuit depth, reduced sampling overhead, and easy integration into hybrid quantum-classical pipelines, and they sketch a variational extension for learned filters.","tokens_in":16351,"tokens_out":4572,"duration_ms":55411,"significance":"If the central claim were established, a quantum convolution layer with polylogarithmic resource scaling would be a significant practical advance for quantum machine learning, because convolution is the dominant computational primitive in CNNs. The DBT reshaping itself is a standard classical technique, and the paper's contribution is the proposed combination with sparse QRAM and a low-depth inner-product circuit. The paper does not provide machine-checked proofs, numerical simulations, or hardware results; its assessment rests on asymptotic resource claims. As detailed below, the central scalability claim is not supported once measurement/readout cost is counted, so the significance is currently limited to a heuristic proposal rather than a validated algorithm.","major_comments":[{"comment":"The sampling cost for reading out the full output tensor is omitted, and this omission is load-bearing for the abstract's central claim of logarithmic scaling. The uniform superposition in Eq. (16) is over (p,q) ∈ [EFM] × [N], so the normalization coefficient should be 1/√(EFM·N), not 1/√(HWC); as written the state is not normalized. With the corrected normalization, the probability of observing a given output pair is P0(p,q) = P_pq/(EFM·N), and Eq. (17)'s denominator HWC makes the suppression even stronger. Estimating each inner product to additive error ε from binary counts therefore requires Ω(EFM·N/ε²) total shots for the full output tensor, and the constant-factor suppression of Eq. (17) only increases this cost. Table 2 lists QRAM complexity, circuit depth, preprocessing, and state preparation cost but no measurement cost; consequently the advertised 'logarithmic scaling' applies only to a single circuit execution, not to producing the convolution output Y. This directly invalidates the paper's main efficiency claim as stated.","section":"§3.2, Eqs. (16)-(17), and Table 2"},{"comment":"The manuscript gives two incompatible inner-product estimation formulas. Eq. (2), for the standard SWAP test, yields P(0) = (1 + |⟨ψ|φ⟩|²)/2, which is quadratic in the inner product. Eq. (14) yields P_pq(0) = (1 + ⟨K_p|X_q⟩)/2, which is linear in the inner product. These correspond to different circuits: Eq. (14) is correct for the controlled-state-preparation (Hadamard-test) circuit in Eqs. (12)-(13), not for the controlled-SWAP circuit described in §2.1. The text says the adapted circuit 'computes |⟨ψ|φ⟩|²' but then derives a linear real-part expression. The paper should either use the standard SWAP test and explain how the squared output is converted back to Y_pq (losing sign information), or explicitly identify the circuit as a Hadamard test and justify the recovery of signed inner products. As written, the algorithmic description is internally inconsistent.","section":"§2.1 Eq. (2) versus §3.2 Eq. (14)"},{"comment":"The manuscript acknowledges that 'to reconstruct the full output tensor Y with a desired precision, the state preparation and measurement process must be repeated multiple times,' but it never quantifies this repetition cost. The claim that 'a small number of measurements can be sufficient to recover the dominant components of Y' is asserted without a concentration bound, a sparsity model, or an error metric; it does not justify full tensor recovery. Moreover, the variational extension in §3.3 replaces the filter state by a parameterized state |θ⟩ but retains the same inner-product estimation scheme, so it does not provide a different readout mechanism; the sampling bottleneck identified above therefore also applies to the proposed hybrid quantum-classical learning loop.","section":"§3.2, final paragraph, and §3.3 variational extension"}],"minor_comments":[{"comment":"The notation is confusing: 'For a matrix A ∈ ℝ^{n×n}, we denote A ∈ ℝ^{n×n} as the number of nonzero entries in A' should define nnz(A) or a separate symbol; the current sentence makes A mean both a matrix and a scalar.","section":"§2.3, text after Eq. (3)"},{"comment":"The placeholder 'for cxxx i ∈ nnz(v)' appears in the sparse-vector illustration and should be corrected.","section":"§2.3"},{"comment":"The claimed structural savings of DBT reshaping over the Toeplitz patch matrix would be much easier to verify if the figures used a single concrete example with explicit nonzero counts; as printed, the dense figures are hard to read.","section":"Figure 6 and Figure 7"},{"comment":"Several citations appear mismatched in the text: [16] is described both as Chen et al. and as Kerenidis et al., and [35] is used for both Canny edge detection and augmented QRAM; the reference numbering should be checked.","section":"References"},{"comment":"The phrase 'reduced sampling overhead' in the abstract is not quantified anywhere in the paper; given Eq. (17), the sampling overhead is actually amplified relative to per-element SWAP testing, so this phrase is misleading.","section":"Abstract and §3.3"}],"recommendation":"reject","confidential_remarks":"The central complexity claim fails because readout measurement cost is not counted and the normalization in Eq. (16)-(17) is erroneous. This is not a local fix: once the measurement cost is included, the algorithm's scaling is polynomial in the output dimensions rather than polylogarithmic. The DBT reformulation is standard, and the paper provides no numerical validation or alternative readout strategy. The manuscript could potentially be repositioned as a heuristic sampling-based feature extractor, but as submitted it does not support the advertised claims."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know this before reading: the central complexity claim is unsupported. The paper reformulates convolution as a sparse doubly block-Toeplitz matrix product and uses a SWAP test to estimate inner products, then claims logarithmic scaling in input size under sparsity. The gap is that the readout cost is never counted. Eq. 17 gives success probability per output position as (1+⟨K|X⟩)/(2HWC). Even after fixing the normalization of Eq. 16—the uniform superposition should have 1/√(EFM·N), not 1/√(HWC)—each inner product is recovered from binary counts with probability O(1/(output size)), so producing the full output tensor requires Ω(EFM·N/ε²) shots. That is polynomial in the number of output positions, not polylogarithmic in input size. Table 2 lists QRAM complexity and circuit depth but no measurement cost, so the 'reduced sampling overhead' claim in the abstract has no basis in the equations.\n\nWhat is genuinely okay: the doubly block-Toeplitz formulation is standard, but the paper explains it clearly with figures. The batch extension is a natural and correct way to handle multiple inputs. The paper also honestly notes that the SWAP-test approach is not learnable, which is a real limitation, and then sketches a variational idea without derivation. That is more candid than many papers.\n\nThe soft spots are the load-bearing one above, plus two smaller issues. Eq. 14 writes the SWAP-test probability as (1+⟨K|X⟩)/2, but the standard result (Eq. 2) has the squared modulus, (1+|⟨K|X⟩|²)/2. If they are using a different test that gives the sign, they should cite or derive it. Eq. 16's normalization is wrong as written—the coefficient should be 1/√(EFM·N), not 1/√(HWC)—which is related to the sampling issue. The variational extension is a sketch, not a method, so it doesn't rescue the readout problem.\n\nShould a serious editor send this to peer review? Yes. The question of whether sampling can be reduced via amplitude estimation or some other trick is worth a rigorous check, and the DBT formulation could be useful to someone building on it. But as it stands, the main claim fails.","headline":"Clear writeup of doubly block-Toeplitz convolution, but the advertised logarithmic scaling omits measurement cost and does not follow.","tokens_in":16941,"tokens_out":3440,"would_cite":false,"duration_ms":33965,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["81P68","68Q12"],"pacs":["03.67.Lx"],"model":"deepseek-v4-flash","headline":"Quantum convolution is recast as a sparse matrix product, cutting state-preparation overhead.","keywords":["quantum convolution","doubly block-Toeplitz matrix","SWAP test inner product estimation","sparse quantum state preparation","augmented QRAM","quantum machine learning","convolutional neural networks","NISQ algorithms"],"falsifier":"Count the measurements implied by Eqs. (16) and (17). Observing a particular output position $(p,q)$ has probability about $1/(2HWC)$, so estimating all $EFM \\times N$ inner products to additive error $\\varepsilon$ needs on the order of $EFM \\cdot N \\cdot HWC / \\varepsilon^2$ repetitions. A resource count or a small simulation that carries this sampling cost through would settle whether the claimed logarithmic scaling survives.","tokens_in":15856,"feed_emoji":"⚛️","tokens_out":7657,"duration_ms":80208,"temperature":0.7,"pith_summary":"The paper tries to establish that a convolutional layer, one of the most expensive operations in a neural network, can be rewritten as a single sparse matrix product that a quantum computer can evaluate with shallow circuits. The reformulation flattens the input image and reshapes the filter tensor into a doubly block-Toeplitz matrix, so no redundant patch-by-patch copy of the input is needed. Convolution outputs are then read out with a low-depth inner-product circuit, the SWAP test, applied between kernel rows and input columns. If the claim is right, sparse images and kernels would be preparable in polylogarithmic time and the circuit depth would stay roughly constant, making quantum convolutional layers practical components of hybrid quantum-classical machine learning pipelines.","feed_headline":"Convolution becomes one sparse matrix product on a quantum chip","feed_subtitle":"A doubly block-Toeplitz filter matrix plus SWAP-test inner products removes redundant input prep.","key_machinery":"The load-bearing object is the doubly block-Toeplitz matrix $\\tilde{K}$ of Eq. (8): a reshaping of the four-dimensional kernel tensor into a sparse matrix whose rows are kernel windows aligned with valid output positions. This object carries the argument because it converts convolution into a matrix-vector product without expanding the input into a redundant patch matrix. The companion mechanism is the SWAP-test inner-product estimator, which encodes a kernel row and an input column, interferes them through a controlled exchange, and measures an ancilla to learn the squared inner product; together with key-value QRAM (quantum random access memory) sparse state preparation, it is what keeps both the state preparation and the circuit depth tied to sparsity rather than to image area.","core_discovery":"The central claim is that convolution $\\tilde{K} \\cdot X = Y$ is an exact rewriting of the convolutional layer, where $\\tilde{K}$ is a doubly block-Toeplitz sparse matrix constructed once from the kernel tensor and $X$ is the flattened input with no duplicated entries. Each output entry is a normalized inner product between a row of $\\tilde{K}$ and a column of $X$; the paper estimates these inner products with a generalized SWAP test at circuit depth $\\widetilde{O}(1)$, using key-value QRAM state preparation whose cost scales with the number of nonzero entries rather than the full input size. The authors argue that this removes the redundant preparation costs of earlier Toeplitz patch-matrix methods, supports batched convolution by running the estimation over all $(p,q)$ pairs in superposition, and achieves logarithmic qubit scaling, $O(\\log HWC + \\log N)$. They present this as a NISQ-friendly route to quantum feature extraction.","pith_inferences":["Editorial extension: the paper's resource table does not count the number of SWAP-test repetitions needed to reconstruct all outputs; if that shot count is included, the scaling with input size depends on $HWC$ through the probability in Eq. (17).","Editorial extension: the same doubly block-Toeplitz reshaping could be paired with amplitude estimation instead of raw SWAP sampling, improving the error scaling from $1/\\varepsilon^2$ to $1/\\varepsilon$; the paper does not explore this.","Editorial extension: the reshaping itself is a classical preprocessing trick, so it could also speed up classical convolution via structured matrix libraries, independent of the quantum readout."],"forward_implications":["A single flattened input state suffices for one convolution layer, so per-input preparation cost does not grow with the number of kernel positions.","The kernel reshaping is done once per filter bank, classically, and is then amortized over many inputs, which suits streaming inference.","Batch convolution over many images and many filters fits naturally in the same circuit by superposing the $(p,q)$ index registers.","Zero padding in the reshaped kernel matrix does not change the asymptotic cost, because preparation complexity depends on the number of nonzero entries.","The qubit count grows as $O(\\log HWC + \\log N)$, so spatial resolution and batch size add only logarithmically to the quantum register."],"supporting_citations":[{"why":"Supplies the prior Toeplitz/circulant convolution encoding whose redundant input patchification this method claims to remove.","marker":"[16]"},{"why":"Provides the augmented-QRAM key-value sparse state preparation model that determines the algorithm's encoding cost.","marker":"[31]"},{"why":"Introduces the SWAP-test inner-product estimator used as the low-depth readout.","marker":"[20]"},{"why":"Provides the generalized SWAP-test circuit that the algorithm adapts for controlled kernel and input state preparation.","marker":"[38]"},{"why":"Gives the multi-SWAP protocol that supports the batched inner-product estimation over many filters and inputs.","marker":"[24]"},{"why":"Underlies the amplitude-amplification step quoted for sparse state preparation.","marker":"[14]"}],"fun_headline_variants":["Sparse Toeplitz encoding turns convolution into one matrix product","Quantum convolution via SWAP-test inner products at low depth","Logarithmic-scaling quantum convolution via sparse matrix","Doubly block-Toeplitz trick simplifies quantum convolution","Batched quantum convolution with single QRAM preparation"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that reading out the convolution output is cheap: the paper counts the cost of preparing sparse quantum states but not the many repeated measurements needed to estimate every output entry from probabilities that are tiny, roughly one over the image size.","fun_headline_variants_meta":{"raw":{"variants":["Sparse Toeplitz encoding turns convolution into one matrix product","Quantum convolution via SWAP-test inner products at low depth","Logarithmic-scaling quantum convolution via sparse matrix","Doubly block-Toeplitz trick simplifies quantum convolution","Batched quantum convolution with single QRAM preparation"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000533,"raw_usage":{"total_tokens":2564,"prompt_tokens":945,"completion_tokens":1619,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":561,"completion_tokens_details":{"reasoning_tokens":1539}},"tokens_in":561,"tokens_out":1619,"duration_ms":12055,"temperature":1.0,"reasoning_tokens":1539,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T14:10:23.299453+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Count the measurements implied by Eqs. (16) and (17). Observing a particular output position $(p,q)$ has probability about $1/(2HWC)$, so estimating all $EFM \\times N$ inner products to additive error $\\varepsilon$ needs on the order of $EFM \\cdot N \\cdot HWC / \\varepsilon^2$ repetitions. A resource count or a small simulation that carries this sampling cost through would settle whether the claimed logarithmic scaling survives.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the prior Toeplitz/circulant convolution encoding whose redundant input patchification this method claims to remove."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the augmented-QRAM key-value sparse state preparation model that determines the algorithm's encoding cost."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the generalized SWAP-test circuit that the algorithm adapts for controlled kernel and input state preparation."},{"cited_title":"Quantum Inf","cited_arxiv_id":null,"evidence_quote":"Gives the multi-SWAP protocol that supports the batched inner-product estimation over many filters and inputs."}],"review_version":1}