UnitDiskMapping

UnitDiskMapping is a   Julia Language   package for reducing a generic maximum (weighted) independent set problem, quadratic unconstrained binary optimization (QUBO) problem or integer factorization problem to a maximum independent set problem on a unit disk grid graph (or hardcore lattice gas in physics), which can then be naturally encoded in neutral-atom quantum computers. To install UnitDiskMapping, please open Julia's interactive session (known as REPL) and press the ] key in the REPL to use the package mode, and then type the commands below.

For installing the current master branch, please type:

pkg> add https://github.com/QuEraComputing/UnitDiskMapping.jl.git

For stable release (not yet ready):

pkg> add UnitDiskMapping

Please check the following notebooks:

1. Unit Disk Mapping, which contains the examples in "Quantum Optimization with Arbitrary Connectivity Using Rydberg Atom Arrays":

   • Reduction from a generic weighted or unweighted maximum independent set (MIS) problem to that on a King's subgraph (KSG).
   • Reduction from a generic or square-lattice QUBO problem to an MIS problem on a unit-disk grid graph.
   • Reduction from an integer factorization problem to an MIS problem on a unit-disk grid graph.

2. Unweighted KSG reduction of the independent set problem, which contains the unweighted reduction from a general graph to a King's subgraph. It covers all example graphs in paper: "Computer-Assisted Gadget Design and Problem Reduction of Unweighted Maximum Independent Set" (To be published).

To run the notebook locally, you will need to activate and instantiate the local environment that specified in the notebooks directory:

$ cd notebooks
$ julia --project -e 'using Pkg; Pkg.instantiate()'

To run the notebook, just type in the same terminal:

julia --project -e "import Pluto; Pluto.run()"

At this point, your browser should automatically launch and display a list of available notebooks you can run. You should just see the notebooks listed.

Much of the software in this ecosystem was developed as a part of an academic research project. If you would like to help support it, please star the repository. If you use our software as part of your research, teaching, or other activities, we would like to request you to cite our work. The CITATION.bib file in the root of this repository lists the relevant papers.