time. We perform such simulations and quantify the error involved in representing the transform as a matrix product operator and simulating the quantum Fourier transform of periodic states.

DOI: 10.48550/arxiv.1406.0931

Related papers

Scaling and efficient classical simulation of the quantum Fourier transform

Kieran J. Woolfe, Charles D. Hill, Lloyd C. L. Hollenberg

We provide numerical evidence that the quantum Fourier transform can be efficiently represented in a matrix product operator with a size growing relatively slowly with the number of qubits. Additionally, we numerically show that the tensors in the operator converge to a common tensor as the number of qubits in the transform increases. Together these results imply that the application of the quantum Fourier transform to a matrix product state with n qubits of maximum Schmidt rank χ can be simulated in O(n (log(n))2 χ 2 ) time. We perform such simulations and quantify the error involved in representing the transform as a matrix product operator and simulating the quantum Fourier transform of periodic states.We provide numerical evidence that the quantum Fourier transform can be efficiently represented in a matrix product operator with a size growing relatively slowly with the number of qubits. Additionally, we numerically show that the tensors in the operator converge to a common tensor as the number of qubits in the transform increases. Together these results imply that the application of the quantum Fourier transform to a matrix product state with n qubits of maximum Schmidt rank χ can be simulated in O(n (log(n))2 χ 2 ) time. We perform such simulations and quantify the error involved in representing the transform as a matrix product operator and simulating the quantum Fourier transform of periodic states.

Quantum Information and ComputationJan 1, 20178 citations

Quantum Fourier Transform Has Small Entanglement

Jielun Chen, Edwin Miles Stoudenmire, Steven R. White

The quantum Fourier transform (QFT) is a key component of many important quantum algorithms, most famously 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 the 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 generate only 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 take time linear in the number of qubits, providing a potential speedup over the classical fast Fourier transform on many classes of functions.We demonstrate this speedup in test calculations on some simple functions.For data vectors of length 10 6 -10 8 , the speedup can be a few orders of magnitude.The quantum Fourier transform (QFT) is a key component of many important quantum algorithms, most famously 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 the 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 generate only 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 take time linear in the number of qubits, providing a potential speedup over the classical fast Fourier transform on many classes of functions.We demonstrate this speedup in test calculations on some simple functions.For data vectors of length 10 6 -10 8 , the speedup can be a few orders of magnitude.

arXiv:2210.08468PRX QuantumOct 27, 202363 citations

Performance scaling of Shor's algorithm with a banded quantum Fourier transform

Yunseong Nam, R. Blümel

In excellent agreement with our numerical simulations of Shor's algorithm, equipped with a truncated quantum Fourier transform of bandwidth $b$ , we find that its performance scales $\ensuremath{\sim}$${2}^{\ensuremath{-}{\ensuremath{\xi}}_{b}n}$, where $n$ is the number of qubits, ${\ensuremath{\xi}}_{b}=1.1\ifmmode\times\else\texttimes\fi{}{2}^{\ensuremath{-}2b}$, and the bandwidth $b$ is the number of quantum states coupled by the quantum Fourier transform. Nonexponential behavior is observed for small $n$ and explained analytically. The large- $n$ exponential scaling implies that $b=7$ is sufficient to operate a 1000-qubit quantum computer running Shor's algorithm on the $95%$ performance level and implies hardware savings of the order of half a million rotation gates.In excellent agreement with our numerical simulations of Shor's algorithm, equipped with a truncated quantum Fourier transform of bandwidth $b$, we find that its performance scales $\ensuremath{\sim}$${2}^{\ensuremath{-}{\ensuremath{\xi}}_{b}n}$, where $n$ is the number of qubits, ${\ensuremath{\xi}}_{b}=1.1\ifmmode\times\else\texttimes\fi{}{2}^{\ensuremath{-}2b}$, and the bandwidth $b$ is the number of quantum states coupled by the quantum Fourier transform. Nonexponential behavior is observed for small $n$ and explained analytically. The large-$n$ exponential scaling implies that $b=7$ is sufficient to operate a 1000-qubit quantum computer running Shor's algorithm on the $95%$ performance level and implies hardware savings of the order of half a million rotation gates.

Physical Review AOct 23, 201214 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.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, 202125 citations

Classical Simulability from Operator Entanglement Scaling

Neil Dowling

Local-operator entanglement (LOE) quantifies the nonlocal structure of Heisenberg operators and serves as a diagnostic of many-body chaos. We provide rigorous bounds showing when an operator can be well-approximated by a matrix-product operator (MPO), given asymptotic scaling of its LOE $α$ -Rényi entropies. Specifically, we prove that a volume law scaling for $α\geq 1$ implies that the operator cannot be approximated efficiently as an MPO while faithfully reproducing all expectation values. On the other hand, if we restrict to correlations over a relevant sub-class of (ensembles of) states, then logarithmic scaling of the $α< 1$ entropies implies MPO simulability. This result covers a range of relevant quantities, including infinite temperature autocorrelation functions, out-of-time-ordered correlators, and average-case expectation values over ensembles of computational basis states. Beyond this regime, we provide numerical evidence together with a random matrix model to argue that this simulability result also typically holds for arbitrary states. Our results put on firm footing the heuristic expectation that a low operator entanglement implies efficient tensor network representability, extending celebrated foundational results from the theory of matrix-product states and providing a formal link between quantum chaos and classical simulability.Local-operator entanglement (LOE) quantifies the nonlocal structure of Heisenberg operators and serves as a diagnostic of many-body chaos. We provide rigorous bounds showing when an operator can be well-approximated by a matrix-product operator (MPO), given asymptotic scaling of its LOE $α$-Rényi entropies. Specifically, we prove that a volume law scaling for $α\geq 1$ implies that the operator cannot be approximated efficiently as an MPO while faithfully reproducing all expectation values. On the other hand, if we restrict to correlations over a relevant sub-class of (ensembles of) states, then logarithmic scaling of the $α< 1$ entropies implies MPO simulability. This result covers a range of relevant quantities, including infinite temperature autocorrelation functions, out-of-time-ordered correlators, and average-case expectation values over ensembles of computational basis states. Beyond this regime, we provide numerical evidence together with a random matrix model to argue that this simulability result also typically holds for arbitrary states. Our results put on firm footing the heuristic expectation that a low operator entanglement implies efficient tensor network representability, extending celebrated foundational results from the theory of matrix-product states and providing a formal link between quantum chaos and classical simulability.

quant-pharXiv:2603.05656Physical Review AMar 9, 20260 citations

Quantum system decomposition for the semi-classical quantum Fourier transform

Benjamin Greco, Jack Lenahan, S. H. Huerth +2 more

For classical simulation, the quantum Fourier transform (QFT) requires very large matrix operations. Previous work has shown that the semi-classical quantum Fourier transform (SCQFT) can use these individual coefficients to perform the QFT using only single-quantum bit (qubit) unitary gates and measurement operators. However, the SCQFT requires these individual decomposed qubits of the quantum system as input to the algorithm. We devise two methods to find separable approximations of quantum systems to serve as inputs to the SCQFT. We introduce an application of the approach on classical radio frequency signals represented through a quantum model. The resulting decomposition and QFT are computed on several simulated results, and an example is given using an experimental signal.For classical simulation, the quantum Fourier transform (QFT) requires very large matrix operations. Previous work has shown that the semi-classical quantum Fourier transform (SCQFT) can use these individual coefficients to perform the QFT using only single-quantum bit (qubit) unitary gates and measurement operators. However, the SCQFT requires these individual decomposed qubits of the quantum system as input to the algorithm. We devise two methods to find separable approximations of quantum systems to serve as inputs to the SCQFT. We introduce an application of the approach on classical radio frequency signals represented through a quantum model. The resulting decomposition and QFT are computed on several simulated results, and an example is given using an experimental signal.

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIEMay 1, 20120 citations

n

qubits of maximum Schmidt rank

χ

can be simulated in

O(n (log(n))^2 χ^2)

time. We perform such simulations and quantify the error involved in representing the transform as a matrix product operator and simulating the quantum Fourier transform of periodic states.

In excellent agreement with our numerical simulations of Shor's algorithm, equipped with a truncated quantum Fourier transform of bandwidth

b

, we find that its performance scales $\ensuremath{\sim}$${2}^{\ensuremath{-}{\ensuremath{\xi}}_{b}n}$, where

n

is the number of qubits, ${\ensuremath{\xi}}_{b}=1.1\ifmmode\times\else\texttimes\fi{}{2}^{\ensuremath{-}2b}$, and the bandwidth

b

is the number of quantum states coupled by the quantum Fourier transform. Nonexponential behavior is observed for small

n

and explained analytically. The large-

n

exponential scaling implies that

b=7

is sufficient to operate a 1000-qubit quantum computer running Shor's algorithm on the

95%

performance level and implies hardware savings of the order of half a million rotation gates.

α

-Rényi entropies. Specifically, we prove that a volume law scaling for

α\geq 1

implies that the operator cannot be approximated efficiently as an MPO while faithfully reproducing all expectation values. On the other hand, if we restrict to correlations over a relevant sub-class of (ensembles of) states, then logarithmic scaling of the

α< 1

entropies implies MPO simulability. This result covers a range of relevant quantities, including infinite temperature autocorrelation functions, out-of-time-ordered correlators, and average-case expectation values over ensembles of computational basis states. Beyond this regime, we provide numerical evidence together with a random matrix model to argue that this simulability result also typically holds for arbitrary states. Our results put on firm footing the heuristic expectation that a low operator entanglement implies efficient tensor network representability, extending celebrated foundational results from the theory of matrix-product states and providing a formal link between quantum chaos and classical simulability.