Quantum Fourier Transform Revisited
- URL: http://arxiv.org/abs/2003.03011v2
- Date: Wed, 23 Sep 2020 20:33:39 GMT
- Title: Quantum Fourier Transform Revisited
- Authors: Daan Camps and Roel Van Beeumen and Chao Yang
- Abstract summary: 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 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.
- Score: 3.23402688755667
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: 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.
Related papers
- Evaluation of phase shifts for non-relativistic elastic scattering using quantum computers [39.58317527488534]
This work reports the development of an algorithm that makes it possible to obtain phase shifts for generic non-relativistic elastic scattering processes on a quantum computer.
arXiv Detail & Related papers (2024-07-04T21:11:05Z) - Direct interpolative construction of the discrete Fourier transform as a matrix product operator [0.0]
We present a simple closed-form construction of the QFT MPO using the interpolative decomposition.
This construction can speed up the application of the QFT and the DFT, respectively, in quantum circuit simulations and QTT applications.
arXiv Detail & Related papers (2024-04-04T03:42:17Z) - Learning with SASQuaTCh: a Novel Variational Quantum Transformer Architecture with Kernel-Based Self-Attention [0.464982780843177]
We show that quantum circuits can efficiently express a self-attention mechanism through the perspective of kernel-based operator learning.
In this work, we are able to represent deep layers of a vision transformer network using simple gate operations and a set of multi-dimensional quantum Fourier transforms.
We analyze our novel variational quantum circuit, which we call Self-Attention Sequential Quantum Transformer Channel (SASTQuaCh), and demonstrate its utility on simplified classification problems.
arXiv Detail & Related papers (2024-03-21T18:00:04Z) - Polynomial-depth quantum algorithm for computing matrix determinant [46.13392585104221]
We propose an algorithm for calculating the determinant of a square matrix, and construct a quantum circuit realizing it.
Each row of the matrix is encoded as a pure state of some quantum system.
The admitted matrix is therefore arbitrary up to the normalization of quantum states of those systems.
arXiv Detail & Related papers (2024-01-29T23:23:27Z) - Multidimensional Quantum Fourier Transformation [0.0]
In this work, the known QFT circuit is used to derive an efficient circuit for the multidimensional QFT.
An example on current hardware is depicted by a 6 qubit 2D-QFT with an IBM quantum computer.
arXiv Detail & Related papers (2023-01-31T18:25:40Z) - Quantum Fourier Transform Has Small Entanglement [0.0]
We show that the Quantum Fourier Transform can introduce large entanglement to qubit systems.
We show that classical simulations of the QFT on a matrix product state with low bond dimension only take time linear in the number of qubits.
For data vectors of length $106$ to $108$, the speedup can be a few orders of magnitude.
arXiv Detail & Related papers (2022-10-16T07:04:22Z) - Quantum Fourier Addition, Simplified to Toffoli Addition [92.18777020401484]
We present the first systematic translation of the QFT-addition circuit into a Toffoli-based adder.
Instead of using approximate decompositions of the gates from the QFT circuit, it is more efficient to merge gates.
arXiv Detail & Related papers (2022-09-30T02:36:42Z) - Softmax-free Linear Transformers [90.83157268265654]
Vision transformers (ViTs) have pushed the state-of-the-art for visual perception tasks.
Existing methods are either theoretically flawed or empirically ineffective for visual recognition.
We propose a family of Softmax-Free Transformers (SOFT)
arXiv Detail & Related papers (2022-07-05T03:08:27Z) - A quantum Fourier transform (QFT) based note detection algorithm [0.0]
In quantum information processing, the quantum transform (QFT) has a plethora of applications.
We create a quantum music note detection algorithm both on a simulated and a real quantum computer.
arXiv Detail & Related papers (2022-04-25T16:45:56Z) - Quantum algorithms for matrix operations and linear systems of equations [65.62256987706128]
We propose quantum algorithms for matrix operations using the "Sender-Receiver" model.
These quantum protocols can be used as subroutines in other quantum schemes.
arXiv Detail & Related papers (2022-02-10T08:12:20Z) - Synthesis of Quantum Circuits with an Island Genetic Algorithm [44.99833362998488]
Given a unitary matrix that performs certain operation, obtaining the equivalent quantum circuit is a non-trivial task.
Three problems are explored: the coin for the quantum walker, the Toffoli gate and the Fredkin gate.
The algorithm proposed proved to be efficient in decomposition of quantum circuits, and as a generic approach, it is limited only by the available computational power.
arXiv Detail & Related papers (2021-06-06T13:15:25Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.