qiskit-camp-asia-19
qiskit-camp-asia-19 copied to clipboard
qiskit-community
Graph colouring and an improved hamiltonian simulation algorithm
Abstract
The problem of Hamiltonian simulation can be described as, given a hermitian matrix H and a real number t, find a circuit for exp(iHt).
Usually this is a hard problem and a widely used algorithm is:
- Find a decomposition H = H_1 + H_2 +... + H_m such that we can find circuits for each exp(iH_j t).
- Approximate exp(iHt) by a product of the exp(iH_j t) (i.e. by putting the smaller circuits in sequence) according to the e.g. Lie-Trotter and Suzuki formulae.
Step 2. is already implemented in Qiskit. The goal of this project would be to obtain the full algorithm by implementing Step 1., which would consist on two parts: finding a decomposition and finding circuits for each exp(iH_j t).
One of the existing ideas to find a decomposition is to view H as the adjacency matrix of a graph, find an edge colouring of such graph and associate the subgraph induced by colour j to H_j. Such a decomposition guarantees that the H_j are 1-sparse (at most one non-zero entry per row or column), and in the literature it has been described how to obtain the circuits for the Hamiltonian simulation of 1-sparse matrices.
Refereneces:
- Finding a decomposition: https://arxiv.org/pdf/quant-ph/0209131.pdf , https://arxiv.org/pdf/quant-ph/0508139.pdf
- 1-sparse Hamiltonian simulation: https://arxiv.org/pdf/quant-ph/0209131.pdf , https://prism.ucalgary.ca/handle/1880/41417/restricted-resource?bitstreamId=4fafa2ac-6065-4984-aa1c-985601bf4123 [Section 4.4.2.]
Description
Members
- @githubhandle
- @githubhandle - Slack:
@slackhandleemail:[email protected] - Qiskit Coach: @anedumla
Deliverable
GitHub repo
Hi, this sounds interesting. I hope we could have a discussion on this topic.
Hi, this sounds interesting. I hope we could have a discussion on this topic.
Good to hear that! yes, of course, we can talk about it.
