Paper Implementation Challenge #855

[Rastaban-TzW]

PR Description

For Paper Implementation Challenge: see https://github.com/Classiq/classiq-library/issues/855 Two files have been added to a new directory at algorithms/lcu_with_unary_iteration

File location and names tentative.

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

Note that, using controlled_selectV(ops: QCallableList[QBit, QArray[QBit]], q: QBit, xs: QArray, target: QArray) from SelectV.py, we can implement this LCU more efficiently than the naive implementation:

repeat(
    count = ops.len,
    iteration = lambda index: if_(
        condition = (index == xs),
        then = lambda: ops[index]
    )
)

Known issues:

1. SelectV.py is not a qmod file, and so does not go into /functions as is. (edit: this may not be a problem if it is treated as an "algorithm", but the construction is essentially a QNum version of functions/open_library_definitions/switch.qmod, and is therefore extremely useful...)
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: https://github.com/Rastaban-TzW/classiq-library/tree/notarget; also, SEE BELOW)
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.~~
5. ~~The LCU tutorial no longer exists! I have redirected those links to the VLQS with LCU directory, for now.~~
6. The directory name could probably be changed; while this particular demonstration is for Hamiltonian simulation, the selectV algorithm is useful for any LCU application, and many others.

Some notes

• [x] Please make sure that you placed the files in an appropriate folder

• [x] And that the files have indicative names.

• [x] Please note that Classiq runs automatic code linting, which may minorly alter some files.

  • [x] If you're familiar with pre-commit, you may run pre-commit install, and then at each commit, your files will be altered in a similar way

[review-notebook-app[bot]]

Check out this pull request on 

See visual diffs & provide feedback on Jupyter Notebooks.

---

Powered by ReviewNB

[Rastaban-TzW]

That's odd. I don't see where the failure is coming from - I already removed those links from the new file... (edit: two notebooks should not have the same name, no matter where they are. Specifically, the new notebook triggered tests on the old notebook, which has broken links. Renaming the new notebook avoids these errors, though I also had to add a test myself later.)

[Rastaban-TzW]

Remark: issue 3 on the list has been solved in a feature branch, https://github.com/Rastaban-TzW/classiq-library/tree/notarget, but requires users to pass gate targets in as a closure, e.g.

def make_lambda(i):
    return lambda ctrl: CX(ctrl, i)

oplist = [make_lambda(i) for i in range(8)]

While this reduces boilerplate, especially when an operation has to be passed through multiple layers of iteration, it is very easy to make difficult-to-debug errors: for example, [lambda ctrl: CX(ctrl, i) for i in range(8)] is incorrect. (Though this error will also come up with the version in main under many common usecases.)

I leave it to the maintainers' discretion which branch is more useful. (edit: The semantics of switch are closer to the notarget version, but I will still leave this to reviewer discretion.)

[TomerGoldfriend]

Thank you @Rastaban-TzW . One general comment: In your PR you essentially took an existing notebook from our repo, as is, and replaced one block in it. The definition of the block is given in a separate Python file. The new thing you are contributing is the unary operation given by the selectV function. Thus, I would make a notebook for it explicitly, including some explanation about its implementation. Then, after defining this new function in the notebook, with its brief theoretical background, you can plug it into a larger, more complex algorithm (e.g., a QSVT). For this latter part, there is no need to provide too much background and explanation, you can link to the existing notebook.

I have several other technical comments, but please address the general comment first.

[Rastaban-TzW]

Thank you for your remarks. I had some difficulty with the implementation, so I did not originally have time for that write-up. What timeline would I have for it?

Secondly, did you have an opinion on which QCallable format to use ? Maintaining a separate feature branch for the "notarget" format is getting tedious...

[TomerGoldfriend]

Thank you for your remarks. I had some difficulty with the implementation, so I did not originally have time for that write-up. What timeline would I have for it?

How much time do you think you will need @Rastaban-TzW ?

Secondly, did you have an opinion on which QCallable format to use ? Maintaining a separate feature branch for the "notarget" format is getting tedious...

Can you specify exactly what is the problem you encountered with the QCallable? In addition, please do not modify the pre-commit file. Let us know why you had to change it and we will handle it.

[TaliCohn]

@Rastaban-TzW Are you still working on this?

[Rastaban-TzW]

Apologies. Things have become quite busy here - I am trying to finish all projects at this current position before I leave. The supplementary materials of the cited paper, as well as the Gidney paper, have good explanations of the high-level algorithm. I may also be able to write something quickly during the weekend.

[TomerGoldfriend]

@Rastaban-TzW are you still working on this?

[Rastaban-TzW]

Yes, I've been very busy, but I should be able to make a short writeup soon.

[TomerGoldfriend]

@Rastaban-TzW , I am closing this PR due to inactivity. You can reopen this if and when you continue to work on it.