GitHub

Search for Rydberg Gadgets on Triangular Lattice

This example demonstrates how to search for Rydberg gadgets using:

  • RydbergModel: State space is restricted to Maximal Independent Sets (MIS)
  • Unit Disk Graphs (UDG): Edges connect vertices within unit distance
  • Vertex weights only: Energy E(σ) = Σᵢ hᵢσᵢ

Notes:

  • The search can be expensive. Tweak max_samples, lattice size, and pin_candidates
using GadgetSearch
using HiGHS
using Combinatorics
using FileIO, ImageShow

Define truth tables for 2-input, 1-output logic gates

truth_tables = [
    TruthTableConstraint(BitMatrix([0 0 0; 1 0 1; 0 1 1; 1 1 1])),   # OR
    TruthTableConstraint(BitMatrix([0 0 0; 1 0 0; 0 1 0; 1 1 1])),   # AND
    TruthTableConstraint(BitMatrix([0 0 1; 1 0 1; 0 1 1; 1 1 0])),   # NAND
    TruthTableConstraint(BitMatrix([0 0 1; 1 0 0; 0 1 0; 1 1 0])),   # NOR
    TruthTableConstraint(BitMatrix([0 0 0; 1 0 1; 0 1 1; 1 1 0]))    # XOR
]
5-element Vector{TruthTableConstraint}:
 TruthTableConstraint(Bool[0 0 0; 1 0 1; 0 1 1; 1 1 1])
 TruthTableConstraint(Bool[0 0 0; 1 0 0; 0 1 0; 1 1 1])
 TruthTableConstraint(Bool[0 0 1; 1 0 1; 0 1 1; 1 1 0])
 TruthTableConstraint(Bool[0 0 1; 1 0 0; 0 1 0; 1 1 0])
 TruthTableConstraint(Bool[0 0 0; 1 0 1; 0 1 1; 1 1 0])

Generate Unit Disk Graph dataset on triangular lattice The UDG constraint means only nearby atoms can interact (Rydberg blockade)

generate_full_grid_udg(Triangular(), 2, 2; path=pkgdir(GadgetSearch, "examples", "rydberg_dataset.g6"))

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

Search using RydbergModel explicitly

  • RydbergModel uses MIS (Maximal Independent Sets) as the state space
  • Only vertex weights (h) are optimized
  • Objective minimizes sum of vertex weights
results, failed = search_gadgets(
    RydbergModel,           # Explicitly use Rydberg model
    dataloader,
    truth_tables;
    optimizer=HiGHS.Optimizer,
    pin_candidates=collect(Combinatorics.combinations(1:4, 3)),
    allow_defect=true,
    objective=h -> sum(h),  # Only vertex weights for Rydberg
    save_path=joinpath(pkgdir(GadgetSearch, "examples"), "triangular_Rydberg_results.json"),
    max_result_num=10,
    max_samples=10000,
    check_connectivity=true
)

println("================================")
println("   RYDBERG MODEL SEARCH RESULTS")
println("================================")
@info "Results: $(length(results)) truth tables searched"
for (i, tt_results) in enumerate(results)
    @info "Truth table $(i-1): $(length(tt_results)) gadgets found"
end

@info "Cache statistics: $(GadgetSearch.get_cache_stats())"
GadgetSearch.clear_cache!()
[ Info: [Rydberg] Searching for constraint 0 [limit=10]

Progress:  12%|█████▏                                   |  ETA: 0:00:09[ Info: found a valid Rydberg solution
weights = [1.0, 1.0, 1.0, 0.0, 2.0, 1.0, 2.0, 2.0]
[ Info: found a valid Rydberg solution
weights = [1.0, 1.0, 1.0, 0.0, 2.0, 1.0, 2.0, 2.0]

Progress: 100%|█████████████████████████████████████████| Time: 0:00:01
[ Info: Constraint 0 processed in 3.81s, found 2 gadgets
[ Info: [Rydberg] Searching for constraint 1 [limit=10]
[ Info: found a valid Rydberg solution
weights = [1.0, 0.0, 1.0, 1.0, 3.0, 3.0, 1.0, 1.0]
[ Info: found a valid Rydberg solution
weights = [1.0, 0.0, 1.0, 1.0, 3.0, 3.0, 1.0, 1.0]
[ Info: Constraint 1 processed in 0.01s, found 2 gadgets
[ Info: [Rydberg] Searching for constraint 2 [limit=10]
[ Info: found a valid Rydberg solution
weights = [1.0, 1.0, 0.0, 1.0, 2.0, 2.0, 2.0, 1.0]
[ Info: found a valid Rydberg solution
weights = [1.0, 1.0, 0.0, 1.0, 2.0, 2.0, 2.0, 1.0]
[ Info: found a valid Rydberg solution
weights = [1.0, 0.0, 1.0, 1.0, 1.0, 2.0, 2.0, 2.0]
[ Info: found a valid Rydberg solution
weights = [1.0, 0.0, 1.0, 1.0, 1.0, 2.0, 2.0, 2.0]
[ Info: Constraint 2 processed in 0.01s, found 4 gadgets
[ Info: [Rydberg] Searching for constraint 3 [limit=10]
[ Info: found a valid Rydberg solution
weights = [1.0, 0.0, 2.0, 1.0, 2.0, 3.0, 1.0, 1.0]
[ Info: found a valid Rydberg solution
weights = [1.0, 1.0, 2.0, 1.0, 2.0, 3.0, 2.0, 2.0]
[ Info: found a valid Rydberg solution
weights = [0.0, 1.0, 2.0, 1.0, 1.0, 3.0, 2.0, 2.0]
[ Info: Constraint 3 processed in 0.01s, found 3 gadgets
[ Info: [Rydberg] Searching for constraint 4 [limit=10]
[ Info: found a valid Rydberg solution
weights = [1.0, 1.0, 1.0, 0.0, 2.0, 2.0, 2.0, 2.0]
[ Info: found a valid Rydberg solution
weights = [1.0, 1.0, 1.0, 0.0, 2.0, 2.0, 2.0, 2.0]
[ Info: found a valid Rydberg solution
weights = [1.0, 0.0, 1.0, 1.0, 2.0, 2.0, 2.0, 2.0]
[ Info: found a valid Rydberg solution
weights = [1.0, 0.0, 1.0, 1.0, 2.0, 2.0, 2.0, 2.0]
[ Info: Constraint 4 processed in 0.01s, found 4 gadgets
[ Info: Search completed in 6.38s. Cache gained 16 entries.
================================
   RYDBERG MODEL SEARCH RESULTS
================================
[ Info: Results: 5 truth tables searched
[ Info: Truth table 0: 2 gadgets found
[ Info: Truth table 1: 2 gadgets found
[ Info: Truth table 2: 4 gadgets found
[ Info: Truth table 3: 3 gadgets found
[ Info: Truth table 4: 4 gadgets found
[ Info: Cache statistics: (size = 16, memory_mb = 0.0026702880859375)
[ Info: MIS cache cleared, 0 entries remaining

Visualize found gadgets

labels = ["OR", "AND", "NAND", "NOR", "XOR"]

for (i, label) in enumerate(labels)
    if !isempty(results[i])
        outpath = pkgdir(GadgetSearch, "examples", "gadget_$(label).png")
        GadgetSearch.plot_gadget(results[i][1], outpath; show_weights=true, round_weights=true)
        @info "Saved $label gate to $outpath"
    end
end
Drawing saved as /home/runner/work/GadgetSearch.jl/GadgetSearch.jl/examples/gadget_OR.png
[ Info: Saved OR gate to /home/runner/work/GadgetSearch.jl/GadgetSearch.jl/examples/gadget_OR.png
Drawing saved as /home/runner/work/GadgetSearch.jl/GadgetSearch.jl/examples/gadget_AND.png
[ Info: Saved AND gate to /home/runner/work/GadgetSearch.jl/GadgetSearch.jl/examples/gadget_AND.png
Drawing saved as /home/runner/work/GadgetSearch.jl/GadgetSearch.jl/examples/gadget_NAND.png
[ Info: Saved NAND gate to /home/runner/work/GadgetSearch.jl/GadgetSearch.jl/examples/gadget_NAND.png
Drawing saved as /home/runner/work/GadgetSearch.jl/GadgetSearch.jl/examples/gadget_NOR.png
[ Info: Saved NOR gate to /home/runner/work/GadgetSearch.jl/GadgetSearch.jl/examples/gadget_NOR.png
Drawing saved as /home/runner/work/GadgetSearch.jl/GadgetSearch.jl/examples/gadget_XOR.png
[ Info: Saved XOR gate to /home/runner/work/GadgetSearch.jl/GadgetSearch.jl/examples/gadget_XOR.png

Check correctness using Rydberg model

The check_gadget function validates ground states using MIS

for (i, label) in enumerate(labels)
    if !isempty(results[i])
        gadget = results[i][1]
        println("\n===== Checking $(label) gate (Rydberg/MIS) =====")
        println("Pins: $(gadget.pins)")
        println("Vertex weights: $(gadget.vertex_weights)")
        println(check_gadget_rydberg(gadget; _return_info=true))
    end
end

===== Checking OR gate (Rydberg/MIS) =====
Pins: [1, 2, 3]
Vertex weights: [1.0, 1.0, 1.0, 0.0, 2.0, 1.0, 2.0, 2.0]
Model: Rydberg (MIS)
Max energy value: 4.0
Ground states (max energy):
  State index=1, pins=[0, 1, 1]
  State index=2, pins=[0, 0, 0]
  State index=4, pins=[1, 0, 1]
  State index=6, pins=[1, 1, 1]

===== Checking AND gate (Rydberg/MIS) =====
Pins: [1, 3, 4]
Vertex weights: [1.0, 0.0, 1.0, 1.0, 3.0, 3.0, 1.0, 1.0]
Model: Rydberg (MIS)
Max energy value: 4.0
Ground states (max energy):
  State index=1, pins=[0, 0, 0]
  State index=2, pins=[0, 1, 0]
  State index=3, pins=[1, 1, 1]
  State index=6, pins=[1, 0, 0]

===== Checking NAND gate (Rydberg/MIS) =====
Pins: [1, 2, 4]
Vertex weights: [1.0, 1.0, 0.0, 1.0, 2.0, 2.0, 2.0, 1.0]
Model: Rydberg (MIS)
Max energy value: 4.0
Ground states (max energy):
  State index=1, pins=[0, 1, 1]
  State index=2, pins=[0, 0, 1]
  State index=4, pins=[1, 0, 1]
  State index=7, pins=[1, 1, 0]

===== Checking NOR gate (Rydberg/MIS) =====
Pins: [1, 3, 4]
Vertex weights: [1.0, 0.0, 2.0, 1.0, 2.0, 3.0, 1.0, 1.0]
Model: Rydberg (MIS)
Max energy value: 4.0
Ground states (max energy):
  State index=1, pins=[0, 0, 1]
  State index=2, pins=[0, 1, 0]
  State index=4, pins=[1, 1, 0]
  State index=6, pins=[1, 0, 0]

===== Checking XOR gate (Rydberg/MIS) =====
Pins: [1, 2, 3]
Vertex weights: [1.0, 1.0, 1.0, 0.0, 2.0, 2.0, 2.0, 2.0]
Model: Rydberg (MIS)
Max energy value: 4.0
Ground states (max energy):
  State index=1, pins=[0, 1, 1]
  State index=2, pins=[0, 0, 0]
  State index=4, pins=[1, 0, 1]
  State index=6, pins=[1, 1, 0]

This page was generated using Literate.jl.