Toward the first quantum simulation with quantum speedup - paper implementation

[IcarusWhite]

Proposal

Team

Keith K. Ng @IcarusWhite - 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!