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

• Quantum Inverse Fast Fourier Transform [0.0]
  An algorithm for Quantum Inverse Fast Fourier Transform (QIFFT) is developed to work for quantum data. We have included the complete formulation of QIFFT algorithm from the classical model and have included butterfly diagram.
  arXiv  Detail & Related papers  (2024-09-12T12:27:47Z)
• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
  Given a quantum circuit containing d tunable RZ gates and G-d Clifford gates, can a learner perform purely classical inference to efficiently predict its linear properties? We prove that the sample complexity scaling linearly in d is necessary and sufficient to achieve a small prediction error, while the corresponding computational complexity may scale exponentially in d. We devise a kernel-based learning model capable of trading off prediction error and computational complexity, transitioning from exponential to scaling in many practical settings.
  arXiv  Detail & Related papers  (2024-08-22T08:21:28Z)
• 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)
• 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.