Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

How to prepare an MPS circuit #218

Open
ACE07-Sev opened this issue Feb 5, 2024 · 9 comments
Open

How to prepare an MPS circuit #218

ACE07-Sev opened this issue Feb 5, 2024 · 9 comments

Comments

@ACE07-Sev
Copy link

ACE07-Sev commented Feb 5, 2024

What is your issue?

Greetings there,

Hope all are well. I am quite new to the quimb package, and was hoping to ask if you have any existing code which would perform the following :

  1. Define the classical data to be encoded
  2. Convert the classical data to a quantum state vector (normalizing, and 0 padding)
  3. Define the infidelity upper bound, and calculate the MPS (where the error upper bound would define the optimal bond dimension)
  4. Prepare the MPS circuit

What this would do is approximate the initial input state through an MPS, and allow one to use that instead of the exponentially scaling exact ones like Mottonen and Shende. For your kind reference, here is the paper I am trying to implement for this :
https://arxiv.org/pdf/2311.07666.pdf

P.S : Step 1 and 2 are quite self-explanatory, and I have code for that, so basically a code which would take a state vector with an error upper bound, calculate the MPS, and then create the circuit for that MPS. Also, if you do indeed allow this (fingers crossed), I would appreciate it if you can link the reference paper you used for my learning, and to confirm if the algorithm allows you to scale the depth linearly with respect to the number of qubits, basically $O(NX^2)$ where X is the bond dimension.

@jcmgray
Copy link
Owner

jcmgray commented Feb 8, 2024

Hi @ACE07-Sev, I'm afraid there are no examples like this at the moment. I'm also not familiar with the paper you linked or the specific task. But some general thoughts are the following:

  1. You can construct a MPS from a dense vector with the following method: https://quimb.readthedocs.io/en/latest/autoapi/quimb/tensor/index.html#quimb.tensor.MatrixProductState.from_dense.
  2. But you would probably want to actually use someting like 'tensor train cross interpolation' to construct the MPS directly from the data (no implemented in quimb yet I'm afraid) without the exponential sized intermediate state vector
  3. The most obvious way to turn an MPS into a circuit is probably by generic gradient optimization with some ansatz circuit, this quimb can do.
  4. There are no guarantees about the depth of the circuit required, though for some relevant MPS it seems the circuits do not need to be deep (e.g. https://journals.aps.org/prx/abstract/10.1103/PhysRevX.12.011047) to be expressive. The classical cost will be $\chi^3$.

@ACE07-Sev
Copy link
Author

I see. I am having a bit of a trouble understanding number 4. Why isn't the depth guaranteed? I thought MPS to circuit required $O(Nχ^2)$. That is actually the main motivation behind trying to implement this paper.

@jcmgray
Copy link
Owner

jcmgray commented Feb 8, 2024

Sorry I was not very clear!

OK well an MPS of $N$ sites with bond dimension $\chi$ can be made up of unitaries $U$ of size $\sim \chi \times \chi$. Assuming $\chi$ is a power of 2, it can be implemented with $n=\log_2(\chi)$ qubits. A general dense unitary acting on these $n$ qubits can be implemented exactly in $\mathcal{O} (2^{2n} )$ two-qubit gates which does equal $\chi^2$ so the scaling you mention is guaranteed, but since $\chi=2^n$ it is not a linear dependence on number of qubits. (There is still however a linear dependence on the number of 'physical sites' you are representing, $N$.)

Want I meant to say was, there has been a fair bit of empirical work showing that in fact a circuit of depth linear in $n$ i.e. $\log_2(\chi)$ can approximately but adequately reproduce the unitaries from physically relevant etc. MPS, but there are no guarantees that this will hold for an arbitrary MPS, as far as I am aware!

@ACE07-Sev
Copy link
Author

Please don't apologize, I am incredibly thankful you are sparing the time to discuss this with me.

I see! In the paper I mentioned, the key condition is that the entanglement entropy and infidelity saturate as the size of the state/system grows (meaning the number of qubits $N$ increase), which allows one to maintain a constant bond dimension even as the state size grows, hence the term $χ^2$ remains constant as we increase the state size, therefore the growth is linear in number of qubits $N$.

So, you would have a linear function representing the growth of the MPS circuit depth, and an exponential function representing the depth of the traditional exact encoders like Mottonen and Shende, like the figure blow :
image

Which after a certain number of qubits (the intersection of the two functions), MPS becomes the better approach, and as qubits increase after that point, the value of MPS grows significantly. So, basically the way they explain this in the paper I sent above is as follows :
"This work focuses on utilizing Tensor Networks (TN), more specifically Matrix Product States (MPS), to prepare arbitrary $N$-qubit quantum states. MPS are states which can be prepared in linear complexity using a depth of $(χ^2 N)$ where $χ$ is the bond dimension. MPS are distinguished by their low entanglement entropy (weakly entangled states). This approach serves as a more efficient state preparation algorithm for approximately encoding the classical data, and is useful in the context of Quantum Machine Learning (QML) as it helps the ansatz to reach better generalization when trained. However, MPS does not come without its limitations. As mentioned, the encoding is approximate, indicating a degree of infidelity (error) associated with the prepared state which depends on the bond dimension chosen. As the bond dimension increases, the infidelity is reduced. For an arbitrary state, the bond dimension may need to be quite large, eliminating any advantage of using MPS, however for weakly entangled states which possess low bonds, MPS is a great alternative. Weakly entangled states possess a low entanglement entropy, or in classical terms, are data with a quickly decaying Fourier spectrum. In Layman terms, these data are those which are composed dominantly by low frequency components, i.e., images."

@ACE07-Sev
Copy link
Author

Did I understand what you explained accurately? Would the condition of keeping the bond dimension constant at the cost of minor infidelity sufficient for keeping the growth strictly linear?

@ACE07-Sev
Copy link
Author

I was wondering, would it be possible if you could perhaps kindly have a look at the paper I sent above? I fully understand that this is for github issues, and therefore what I am asking is quite inappropriate and inconsiderate, however, I feel you would have a better idea of what I am proposing.

There is also this paper, which actually does the exact same thing (to the point of using the same data, aka images), and it's only 5 or so pages.
https://arxiv.org/pdf/2310.05897.pdf

@ACE07-Sev
Copy link
Author

ACE07-Sev commented Feb 8, 2024

My goal at the moment is to simply make an algorithm which would take a state vector (a normalized list of values, with a length of $2^N$, where $N$ is the number of qubits), calculate its MPS, and then create the circuit which would prepare the MPS, in a way that would match the output of the papers I sent.

If I understand correctly, you mentioned quimb does allow for MPS to circuit conversion, so I am wondering if we can pair it with tensornetwork package and do what I described.

Would you be interested in assisting me with this implementation? I have a repo prepared, so I can add you there, and I would appreciate any help or guidance you can provide considering your current commitments. Again, I would like to thank you for all of your guidance and kind help thus far, it is simply more than I could ever ask for, so I do hope you can forgive my over-eagerness which I understand may sometimes come across as being inconsiderate or pushy hehe. At the moment, I am a bit lost on how to do this, so I would deeply appreciate your experience and guidance regarding this small project.

@jcmgray
Copy link
Owner

jcmgray commented Feb 9, 2024

I'm afraid I don't have time to do a deep dive into these papers or develop any research code! but I think the quote from the paper above is all consistent.

If you have a $L$ dimensional quantum system, then in the general case it requires a $2^L$ coefficient state vector description. For a certain subset of quantum systems (including many relevant things like images) you can approximately describe them using the MPS with bond dimension $\chi$ and only $L\chi^2$ parameters.

To implement this MPS exactly on a quantum compute you need $n=\log_2(X)$ qubits and a circuit depth $L2^{2n}=L\chi^2$.

So with the assumption that a $2^L$ state-vector can be efficiently described by an MPS (which will depend on what and how you are trying to encode it), you will need a circuit depth linear in number of sites of the MPS $L$, and exponential in the number of qubits $n$, but this number of qubits is logarithmic in $\chi$ so overall yes the scaling is $L \chi^2$.

@ACE07-Sev
Copy link
Author

Ohh, that makes so much more sense now. I still am digesting it, but I think I am clear now. Thank you so much! May I keep this thread open?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants