search

QuEraComputing / UnitDiskMapping.jl

Reduce several arbitrary-connectivity optimization problems into maximum independent set problems on a grid
https://github.com/QuEraComputing/UnitDiskMapping.jl
Other
16 stars 3 forks source link

how to do automatic simplification (tries)? #49

Open RobG-LHind opened 2 months ago

RobG-LHind commented 2 months ago

Hello & thank you for your library on this interesting topic.

sorry, if I may miss the obvious (this is my first contact to julia-libraries).

I created a simple all-to-all graph for 4 qbits:

grafik

as far as I understand, the simplest implementation to a unit-disk graph should be just 2x2 atoms connected to each other (left upper corner). surely the automatic mapping creates something much more complicated (unweighted_res = map_graph(graph; vertex_order=MinhThiTrick());):

grafik

how do I apply simplification on this mapping? i tried unweighted_res2 = map_graph( UnWeighted(), graph, vertex_order=MinhThiTrick(), ruleset=UnitDiskMapping.default_simplifier_ruleset(UnWeighted())) (did not find functions for vertex-reordering).

GiggleLiu commented 2 months ago

The reduction in this package is a generic one. Although the method claims to be "optimal up to a constant factor", which can be far from the optimal.

Post-processing based on the mapped graph may help. However, it is not considered a lot in this package.

RobG-LHind commented 2 months ago

Thank you @GiggleLiu for your quick response. Do I understand you right, that this was the right approach:

unweighted_res2 = map_graph( UnWeighted(), graph, vertex_order=MinhThiTrick(), ruleset=UnitDiskMapping.default_simplifier_ruleset(UnWeighted()))

and that those rulesets (and maybe added rulesets by me) are working on the grid-(string-)representation (local?)?

is there / do you have an example of using methods of simplifiers.jl on a grid > (4,3) (as in tests)?

GiggleLiu commented 2 months ago

Thank you @GiggleLiu for your quick response. Do I understand you right, that this was the right approach:

unweighted_res2 = map_graph( UnWeighted(), graph, vertex_order=MinhThiTrick(), ruleset=UnitDiskMapping.default_simplifier_ruleset(UnWeighted()))

and that those rulesets (and maybe added rulesets by me) are working on the grid-(string-)representation (local?)?

is there / do you have an example of using methods of simplifiers.jl on a grid > (4,3) (as in tests)?

You are right. The simplification rules will be applied repeatedly and locally on the grid. Currently, only the rule of removing dangling edges are considered in the package. I think the grid size is not an issue.

Here is an example of calling simplifier explicitly: https://github.com/QuEraComputing/UnitDiskMapping.jl/blob/4ef1965cb8679cc9bdfbe264fa17744e178345e8/test/mapping.jl#L40