Simulate Large Quantum Circuits With Low Entanglement Using the Matrix Product State Simulator
By Merav Aharoni, Yael Ben Haim
Learn more about the Matrix Product State Simulator here.
It’s difficult to answer “how big a quantum computer can a classical computer simulate,” because the answer is, well, it depends. But built into Qiskit, we have a simulator that can tackle certain kinds of quantum circuits with hundreds of qubits with relative ease.
Quantum circuit simulators are software programs used to mimic the behavior of quantum computers. They aid us in quantum computers’ research and development, and in gaining a better understanding of quantum algorithms. Crucial to using simulators is to pick the one best suited to the circuit you hope to simulate. If you’re aiming for circuits with lots of qubits but relatively little entanglement, the Matrix Product State Simulator might be your best bet.
The most common approach to implementing simulators stores the statevector as an array of 2^n complex numbers, where n is the number of qubits. Every quantum gate applied to the qubits changes the values in this array. This representation precisely describes the quantum state — but clearly, the memory required by this simulator scales exponentially with the number of qubits. The circuits we can represent this way are limited to around 30 qubits (depending on the computer’s memory).
But we don’t always need 2^n values to represent a circuit, especially when the circuit contains a relatively low amount of entanglement. A simulator based on the matrix product state (MPS) approach is based on a completely different concept. Using this approach, it is sometimes possible to represent circuits of hundreds of qubits. For the MPS simulator, the limitation on the circuit stems from the degree of entanglement, not from the number of qubits.
This approach represents every qubit by a single tensor, or 3D matrix of complex numbers, all lined up such that only neighboring qubits can interact. The simulator represents entanglement among the qubits with a series of n-1 vectors, where n is the number of qubits. Each vector represents the entanglement between all qubits to the left of the vector and all qubits to the right. We refer to the sizes of these vectors as the bond dimension and they are a measure of the entanglement in the circuit.
Initially, all these data structures are small: the tensors are 2x1x1 and the vectors are of length 1. Gates applied to a single qubit do not increase the size of the structures. Gates applied to 2 qubits may increase the sizes of the corresponding tensors, as well as that of the vector between them, by a factor of 2. Thus the number of tensors and of vectors is constant throughout execution of the circuit. However in the worst case, the sizes of the data structures may scale at O(2^(n/2)). In other words, the representation becomes exponential when entanglement is high in the circuit.
This representation has obvious advantages: it’s a simulator that doesn’t necessarily scale exponentially with the number of qubits. Quantum gates, computing expectation values, and measurement aren’t necessarily exponential, either. Additionally, the structure gives an immediate measure of the amount of entanglement of the circuit, simply by looking at the size of the data structures.
These results were clear in our tests: using the MPS allowed us to run circuits that are larger than the commonly used statevector simulator could. Here’s an example comparing the statevector simulator and the MPS for a series of chemistry benchmarks. As you can see, the time it takes to run the statevector simulator quickly increases, while the MPS can handle a ~70 qubit circuit in the same amount of time the statevector simulator can simulate a ~20 qubit circuit.
Here’s another example we tried: Using an MPS simulator, we could run Quantum Fourier Transform on hundreds of qubits, while using the statevector simulator becomes impossible at around 30 qubits.
Finally, the MPS representation lends itself readily to approximation. We can keep the data structures small by truncating the smallest values in the vectors after each operation. Using approximation, we can limit the sizes of the vectors and the tensors. However, note that we must use approximation with care, otherwise fidelity may decrease significantly. We show this in the following graphs, where you can see the results of expectation values on quantum volume circuits using different levels of approximation (ie., the cutoff threshold).
We hope that we’ve convinced you of the usefulness of this simulator for simulating quantum circuits with less entanglement, such as in certain chemistry problems. To learn more and to try the MPS simulator on your own, get started with Qiskit by clicking here.
