Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Matrix Product Operator Simulations of Quantum Algorithms

Kieran J. Woolfe

Published Feb 1, 2015• 6 citations
OpenAlex

Abstract

We develop simulation methods for matrix product operators, and perform simulations of the Quantum Fourier Transform, Shor’s algorithm and Grover’s algorithm using matrix product states and matrix product operators. By doing so, we provide numerical evidence that a constant number of QFTs can be efficiently classically simulated on any state whose Schmidt rank grows only polynomially with the number of qubits, and quantify the amount of entanglement present in Shor’s algorithm. The efficiency of the matrix product state and operator representation allows us to perform moderately large simulations of both Shor’s algorithm with Z errors and Grover’s algorithm with up to 15 X, Y and Z errors. While larger simulations have been performed, our results have been computed with little computational power and provide new methods to perform large-scale quantum algorithm simulations.

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.

arXiv:1406.0931•Quantum Information and Computation•Jan 1, 2017•15 citations

Distributed Matrix Product State Simulations of Large-Scale Quantum Circuits

Aidan Dang

Before large-scale, robust quantum computers are developed, it is valuable to be able to classically simulate quantum algorithms to study their properties.To do so, we developed a numerical library for simulating quantum circuits via the matrix product state formalism on distributed memory architectures.By examining the multipartite entanglement present across Shor's algorithm, we were able to effectively map a high-level circuit of Shor's algorithm to the one-dimensional structure of a matrix product state, enabling us to perform a simulation of a specific 60 qubit instance in approximately 14 TB of memory: potentially the largest non-trivial quantum circuit simulation ever performed.We then applied matrix product state and matrix product density operator techniques to simulating one-dimensional circuits from Google's quantum supremacy problem with errors and found it mostly resistant to our methods.Most importantly, I give my gratitude to Doctor Charles Hill and Professor Lloyd Hollenberg for their guidance and vision in directing this work, for providing me with the resources necessary to produce the results of this thesis and for pushing me to realise my potential.In aiding the development of our numerical library and the production of our results, I acknowledge that this work was supported by resources provided by the Pawsey Supercomputing Centre with funding from the Australian Government and the Government of Western Australia.To The University of Melbourne, and especially the School of Physics, I am thankful to have been in an environment that would fuel the growth of my abilities.In order that I may focus on my studies, I would also like to thank Ms Rose Cooney, Ms Jenny de Boer and Associate Professor Michelle Livett for greatly simplifying the daunting administrative matters that I was faced with.Finally, to all the friends, classmates, teachers and students that I have ever had, and anyone else I have ever learned something from, I hope that you might have gained something from me in return.

•Jan 1, 2017•2 citations

Quantum Algorithms and their Implementation on Quantum Computer Simulators

Mike van der Lans

Quantum computation is becoming an increasingly interesting field, especially with the rise of real quantum computers. However, current quantum processors contain a few tens of error-prone qubits and the realization of large-scale quantum computers is still very challenging. Therefore, quantum computer simulators are particularly suitable for testing and analysing quantum algorithms without having a real quantum computer at one's disposal. In this thesis, different quantum algorithms such as Grover's and Shor's algorithm as well as key quantum routines such as the Quantum Fourier Transform (QFT) and a quantum adder/subtractor are described and analysed (optimal number of iterations, time complexity). Some of them have been implemented for an arbitrary number of qubits and have been simulated using two different quantum simulators, the QX simulator developed at QuTech and the Liquid simulator from Microsoft. In addition, how errors affect the success rate of the algorithms has been investigated.

•Jan 1, 2018•0 citations

Efficient classical simulation of the quantum Fourier transform

Dan E. Browne

A number of elegant approaches have been developed for the identification of quantum circuits which can be efficiently simulated on a classical computer. Recently, these methods have been employed to demonstrate the classical simulability of the quantum Fourier transform (QFT). Here we show that one can demonstrate a number of simulability results for QFT circuits in a straightforward manner using Griffiths and Niu's semi-classical QFT construction (Griffiths and Niu 1996 Phys. Rev. Lett. 76 3228). We use this to analyse the simulability properties of the QFT with a variety of classes of entangled input states. We then discuss the consequences of these results in the context of Shor's factorization algorithm.

arXiv:quant-ph/0612021•New Journal of Physics•May 23, 2007•68 citations

Iterative Matrix Product State Simulation for Scalable Grover's Algorithm

Mei Ian Sam, Tzu-Ling Kuo, Tai-Yue Li

Grover's algorithm is a cornerstone of quantum search algorithm, offering quadratic speedup for unstructured problems. However, limited qubit counts and noise in today's noisy intermediate-scale quantum (NISQ) devices hinder large-scale hardware validation, making efficient classical simulation essential for algorithm development and hardware assessment. We present an iterative Grover simulation framework based on matrix product states (MPS) to efficiently simulate large-scale Grover's algorithm. Within the NVIDIA CUDA-Q environment, we compare iterative and common (non-iterative) Grover's circuits across statevector and MPS backends. On the MPS backend at 29 qubits, the iterative Grover's circuit runs about 15x faster than the common (non-iterative) Grover's circuit, and about 3-4x faster than the statevector backend. In sampling experiments, Grover's circuits demonstrate strong low-shot stability: as the qubit number increases beyond 13, a single-shot measurement still closely mirrors the results from 4,096 shots, indicating reliable estimates with minimal sampling and significant potential to cut measurement costs. Overall, an iterative MPS design delivers speed and scalability for Grover's circuit simulation, enabling practical large-scale implementations.

quant-pharXiv:2601.03832•IEEE International Conference on Acoustics Speech and Signal Processing•Jan 8, 2026•3 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.

arXiv:2210.08468•PRX Quantum•Oct 27, 2023•92 citations
We develop simulation methods for matrix product operators, and perform simulations of the Quantum Fourier Transform, Shor’s algorithm and Grover’s algorithm using matrix product states and matrix product operators. By doing so, we provide numerical evidence that a constant number of QFTs can be efficiently classically simulated on any state whose Schmidt rank grows only polynomially with the number of qubits, and quantify the amount of entanglement present in Shor’s algorithm. The efficiency of the matrix product state and operator representation allows us to perform moderately large simulations of both Shor’s algorithm with Z errors and Grover’s algorithm with up to 15 X, Y and Z errors. While larger simulations have been performed, our results have been computed with little computational power and provide new methods to perform large-scale quantum algorithm simulations.
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.
Before large-scale, robust quantum computers are developed, it is valuable to be able to classically simulate quantum algorithms to study their properties.To do so, we developed a numerical library for simulating quantum circuits via the matrix product state formalism on distributed memory architectures.By examining the multipartite entanglement present across Shor's algorithm, we were able to effectively map a high-level circuit of Shor's algorithm to the one-dimensional structure of a matrix product state, enabling us to perform a simulation of a specific 60 qubit instance in approximately 14 TB of memory: potentially the largest non-trivial quantum circuit simulation ever performed.We then applied matrix product state and matrix product density operator techniques to simulating one-dimensional circuits from Google's quantum supremacy problem with errors and found it mostly resistant to our methods.Most importantly, I give my gratitude to Doctor Charles Hill and Professor Lloyd Hollenberg for their guidance and vision in directing this work, for providing me with the resources necessary to produce the results of this thesis and for pushing me to realise my potential.In aiding the development of our numerical library and the production of our results, I acknowledge that this work was supported by resources provided by the Pawsey Supercomputing Centre with funding from the Australian Government and the Government of Western Australia.To The University of Melbourne, and especially the School of Physics, I am thankful to have been in an environment that would fuel the growth of my abilities.In order that I may focus on my studies, I would also like to thank Ms Rose Cooney, Ms Jenny de Boer and Associate Professor Michelle Livett for greatly simplifying the daunting administrative matters that I was faced with.Finally, to all the friends, classmates, teachers and students that I have ever had, and anyone else I have ever learned something from, I hope that you might have gained something from me in return.
Quantum computation is becoming an increasingly interesting field, especially with the rise of real quantum computers. However, current quantum processors contain a few tens of error-prone qubits and the realization of large-scale quantum computers is still very challenging. Therefore, quantum computer simulators are particularly suitable for testing and analysing quantum algorithms without having a real quantum computer at one's disposal. In this thesis, different quantum algorithms such as Grover's and Shor's algorithm as well as key quantum routines such as the Quantum Fourier Transform (QFT) and a quantum adder/subtractor are described and analysed (optimal number of iterations, time complexity). Some of them have been implemented for an arbitrary number of qubits and have been simulated using two different quantum simulators, the QX simulator developed at QuTech and the Liquid simulator from Microsoft. In addition, how errors affect the success rate of the algorithms has been investigated.
A number of elegant approaches have been developed for the identification of quantum circuits which can be efficiently simulated on a classical computer. Recently, these methods have been employed to demonstrate the classical simulability of the quantum Fourier transform (QFT). Here we show that one can demonstrate a number of simulability results for QFT circuits in a straightforward manner using Griffiths and Niu's semi-classical QFT construction (Griffiths and Niu 1996 Phys. Rev. Lett. 76 3228). We use this to analyse the simulability properties of the QFT with a variety of classes of entangled input states. We then discuss the consequences of these results in the context of Shor's factorization algorithm.
Grover's algorithm is a cornerstone of quantum search algorithm, offering quadratic speedup for unstructured problems. However, limited qubit counts and noise in today's noisy intermediate-scale quantum (NISQ) devices hinder large-scale hardware validation, making efficient classical simulation essential for algorithm development and hardware assessment. We present an iterative Grover simulation framework based on matrix product states (MPS) to efficiently simulate large-scale Grover's algorithm. Within the NVIDIA CUDA-Q environment, we compare iterative and common (non-iterative) Grover's circuits across statevector and MPS backends. On the MPS backend at 29 qubits, the iterative Grover's circuit runs about 15x faster than the common (non-iterative) Grover's circuit, and about 3-4x faster than the statevector backend. In sampling experiments, Grover's circuits demonstrate strong low-shot stability: as the qubit number increases beyond 13, a single-shot measurement still closely mirrors the results from 4,096 shots, indicating reliable estimates with minimal sampling and significant potential to cut measurement costs. Overall, an iterative MPS design delivers speed and scalability for Grover's circuit simulation, enabling practical large-scale implementations.
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.