# How to efficiently get the largest probabilities / amplitudes of a quantum state stored as an MPS?

Let's say, that we have the following pure, superposition state

$$|\psi \rangle = \frac{1}{\sqrt{2}}|000001 \rangle + \frac{1}{2}|101101 \rangle + \frac{1}{2}|100100 \rangle$$

stored in the MPS form. So, for that purpose we would need 6 different $$M_i$$ matrices, each corresponding to single component qubit / site. In the further part of this post I will refer to each component as qubit, for simplicity.

If we divide this system into two subsystems $$A$$ and $$B$$, where $$A$$ consists of first 3 qubits and $$B$$ of the 3 remaining ones, the resulting von Neumann entropy will be equal to 1.5, which is much smaller than the maximally allowed value of 3 ($$= \log_2 8$$). Because of that, we could discard some Schmidt values while generating the MPS representation (with the use of SVD), and as a result reduce the size of the bond connecting $$M_2$$ and $$M_3$$ matrices. For a maximally entangled state this bond size would be equal to 8, but in our case we could achieve some smaller value. This compression will be crucial later on.

Now, in the scenario that I'm interested in, I don't know the exact form of $$|\psi \rangle$$, but it can be obtained in an efficient way (e.g. from oracle, or using DMRG / TEBD algorithms). It's crucial, that this final MPS is a compressed one, with respect to the full Hilbert space of the whole system. At the end of the day, I will be interested in much larger systems than the one given above, as an example, but all these larger systems can be compressed by truncating the bonds. My question is the following - how to get from this given MPS the largest amplitudes and states, to which they are corresponding to? So for the above example, I would like to obtain $$1 / \sqrt{2}$$ value and $$|000001 \rangle$$ basis state. The next, smaller amplitudes would also be interesting, but getting them is not essential.

Three things came to my mind, but none of them sounds reasonable:

• Multiplying all $$M_i$$ matrices to obtain the full state and finding the largest amplitude. However this is pointless, because in that way I would obtain a vector of the size of the full Hilbert space, so the compression coming from an MPS would be lost.
• Sampling the state - calculating a single amplitude for a chosen basis state can be done efficiently, but in the worst case I could make $$2^n$$ such samplings, where $$n$$ is the number of qubits.
• Calculating the expected value of each qubit in the $$Z$$ axis, combined with calculating $$\langle Z_i Z_j \rangle$$ correlations on neighbouring sites. Thanks to that, I could make a better guess when choosing the basis state, for which I could calculate the amplitude. However, this would fail for example, for the following state $$|\psi \rangle = 1 / \sqrt{2} (|000000 \rangle + |111111 \rangle)$$.

Do you have any ideas on how to tackle this problem?

• Amplitudes are basis dependent. In which basis do you want the largest amplitude? The computational basis? Oct 6, 2022 at 6:21
• On the spot, I would guess this can be solved with dynamic programming. I'll try think about it later. Oct 6, 2022 at 6:24
• Yes, the computational basis. Oct 6, 2022 at 10:36
• Thinking about it, the question might be tricky, and it might depend on how much you are asking for. Imagine, e.g., that there are two states with almost equal amplitudes, different by some extremely small $\epsilon$. Do you still demand that you get the largest one? Or are you happy to obtain the largest one up to some $\delta$? It could well be that the difficulty depends on the value of such a $\delta$. Oct 9, 2022 at 12:52
• Getting the largest one up to some $\delta$ would be enough. To be honest, even getting any "significant" amplitude (that is much larger than 0) and its corresponding computational basis state would be a good starting point. Oct 10, 2022 at 9:03