search

qiskit-community / qiskit-camp-asia-19

31 stars 7 forks source link

Graph colouring and an improved hamiltonian simulation algorithm #20

Open anedumla opened 4 years ago

anedumla commented 4 years ago

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:

  1. Find a decomposition H = H_1 + H_2 +... + H_m such that we can find circuits for each exp(iH_j t).
  2. 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:

Description

Members

Deliverable

GitHub repo

JRWSP commented 4 years ago

Hi, this sounds interesting. I hope we could have a discussion on this topic.

anedumla commented 4 years ago

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.

atsuyahasegawa commented 4 years ago

My name is Atsuya Hasegawa. I am interested in it.

YU-ZU commented 4 years ago

I’m in

martian17 commented 4 years ago

I'm interested in this! Computer science major

martian17 commented 4 years ago

I'm in

hyungseokChang commented 4 years ago

I am interested in this issue.

martian17 commented 4 years ago

https://github.com/martian17/qiskit-graph-coloring

atsuyahasegawa commented 4 years ago

https://www.geeksforgeeks.org/edge-coloring-of-a-graph/

martian17 commented 4 years ago

https://gist.github.com/martian17/865336f906f0778e942f8488ae2b337c