unitaryHACK #2: Optimization of MPO construction

[TimWeaving]

Goal: Optimize MPO construction in Symmer.

Reward: $200

A subroutine of qubit subspace techniques is the identification of the correct symmetry sector - an assignment of $\pm1$ eigenvalues to the chosen stabilizers over which we project to yield a reduced subspace. Naively this problem scales exponentially in the number of stabilizers one wishes to enforce; however, if you have access to a reference state with non-zero overlap with the ground state, the eigenvalue-assignment problem becomes trivial - 'measure' each symmetry generator in the reference state and we get the assignment for free. This poses a problem - how do we identify such a reference state? For quantum chemistry application we may choose the Hartree-Fock state, but in general it is not straightforward.

One approach is to use the Density Matrix Renormalization Group (DMRG), that allows you to construct approximate ground states, whose overlap is dependent on the bond dimension of an associated Matrix Product Operator (MPO).

This is implemented in symmer.approximate, however there are optimizations that can be made to speed-up the construction of MPOs, for example it could be parallelised.

That is the goal of this bounty.

[s-aldaihan]

Hi, I am interested in this issue, can you please assign it to me? @TimWeaving

[AlexisRalli]

Hi @s-aldaihan - thanks for your interest! The way this hackathon works is that you have to open a PR that will be approved and merged, then the issue/task will be assigned to you and closed. If more than one coders submit PRs for the same issue, the maintainers will chose the solution they consider the best, or even decide to split the bounty.

We welcome any pull request you make on this issue. Good luck and feel free to post any questions here.

[adilnaut]

Hi @TimWeaving I've run MPO construction part through profiler and generated heat graph. I am not very experienced with profiler, but it seems like numpy.core._multiarray_umath.implement_array_function might be causing some overhead in execution (~30 % in self time) and data transfer 2 * ~80 calls to tensordot with 20-30% in transfer. Note: I've run it with handwritten example and it executes for 0.5 seconds in total.
['ZXZYXYYZIZZ', 'XZIIYZIIYZX', 'XYZXYZXIXYZ', 'ZIXXXYXIXYZ', 'ZXZYYIZIZIZ', 'ZXZZYYYZIZZ', 'XZIIYZIYZIX', 'XYZXYZXXYZI']

This was also discussed here

Apart from that, my current intuition so far would be to "achive parallelism" by re-writing loop/iterative parts of p_strings_to_mpo and and sum_mpo and truncate_MPO with corresponding equivalent yet more efficient matrix operations (if that makes sense). Another way might be just to pool with multi-worker threads (?).

Would be happy to get any comments if you think I am on a right way or misunderstood which parts should be optimized!

[adilnaut]

@AlexisRalli how important is to Truncate MPO after each consequtive sum operation? What difference would it make if we just truncate it once after we build it - would it be numerically inconsistent? Running trough allclose tests with WordOp = PauliwordOp.from_list(pauli_list_3, coeff_vec_1) with truncation in the end or without truncation whatsoever passes, but I wanted to check what it tests exactly. I think I am onto some potential speedup without truncation due to fact that all the middle term summations become diagonal appends; while all the other construction and summation are list operations. Which give an opportunity to run them in parallel with multiprocessing.

[adilnaut]

@TimWeaving @AlexisRalli should I delete this PR as unitary hack has come to an end and I haven't received any communication?

[AlexisRalli]

@TimWeaving @AlexisRalli should I delete this PR as unitary hack has come to an end and I haven't received any communication?

Hey @adilnaut - sorry for the slow reply. What you have written looks good. I am just running the unit tests and if they pass I'll merge it into main. The unitary hack event is still valid unitl the end of today, so you should be getting this bounty.

[natestemen]

@AlexisRalli looks like this needs to be reassigned to the hacker who completed the bounty so they can get proper credit. Would you mind switching it?

[AlexisRalli]

@AlexisRalli looks like this needs to be reassigned to the hacker who completed the bounty so they can get proper credit. Would you mind switching it?

@natestemen - My mistake. Should be updated now