# What is the computational cost of simulating a quantum circuit with matrix product states?

If we simulate Quantum circuits with the Matrix Product State (MPS) technique, the computational cost of the simulation depends on the entanglement in the circuit. How can I calculate this quantity for a given quantum circuit? I'm interested in which quantum circuit can be simulated efficiently with MPS and which quantum circuit requires an exponential amount of resources.

Thank you!

• Just run the simulation and see. Generally, there's no easy answer to this question -- except that quantum algorithms with so little entanglement that they can be simulated efficiently classically are not that interesting, as they can be simulated efficiently classically. Commented Feb 4, 2023 at 21:33

A matrix product state is an ansatz for a wavefunction, and it can be used for modeling the qubits associated wtih any circuit, depending on your desired accuracy. If you want all amplitudes in the wavefunction to have an error below $$10^{-100}$$, then you will need huge matrices in your matrix product state, even if the entanglement associated with the circuit is "small". If you just want a wavefunction for the qubits and don't care if its amplitudes have errors as big as $$10^{-2}$$ (for example), then you can use relatively small matrices in your matrix product state, even if the amount of entanglement is "large".
For any arbitrarily given circuit, it's not possible to represent the wavefunction of the qubits by an MPS ansatz with no error, without using resources that scale exponentially with the number of resources, so the size of the matrices that you need will depend not only on the nature of the circuit but also your desired accuracy. Finally, even if you asked "given a circuit and a desired maximum error of $$\epsilon$$ in the wavefunction amplitudes, how big do the matrices in the MPS ansatz have to be?", there is no known answer that applies to "any given circuit".