search

unitaryfund / mitiq

Mitiq is an open source toolkit for implementing error mitigation techniques on most current intermediate-scale quantum computers.
https://mitiq.readthedocs.io
GNU General Public License v3.0
347 stars 145 forks source link

`Observable` partitioning by minimum clique cover #987

Open rmlarose opened 2 years ago

rmlarose commented 2 years ago

Currently, Observable partitioning (grouping the observable's PauliStrings into simultaneously measurable sets) is done by a greedy algorithm. There are many ways to do such a partitioning, and we should support more. One way is representing the Observable as a graph and finding the minimum clique cover (MCC) as described in this paper https://arxiv.org/pdf/1907.03358.pdf. Figure 1, copied below, describes the setup

image

and the paper lists several heuristic algorithms for MCC, some of which (the Ramsey algorithm) are in networkx.

This issue could use a short RFC outlining

  1. What graph representation do you plan to use?
  2. What (approximate) algorithms do you plan to use for MCC?

This issue can be considered closed by a method Observable.partition_mcc which groups the Observables PauliStrings into PauliStringCollections via the MCC method described above.

For reference, the current greedy partitioning is below.

https://github.com/unitaryfund/mitiq/blob/4f827e48ec260ca13659979a5560f8a4e1b68965/mitiq/observable/observable.py#L60-L80

github-actions[bot] commented 2 years ago

This issue had no activity for 2 months, and will be closed in one week unless there is new activity. Cheers!

purva-thakre commented 2 years ago

@rmlarose Do you mind clarifying statement 1 a bit more ?

What graph representation do you plan to use?

By definition for cliques to exist, the graph has to be undirected (which is also used in the paper linked above). Is your comment referring to choose some particular undirected graph representation (say bipartite, planar, non-planar, cyclic, non-cyclic etc.) ?

I think the one used in the linked paper is a bipartite graph after it has been converted to a graph coloring problem.

image

rmlarose commented 2 years ago

Hi @purva-thakre, I meant software representation of a graph (e.g., nx.Graph or other).

purva-thakre commented 2 years ago

Thanks ! I was overthinking it !

github-actions[bot] commented 2 years ago

This issue had no activity for 2 months, and will be closed in one week unless there is new activity. Cheers!

github-actions[bot] commented 1 year ago

This issue had no activity for 4 months, and will be closed in 2 weeks unless there is new activity. Cheers!