Block encoding of select structured matrices

[virajd98]

Hi,

I'll be implementing most parts of this paper.

Block encoding is a nice technique to input non-unitary matrices on a quantum computer by embedding them in larger unitaries. But, this process is not trivial for random matrices. However, for certain structured and sparse matrices this can be done In efficient ways by constructing appropriate oracles that exploit the structure and sparsity in the matrices. This paper explicitly provides such construction for the following matrix structures: Checkerboard matrix, Toeplitz matrix, Tridiagonal symmetric matrix, 2D Laplacian with Dirichlet boundary conditions, etc. Notably, the techniques provided in the paper allows for embedding large matrices using fewer resources compared to the widely known LCU approach for block encoding.

Technical Approach for Implementation:

I'll construct a general quantum circuits for block encoding the structures stated above via Qmod as per the details given in the paper and then benchmark the algorithm. Also, beyond the paper, I'll provide estimates as to how this approach scales efficiently compared to linear combination of unitaries. I'll try to complete implementing all the aspects of the paper. The approach and final deliverable would be similar as one of my past contributions on block encodings to classiq.

Deliverables

A detailed Jupyter notebook with all implementations and benchmarks.

Thanks

[TomerGoldfriend]

Thank you @virajd98 for this issue. Sounds good!
Please note that we accept high-quality implementations to our repository and will be glad to accept a PRs that meets our standards. Looking forward for your notebook.