Reference

EnergyModel

Abstract type for energy models. Subtypes define how energy is computed from vertex states.

Gadget{M<:EnergyModel, T<:Real}

A gadget found by the search algorithm.

Type Parameters

• M: Energy model type (RydbergModel or QUBOModel)
• T: Numeric type for weights

Fields

• constraint::GadgetConstraint: The constraint this gadget satisfies
• graph::SimpleGraph{Int}: The graph structure
• pins::Vector{Int}: Pin vertex indices
• vertex_weights::Vector{T}: Vertex weights (hᵢ)
• edge_weights::Vector{T}: Edge weights (Jᵢⱼ), empty for RydbergModel
• edge_list::Vector{Tuple{Int,Int}}: Edge list corresponding to edge_weights
• pos::Union{Nothing, Vector{Tuple{Float64, Float64}}}: Vertex positions

GadgetConstraint

Abstract type for gadget constraints. Subtypes define what ground states are required.

QUBOModel <: EnergyModel

Energy model for general QUBO (Quadratic Unconstrained Binary Optimization).

• State space: All 2^n binary configurations
• Energy: E(σ) = Σᵢ hᵢσᵢ + Σ₍ᵢ,ⱼ₎ Jᵢⱼσᵢσⱼ (vertex + edge weights)

RydbergModel <: EnergyModel

Energy model for Rydberg atom systems.

• State space: Maximal Independent Sets (MIS)
• Energy: E(σ) = Σᵢ hᵢσᵢ (vertex weights only)

TruthTableConstraint <: GadgetConstraint

Constraint defined by a truth table (for Rydberg/MIS-based gadgets).

Fields

• truth_table::BitMatrix: Truth table where each row is a ground state configuration on pins

UnweightedGadget

Result of an unweighted gadget search (Definition 3.6 / Theorem 3.7 in the paper).

Fields

• pattern_graph::SimpleGraph{Int}: The target graph R
• replacement_graph::SimpleGraph{Int}: The candidate graph R' that replaces R
• boundary_vertices::Vector{Int}: Boundary vertices of replacement_graph
• constant_offset::Float64: Constant offset between the reduced alpha tensors of pattern_graph and replacement_graph
• pos::Union{Nothing, Vector{Tuple{Float64, Float64}}}: Vertex positions of replacement_graph

_find_weights(::Type{RydbergModel}, ...) -> Union{Nothing, Vector{Float64}}

Find vertex weights for Rydberg model.

_find_weights(::Type{QUBOModel}, ...) -> Union{Nothing, Tuple{Vector{Float64}, Vector{Float64}}}

Find vertex and edge weights for QUBO model.

_graph_hash(g::SimpleGraph{Int}) -> UInt64

Create a hash for graph structure for caching purposes.

_solve_weights_sampled(...)

Optimized version for large combination spaces using random sampling.

calculate_alpha_tensor(graph, boundary_vertices)

Compute the alpha tensor of a graph with given boundary vertices using tropical tensor network contraction.

The alpha tensor alpha(R) is a rank-|boundary| tensor where each element alpha(R)_s is the size of the largest independent set of R with boundary vertices fixed to configuration s, or -Inf if s violates the independent set constraint.

Arguments

• graph::SimpleGraph{Int}: The graph R
• boundary_vertices::Vector{Int}: The boundary vertex indices (1-indexed)

Returns

• Array{<:Tropical}: Tropical tensor of shape (2, 2, ..., 2) with length(boundary_vertices) dimensions

calculate_reduced_alpha_tensor(graph, boundary_vertices)

Compute the reduced alpha tensor α̃(R) of a graph with given boundary vertices.

The reduced alpha tensor is obtained by applying mis_compactify! to the alpha tensor: a boundary configuration s is set to -Inf if there exists a subset configuration s' ⊆ s (fewer boundary vertices selected) that achieves an equal or better MIS size. This removes dominated configurations, leaving only the "essential" boundary behaviors.

Arguments

• graph::SimpleGraph{Int}: The graph R
• boundary_vertices::Vector{Int}: The boundary vertex indices (1-indexed)

Returns

• Array{<:Tropical}: Reduced tropical tensor of shape (2, 2, ..., 2)

check_connectivity_after_removal(graph, vertices_to_remove)

Check if a graph remains connected after removing specified vertices.

check_gadget(gadget::Gadget; _return_info::Bool=false, model::Type{<:EnergyModel}=RydbergModel)

Validate a Gadget by computing energies for its state space and reporting the ground state configurations on pins.

Arguments

• gadget::Gadget: The gadget to check.

Keyword Arguments

• _return_info::Bool=false: If true, return a string; otherwise log with @info.
• model::Type{<:EnergyModel}=RydbergModel: Energy model to use for validation.

Returns

• When _return_info is true, returns a formatted String; otherwise returns nothing.

check_gadget_qubo(gadget::Gadget; _return_info::Bool=false)

Check gadget using QUBO (full state space) model.

check_gadget_rydberg(gadget::Gadget; _return_info::Bool=false)

Check gadget using Rydberg (MIS) model.

clear_cache!()

Clear the MIS cache to free memory. Useful for long-running processes.

complete_graph(n::Int) -> SimpleGraph

Create a complete graph with n vertices where every pair of vertices is connected.

Arguments

• n: Number of vertices

Returns

• SimpleGraph: The complete graph K_n

find_matching_gadget(loader; filter=nothing, limit=nothing, keys_range=nothing, max_results=nothing)

Find gadgets matching a given filter function from the graph loader.

find_maximal_independent_sets(g)

Find all maximal independent sets of a graph using bit masks with caching.

generate_full_grid_graph(lattice::LatticeType, nx::Int, ny::Int; path::String="grid.g6") -> String

Generate complete graphs on a grid lattice (without boundary expansion) and save to file. All vertices are connected to each other, regardless of distance.

Arguments

• lattice: Type of lattice (Square or Triangular) - determines physical positions
• nx: Number of grid points in x direction
• ny: Number of grid points in y direction
• path: Output file path for saving graphs (default: "grid.g6")

Returns

• String: Path to the saved graph file

Details

Generates a single complete graph on the nx×ny grid. The physical positions follow the lattice geometry, but edges connect all pairs of vertices.

generate_full_grid_udg(lattice::LatticeType, nx::Int, ny::Int; path::String="udg.g6") -> String

Generate unit disk graphs on a grid lattice with four boundary pins and save to file.

Arguments

• lattice: Type of lattice (Square or Triangular)
• nx: Number of inner positions in x direction
• ny: Number of inner positions in y direction
• path: Output file path for saving graphs (default: "udg.g6")

Returns

• String: Path to the saved graph file

Details

Generates all possible UDGs by placing pins on boundary positions and connecting vertices within unit distance on the specified lattice type.

get_cache_stats()

Get statistics about the MIS cache usage.

get_state_space(::Type{QUBOModel}, graph::SimpleGraph{Int}) -> Tuple{Vector{UInt32}, Int}

Get the state space for QUBO model (all 2^n states).

get_state_space(::Type{RydbergModel}, graph::SimpleGraph{Int}) -> Tuple{Vector{UInt32}, Int}

Get the state space for Rydberg model (Maximal Independent Sets).

is_diff_by_constant(t1, t2)

Check whether two reduced alpha tensors differ by a constant (Theorem 3.7 in the paper).

Two gadgets R and R' are valid MIS replacements if and only if their reduced alpha tensors differ only by a constant offset. This function tests that condition.

Returns (true, c) if t1[i] - t2[i] == c for all finite entries, and both tensors have -Inf at exactly the same positions. Returns (false, 0) otherwise.

Callers must ensure that at least one tensor has a finite entry (i.e., not all-Inf).

Arguments

• t1::AbstractArray{T}: First reduced alpha tensor (finite values or -Inf)
• t2::AbstractArray{T}: Second reduced alpha tensor (finite values or -Inf)

Returns

• Tuple{Bool, Real}: (is_valid, constant_offset)

is_gadget_replacement(g1, g2, open_vertices1, open_vertices2)

Check whether gadget g2 (with boundary open_vertices2) is a valid MIS replacement for gadget g1 (with boundary open_vertices1), i.e., their reduced alpha tensors differ only by a constant (Theorem 3.7 in the paper).

Returns

• Tuple{Bool, Real}: (is_valid, constant_offset) where constant_offset = α̃(g2) - α̃(g1)

make_filter(model_type, constraint, optimizer, env; kwargs...)

Create a filter closure for graph search that checks if a graph can implement the given constraint.

Arguments

• model_type::Type{<:EnergyModel}: RydbergModel or QUBOModel
• constraint::GadgetConstraint: The target constraint to implement
• optimizer: Optimization solver for weight finding
• env: Environment for the optimizer

Keywords

• connected::Bool=false: Whether to require connected graphs only
• objective=nothing: Objective function for optimization
• allow_defect::Bool=false: Whether to allow zero vertex weights
• max_samples::Int=1000: Maximum samples for enumeration
• pin_candidates::Union{Nothing, Vector{Vector{Int}}}=nothing: Candidate pin combinations
• check_connectivity::Bool=true: Whether to check graph connectivity

Returns

• Function: Filter function that takes (graph, pos, pin_set) and returns Gadget or nothing

make_unweighted_filter(target_graph, target_boundary)

Create a filter closure for unweighted gadget search.

Pre-computes α̃(target_graph) once, then returns a closure that checks each candidate graph by trying all boundary vertex combinations of the same size.

Arguments

• target_graph::SimpleGraph{Int}: The pattern graph R
• target_boundary::Vector{Int}: Boundary vertices of R

Returns

• Function: Closure (candidate, pos, pin_set) -> UnweightedGadget | nothing

match_constraint_to_states(states, constraint, pin_set)

Match constraint ground states to full graph states based on pin configuration.

Returns

• Vector{Vector{Int}}: For each ground state pattern, indices of matching states in the state space

search_by_truth_tables(loader, truth_tables; kwargs...)

Search for Rydberg gadgets by truth tables (legacy interface).

search_gadgets(model_type, loader, constraints; kwargs...)

Unified search function for both Rydberg and QUBO gadgets.

Arguments

• model_type::Type{<:EnergyModel}: RydbergModel or QUBOModel
• loader::GraphLoader: The graph loader containing candidate graphs
• constraints::Vector{<:GadgetConstraint}: Constraints to search for

Keywords

• optimizer: Optimization solver to use for weight finding
• env=nothing: Environment for the optimizer
• connected::Bool=false: Whether to require connected graphs only
• objective=nothing: Objective function for optimization
• allow_defect::Bool=false: Whether to allow zero vertex weights
• limit=nothing: Maximum number of graphs to search
• max_samples::Int=100: Maximum samples for weight enumeration
• save_path::String="results.json": Path to save intermediate results
• pin_candidates::Union{Nothing, Vector{Vector{Int}}}=nothing: Candidate pin combinations
• check_connectivity::Bool=true: Whether to check graph connectivity
• max_result_num::Int=1: Maximum number of results per constraint

Returns

• Tuple{Vector{Vector{Gadget}}, Vector{<:GadgetConstraint}}: Found gadgets grouped by constraint and failed constraints

search_unweighted_gadgets(target_graph, target_boundary, loader; limit, max_results)

Search for unweighted gadget replacements of target_graph by iterating over a GraphLoader.

For each candidate graph, tries all boundary vertex combinations of size length(target_boundary) and checks if the reduced alpha tensors differ by a constant (Theorem 3.7). Returns on the first valid boundary found per candidate.

Arguments

• target_graph::SimpleGraph{Int}: The pattern graph R
• target_boundary::Vector{Int}: Boundary vertices of R
• loader::GraphLoader: Graph dataset to search over

Keywords

• limit::Union{Int,Nothing}=nothing: Maximum number of graphs to examine
• max_results::Union{Int,Nothing}=nothing: Stop after finding this many results

Returns

• Vector{UnweightedGadget}

solve_weights(model_type, states, target_indices_all, graph, pin_set, optimizer; kwargs...)

Unified weight solver that works for both Rydberg and QUBO models.

unit_disk_graph(locs::AbstractVector, unit::Real) -> SimpleGraph

Create a unit disk graph from given locations. Two vertices are connected if their Euclidean distance is less than the unit distance.

Arguments

• locs: Vector of vertex locations
• unit: Unit distance threshold for edge creation

Returns

• SimpleGraph: The constructed unit disk graph