quantumlib
Add matrix product state (MPS) preparation algorithm
The sequential MPS preparation algorithm of Schön et al. (arXiv:quant-ph/0501096) would be a valuable addition to Qualtran, providing a leading state preparation algorithm. The Toffoli compilation of this algorithm is costed in appendix E of the recent Fomichev et al. paper (arXiv:2310.18410), and it used building blocks like PREPARE-based reflections.
The goal is to construct a composite bloq which will have as input the MPS (or possibly only the shape of the MPS tensors and the required bit precision) and implements the MPS preparation.
As an element of this algorithm, we need a bloq combining PREPARE-based reflections with an ancilla to synthesize $k$-qubit unitary operations where only the first $m \leq 2^{k}$ columns are defined. See eq. E1 to E8 of arXiv:2310.18410. This bloq can be implemented by using existing primitives.
To construct this algorithm, we need a building bloq $W$ preparing a state $|w\rangle = W|0\rangle$.
This state has a specific structure: the output register can be split into an auxiliary qubit $R$ (reflection ancilla) and a target register T $$|w\rangle = \frac{1}{\sqrt{2}} ( |1\rangle_R |\alpha\rangle_T - |0\rangle |u_\alpha\rangle_T)$$ where $|j\rangle_T$ is a computational basis state which can be prepared only using CX gates (controlled on $R$), and $|u_j\rangle_T$ is a generic state which should be constructed by controlled-PREPARE. [See Eq. E5 and E8 of arXiv:2310.18410)
To do this, we should first implement a controlled version of PREPARE.
Copying this over from the closed PR (#615) for visibility / continue the conversation.
Thank you for your detailed answer, now the tensor contract works.
Also, I plan to implement an MPS preparation algorithm (issue #596) and I would like to tell you what I think I need to implement to avoid duplicating code. In order to do so I need to compile a n qubit quantum gate of which only k columns are specified using Householder reflections (refer to [1] https://arxiv.org/abs/2310.18410 sections IIIB page 7 and apendix E on page 24 for the details) . The blocks that I need are:
- A bloq for the reflection I-2|w><w| (equation E3 from [1]), for which I plan to use ReflectUsingPrepare with a custom prepare oracle.
- A prepare oracle to prepare the state |w>, equation E5 and E8 from [1]. This I plan to implement myself, as the state |w> is easily decomposed in other gates and using a generic state prepare oracle would be overkill.
- For the prepare oracle W I also need a controlled state preparation bloq. I saw that qualtran has the class StatePreparationAliasSampling, but I see two problems with it for this specific use case. The first one is that it produces entangled junk qubits, which need special handling and could interfere with the rest of the algorithm. The second one is that, as far as I can tell, there is not a controlled version of it. For this reason, I implemented the state preparation algorithm from https://arxiv.org/abs/1812.00954 page 3, which produces no entangled garbage qubits and can be easily adapted to be controlled.
- Finally, for the previous step I need a programable rotation gate array. I found the class ProgrammableRotationGateArray, which something similar, but I think that for this algorithm it would be more efficient to use a gradient state and perform the rotations via phase kickback (which is the technique used in the paper), because there are multiple rotation gate arrays and this would lead to redundancies.
Please let me know if those would be valuable contributions to the project or if there are already valid alternatives to them which I can use. Thanks!
That sounds good to me. @tanujkhattar might have more insights here as he added most of these bloqs.
Bumping this up with some context:
MPS state preparation reduces to unitary synthesis via approach described in https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.95.110503 and Unitary synthesis can be done via approach described in https://arxiv.org/abs/1812.00954. There's also more recent and optimized constructions given in https://arxiv.org/abs/2409.11748 which can be used.
https://github.com/quantumlib/Qualtran/pull/758 is a step in this direction but never got merged.
