Toward the first quantum simulation with quantum speedup - paper implementation

[Rastaban-TzW]

Proposal

Team

Keith K. Ng @icaruswhite @Rastaban-TzW - Nanyang Technological University, Singapore

Paper Details

Title: Toward the first quantum simulation with quantum speedup
Authors: Andrew M. Childs, Dmitri Maslov, Yunseong Nam, Neil J. Ross, and Yuan Su

Brief Problem Statement

Simulating the time evolution of spin systems is a classically hard problem that is both useful, and easy to simulate with quantum computers. The implementations described in this paper are highly optimized, and comparisons are made between these implementations. By finding the best method of quantum simulation, we provide a detailed blueprint for what could be the first of many useful applications of quantum computers. Furthermore, the "unary iteration" method described in this paper is likely to be generally useful among a variety of applications, especially those involving LCUs, qubitization and Hamiltonian simulation, since it allows the following construction to be implemented more efficiently, even in cases where the different operations do not commute:

@qfunc()
def selectV(selector: QNum, cases: QFunc[], x: QArray):
    repeat(cases.len(),
    lambda i: control(selector==i, lambda: cases[i](x))
    )

Implementation

This paper compares three different methods for simulating the spin system Hamiltonian:

1. High-order product formulas (PF)
2. Taylor series (TS)
3. Quantum Signal Processing (QSP)

The authors of the paper have made their code available on Github, but it is written in Quipper. We plan to rewrite their code in Classiq, with particular focus on their QSP implementation, which uses a construction they call "unary iteration". This construction is generally applicable to any situation where Linear Combinations of Unitaries (LCU) are needed, among others.

Future Directions

While this paper is among the first to use unary iteration, other implementations have been made with different width/depth tradeoffs, as described in "Rise of conditionally clean ancillae for optimizing quantum circuits". In particular, while this paper's implementation uses a number of ancillas logarithmic in the number of unitaries making up the LCU, Gidney describes another implementation which only requires a number of ancillas scaling as the logarithm of the logarithm, though its structure is more difficult to describe.

Personal Note

As stated previously, my primary interest is the unary iteration scheme, and I also plan to implement this as part of QSP first. The other methods will be implemented afterwards, time permitting.

[TomerGoldfriend]

Sounds perfect @IcarusWhite ! Please note that we already have built-in product formulas such as Suzuki Trotter and qDRIFT, which already have optimized implementations. Focusing on the unary iteration is great, as you said, it is relevant for other use-cases as well.

In addition, we have a basic example of applying QSVT for Hamiltonian simulation (this is a pedagogical tutorial and there are several places in which it can be optimized). There, the block encoding is done with a naive LCU. It might be helpful to go over it.

Finally, please note that we accept high-quality implementations to our repository and will be glad to accept a contribution that meets our standards.
Feel free to reach out to the community for any questions!
Good luck!

[Rastaban-TzW]

At my repository here I now have two files of interest:

1. SelectV.py, containing the translation of the Quipper/Haskell file from the paper.
2. hamiltonian_simulation_with_block_encoding.ipynb, edited to use SelectV.py.

I believe this follows the spirit of previous discussion: implementing the core algorithm while using the existing QSP implementation.

Known issues:

1. SelectV.py is not a qmod file, and so does not go into /functions as is.
2. SelectV.py is based on a Haskell implementation, and currently expects a number in big-endian representation. There are helper functions in the file, and the .ipynb also defines another, but a full rewrite is likely necessary.
3. Related to this, the original Haskell implementation defined a controlled operator as a function taking a control qubit and a target system. Experience has shown that it is much easier to only require the control qubit as input, i.e. QCallable[QBit],
   and have the "target" bound in closure, but this is a significant refactor. (EDIT: see PR for more info.)
4. The .ipynb uses a controlled_selectV inside a controlled block; I am unsure whether the program is using the control line properly, and it would require a substantial refactor to "link" the controls properly.

And on another note, I appear to have broken the venv on the Classiq online studio, somehow, while trying to fix a frustrating issue. I've been testing on a local venv on my laptop instead, but it's very inconvenient...

Please advise on next steps!

Edit: pull request made attempted at #896 -- I have to clean things up a bit before I try again.

Edit2: forked classiq-library repository, moved files to a new directory in tutorials. Attempting branch rebase...

[Rastaban-TzW]

New pull request made at #897. Hopefully this works...

[Rastaban-TzW]

Previous pull request closed due to test failure. Fixed links. Trying again at #898.

[Rastaban-TzW]

Tests added and successful.
I might go back and fix some of those outstanding issues later, but the concept is there....

[Rastaban-TzW]

Outstanding issues fixed! Mostly.
As noted in the pull request, one of the "features" needs the user to understand closures to use properly. It's in branch notarget for now.

[Rastaban-TzW]

Updated notebooks and tests to be compatible with pre-commit.
I think I am comfortable with what is in the PR now. I might make some small changes later, but the PR is essentially feature-complete now.