Quantum convolution and quantum correlation algorithms are physically impossible

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.

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

References in corpus (1)

• Nonlinear quantum mechanics implies polynomial-time solution for NP-complete and #P problems

Cited by in corpus (7)

• The Hidden Subgroup Problem - Review and Open Problems
• Quantum algorithms for group convolution, cross-correlation, and equivariant transformations
• QFCNN: Quantum Fourier Convolutional Neural Network
• Quantum Optical Convolutional Neural Network: A Novel Image Recognition Framework for Quantum Computing
• Tristochastic operations and convolutions of quantum states
• Robust String Matching in O(\sqrt{N}+M) Quantum Queries
• Quantum Pseudo-fractional Fourier Transform and its application to quantum phase estimation