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

arXiv:quant-ph/0503174 · Physical Review A

Simulation of many-qubit quantum computation with matrix product states

Mari Carmen Bañuls, Román Orús, José Ignacio Latorre, Armando Pérez, Pedro Ruiz-Femenía

Published Feb 24, 2006• 41 citations
arXivHTMLPDF

Abstract

Matrix product states provide a natural entanglement basis to represent a quantum register and operate quantum gates on it. This scheme can be materialized to simulate a quantum adiabatic algorithm solving hard instances of an $NP$-complete problem. Errors inherent to truncations of the exact action of interacting gates are controlled by the size of the matrices in the representation. The property of finding the right solution for an instance and the expected value of the energy (cost function) are found to be remarkably robust against these errors. As a symbolic example, we simulate the algorithm solving a 100-qubit hard instance, that is, finding the correct product state out of $\ensuremath{\sim}{10}^{30}$ possibilities. Accumulated statistics for up to $60$ qubits seem to point at a subexponential growth of the average minimum time to solve hard instances with highly truncated simulations of adiabatic quantum evolution.

DOI
10.1103/physreva.73.022344

Related papers

An entanglement-aware quantum computer simulation algorithm

Maxime Oliva

The advent of quantum computers promises exponential speed ups in the execution of various computational tasks. While their capabilities are hindered by quantum decoherence, they can be exactly simulated on classical hardware at the cost of an exponential scaling in terms of number of qubits. To circumvent this, quantum states can be represented as matrix product states (MPS), a product of tensors separated by so-called bond dimensions. Limiting bond dimensions growth approximates the state, but also limits its ability to represent entanglement. Methods based on this representation have been the most popular tool at simulating large quantum systems. But how to trust resulting approximate quantum states for such intractable systems sizes ? I propose here a method for inferring the fidelity of an approximate quantum state without direct comparison to its exact counterpart, and use it to design an ``entanglement-aware'' (EA) algorithm for both pure and mixed states. As opposed to state of the art methods which limit bond dimensions up to an arbitrary maximum value, this algorithm receives as input a fidelity, and adapts dynamically its bond dimensions to both local entanglement and noise such that the final quantum state fidelity at least reaches the input fidelity. I show that this algorithm far surpasses standard fixed bond dimension truncation schemes. In particular, a noiseless random circuit of 300 qubits and depth 75 simulated using MPS methods takes one week of computation time, while EA-MPS only needs 2 hours to reach similar quantum state fidelity.

arXiv:2307.16870•Jul 31, 2023•1 citation

Simulating quantum systems on classical computers with matrix product states

Adrian Kleine, Ulrich Schollwöck

In this thesis, the numerical simulation of strongly-interacting many-body quantum-mechanical systems using matrix product states (MPS) is considered. Compared to classical systems, quantum many-body systems possess an exponentially enlarged number of degrees of freedom, significantly complicating a simulation on a classical computer. Matrix-Product-States are a novel representation of arbitrary quantum many-body states. Using quantum information theory, it is possible to show that Matrix-Product-States provide a polynomial-sized representation of one-dimensional quantum systems, thus allowing an efficient simulation of one-dimensional quantum system on classical computers. Matrix-Product-States form the conceptual framework of the density-matrix renormalization group (DMRG). Based upon this connection, deeper understanding of the density matrix renormalization group can be obtained. After a general introduction in the first chapter of this thesis, the second chapter deals with Matrix-Product-States, focusing on the development of fast and stable algorithms. It is possible to extend the Matrix-Product-States approach to be able to represent arbitrary operators, the so-called Matrix-Product-Operators, which allows a fast and flexible calculation of arbitrary expectation values. To obtain algorithms to efficiently calculate groundstates, the density-matrix renormalization group is reformulated using the Matrix-Product-States framework. Further, time-dependent problems are considered. Two different algorithms are presented, one based on a Trotter decomposition of the time-evolution operator, the other one on Krylov subspaces. Finally, the evaluation of dynamical spectral functions is discussed, and a correction vector-based method is presented. In the following chapters, the methods presented in the second chapter, are applied to a number of different physical problems. The third chapter deals with the existence of chiral phases in isotropic one-dimensional quantum spin systems. A preceding analytical study based on a mean-field approach indicated the possible existence of those phases in an isotopic Heisenberg model with a frustrating zig-zag interaction and a magnetic field. In this thesis, the existence of the chiral phases will be shown numerically by using Matrix-Product-States-based algorithms. A key effect of interacting one-dimensional quantum-mechanical many-body systems is the spin-charge separation. However, up to now only signs of the spin-charge separation have been observed in experiments. In the fourth chapter, we propose an experiment using ultracold atomic gases in optical lattices, which allows a well controlled observation of the spin-charge separation (of different hyperfine states of the ultracold atoms) with current state of the art experimental techniques. Ultracold atoms in optical lattices are well described by (Bose)-Hubbard models. In order to support this proposal, we present numerical results for realistic system parameters. Matrix-Product-States are an excellent tool for the simulation of one-dimensional quantum systems, however, they are not well suited for the simulation of higher dimensional systems. For strongly-correlated systems, for instance cuprates-based high-temperature superconductors, quantum fluctuations play an essential role. Classical mean-field theories neglect any kind of fluctuations, thus they are not suitable to describe strongly-correlated systems. The dynamical mean-field theory (DMFT) fully takes local quantum fluctuations into account but neglects any kind of spatial fluctuations. The many-body problem on the lattice is mapped onto an impurity problem, which needs to be solved self-consistently. In the last chapter of this thesis, Matrix-Product-States-based algorithms are used to solve the impurity problem of the dynamical mean-field theory. We present results for a Hubbard model on a one-dimensional lattice and on a Bethe lattice obtained by the dynamical mean-field and compare them with exact results.

•Jan 1, 2010•1 citation

A Heuristic for Matrix Product State Simulation of Out-of-Equilibrium Dynamics of Two-Dimensional Quantum Spin Systems

Salvatore Mandrà, Brayden Ware, Nikita Astrakhantsev +4 more

Out-of-equilibrium dynamics of non-integrable Hamiltonian many-body quantum systems are characterized by highly entangled wave functions. Near-maximal entanglement arises in systems exhibiting thermalization or pre-thermalization, where the system converges to a steady state with a fixed energy density. Classical simulation of the time dependence of such wave functions requires exponential resources. However, typical computations aim to estimate expectation values of local operators and correlation functions to some expected precision. For thermalizing systems at sufficiently high energy densities, such computations can be done without storing the full wave function by instead simulating the evolution of the local operator, which requires significantly fewer resources. Nonetheless, constructing such resource-efficient classical algorithms remains a challenge for intermediate energy densities, where simulating both the wave function and operator evolution is costly. In this paper, we propose a heuristic approach to accelerate the convergence of Matrix Product State (MPS) simulations of expectation values, applicable across a broad range of energy densities. We estimate the desired observables by rescaling the MPS results at low bond dimensions with a factor that depends on the fidelity of the MPS wave function. Using this technique, we simulated the dynamics of the two-dimensional Transverse-Field Ising Model (TFIM) on a $7\times8$ grid with periodic boundary conditions, using a maximum bond dimension of $χ= 4096$ on a single A100 GPU, as well as the dynamics of the two-dimensional XY model on grids of size up to $9\times9$. We compare our TFIM results to similar simulations on a digital quantum processor [R. Haghshenas et al., Nature 653, 56 (2026)], demonstrating excellent agreement and confirming the predictive power of our method.

quant-pharXiv:2511.23438•PRX Quantum•Dec 1, 2025•10 citations

Solving Constraint Satisfaction Problems with Matrix Product States

Sabine Pelton

In the past decade, Matrix Product State (MPS) algorithms have emerged as an efficient method of modeling some many-body quantum spin systems. Since spin system Hamiltonians can be considered constraint satisfaction problems (CSPs), it follows that MPS should provide a versatile framework for studying a variety of general CSPs. In this thesis, we apply MPS to two types of CSP. First, use MPS to simulate adiabatic quantum computation (AQC), where the target Hamiltonians are instances of a fully connected, random Ising spin glass. Results of the simulations help shed light on why AQC fails for some optimization problems. We then present the novel application of a modified MPS algorithm to classical Boolean satisfiability problems, specifically k-SAT and max k-SAT. By construction, the algorithm also counts solutions to a given Boolean formula (\#-SAT). For easy satisfiable instances, the method is more expensive than other existing algorithms; however, for hard and unsatisfiable instances, the method succeeds in finding satisfying assignments where other algorithms fail to converge.

Journal of International Crisis and Risk Communication Research•Jan 1, 2017•0 citations

A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem

Edward Farhi, Jeffrey Goldstone, Sam Gutmann +3 more

A quantum system will stay near its instantaneous ground state if the Hamiltonian that governs its evolution varies slowly enough. This quantum adiabatic behavior is the basis of a new class of algorithms for quantum computing. We tested one such algorithm by applying it to randomly generated hard instances of an NP-complete problem. For the small examples that we could simulate, the quantum adiabatic algorithm worked well, providing evidence that quantum computers (if large ones can be built) may be able to outperform ordinary computers on hard sets of instances of NP-complete problems.

arXiv:quant-ph/0104129•Science•Apr 20, 2001•2,100 citations

Quantum-inspired classical simulation through randomized time evolution

Fredrik Hasselgren, Bálint Koczor

Tensor-network simulations of quantum many-body dynamics are fundamentally limited by entanglement build-up, which leads to exponentially growing computational costs. Furthermore, these classical simulation algorithms are inherently sequential as typically a tensor network representation of the quantum state is updated incrementally at each time step. We build on recently introduced randomized quantum algorithms for time evolution (TE-PAI), and adapt them to the classical simulation context with the purpose of enabling massive parallelisation. Our MPS TE-PAI approach achieves exact time evolution on average (unbiased estimator) and proceeds by representing an ensemble of randomized shallow Trotter-variant circuits as tensor networks. As each circuit instance yields a deterministic quantum state (or observable expecation value), the only source of randomness is the sampling of circuit variants; the absence of shot noise therefore yields a reduced estimator variance relative to quantum hardware implementations of TE-PAI. We simulate representative disordered one-dimensional spin-ring Hamiltonians, and numerically observe reductions in the per-sample gate-count by a factor of up to $10^3$ relative to Trotterized MPS evolution, yielding orders of magnitude reduction in the time-to-solution under realistic levels of parallelisation. Finally, we numerically observe that MPS TE-PAI is substantially more robust against severe bond-dimension truncation than product formulas, potentially making it useful for the simulation of strongly correlated systems where truncation is necessary in practice. We also demonstrate that the approach can be used naturally in combination with existing time evolution algorithms, effectively extending their time depth via parallelisation.

quant-pharXiv:2604.13144•Apr 15, 2026•2 citations
Matrix product states provide a natural entanglement basis to represent a quantum register and operate quantum gates on it. This scheme can be materialized to simulate a quantum adiabatic algorithm solving hard instances of an NPNPNP-complete problem. Errors inherent to truncations of the exact action of interacting gates are controlled by the size of the matrices in the representation. The property of finding the right solution for an instance and the expected value of the energy (cost function) are found to be remarkably robust against these errors. As a symbolic example, we simulate the algorithm solving a 100-qubit hard instance, that is, finding the correct product state out of \ensuremath∼1030\ensuremath{\sim}{10}^{30}\ensuremath∼1030 possibilities. Accumulated statistics for up to 606060 qubits seem to point at a subexponential growth of the average minimum time to solve hard instances with highly truncated simulations of adiabatic quantum evolution.
The advent of quantum computers promises exponential speed ups in the execution of various computational tasks. While their capabilities are hindered by quantum decoherence, they can be exactly simulated on classical hardware at the cost of an exponential scaling in terms of number of qubits. To circumvent this, quantum states can be represented as matrix product states (MPS), a product of tensors separated by so-called bond dimensions. Limiting bond dimensions growth approximates the state, but also limits its ability to represent entanglement. Methods based on this representation have been the most popular tool at simulating large quantum systems. But how to trust resulting approximate quantum states for such intractable systems sizes ? I propose here a method for inferring the fidelity of an approximate quantum state without direct comparison to its exact counterpart, and use it to design an ``entanglement-aware'' (EA) algorithm for both pure and mixed states. As opposed to state of the art methods which limit bond dimensions up to an arbitrary maximum value, this algorithm receives as input a fidelity, and adapts dynamically its bond dimensions to both local entanglement and noise such that the final quantum state fidelity at least reaches the input fidelity. I show that this algorithm far surpasses standard fixed bond dimension truncation schemes. In particular, a noiseless random circuit of 300 qubits and depth 75 simulated using MPS methods takes one week of computation time, while EA-MPS only needs 2 hours to reach similar quantum state fidelity.
In this thesis, the numerical simulation of strongly-interacting many-body quantum-mechanical systems using matrix product states (MPS) is considered. Compared to classical systems, quantum many-body systems possess an exponentially enlarged number of degrees of freedom, significantly complicating a simulation on a classical computer. Matrix-Product-States are a novel representation of arbitrary quantum many-body states. Using quantum information theory, it is possible to show that Matrix-Product-States provide a polynomial-sized representation of one-dimensional quantum systems, thus allowing an efficient simulation of one-dimensional quantum system on classical computers. Matrix-Product-States form the conceptual framework of the density-matrix renormalization group (DMRG). Based upon this connection, deeper understanding of the density matrix renormalization group can be obtained. After a general introduction in the first chapter of this thesis, the second chapter deals with Matrix-Product-States, focusing on the development of fast and stable algorithms. It is possible to extend the Matrix-Product-States approach to be able to represent arbitrary operators, the so-called Matrix-Product-Operators, which allows a fast and flexible calculation of arbitrary expectation values. To obtain algorithms to efficiently calculate groundstates, the density-matrix renormalization group is reformulated using the Matrix-Product-States framework. Further, time-dependent problems are considered. Two different algorithms are presented, one based on a Trotter decomposition of the time-evolution operator, the other one on Krylov subspaces. Finally, the evaluation of dynamical spectral functions is discussed, and a correction vector-based method is presented. In the following chapters, the methods presented in the second chapter, are applied to a number of different physical problems. The third chapter deals with the existence of chiral phases in isotropic one-dimensional quantum spin systems. A preceding analytical study based on a mean-field approach indicated the possible existence of those phases in an isotopic Heisenberg model with a frustrating zig-zag interaction and a magnetic field. In this thesis, the existence of the chiral phases will be shown numerically by using Matrix-Product-States-based algorithms. A key effect of interacting one-dimensional quantum-mechanical many-body systems is the spin-charge separation. However, up to now only signs of the spin-charge separation have been observed in experiments. In the fourth chapter, we propose an experiment using ultracold atomic gases in optical lattices, which allows a well controlled observation of the spin-charge separation (of different hyperfine states of the ultracold atoms) with current state of the art experimental techniques. Ultracold atoms in optical lattices are well described by (Bose)-Hubbard models. In order to support this proposal, we present numerical results for realistic system parameters. Matrix-Product-States are an excellent tool for the simulation of one-dimensional quantum systems, however, they are not well suited for the simulation of higher dimensional systems. For strongly-correlated systems, for instance cuprates-based high-temperature superconductors, quantum fluctuations play an essential role. Classical mean-field theories neglect any kind of fluctuations, thus they are not suitable to describe strongly-correlated systems. The dynamical mean-field theory (DMFT) fully takes local quantum fluctuations into account but neglects any kind of spatial fluctuations. The many-body problem on the lattice is mapped onto an impurity problem, which needs to be solved self-consistently. In the last chapter of this thesis, Matrix-Product-States-based algorithms are used to solve the impurity problem of the dynamical mean-field theory. We present results for a Hubbard model on a one-dimensional lattice and on a Bethe lattice obtained by the dynamical mean-field and compare them with exact results.
Out-of-equilibrium dynamics of non-integrable Hamiltonian many-body quantum systems are characterized by highly entangled wave functions. Near-maximal entanglement arises in systems exhibiting thermalization or pre-thermalization, where the system converges to a steady state with a fixed energy density. Classical simulation of the time dependence of such wave functions requires exponential resources. However, typical computations aim to estimate expectation values of local operators and correlation functions to some expected precision. For thermalizing systems at sufficiently high energy densities, such computations can be done without storing the full wave function by instead simulating the evolution of the local operator, which requires significantly fewer resources. Nonetheless, constructing such resource-efficient classical algorithms remains a challenge for intermediate energy densities, where simulating both the wave function and operator evolution is costly. In this paper, we propose a heuristic approach to accelerate the convergence of Matrix Product State (MPS) simulations of expectation values, applicable across a broad range of energy densities. We estimate the desired observables by rescaling the MPS results at low bond dimensions with a factor that depends on the fidelity of the MPS wave function. Using this technique, we simulated the dynamics of the two-dimensional Transverse-Field Ising Model (TFIM) on a 7×87\times87×8 grid with periodic boundary conditions, using a maximum bond dimension of χ=4096χ= 4096χ=4096 on a single A100 GPU, as well as the dynamics of the two-dimensional XY model on grids of size up to 9×99\times99×9. We compare our TFIM results to similar simulations on a digital quantum processor [R. Haghshenas et al., Nature 653, 56 (2026)], demonstrating excellent agreement and confirming the predictive power of our method.
In the past decade, Matrix Product State (MPS) algorithms have emerged as an efficient method of modeling some many-body quantum spin systems. Since spin system Hamiltonians can be considered constraint satisfaction problems (CSPs), it follows that MPS should provide a versatile framework for studying a variety of general CSPs. In this thesis, we apply MPS to two types of CSP. First, use MPS to simulate adiabatic quantum computation (AQC), where the target Hamiltonians are instances of a fully connected, random Ising spin glass. Results of the simulations help shed light on why AQC fails for some optimization problems. We then present the novel application of a modified MPS algorithm to classical Boolean satisfiability problems, specifically k-SAT and max k-SAT. By construction, the algorithm also counts solutions to a given Boolean formula (\#-SAT). For easy satisfiable instances, the method is more expensive than other existing algorithms; however, for hard and unsatisfiable instances, the method succeeds in finding satisfying assignments where other algorithms fail to converge.
A quantum system will stay near its instantaneous ground state if the Hamiltonian that governs its evolution varies slowly enough. This quantum adiabatic behavior is the basis of a new class of algorithms for quantum computing. We tested one such algorithm by applying it to randomly generated hard instances of an NP-complete problem. For the small examples that we could simulate, the quantum adiabatic algorithm worked well, providing evidence that quantum computers (if large ones can be built) may be able to outperform ordinary computers on hard sets of instances of NP-complete problems.
Tensor-network simulations of quantum many-body dynamics are fundamentally limited by entanglement build-up, which leads to exponentially growing computational costs. Furthermore, these classical simulation algorithms are inherently sequential as typically a tensor network representation of the quantum state is updated incrementally at each time step. We build on recently introduced randomized quantum algorithms for time evolution (TE-PAI), and adapt them to the classical simulation context with the purpose of enabling massive parallelisation. Our MPS TE-PAI approach achieves exact time evolution on average (unbiased estimator) and proceeds by representing an ensemble of randomized shallow Trotter-variant circuits as tensor networks. As each circuit instance yields a deterministic quantum state (or observable expecation value), the only source of randomness is the sampling of circuit variants; the absence of shot noise therefore yields a reduced estimator variance relative to quantum hardware implementations of TE-PAI. We simulate representative disordered one-dimensional spin-ring Hamiltonians, and numerically observe reductions in the per-sample gate-count by a factor of up to 10310^3103 relative to Trotterized MPS evolution, yielding orders of magnitude reduction in the time-to-solution under realistic levels of parallelisation. Finally, we numerically observe that MPS TE-PAI is substantially more robust against severe bond-dimension truncation than product formulas, potentially making it useful for the simulation of strongly correlated systems where truncation is necessary in practice. We also demonstrate that the approach can be used naturally in combination with existing time evolution algorithms, effectively extending their time depth via parallelisation.