Direct interpolative construction of the discrete Fourier transform as a matrix product operator

• URL: http://arxiv.org/abs/2404.03182v1
• Date: Thu, 4 Apr 2024 03:42:17 GMT
• Title: Direct interpolative construction of the discrete Fourier transform as a matrix product operator
• Authors: Jielun Chen, Michael Lindsey,
• Abstract summary: 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.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The quantum Fourier transform (QFT), which can be viewed as a reindexing of the discrete Fourier transform (DFT), has been shown to be compressible as a low-rank matrix product operator (MPO) or quantized tensor train (QTT) operator. However, the original proof of this fact does not furnish a construction of the MPO with a guaranteed error bound. Meanwhile, the existing practical construction of this MPO, based on the compression of a quantum circuit, is not as efficient as possible. We present a simple closed-form construction of the QFT MPO using the interpolative decomposition, with guaranteed near-optimal compression error for a given rank. This construction can speed up the application of the QFT and the DFT, respectively, in quantum circuit simulations and QTT applications. We also connect our interpolative construction to the approximate quantum Fourier transform (AQFT) by demonstrating that the AQFT can be viewed as an MPO constructed using a different interpolation scheme.

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)
• Experimental implementation of the optical fractional Fourier transform in the time-frequency domain [0.0]
  We present the experimental realization of the fractional Fourier transform in the time-frequency domain using an atomic quantum-optical memory system. We have verified the FrFT by analyses of chroncyclic Wigner functions measured via a shot-noise limited homodyne detector.
  arXiv  Detail & Related papers  (2023-03-23T14:39:52Z)
• D4FT: A Deep Learning Approach to Kohn-Sham Density Functional Theory [79.50644650795012]
  We propose a deep learning approach to solve Kohn-Sham Density Functional Theory (KS-DFT) We prove that such an approach has the same expressivity as the SCF method, yet reduces the computational complexity. In addition, we show that our approach enables us to explore more complex neural-based wave functions.
  arXiv  Detail & Related papers  (2023-03-01T10:38:10Z)
• Transform Once: Efficient Operator Learning in Frequency Domain [69.74509540521397]
  We study deep neural networks designed to harness the structure in frequency domain for efficient learning of long-range correlations in space or time. This work introduces a blueprint for frequency domain learning through a single transform: transform once (T1)
  arXiv  Detail & Related papers  (2022-11-26T01:56:05Z)
• Deep Fourier Up-Sampling [100.59885545206744]
  Up-sampling in the Fourier domain is more challenging as it does not follow such a local property. We propose a theoretically sound Deep Fourier Up-Sampling (FourierUp) to solve these issues.
  arXiv  Detail & Related papers  (2022-10-11T06:17:31Z)
• 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)
• Quantum Augmented Dual Attack [8.134961550216618]
  We present a quantum augmented variant of the dual lattice attack on the Learning with Errors (LWE) problem, using classical memory with quantum random access (QRACM) Applying our results to lattice parameters from the literature, we find that our algorithm outperforms previous algorithms, assuming unit cost access to a QRACM.
  arXiv  Detail & Related papers  (2022-05-27T13:54:31Z)
• Programmable Hamiltonian engineering with quadratic quantum Fourier transform [8.261869047984895]
  We propose a protocol of quadratic quantum Fourier transform (QQFT), considering cold atoms confined in an optical lattice. This QQFT is equivalent to QFT in the single-particle subspace, and produces a different unitary operation in the entire Hilbert space. We show this QQFT protocol can be implemented using programmable laser potential with the digital-micromirror-device techniques recently developed in the experiments.
  arXiv  Detail & Related papers  (2022-04-09T03:36:40Z)
• Simulating the Mott transition on a noisy digital quantum computer via Cartan-based fast-forwarding circuits [62.73367618671969]
  Dynamical mean-field theory (DMFT) maps the local Green's function of the Hubbard model to that of the Anderson impurity model. Quantum and hybrid quantum-classical algorithms have been proposed to efficiently solve impurity models. This work presents the first computation of the Mott phase transition using noisy digital quantum hardware.
  arXiv  Detail & Related papers  (2021-12-10T17:32:15Z)
• Simulating nonnative cubic interactions on noisy quantum machines [65.38483184536494]
  We show that quantum processors can be programmed to efficiently simulate dynamics that are not native to the hardware. On noisy devices without error correction, we show that simulation results are significantly improved when the quantum program is compiled using modular gates.
  arXiv  Detail & Related papers  (2020-04-15T05:16:24Z)
• Quantum Fourier Transform Revisited [3.23402688755667]
  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.
  arXiv  Detail & Related papers  (2020-03-06T02:46:58Z)

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.