GitHub

Search for QUBO Gadgets on Triangular Lattice

This example demonstrates how to search for QUBO gadgets using:

  • QUBOModel: State space includes ALL 2^n binary configurations
  • Complete graphs: All vertex pairs are connected
  • Vertex + Edge weights: Energy E(σ) = Σᵢ hᵢσᵢ + Σᵢⱼ Jᵢⱼσᵢσⱼ

Notes:

  • QUBO search is more general but computationally more expensive
  • State constraints are specified directly as ground state strings
using GadgetSearch
using HiGHS
using Combinatorics
using FileIO, ImageShow

Define truth table constraints for QUBO Each constraint specifies which pin configurations should be ground states Format: TruthTableConstraint(BitMatrix) where each row is a ground state

constraints = [
    TruthTableConstraint(Bool[0 0 0; 0 1 1; 1 0 1; 1 1 1]),  # OR-like
    TruthTableConstraint(Bool[0 0 0; 0 1 0; 1 0 0; 1 1 1]),  # AND-like
    TruthTableConstraint(Bool[0 0 0; 0 1 1; 1 0 1; 1 1 0])   # XOR-like
]
3-element Vector{TruthTableConstraint}:
 TruthTableConstraint(Bool[0 0 0; 0 1 1; 1 0 1; 1 1 1])
 TruthTableConstraint(Bool[0 0 0; 0 1 0; 1 0 0; 1 1 1])
 TruthTableConstraint(Bool[0 0 0; 0 1 1; 1 0 1; 1 1 0])

Generate Complete Graph dataset on triangular lattice All vertices are connected (no distance restriction like UDG)

generate_full_grid_graph(Triangular(), 2, 2; path=pkgdir(GadgetSearch, "examples", "qubo_dataset.g6"))

dataloader = GraphLoader(pkgdir(GadgetSearch, "examples", "qubo_dataset.g6"))
GraphLoader with 1 graphs, no cache

Search using QUBOModel explicitly

  • QUBOModel uses ALL 2^n states (not just MIS)
  • Both vertex weights (h) and edge weights (J) are optimized
  • Objective minimizes sum of h and J
results, failed = search_gadgets(
    QUBOModel,              # Explicitly use QUBO model
    dataloader,
    constraints;
    optimizer=HiGHS.Optimizer,
    allow_defect=true,
    save_path=joinpath(pkgdir(GadgetSearch, "examples"), "triangular_QUBO_results.json"),
    max_result_num=5,
    max_samples=5000,
    check_connectivity=true
)

@show failed
println("================================")
println("    QUBO MODEL SEARCH RESULTS")
println("================================")
@info "Results: $(length(results)) constraints searched"
labels = ["OR-like", "AND-like", "XOR-like"]
for (i, label) in enumerate(labels)
    @info "Constraint '$label': $(length(results[i])) gadgets found"
end

@info "Cache statistics: $(GadgetSearch.get_cache_stats())"
GadgetSearch.clear_cache!()
[ Info: [QUBO] Searching for constraint 0 [limit=5]
┌ Warning: pin_candidates is not provided, using all possible pin combinations
└ @ GadgetSearch ~/work/GadgetSearch.jl/GadgetSearch.jl/src/core/search.jl:634
[ Info: found a valid QUBO solution
(vertex_weights, edge_weights) = ([-1.0, -1.0, -1.0, -1.0], [-1.0, 2.0, 0.0, 2.0, 0.0, 0.0])
[ Info: Constraint 0 processed in 0.76s, found 1 gadgets
[ Info: [QUBO] Searching for constraint 1 [limit=5]
┌ Warning: pin_candidates is not provided, using all possible pin combinations
└ @ GadgetSearch ~/work/GadgetSearch.jl/GadgetSearch.jl/src/core/search.jl:634
[ Info: found a valid QUBO solution
(vertex_weights, edge_weights) = ([1.0, 1.0, -3.0, 1.0], [-2.0, 2.0, -3.0, 2.0, -3.0, 2.0])
[ Info: Constraint 1 processed in 0.01s, found 1 gadgets
[ Info: [QUBO] Searching for constraint 2 [limit=5]
┌ Warning: pin_candidates is not provided, using all possible pin combinations
└ @ GadgetSearch ~/work/GadgetSearch.jl/GadgetSearch.jl/src/core/search.jl:634
[ Info: found a valid QUBO solution
(vertex_weights, edge_weights) = ([3.0, 3.0, 3.0, 4.0], [-2.0, -2.0, -4.0, -2.0, -4.0, -4.0])
[ Info: Constraint 2 processed in 0.01s, found 1 gadgets
[ Info: Search completed in 1.03s. Cache gained 0 entries.
failed = TruthTableConstraint[]
================================
    QUBO MODEL SEARCH RESULTS
================================
[ Info: Results: 3 constraints searched
[ Info: Constraint 'OR-like': 1 gadgets found
[ Info: Constraint 'AND-like': 1 gadgets found
[ Info: Constraint 'XOR-like': 1 gadgets found
[ Info: Cache statistics: (size = 5, memory_mb = 0.001953125)
[ Info: MIS cache cleared, 0 entries remaining

Examine found QUBO gadgets

QUBO gadgets have both vertex and edge weights

for (i, label) in enumerate(labels)
    if !isempty(results[i])
        gadget = results[i][1]
        @info """===== Found QUBO gadget for '$label' =====
        Constraint: $(gadget.ground_states)
        Pins: $(gadget.pins)
        Vertex weights (h): $(gadget.vertex_weights)
        Edge weights (J): $(gadget.edge_weights)
        Edge list: $(gadget.edge_list)
        """
        outpath = pkgdir(GadgetSearch, "examples", "qubo_gadget_$(label).png")
        GadgetSearch.plot_gadget(gadget, outpath;
            show_weights=true,           # Show vertex weights
            show_edge_weights=true,      # Show edge weights (QUBO specific)
            round_weights=true
        )
        @info "Saved to $outpath"
    end
end
┌ Info: ===== Found QUBO gadget for 'OR-like' =====
│ Constraint: Bool[0 0 0; 0 1 1; 1 0 1; 1 1 1]
│ Pins: [1, 2, 3]
│ Vertex weights (h): [-1.0, -1.0, -1.0, -1.0]
│ Edge weights (J): [-1.0, 2.0, 0.0, 2.0, 0.0, 0.0]
└ Edge list: [(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]
Drawing saved as /home/runner/work/GadgetSearch.jl/GadgetSearch.jl/examples/qubo_gadget_OR-like.png
[ Info: Saved to /home/runner/work/GadgetSearch.jl/GadgetSearch.jl/examples/qubo_gadget_OR-like.png
┌ Info: ===== Found QUBO gadget for 'AND-like' =====
│ Constraint: Bool[0 0 0; 0 1 0; 1 0 0; 1 1 1]
│ Pins: [1, 2, 3]
│ Vertex weights (h): [1.0, 1.0, -3.0, 1.0]
│ Edge weights (J): [-2.0, 2.0, -3.0, 2.0, -3.0, 2.0]
└ Edge list: [(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]
Drawing saved as /home/runner/work/GadgetSearch.jl/GadgetSearch.jl/examples/qubo_gadget_AND-like.png
[ Info: Saved to /home/runner/work/GadgetSearch.jl/GadgetSearch.jl/examples/qubo_gadget_AND-like.png
┌ Info: ===== Found QUBO gadget for 'XOR-like' =====
│ Constraint: Bool[0 0 0; 0 1 1; 1 0 1; 1 1 0]
│ Pins: [1, 2, 3]
│ Vertex weights (h): [3.0, 3.0, 3.0, 4.0]
│ Edge weights (J): [-2.0, -2.0, -4.0, -2.0, -4.0, -4.0]
└ Edge list: [(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]
Drawing saved as /home/runner/work/GadgetSearch.jl/GadgetSearch.jl/examples/qubo_gadget_XOR-like.png
[ Info: Saved to /home/runner/work/GadgetSearch.jl/GadgetSearch.jl/examples/qubo_gadget_XOR-like.png

Check correctness using QUBO model

The checkgadgetqubo function validates using ALL states (not just MIS)

for (i, label) in enumerate(labels)
    if !isempty(results[i])
        gadget = results[i][1]
        println("\n===== Checking '$label' gadget (QUBO/Full state space) =====")
        println(check_gadget_qubo(gadget; _return_info=true))
    end
end

===== Checking 'OR-like' gadget (QUBO/Full state space) =====
Model: QUBO (Full)
Max energy value: 0.0
Ground states (max energy):
  State index=1, pins=[0, 0, 0]
  State index=6, pins=[1, 0, 1]
  State index=7, pins=[0, 1, 1]
  State index=8, pins=[1, 1, 1]

===== Checking 'AND-like' gadget (QUBO/Full state space) =====
Model: QUBO (Full)
Max energy value: 1.0
Ground states (max energy):
  State index=2, pins=[1, 0, 0]
  State index=3, pins=[0, 1, 0]
  State index=8, pins=[1, 1, 1]
  State index=9, pins=[0, 0, 0]

===== Checking 'XOR-like' gadget (QUBO/Full state space) =====
Model: QUBO (Full)
Max energy value: 4.0
Ground states (max energy):
  State index=4, pins=[1, 1, 0]
  State index=6, pins=[1, 0, 1]
  State index=7, pins=[0, 1, 1]
  State index=9, pins=[0, 0, 0]

This page was generated using Literate.jl.