MQT IonShuttler
D. Schoenberger, S. Hillmich, M. Brandl, R. Wille. Using Boolean Satisfiability for Exact Shuttling in Trapped-Ion Quantum Computers. ASP-DAC 2024. arXiv:2311.03454; and Shuttling for Scalable Trapped-Ion Quantum Computers, IEEE TCAD, arXiv:2402.14065 · their code: munich-quantum-toolkit/ionshuttler (MIT)
Ion chains on the edges of a junction grid, one chain to an edge, with a one-way processing zone where the gates run; time is counted in steps. An exact shuttler built on a SAT solver and a fast cycle heuristic, by the same authors.
- The idea of an exact SAT search as an optimality oracle for small instances, which the compiler's router uses.
Run locally with a patch that only writes out each schedule. The same commit holds the cycle heuristic of the authors' TCAD paper, which is replayed too.
Both tools count abstract time steps. The SAT tool prints the number of states (one more than the number of moves); the heuristic prints the index, from zero, of its last step. Every schedule each tool produced is replayed under the paper's rules, and the replayed length must equal the printed number. The paper reports the mean over runs with random placements; the placements are reproduced from the tool's own seeding, seeds 0 to 9.
| configuration | runs | their code, per seed | mean | the paper (Table I) | checks under the paper's rules |
|---|---|---|---|---|---|
| exact SAT, Lattice 4 4 1 1, 12 chains on 24 sites, full register access ▶ watch seed 0 in the Studio | 10 | 18 18 20 19 19 18 18 18 19 18 = ours | 18.5 | 18.5 equal | all 10 runs pass |
| exact SAT, Lattice 3 3 1 1, 6 chains on 12 sites, full register access ▶ watch seed 0 in the Studio | 10 | 11 11 12 11 11 10 11 11 11 10 = ours | 10.9 | 10.9 equal | all 10 runs pass |
| exact SAT, Lattice 4 4 1 1, 6 chains on 24 sites, full register access ▶ watch seed 0 in the Studio | 10 | 12 12 14 13 13 12 12 12 13 12 = ours | 12.5 | 12.5 equal | all 10 runs pass |
| exact SAT, Racetrack 2 2 1 5, 6 chains on 12 sites, full register access ▶ watch seed 0 in the Studio | 10 | 13 14 14 14 12 14 14 13 13 11 = ours | 13.2 | 11.0 differs | all 10 runs pass |
| cycle heuristic, Lattice 4 4 1 1, 12 chains on 24 sites, full register access (Gate Selection on) ▶ watch seed 0 in the Studio | 10 | 18 21 21 23 21 23 21 29 19 20 = ours | 21.6 | 26.6 differs | all 10 runs pass |
| cycle heuristic, Horizontal Grate 6 2 1 1, 8 chains on 16 sites, full register access (Gate Selection on) ▶ watch seed 0 in the Studio | 5 | 18 18 12 13 12 = ours | 14.6 | 24.4 differs | all 5 runs pass |
Made by schedule_ours, a scheduler we wrote for this comparison; it is not the compiler that compiles this website's leaderboard entries.
Our scheduler works in the heuristic's own model: its device, its processing zone and parking edge, the placement its run of each seed starts from, one edge per chain per step through one node, one gate at a time. The SAT tool's model differs (another processing-zone layout, a fixed gate order), so its numbers are not compared with these.
| configuration | the heuristic | ours | lower bound | checks |
|---|---|---|---|---|
| cycle heuristic, Horizontal Grate 6 2 1 1, 8 chains on 16 sites, full register access (Gate Selection on), seeds 0–4 ▶ watch ours (seed 0) | mean 14.6 18 18 12 13 12 | mean 8 8 8 8 8 8 | = ours on every seed | all 5 pass |
| cycle heuristic, Lattice 4 4 1 1, 12 chains on 24 sites, full register access (Gate Selection on), seeds 0–9 ▶ watch ours (seed 0) | mean 21.6 18 21 21 23 21 23 21 29 19 20 | mean 13.3 13 14 13 13 14 13 13 14 13 13 | = ours on every seed | all 10 pass |
Every one of ours reaches a lower bound: gates run one at a time, and a chain that is m moves from the parking edge cannot have its gate before step m − 1. So no schedule that moves one edge per step, as the heuristic does, can be shorter on these placements.