Quantum Fourier Transform Has Small Entanglement
- URL: http://arxiv.org/abs/2210.08468v3
- Date: Fri, 27 Oct 2023 23:16:52 GMT
- Title: Quantum Fourier Transform Has Small Entanglement
- Authors: Jielun Chen, E.M. Stoudenmire, Steven R. White
- Abstract summary: 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.
- Score: 0.0
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: The Quantum Fourier Transform (QFT) is a key component of many important
quantum algorithms, most famously as being the essential ingredient in Shor's
algorithm for factoring products of primes. Given its remarkable capability,
one would think it can introduce large entanglement to qubit systems and would
be difficult to simulate classically. While early results showed QFT indeed has
maximal operator entanglement, we show that this is entirely due to the bit
reversal in the QFT. The core part of the QFT has Schmidt coefficients decaying
exponentially quickly, and thus it can only generate a constant amount of
entanglement regardless of the number of qubits. In addition, we show the
entangling power of the QFT is the same as the time evolution of a Hamiltonian
with exponentially decaying interactions, and thus a variant of the area law
for dynamics can be used to understand the low entanglement intuitively. Using
the low entanglement property of the QFT, 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, providing a potential speedup over the classical fast
Fourier transform (FFT) on many classes of functions. We demonstrate this
speedup in test calculations on some simple functions. For data vectors of
length $10^6$ to $10^8$, the speedup can be a few orders of magnitude.
Related papers
- Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
We study the problem of estimating frequency response functions of systems of coupled, classical harmonic oscillators using a quantum computer.
Our proposed quantum algorithm operates in the standard $s-sparse, oracle-based query access model.
We show that a simple adaptation of our algorithm solves the random glued-trees problem in time.
arXiv Detail & Related papers (2024-05-14T15:28:37Z) - Towards Neural Variational Monte Carlo That Scales Linearly with System
Size [67.09349921751341]
Quantum many-body problems are central to demystifying some exotic quantum phenomena, e.g., high-temperature superconductors.
The combination of neural networks (NN) for representing quantum states, and the Variational Monte Carlo (VMC) algorithm, has been shown to be a promising method for solving such problems.
We propose a NN architecture called Vector-Quantized Neural Quantum States (VQ-NQS) that utilizes vector-quantization techniques to leverage redundancies in the local-energy calculations of the VMC algorithm.
arXiv Detail & Related papers (2022-12-21T19:00:04Z) - 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) - 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) - Unimon qubit [42.83899285555746]
Superconducting qubits are one of the most promising candidates to implement quantum computers.
Here, we introduce and demonstrate a superconducting-qubit type, the unimon, which combines the desired properties of high non-linearity, full insensitivity to dc charge noise, insensitivity to flux noise, and a simple structure consisting only of a single Josephson junction in a resonator.
arXiv Detail & Related papers (2022-03-11T12:57:43Z) - An Algebraic Quantum Circuit Compression Algorithm for Hamiltonian
Simulation [55.41644538483948]
Current generation noisy intermediate-scale quantum (NISQ) computers are severely limited in chip size and error rates.
We derive localized circuit transformations to efficiently compress quantum circuits for simulation of certain spin Hamiltonians known as free fermions.
The proposed numerical circuit compression algorithm behaves backward stable and scales cubically in the number of spins enabling circuit synthesis beyond $mathcalO(103)$ spins.
arXiv Detail & Related papers (2021-08-06T19:38:03Z) - Fast-Forwarding with NISQ Processors without Feedback Loop [0.0]
We present the Classical Quantum Fast Forwarding (CQFF) as an alternative diagonalisation based algorithm for quantum simulation.
CQFF removes the need for a classical-quantum feedback loop and controlled multi-qubit unitaries.
Our work provides a $104$ improvement over the previous record.
arXiv Detail & Related papers (2021-04-05T14:29:33Z) - Implementing a Fast Unbounded Quantum Fanout Gate Using Power-Law
Interactions [0.9634136878988853]
Power-law interactions with strength decaying as $1/ralpha$ in the distance provide an experimentally realizable resource for information processing.
We leverage the power of these interactions to implement a fast quantum fanout gate with an arbitrary number of targets.
We show that power-law systems with $alpha le D$ are difficult to simulate classically even for short times, under a standard assumption that factoring is classically intractable.
arXiv Detail & Related papers (2020-07-01T18:00:00Z) - 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) - Discretizing quantum field theories for quantum simulation [0.0]
We show that a timestep equal to or going to zero faster than the spatial lattice spacing is necessary for quantum simulations of QFT.
We give a quantum circuit exactly equivalent to the real-time path integral from the discrete-time Lagrangian formulation of lattice QFT.
All of these circuits have an analogue of a lightcone on the lattice and therefore are examples of quantum cellular automata.
arXiv Detail & Related papers (2020-02-07T06:55:51Z) - Probing the Universality of Topological Defect Formation in a Quantum
Annealer: Kibble-Zurek Mechanism and Beyond [46.39654665163597]
We report on experimental tests of topological defect formation via the one-dimensional transverse-field Ising model.
We find that the quantum simulator results can indeed be explained by the KZM for open-system quantum dynamics with phase-flip errors.
This implies that the theoretical predictions of the generalized KZM theory, which assumes isolation from the environment, applies beyond its original scope to an open system.
arXiv Detail & Related papers (2020-01-31T02:55:35Z)
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.