Inefficient sampling of matrix product states

[smiserman]

What is the expected behavior?

For larger bond dimensions and a larger number of qubits, the implemented smapling algorithm in qiskit is not efficient. It is not necessary to copy the matrix product state for each sample and then transfer a single qubit measurement via SVD to the other qubits (at least this is how it looks in the C++ code). Copying very large matrix product states each time and repeated SVD on $2 \chi \times 2 \chi$ matrices is computationally expensive! Instead, one can successively calculate the |0><0| element of the conditional density matrix. Sampling over all qubits this algorithm is only of order $O(N \chi^2)$ with $N$ qubits and maximum bond dimension $\chi$. I implemented this in numpy in a few lines of code and it is 30-40 times faster than qiskit's implementation. Details of the code and further hints can be found at Understanding efficient simulation of NISQ quantum computers with matrix product states on my reserchgate page.