REVIEW 3 major objections 5 minor 38 references
Quantum-Efficient Convolution through Sparse Matrix Encoding and Low-Depth Inner Product Circuits
T0 review · 3 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash
Pith's one-line read Quantum convolution is recast as a sparse matrix product, cutting state-preparation overhead.
desk verdict Clear writeup of doubly block-Toeplitz convolution, but the advertised logarithmic scaling omits measurement cost and does not follow. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
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.
What would settle it
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.
Extended reading notes
Core claim
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.
Load-bearing premise
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.
Editorial extensions
If this is right
- 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.
Reading between the lines
- 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.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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.
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 (3)
- [§3.2, Eqs. (16)-(17), and Table 2] 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.
- [§2.1 Eq. (2) versus §3.2 Eq. (14)] 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.
- [§3.2, final paragraph, and §3.3 variational extension] 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.
minor comments (5)
- [§2.3, text after Eq. (3)] 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.
- [§2.3] The placeholder 'for cxxx i ∈ nnz(v)' appears in the sparse-vector illustration and should be corrected.
- [Figure 6 and Figure 7] 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.
- [References] 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.
- [Abstract and §3.3] 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.
Circularity Check
No significant circularity: the derivation reduces convolution to a doubly block-Toeplitz matrix product and estimates the resulting inner products with a standard SWAP test, with no fitted parameters or load-bearing self-citations.
full rationale
The paper's central derivation is Eq. 8, K~ X = Y, where K~ is the doubly block-Toeplitz reshaping of the convolution kernel. This is a direct algebraic identity: the entries of K~ are defined so that the matrix-vector product reproduces the summation in Eq. 7, and no target result is built into the assumption. The quantum component estimates the normalized inner products <K_p|X_q> using the SWAP test, whose probability formula in Eq. 14 is standard and externally established. The output is then recovered by multiplying by the known norms stored as QRAM metadata, which is not a fitted or circular step. The paper's self-citations in Refs. 1-3 appear only in the introductory sentence 'Quantum algorithms [1–3] have demonstrated remarkable potential' and are not used to justify the main claim. The sparsity-aware preparation results are cited to Prakash's thesis and Kerenidis-Landman-Prakash, which are independent external sources. The variational extension is openly described as a proposal rather than a derived result. The main weaknesses of the paper are correctness and completeness concerns about the normalization in Eq. 16, the omitted sampling overhead from Eq. 17, and the unsupported logarithmic scaling claim in Table 2; these are not circularity patterns, because the claimed output is not equivalent to the input by construction and no fitted parameter is renamed as a prediction.
Assumptions & free parameters
assumptions (4)
- standard math Convolution of tensor X with kernel K equals multiplication by doubly block-Toeplitz matrix K~ (Eq. 8).
- standard math SWAP test or a controlled-preparation variant estimates inner products with O(1/epsilon^2) repetitions.
- domain assumption Sparse vectors can be loaded into quantum states in O~(sqrt(nnz)) per copy using a quantum key-value map with augmented QRAM.
- domain assumption Inputs and kernels are sparse and localized, so nnz is small.
Cite this review
Pith. "Pith review of Quantum-Efficient Convolution through Sparse Matrix Encoding and Low-Depth Inner Product Circuits." pith.science (2026). https://pith.science/paper/ERHKWVWK
@misc{pith2026250719658,
author = {Pith},
title = {Pith review of: Quantum-Efficient Convolution through Sparse Matrix Encoding and Low-Depth Inner Product Circuits},
year = {2026},
howpublished = {\url{https://pith.science/paper/ERHKWVWK}},
note = {Machine review of arXiv:2507.19658}
}
read the original abstract
Convolution operations are foundational to classical image processing and modern deep learning architectures, yet their extension into the quantum domain has remained algorithmically and physically costly due to inefficient data encoding and prohibitive circuit complexity. In this work, we present a resource-efficient quantum algorithm that reformulates the convolution product as a structured matrix multiplication via a novel sparse reshaping formalism. Leveraging the observation that localized convolutions can be encoded as doubly block-Toeplitz matrix multiplications, we construct a quantum framework wherein sparse input patches are prepared using optimized key-value QRAM state encoding, while convolutional filters are represented as quantum states in superposition. The convolution outputs are computed through inner product estimation using a low-depth SWAP test circuit, which yields probabilistic amplitude information with reduced sampling overhead. Our architecture supports batched convolution across multiple filters using a generalized SWAP circuit. Compared to prior quantum convolutional approaches, our method eliminates redundant preparation costs, scales logarithmically with input size under sparsity, and enables direct integration into hybrid quantum-classical machine learning pipelines. This work provides a scalable and physically realizable pathway toward quantum-enhanced feature extraction, opening up new possibilities for quantum convolutional neural networks and data-driven quantum inference.
Figures
Figures from the paper (3 more)
Reference graph
Works this paper leans on
-
[1]
Kookani, A., Mafi, Y., Kazemikhah, P., Aghababa, H., Fouladi, K., Barati, M.: XpookyNet: advancement in quantum system analysis through convolutional neural networks for detection of entanglement. Quantum Mach. Intell. 6, 50 (2024). https://doi.org/10.1007/s42484-024-00183-y
- [2]
-
[3]
Ahmadkhaniha, A., Mafi, Y., Kazemikhah, P., Aghababa, H., Barati, M., Kolahdouz, M.: Performance Analysis of the Hardware-Efficient Quantum Search Algorithm. Int. J. Theor. Phys. 62, 168 (2023). https://doi.org/10.1007/s10773- 023-05424-7
doi:10.1007/s10773- 2023
-
[4]
Shor, P.W.: Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM Rev. 41, 303–332 (1999). https://doi.org/10.1137/S0036144598347011
-
[5]
In: Proceedings 35th Annual Symposium on Foundations of Computer Science
Shor, P.W.: Algorithms for quantum computation: discrete logarithms and factoring. In: Proceedings 35th Annual Symposium on Foundations of Computer Science. pp. 124–134 (1994)
work page 1994
-
[6]
In: Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing
Grover, L.K.: A Fast Quantum Mechanical Algorithm for Database Search. In: Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing. pp. 212–219. Association for Computing Machinery, New York, NY, USA (1996)
work page 1996
-
[7]
Long, G.L.: Grover algorithm with zero theoretical failure rate. Phys. Rev. A. 64, 22307 (2001). https://doi.org/10.1103/PhysRevA.64.022307
-
[8]
Toyama, F.M., van Dijk, W., Nogami, Y.: Quantum search with certainty based on modified Grover algorithms: optimum choice of parameters. Quantum Inf. Process. 12, 1897–1914 (2013). https://doi.org/10.1007/s11128-012-0498-0
Show all 38 references
-
[9]
Harrow, A.W., Hassidim, A., Lloyd, S.: Quantum Algorithm for Linear Systems of Equations. Phys. Rev. Lett. 103, 150502 (2009). https://doi.org/10.1103/PhysRevLett.103.150502
2009 doi
-
[10]
Clader, B.D., Jacobs, B.C., Sprouse, C.R.: Preconditioned Quantum Linear System Algorithm. Phys. Rev. Lett. 110, 250504 (2013). https://doi.org/10.1103/PhysRevLett.110.250504
2013 doi
-
[11]
Presented at the (2013)
Gall, F.: Quantum Algorithms for Matrix Multiplication. Presented at the (2013)
2013
-
[12]
In: Ravi, R
Le Gall, F., Nishimura, H.: Quantum Algorithms for Matrix Products over Semirings. In: Ravi, R. and Gørtz, I.L. (eds.) Algorithm Theory -- SWAT 2014. pp. 331–343. Springer International Publishing, Cham (2014)
2014
-
[13]
A.Yu.Kitaev: Quantum measurements and the Abelian Stabilizer Problem, (1995)
1995
-
[14]
Quantum Comput
Brassard, G., Høyer, P., Mosca, M., Tapp, A.: Quantum amplitude amplification and estimation. Quantum Comput. Inf. 53–74 (2002). https://doi.org/10.1090/conm/305/05215
2002 doi
-
[15]
Science (80-
Farhi, E., Goldstone, J., Gutmann, S., Lapan, J., Lundgren, A., Preda, D.: A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem. Science (80-. ). 292, 472–475 (2001). https://doi.org/10.1126/science.1057726
2001 doi
-
[16]
Kerenidis, I., Landman, J., Prakash, A.: Quantum Algorithms for Deep Convolutional Neural Networks, (2019)
2019
-
[17]
Shao, C.: Quantum Algorithms to Matrix Multiplication, (2018)
2018
-
[18]
V, Hopcroft, J.E.: The design and analysis of computer algorithms
Aho, A. V, Hopcroft, J.E.: The design and analysis of computer algorithms. Pearson Education India (1974)
1974
-
[19]
In: 8th Innovations in Theoretical Computer Science Conference
Kerenidis, I., Prakash, A.: Quantum Recommendation Systems. In: 8th Innovations in Theoretical Computer Science Conference. pp. 1–21 (2017)
2017
-
[20]
Buhrman, H., Cleve, R., Watrous, J., de Wolf, R.: Quantum Fingerprinting. Phys. Rev. Lett. 87, 167902 (2001). https://doi.org/10.1103/PhysRevLett.87.167902
2001 doi
-
[21]
Garcia-Escartin, J.C., Chamorro-Posada, P.: swap test and Hong-Ou-Mandel effect are equivalent. Phys. Rev. A. 87, 52330 (2013). https://doi.org/10.1103/PhysRevA.87.052330
2013 doi
-
[22]
In: Proceedings of the Seventeenth Annual ACM- SIAM Symposium on Discrete Algorithm
Buhrman, H., Špalek, R.: Quantum Verification of Matrix Products. In: Proceedings of the Seventeenth Annual ACM- SIAM Symposium on Discrete Algorithm. pp. 880–889. Society for Industrial and Applied Mathematics, USA (2006)
2006
-
[23]
Zhang, X.-D., Zhang, X.-M., Xue, Z.-Y.: Quantum hyperparallel algorithm for matrix multiplication. Sci. Rep. 6, 24910 (2016). https://doi.org/10.1038/srep24910
2016 doi
-
[24]
Quantum Inf
Gitiaux, X., Morris, I., Emelianenko, M., Tian, M.: SWAP test for an arbitrary number of quantum states. Quantum Inf. Process. 21, (2022). https://doi.org/10.1007/s11128-022-03643-1
2022 doi
-
[25]
Neural Networks
Li, P., Wang, B.: Quantum neural networks model based on swap test and phase estimation. Neural Networks. 130, 152–164 (2020)
2020
-
[26]
Image Process
Getreuer, P.: A Survey of Gaussian Convolution Algorithms. Image Process. Line. 3, 286–310 (2013)
2013
-
[27]
LeCun, Y., Bengio, Y., Hinton, G.: Deep learning. Nature. 521, 436–444 (2015). https://doi.org/10.1038/nature14539
2015 doi
-
[28]
Russakovsky, O., Deng, J., Su, H., Krause, J., Satheesh, S., Ma, S., Huang, Z., Karpathy, A., Khosla, A., Bernstein, M., Berg, A.C., Fei-Fei, L.: ImageNet Large Scale Visual Recognition Challenge. Int. J. Comput. Vis. 115, 211–252 (2015). https://doi.org/10.1007/s11263-015-0816-y
2015 doi
-
[29]
Simonyan, K., Zisserman, A.: Very Deep Convolutional Networks for Large-Scale Image Recognition, (2015)
2015
-
[30]
Bennett, C.H., Bernstein, E., Brassard, G., Vazirani, U.: Strengths and Weaknesses of Quantum Computing. SIAM J. Comput. 26, 1510–1523 (1997). https://doi.org/10.1137/S0097539796300933
1997 doi
-
[31]
Prakash, A.: Quantum algorithms for linear algebra and machine learning., (2014)
2014
-
[32]
Giovannetti, V., Lloyd, S., Maccone, L.: Quantum Random Access Memory. Phys. Rev. Lett. 100, 160501 (2008). https://doi.org/10.1103/PhysRevLett.100.160501
2008 doi
-
[33]
Giovannetti, V., Lloyd, S., Maccone, L.: Architectures for a quantum random access memory. Phys. Rev. A. 78, 52310 (2008). https://doi.org/10.1103/PhysRevA.78.052310
2008 doi
-
[34]
In: National Key Lab for Novel Software Technology
Wu, J.: Introduction to Convolutional Neural Networks. In: National Key Lab for Novel Software Technology. Nanjing University. China. p. 5. pp. 23, (2017)
2017
-
[35]
Canny, J.: A computational approach to edge detection. Trans. pattern Anal. Mach. Intell. 679–698 (1986)
1986
-
[36]
Gray, R.M.: Toeplitz and Circulant Matrices: A Review. Found. Trends® Commun. Inf. Theory. 2, 155–239 (2006). https://doi.org/10.1561/0100000006
2006 doi
-
[37]
Algorithms
Heinig, G., Bojanczyk, A.: Transformation techniques for Toeplitz and Toeplitz-plus-Hankel matrices II. Algorithms. Linear Algebra Appl. 278, 11–36 (1998). https://doi.org/https://doi.org/10.1016/S0024-3795(97)10043-X
1998 doi
-
[38]
Kerenidis, I., Landman, J., Luongo, A., Prakash, A.: q-means: A quantum algorithm for unsupervised machine learning, (2018)
2018
Reviewed August 6, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.