3
$\begingroup$

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!

$\endgroup$
1
  • 2
    $\begingroup$ 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. $\endgroup$ Feb 4, 2023 at 21:33

1 Answer 1

1
$\begingroup$

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".

Therefore, the size of the matrices required in your matrix product state, do not depend just on the amount of entanglement between the qubits, but also on your desired error.

In extremely rare cases, like in the case of a GHZ state, the MPS ansatz will give you the wavefunction with zero error, without requiring huge matrices, so circuits like the following one are in the category that you seek:

enter image description here

However, this is not possible for the vast majority of circuits. The required size of the matrices in the MPS ansatz depends on the amount of entanglement between the particles (or qubits), and you asked:

"How can I calculate this quantity for a given quantum circuit?"

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".

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.