Quantum convolution and quantum correlation algorithms are physically impossible

2003/09/08 by Chris Lomont, Lomont, Chris · 3 citations
Computer Science · Physics and Astronomy · #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Mechanics and Applications #Quantum Physics (quant-ph) #quant-ph

paper · pdf · doi:10.48550/arxiv.quant-ph/0309070

10 pages. Added reference to similar work, and fixed two typos from DCT to DFT

openalex publication_date 2003/09/08 · arxiv created 2003/12/03 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The key step in classical convolution and correlation algorithms, the componentwise multiplication of vectors after initial Fourier Transforms, is shown to be physically impossible to do on quantum states. Then this is used to show that computing the convolution or correlation of quantum state coefficients violates quantum mechanics, making convolution and correlation of quantum coefficients physically impossible.

Citations

• An algorithm for the machine calculation of complex Fourier series

Cited by

• Robust String Matching in O(√(N)+M) Quantum Queries
• Quantum Pseudo-fractional Fourier Transform and its application to quantum phase estimation
• The Hidden Subgroup Problem - Review and Open Problems

Related

• Grover search algorithm
• Quantum Entanglement as Super-Confounding: From Bell's Theorem to Robust Machine Learning
• Conditions on local operations to create quantum correlation
• Quantum algorithms revisited
• Basic Quantum Algorithms