Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

International symposium on image and signal processing and analysis/ISPA ...

Discrete cosine transforms on quantum computers

Andreas Klappenecker, Martin Rötteler

Published Nov 13, 2002• 67 citations
Publisher

Abstract

A classical computer does not allow the calculation of a discrete cosine transform on N points in less than linear time. This trivial lower bound is no longer valid for a computer that takes advantage of quantum mechanical superposition, entanglement, and interference principles. In fact, we show that it is possible to realize the discrete cosine transforms and the discrete sine transforms of size N/spl times/N and types I, II, III and IV with as little as O(log/sup 2/N) operations on a quantum computer; whereas the known fast algorithms on a classical computer need O(N logN) operations.

DOI
10.1109/ispa.2001.938674

Related papers

Discrete Cosine Transforms on Quantum Computers

Andreas Klappenecker, Martin Roetteler

A classical computer does not allow to calculate a discrete cosine transform on N points in less than linear time. This trivial lower bound is no longer valid for a computer that takes advantage of quantum mechanical superposition, entanglement, and interference principles. In fact, we show that it is possible to realize the discrete cosine transforms and the discrete sine transforms of size NxN and types I,II,III, and IV with as little as O(log^2 N) operations on a quantum computer, whereas the known fast algorithms on a classical computer need O(N log N) operations.

arXiv:quant-ph/0111038•Nov 7, 2001•54 citations

On the Irresistible Efficiency of Signal Processing Methods in Quantum Computing

Andreas Klappenecker, Martin Roetteler

We show that many well-known signal transforms allow highly efficient realizations on a quantum computer. We explain some elementary quantum circuits and review the construction of the Quantum Fourier Transform. We derive quantum circuits for the Discrete Cosine and Sine Transforms, and for the Discrete Hartley transform. We show that at most O(log^2 N) elementary quantum gates are necessary to implement any of those transforms for input sequences of length N.

arXiv:quant-ph/0111039•Nov 7, 2001•3 citations

Quantum computing and a unified approach to fast unitary transforms

Sos С. Agaian, Andreas Klappenecker

A quantum computer directly manipulates information stored in the state of quantum mechanical systems. The available operations have many attractive features but also underly severe restrictions, which complicate the design of quantum algorithms. We present a divide-and-conquer approach to the design of various quantum algorithms. The class of algorithm includes many transforms which are well-known in classical signal processing applications. We show how fast quantum algorithms can be derived for the discrete Fourier transform, the Walsh-Hadamard transform, the Slant transform, and the Hartley transform. All these algorithms use at most O(log^2 N) operations to transform a state vector of a quantum computer of length N.

arXiv:quant-ph/0201120•Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•May 23, 2002•6 citations

Fast Laplace transforms on quantum computers

Julien Zylberman

While many classical algorithms rely on Laplace transforms, it has remained an open question whether these operations could be implemented efficiently on quantum computers. In this work, we introduce the Quantum Laplace Transform (QLT), which enables the implementation of $N\times N$ discrete Laplace transforms on quantum states encoded in $\lceil \log_2(N)\rceil$-qubits. In many cases, the associated quantum circuits have a depth that scales with $N$ as $O(\log(\log(N)))$ and a size that scales as $O(\log(N))$, requiring exponentially fewer operations and double-exponentially less computational time than their classical counterparts. These efficient scalings open the possibility of developing a new class of quantum algorithms based on Laplace transforms, with potential applications in physics, engineering, chemistry, machine learning, and finance.

arXiv:2412.05173•Dec 6, 2024•0 citations

Large quantum Fourier transforms are never exactly realized by braiding conformal blocks

Michael Hartley Freedman, Zhenghan Wang

Fourier transform is an essential ingredient in Shor's factoring algorithm. In the standard quantum circuit model with the gate set {$\mathbb{U}(2)$, controlled-NOT}, the discrete Fourier transforms ${F}_{N}={({\ensuremath{\omega}}^{ij})}_{N\ifmmode\times\else\texttimes\fi{}N}$, $i,j=0,1,\dots{},N\ensuremath{-}1$, $\ensuremath{\omega}={e}^{2\ensuremath{\pi}i∕N}$, can be realized exactly by quantum circuits of size $O({n}^{2})$, $n=\mathrm{ln}\phantom{\rule{0.2em}{0ex}}N$, and so can the discrete sine or cosine transforms. In topological quantum computing, the simplest universal topological quantum computer is based on the Fibonacci $(2+1)$-topological quantum field theory (TQFT), where the standard quantum circuits are replaced by unitary transformations realized by braiding conformal blocks. We report here that the large Fourier transforms ${F}_{N}$ and the discrete sine or cosine transforms can never be realized exactly by braiding conformal blocks for a fixed TQFT. It follows that an approximation is unavoidable in the implementation of Fourier transforms by braiding conformal blocks.

arXiv:cond-mat/0609411•Physical Review A•Mar 15, 2007•58 citations

Physical foundations of quantum informatics: from quantum mechanics through quantum computing to quantum cryptography

Petro Kosobutskyy

A methodical analysis of the basic problem related to quantum calculations of parameters of physical systems was made. Emphasis is placed on the physical principles of the operation of a quantum computer, with an emphasis on the fact that simultaneous access to all quantum states is important in quantum computing, which allows the simultaneous change of the quantum state from all superpositions in the qubit system. Emphasis is placed on the fact that in quantum algorithms the Fourier transform and the Hadamard transform are the basic operations - as a simple discrete Fourier transform. The reader's attention is drawn to the fact that quantum computing is primarily implemented in quantum objects with the properties of elementary NOT gates and controlled CNOT, which can be implemented on a Mach-Zehnder interferometer using the phenomena of photon interference and rotation of its polarization vector. Despite the progress of conventional computers, the need for the development of quantum computing is due to the technological limitation due to the dimensional quantization of the electronic spectrum and the exponential increase in the time of calculations by classical algorithms when the volume of data increases. However, the widespread use of quantum computers is limited by a number of problems. This is, first of all, insufficient accuracy and high sensitivity to external influences that can destroy the quantum state. Therefore, to increase the accuracy of calculations on a quantum computer, the calculation algorithm must be repeated a certain number of times, and to avoid the destruction of the quantum states of the qubit, low temperatures are used.

Computer Design Systems Theory and Practice•Jan 1, 2022•3 citations
A classical computer does not allow the calculation of a discrete cosine transform on N points in less than linear time. This trivial lower bound is no longer valid for a computer that takes advantage of quantum mechanical superposition, entanglement, and interference principles. In fact, we show that it is possible to realize the discrete cosine transforms and the discrete sine transforms of size N/spl times/N and types I, II, III and IV with as little as O(log/sup 2/N) operations on a quantum computer; whereas the known fast algorithms on a classical computer need O(N logN) operations.
A classical computer does not allow to calculate a discrete cosine transform on N points in less than linear time. This trivial lower bound is no longer valid for a computer that takes advantage of quantum mechanical superposition, entanglement, and interference principles. In fact, we show that it is possible to realize the discrete cosine transforms and the discrete sine transforms of size NxN and types I,II,III, and IV with as little as O(log^2 N) operations on a quantum computer, whereas the known fast algorithms on a classical computer need O(N log N) operations.
A quantum computer directly manipulates information stored in the state of quantum mechanical systems. The available operations have many attractive features but also underly severe restrictions, which complicate the design of quantum algorithms. We present a divide-and-conquer approach to the design of various quantum algorithms. The class of algorithm includes many transforms which are well-known in classical signal processing applications. We show how fast quantum algorithms can be derived for the discrete Fourier transform, the Walsh-Hadamard transform, the Slant transform, and the Hartley transform. All these algorithms use at most O(log^2 N) operations to transform a state vector of a quantum computer of length N.
While many classical algorithms rely on Laplace transforms, it has remained an open question whether these operations could be implemented efficiently on quantum computers. In this work, we introduce the Quantum Laplace Transform (QLT), which enables the implementation of N×NN\times NN×N discrete Laplace transforms on quantum states encoded in ⌈log⁡2(N)⌉\lceil \log_2(N)\rceil⌈log2​(N)⌉-qubits. In many cases, the associated quantum circuits have a depth that scales with NNN as O(log⁡(log⁡(N)))O(\log(\log(N)))O(log(log(N))) and a size that scales as O(log⁡(N))O(\log(N))O(log(N)), requiring exponentially fewer operations and double-exponentially less computational time than their classical counterparts. These efficient scalings open the possibility of developing a new class of quantum algorithms based on Laplace transforms, with potential applications in physics, engineering, chemistry, machine learning, and finance.
Fourier transform is an essential ingredient in Shor's factoring algorithm. In the standard quantum circuit model with the gate set {U(2)\mathbb{U}(2)U(2), controlled-NOT}, the discrete Fourier transforms ${F}_{N}={({\ensuremath{\omega}}^{ij})}_{N\ifmmode\times\else\texttimes\fi{}N}$, $i,j=0,1,\dots{},N\ensuremath{-}1$, $\ensuremath{\omega}={e}^{2\ensuremath{\pi}i∕N}$, can be realized exactly by quantum circuits of size O(n2)O({n}^{2})O(n2), n=lnNn=\mathrm{ln}\phantom{\rule{0.2em}{0ex}}Nn=lnN, and so can the discrete sine or cosine transforms. In topological quantum computing, the simplest universal topological quantum computer is based on the Fibonacci (2+1)(2+1)(2+1)-topological quantum field theory (TQFT), where the standard quantum circuits are replaced by unitary transformations realized by braiding conformal blocks. We report here that the large Fourier transforms FN{F}_{N}FN​ and the discrete sine or cosine transforms can never be realized exactly by braiding conformal blocks for a fixed TQFT. It follows that an approximation is unavoidable in the implementation of Fourier transforms by braiding conformal blocks.
A methodical analysis of the basic problem related to quantum calculations of parameters of physical systems was made. Emphasis is placed on the physical principles of the operation of a quantum computer, with an emphasis on the fact that simultaneous access to all quantum states is important in quantum computing, which allows the simultaneous change of the quantum state from all superpositions in the qubit system. Emphasis is placed on the fact that in quantum algorithms the Fourier transform and the Hadamard transform are the basic operations - as a simple discrete Fourier transform. The reader's attention is drawn to the fact that quantum computing is primarily implemented in quantum objects with the properties of elementary NOT gates and controlled CNOT, which can be implemented on a Mach-Zehnder interferometer using the phenomena of photon interference and rotation of its polarization vector. Despite the progress of conventional computers, the need for the development of quantum computing is due to the technological limitation due to the dimensional quantization of the electronic spectrum and the exponential increase in the time of calculations by classical algorithms when the volume of data increases. However, the widespread use of quantum computers is limited by a number of problems. This is, first of all, insufficient accuracy and high sensitivity to external influences that can destroy the quantum state. Therefore, to increase the accuracy of calculations on a quantum computer, the calculation algorithm must be repeated a certain number of times, and to avoid the destruction of the quantum states of the qubit, low temperatures are used.