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. Stores the pattern graph R, replacement graph R', boundary vertices, constant offset between reduced alpha tensors, and optional vertex positions.

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

_make_unweighted_filter(pattern_graph, pattern_boundary; prefilter)

Build a filter closure that checks candidate graphs against the target pattern.

_solve_weights_sampled(...)

Optimized version for large combination spaces using random sampling.

calculate_alpha_tensor(graph, boundary_vertices) -> Array{<:Tropical}

Compute the alpha tensor α(R) via tropical tensor network contraction. Element α(R)_s is the maximum independent set size with boundary fixed to s, or -Inf if s violates the independent set constraint.

calculate_reduced_alpha_tensor(graph, boundary_vertices) -> Array{Float64}

Compute the reduced alpha tensor α̃(R) by applying mis_compactify! to α(R). Dominated boundary configurations (where a subset achieves equal or better MIS size) are set to -Inf.

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

graph_to_g6(g::SimpleGraph{Int}; include_header::Bool=false) -> String

Encode a graph to graph6 text. By default this returns the canonical graph6 payload without the >>graph6<< prefix so it can be used directly in GraphDataset.

inf_mask(tensor) -> BigInt

Bitmask encoding -Inf positions in tensor (LSB = first linear index).

is_diff_by_constant(t1, t2) -> (Bool, Real)

Return (true, c) if t1 - t2 == c at all finite entries and both tensors share the same -Inf pattern; (false, 0) otherwise.

is_gadget_replacement(g1, g2, open_vertices1, open_vertices2) -> (Bool, Real)

Check whether g2 is a valid MIS replacement for g1, i.e., their reduced alpha tensors differ only by a constant. Returns (is_valid, α̃(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

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

pins_prefilter(g, pins)

Return true when every connected component of g contains at least one pin.

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

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

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