Maximum Independent Set

Rydberg Blockade is one of the most important properties of neutral-atom quantum computing based on Rydberg states. It naturally encodes the independent set constraint. More specifically, Rydberg blockade implies that two atoms cannot be both excited to the Rydberg state $|r\rangle$ if they are close to each other, whereas independent set constraint means two vertices cannot be both in the independent set when they are connected by an edge. Thus, one can consider atoms in the Rydberg state as vertices in an independent set. See the proposal in H. Pichler, et al. for more details.

In particular, one can use the ground state of the Rydberg Hamiltonian to encode the maximum independent set problem, which is to find the largest independent set of a given graph. For a particular subclass of geometric graphs, the so-called unit disk graphs, the Rydberg Hamiltonian can encode the solution without any overhead in the number of qubits. In fact, an experimental demonstration of quantum optimization has been realized in solving the maximum independent set problem up to 289 qubits in S. Ebadi, et al..

In Bloqade, we provide several functions to support the simulation of solving independent set problems on neutral-atom quantum computers. We list them here in this section.

The Maximum Independent Set Problem

In graph theory, an independent set is a set of vertices in a graph such that no two of which are connected by an edge. The problem of finding maximum independent sets (MIS) is NP-hard, i.e., it is unlikely to be solved in a time polynomial to the problem size. However, for a graph with a small to intermediate size, various solution space properties, including finding the MIS size and enumerating all MISs, can be computed using the package GenericTensorNetworks; please also refer to the related manual pages the independent set problem and the maximal independent set problem.

A tutorial on how to solve the MIS problem using Bloqade is detailed in the MIS tutorial page.

In the following, we list the APIs in the module BloqadeMIS, many of which support the simulation of variational quantum algorithms for solving the MIS problem.

References

BloqadeMIS.add_random_vertices — Function
add_random_vertices([rng=GLOBAL_RNG], config::AbstractVector, graph::AbstractGraph, ntrials::Int = 10)

Add vertices randomly to given configuration for ntrials times and pick the one that has largest count_vertices.

Arguments

  • rng: optional, Random Number Generator.
  • config: configuration to tweak.
  • graph: problem graph.
  • ntrials: number of trials to use, default is 10.
source
BloqadeMIS.anyone — Method
anyone(index::Integer, mask::Integer) -> Bool

Return true if any masked position of index is 1.

Example

true if any masked positions is 1.

julia> anyone(0b1011, 0b1001)
true
julia> anyone(0b1011, 0b1100)
true
julia> anyone(0b1011, 0b0100)
false
source
BloqadeMIS.bmask — Function
bmask(::Type{T}) where T <: Integer -> zero(T)
bmask([T::Type], positions::Int...) -> T
bmask([T::Type], range::UnitRange{Int}) -> T

Return an integer mask of type T where 1 is the position masked according to positions or range. Directly use T will return an empty mask 0.

source
BloqadeMIS.create_subspace_from_mis — Method
create_subspace_from_mis(T, n::Int, mis::AbstractVector)

Create Subspace from given list of maximal cliques/maximal independent set.

Arguments

  • n: number of vertices of the graph.
  • mis: the list of maximal independent set.
source
BloqadeMIS.gibbs_loss — Method
gibbs_loss([f], reg_or_samples, α::Real)

The Gibbs loss for maximum independent set defined as

\[L = -1/α \log(\langle ψ|\exp(α \sum(n))|ψ\rangle),\]

where n is the vertex set size.

Arguments

  • f: optional, postprocessing callback function f(config) -> config. The input config is an integer of type Int, the output config can be a type supports count_vertices e.g, an AbstractVector or an Integer.
  • reg_or_samples can be a register (Yao.ArrayReg or SubspaceArrayReg) or a list of measurement result (config) in AbstractVector.
  • α::Real: the parameter of Gibbs loss.
source
BloqadeMIS.independent_set_probabilities — Function
independent_set_probabilities([f], reg::YaoAPI.AbstractRegister, graph_or_mis)

Calculate the probabilities of independent sets with given postprocessing function f(config) -> config. The default postprocessing function f will only reduce all configurations to independent set.

Arguments

  • f: optional, postprocessing function, default is to_independent_set.
  • reg: required, the register object.
  • graph_or_mis: a problem graph or the MIS size of the problem graph (can be calculated via exact_solve_mis).
source
BloqadeMIS.is_independent_set — Method
is_independent_set(config, graph::AbstractGraph)

Return true if config is an independent set of graph. config can be a BitStr, a vector, or any iterable.

source
BloqadeMIS.ismatch — Method
ismatch(index::Integer, mask::Integer, target::Integer) -> Bool

Return true if bits at positions masked by mask equal to 1 are equal to target.

Example

julia> n = 0b11001; mask = 0b10100; target = 0b10000;

julia> ismatch(n, mask, target)
true
source
BloqadeMIS.num_mis_violation — Method
num_mis_violation(config, graph::AbstractGraph, i::Int)

Calculate the number of MIS violations for i-th vertex in graph and configuration config. The config should be a subtype of AbstractVector.

source
BloqadeMIS.rydberg_density_sum — Function
rydberg_density_sum([f], reg_or_samples)

Sum of rydberg density.

Arguments

  • f: optional, postprocessing callback function f(config) -> config. The input config is an integer of type Int, the output config can be a type supports count_vertices e.g, an AbstractVector or an Integer.
  • reg_or_samples can be a register (Yao.ArrayReg or SubspaceArrayReg) or a list of measurement result (config) in AbstractVector.

Example

To implement the postprocessing protocal in MIS experiment:

  1. calculating rydberg_density_sum by first reducing the configuration

to independent set using to_independent_set

  1. randomly adding vertices then pick the largest count_vertices

using add_random_vertices.

rydberg_density_sum(r) do config
    config = to_independent_set(config, graph)
    add_random_vertices(config, graph, 10)
    return config
end

Or one can also just add vertice by atom order

rydberg_density_sum(r) do config
    config = to_independent_set(config, graph)
    add_vertices!(config, graph)
    return config
end
source
BloqadeMIS.to_independent_set! — Method
to_independent_set!(config::AbstractVector, graph::AbstractGraph)

Eliminate vertices in config so that remaining vertices do not have connected edges. This algorithm is a naive vertex elimination that does not nesesarily give the maximum possible vertex set.

# run the following code in Atom/VSCode
atoms = [(0.0, 1.0), (1.0, 0.), (2.0, 0.0), (1.0, 1.0), (1.0, 2.0), (2.0, 2.0)]
graph = unit_disk_graph(atoms, 1.5)

config = [1, 1, 1, 0, 1, 1]
viz_config(atoms, graph, config)

to_independent_set!(config, graph)
viz_config(atoms, graph, config)
source
BloqadeMIS.unit_disk_graph — Function
unit_disk_graph(atoms::AbstractVector, radius=1)

Create a unit disk graph from atom positions atoms. It returns a Graphs.SimpleGraph instance.

  • atoms is vector of atoms positions.
  • radius is the unit in the unit disk graph definition.
source