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.

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

blockade_subspace(atoms[, radius=1.0])

Create a blockade approximation subspace from given atom positions and radius.

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.

count_vertices(config::Integer)

counter the number of vertices in a spin configuration.

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.

exact_solve_mis(g::AbstractGraph)

Return the exact MIS size of a graph g.

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.

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).

independent_set_subspace([T, ]graph)

Create a subspace from given graph's maximal independent set.

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.

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

mis_postprocessing(config, graph::AbstractGraph; ntrials::Int=10)

The postprocessing protocal used in Harvard experiment for finding MISs: arxiv:2202.09372, which includes a combination of to_independent_set and add_random_vertices.

Arguments

• config: configuration to postprocess.
• graph: the problem graph.

Keyword Arguments

• ntrials: number of trials to use.

mis_postprocessing(graph::AbstractGraph; ntrials::Int = 10)

Curried version of mis_postprocessing.

Example

to calculate rydberg_density_sum loss with postprocessing used in Harvard experiment: arxiv:2202.09372.

rydberg_density_sum(mis_postprocessing(graph), reg)

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.

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

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)

to_independent_set(config::Integer, graph::AbstractGraph)

Eliminate vertices in config so that remaining vertices do not have connected edges without changing the original config, see also to_independent_set!.

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.