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

IEEE Asia Pacific Conference on Circuits and Systems (APCCAS)

Quantum circuit design of 8x8 discrete fourier transform using its fast computation flow graph

Chien‐Cheng Tseng, Tsung-Ming Hwang

Published Apr 12, 2005• 5 citations
Publisher

Abstract

In this paper, quantum circuit design of 8x8 discrete cosine transform (DCT) is investigated. The proposed design procedure can be divided into the following three steps. First, the DCT matrix is decomposed into the product of sparse matrices based on its fast computation flow graph. Second, each sparse matrix is implemented by elementary quantum gates. Third, cascade the circuits of sparse matrices to obtain the final circuit. The proposed method makes fast DCT computation algorithm in digital signal processing be suitable for implementation in quantum computer.

DOI
10.1109/apccas.2004.1413000

Related papers

Quantum Circuit Design of 8 X 8 Discrete Cosine Transform using its Fast Computation Flow Graph

Chien‐Cheng Tseng, Tsung-Ming Hwang

In this paper, the quantum circuit design of an 8/spl times/8 discrete cosine transform (DCT) is investigated. The proposed design procedure can be divided into the following three steps. First, the DCT matrix is decomposed into the product of sparse matrices, based on its fast computation flow graph. Second, each sparse matrix is implemented by elementary quantum gates. Third, the sparse matrix circuits are cascaded to obtain the final circuit. The proposed method makes the fast DCT computation algorithm in digital signal processing suitable for implementation in a quantum computer.

IEEE International Symposium on Circuits and Systems proceedings•Jul 27, 2005•29 citations

Quantum circuit design of 8 /spl times/ 8 discrete Hartley transform

Chien‐Cheng Tseng, Tsung-Ming Hwang

In this paper, the 8 /spl times/ 8 discrete Hartley transform will be implemented by using quantum elementary gates such as controlled NOT gates and Hadamard gates. Two steps involved are as follows: first, the discrete Hartley transform matrix is decomposed into the product of several sparse unitary matrices using the structure of fast Hartley transform algorithm. Then, each sparse matrix is implemented by elementary quantum gates and cascade them to obtain the final circuit. The design results show that the proposed design method has less circuit complexity than the conventional Cybenko's method.

IEEE International Symposium on Circuits and Systems proceedings•Jan 1, 2004•10 citations

Quantum Circuit Design of Discrete Hartley Transform using Recursive Decomposition Formula

Chien‐Cheng Tseng, Tsung-Ming Hwang

In this paper, the quantum circuit design of a discrete Hartley transform (DHT) is investigated. The proposed design procedure can be divided into the following two steps. First, the N-point transform matrix is decomposed into the combination of N/2-point transform matrices and several sparse matrices such that any 2/sup n/-point transform can be computed recursively from the 2-point transform. Second, starting from the 2-point Hadamard transform, the quantum circuit of 2/sup n/-point transform can be designed recursively by using elementary quantum gates. The design results are compared with those of the conventional factorization method to demonstrate the effectiveness of proposed method.

IEEE International Symposium on Circuits and Systems proceedings•Jul 27, 2005•8 citations

Quantum Discrete Cosine Transform for Image Compression

Pang, Chao Yang, Zheng Zhou, Guo, Guang Can

Discrete Cosine Transform (DCT) is very important in image compression. Classical 1-D DCT and 2-D DCT has time complexity O(NlogN) and O(N²logN) respectively. This paper presents a quantum DCT iteration, and constructs a quantum 1-D and 2-D DCT algorithm for image compression by using the iteration. The presented 1-D and 2-D DCT has time complexity O(sqrt(N)) and O(N) respectively. In addition, the method presented in this paper generalizes the famous Grover's algorithm to solve complex unstructured search problem.

arXiv:quant-ph/0601043•Jan 8, 2006•15 citations

Quantum Fourier transform revisited

Camps, D, Van Beeumen, R, Yang, C

The fast Fourier transform (FFT) is one of the most successful numerical algorithms of the 20th century and has found numerous applications in many branches of computational science and engineering. The FFT algorithm can be derived from a particular matrix decomposition of the discrete Fourier transform (DFT) matrix. In this paper, we show that the quantum Fourier transform (QFT) can be derived by further decomposing the diagonal factors of the FFT matrix decomposition into products of matrices with Kronecker product structure. We analyze the implication of this Kronecker product structure on the discrete Fourier transform of rank-1 tensors on a classical computer. We also explain why such a structure can take advantage of an important quantum computer feature that enables the QFT algorithm to attain an exponential speedup on a quantum computer over the FFT algorithm on a classical computer. Further, the connection between the matrix decomposition of the DFT matrix and a quantum circuit is made. We also discuss a natural extension of a radix-2 QFT decomposition to a radix-d QFT decomposition. No prior knowledge of quantum computing is required to understand what is presented in this paper. Yet, we believe this paper may help readers to gain some rudimentary understanding of the nature of quantum computing from a matrix computation point of view.

•Jan 1, 2021•25 citations

New method of computing the quantum cosine transforms

Artyom M. Grigoryan, Alexis A. Gomez, Sos С. Agaian

The Quantum Signal Induced Heap Transform (QsiHT) is an emerging transform in the field of quantum computing, designed to enhance efficiency in signal processing tasks. This transform offers a novel approach for handling large-scale data structures in quantum algorithms, particularly in applications related to quantum image processing and signal decomposition. In this paper, we explore the use of QsiHT in generating various types of the quantum discrete cosine transforms (DCT), including the II-DCT and III-DCT, commonly used in image compression and signal processing. In QsiHT, different paths can be used in the computation, and in this work, we analyze a specific path to make the transformation computation most efficient. The proposed quantum circuits and algorithms for the QsiHT with 3 qubits are described in detail.

Multimodal Image Exploitation and Learning•May 28, 2025•0 citations
In this paper, quantum circuit design of 8x8 discrete cosine transform (DCT) is investigated. The proposed design procedure can be divided into the following three steps. First, the DCT matrix is decomposed into the product of sparse matrices based on its fast computation flow graph. Second, each sparse matrix is implemented by elementary quantum gates. Third, cascade the circuits of sparse matrices to obtain the final circuit. The proposed method makes fast DCT computation algorithm in digital signal processing be suitable for implementation in quantum computer.
In this paper, the quantum circuit design of an 8/spl times/8 discrete cosine transform (DCT) is investigated. The proposed design procedure can be divided into the following three steps. First, the DCT matrix is decomposed into the product of sparse matrices, based on its fast computation flow graph. Second, each sparse matrix is implemented by elementary quantum gates. Third, the sparse matrix circuits are cascaded to obtain the final circuit. The proposed method makes the fast DCT computation algorithm in digital signal processing suitable for implementation in a quantum computer.
In this paper, the 8 /spl times/ 8 discrete Hartley transform will be implemented by using quantum elementary gates such as controlled NOT gates and Hadamard gates. Two steps involved are as follows: first, the discrete Hartley transform matrix is decomposed into the product of several sparse unitary matrices using the structure of fast Hartley transform algorithm. Then, each sparse matrix is implemented by elementary quantum gates and cascade them to obtain the final circuit. The design results show that the proposed design method has less circuit complexity than the conventional Cybenko's method.
In this paper, the quantum circuit design of a discrete Hartley transform (DHT) is investigated. The proposed design procedure can be divided into the following two steps. First, the N-point transform matrix is decomposed into the combination of N/2-point transform matrices and several sparse matrices such that any 2/sup n/-point transform can be computed recursively from the 2-point transform. Second, starting from the 2-point Hadamard transform, the quantum circuit of 2/sup n/-point transform can be designed recursively by using elementary quantum gates. The design results are compared with those of the conventional factorization method to demonstrate the effectiveness of proposed method.
Discrete Cosine Transform (DCT) is very important in image compression. Classical 1-D DCT and 2-D DCT has time complexity O(NlogN) and O(N²logN) respectively. This paper presents a quantum DCT iteration, and constructs a quantum 1-D and 2-D DCT algorithm for image compression by using the iteration. The presented 1-D and 2-D DCT has time complexity O(sqrt(N)) and O(N) respectively. In addition, the method presented in this paper generalizes the famous Grover's algorithm to solve complex unstructured search problem.
The fast Fourier transform (FFT) is one of the most successful numerical algorithms of the 20th century and has found numerous applications in many branches of computational science and engineering. The FFT algorithm can be derived from a particular matrix decomposition of the discrete Fourier transform (DFT) matrix. In this paper, we show that the quantum Fourier transform (QFT) can be derived by further decomposing the diagonal factors of the FFT matrix decomposition into products of matrices with Kronecker product structure. We analyze the implication of this Kronecker product structure on the discrete Fourier transform of rank-1 tensors on a classical computer. We also explain why such a structure can take advantage of an important quantum computer feature that enables the QFT algorithm to attain an exponential speedup on a quantum computer over the FFT algorithm on a classical computer. Further, the connection between the matrix decomposition of the DFT matrix and a quantum circuit is made. We also discuss a natural extension of a radix-2 QFT decomposition to a radix-d QFT decomposition. No prior knowledge of quantum computing is required to understand what is presented in this paper. Yet, we believe this paper may help readers to gain some rudimentary understanding of the nature of quantum computing from a matrix computation point of view.
The Quantum Signal Induced Heap Transform (QsiHT) is an emerging transform in the field of quantum computing, designed to enhance efficiency in signal processing tasks. This transform offers a novel approach for handling large-scale data structures in quantum algorithms, particularly in applications related to quantum image processing and signal decomposition. In this paper, we explore the use of QsiHT in generating various types of the quantum discrete cosine transforms (DCT), including the II-DCT and III-DCT, commonly used in image compression and signal processing. In QsiHT, different paths can be used in the computation, and in this work, we analyze a specific path to make the transformation computation most efficient. The proposed quantum circuits and algorithms for the QsiHT with 3 qubits are described in detail.