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

A verifier-accepted replacement together with its concrete lattice embedding.

Result of rewriting and re-synthesizing one realized lattice gadget.

One verifier-certified atom-reducing rewrite.

Outcome of a bounded direct SAT search on one concrete lattice.

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

analyze_gadget(gadget::Gadget; model::Type{<:EnergyModel}=RydbergModel)

Compute the maximum-energy states of a gadget and return structured data for programmatic consumers such as the visual editor.

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.

check_gadget_geometry(lattice, coordinates, pins, pin_rays)

Check the four gadget geometry conditions. pin_rays[i] is the outward lattice direction attached to pins[i]. The returned named tuple reports G1 (strict hull interfaces), G2 (alternating channels), G3 (outward rays), and G4 (clear pairwise non-adjacent exterior corridors).

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

optimize_unweighted_gadget(gadget, target_boundary; kwargs...)

Reduce a verifier-accepted four-pin lattice gadget with certified rewrite rules. The optimizer contracts even boundary tails, contracts opposite leaf pins in pairs, and uses fixed-frame SAT to re-synthesize the interior after a one-step frame rewrite. Direct rewrites are explored to a closure before re-synthesis, so the optimizer does not commit to the first smaller direct result. It never proposes arbitrary vertex deletion.

pins_prefilter(g, pins)

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

Read progress and staged-filter counters from a saved unweighted search.

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 one joint occupancy-and-frame SAT instance in a fixed lattice window.

Unlike search_unweighted_gadgets, this formulation chooses the occupied sites, four pins, and four outward rays in one CNF. atom_count and offset identify the exact instance to solve. The unchanged gadget verifier checks every result.

Search a four-pin unweighted gadget in a finite window of lattice. Every returned gadget satisfies the reduced-alpha target up to a constant and the four-direction crossing geometry.

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