Compiling quantum circuits to realistic hardware architectures using temporal planners

1. Introduction

• Gate-model processors are universal once scaled up, while currently commercially available quantum hardware is limited to special-purpose quantum annealers.Gate-model processors could broaden empirical exploration beyond optimization algorithms.Source: §1 · p. 2
• Idealized circuits often require gates between non-neighboring qubits, so compilation to superconducting hardware adds gates to move qubit states.The hardware examples include planar architectures with nearest-neighbor restrictions.Source: §1 · pp. 2–3
• Commuting gates enlarge the search space for feasible compilations, making optimal plans harder to find but increasing the potential gains from optimization.The motivation is especially relevant because decoherence degrades quantum algorithm performance over time, and near-term hardware has limited mitigation.Source: §1 · p. 3
• Temporal planning had not previously been applied to this compilation problem and can address variable-duration gates, inhomogeneous architectures, and circuits with many commuting gates.Existing scheduling work on commuting gates was limited to gates of unit duration and/or linear architectures.Source: §1 · p. 4
• Temporal planners produced machine-dependent plans that respect hardware constraints and minimize makespan, demonstrating a viable approach to quantum circuit compilation.The experiments use diverse temporal planners to compile circuits of various sizes to an architecture inspired by those under construction.Source: §1 · p. 4

2. Architecture-specific quantum circuit compilation problem

• The hardware model represents qubits as graph nodes and gates as labeled edges with durations, while allowing concurrency subject to additional restrictions.The study simplifies swaps to equal-duration gates between adjacent qubits, although the planning approach can handle more general cases.Source: §2 · pp. 5–6
• Swap gates move qubit states between locations so desired gates can be applied, and a swap can be synthesized from three CNOTs.The figure also depicts recursively replacing the CNOTs with iSWAPs and X-rotations; the model abstracts gate durations based on synthesis.Source: §2 · p. 6, Figure 1 · p. 6

2.1. Formal problem statement

• The compiler maps an idealized circuit and hardware multigraph to a time-resolved hardware-specific circuit that minimizes schedule makespan.The circuit includes operations that may commute, and the hardware graph represents physical qubits and implementable gates.Source: §2.1 · p. 7

2.2. Compilation examples

• The example chip uses two-qubit gate types with distinct durations, and compilation adds swaps or reorders commuting operations to reduce execution time.The hypothetical architecture is inspired by Rigetti's proposal and includes multiple nearest-neighbor relations.Source: §2.2 · p. 7, Figure 2 · p. 8
• A compilation example shows that commuting blue and red gates can be scheduled differently depending on the blue-gate duration relative to three swap durations.When the blue gate takes longer, it can run while swaps move another qubit; when shorter, the swap sequence can wait until the blue gate finishes.Source: §2.2 · pp. 8–9

3. Compiling QAOA for the MaxCut problem

• Because phase-separation gates commute, they can be applied in any order, enlarging the search space while creating more scope for compilation optimization.The paper therefore focuses on QAOA circuits despite their greater optimization challenge compared with less flexible circuits.Source: §3 · pp. 9, 11
• The experiments compile QAOA p = 1 and p = 2 circuits for MaxCut to an architecture inspired by Rigetti, with two kinds of nearest-neighbor relation.The two relation types correspond to different phase-separation gate durations; the assigned durations are realistic illustrations, not measurements from ongoing designs.Source: §3 · pp. 9, 11
• The target is MaxCut: partition graph vertices into two sets to maximize the number of edges crossing between them.The section expresses the objective as a quadratic Boolean function with one binary variable per vertex.Source: §3 · p. 10
• QAOA for MaxCut requires a two-qubit phase-separation gate for each graph edge and one-qubit mixing gates for each vertex.The final mixing step is omitted from the compilation problem because it can be applied directly at the end.Source: §3 · pp. 10–11
• For each qubit, its mixing operation must wait until all phase-separation gates involving that qubit in the preceding phase have been carried out.The phase-separation and mixing steps repeat p times; the final mixing step is treated separately.Source: §3 · p. 11

4. Compilation of a Quantum Circuit as Temporal Planning Problem

• The model separates shared domain behavior from instance-specific objects, initial states, and goals, using PDDL 2.1 to represent action durations and temporal conditions.PDDL modeling choices were selected to keep models compact, reduce preprocessing, and remain usable by a broad range of temporal planners.Source: §4 · pp. 13, 15
• Encoding the sparse qubit-connection graph in the domain reduces potential two-qubit ground actions from N^4 to N^2 × |E| and sped preprocessing by up to 40×.The authors embed qubit locations in action declarations rather than making qubit locations action parameters.Source: §4 · p. 15
• The PDDL model represents SWAP, phase-separation, and mixing gates as durative actions, with conditions and effects encoding state locations and completed operations.Actions are permitted only when the relevant qstates occupy the required qubits; the model also prevents a qstate from being used by multiple gates simultaneously.Source: §4 · pp. 15–16, Figure 4
• Mixing actions explicitly require every preceding phase-separation gate involving that qstate, avoiding PDDL features unsupported by many effective temporal planners.The alternatives considered were a per-qstate count variable and quantified conditions with conditional effects.Source: §4 · p. 16
• The planning objective is to minimize plan makespan, matching the compilation goal of minimizing circuit depth.The goal predicates require the phase-separation gates and, for p = 2, the intermediate mixing operations; the final mixing step is added by hand.Source: §4 · p. 16
• Initial tests found that a discretized non-temporal model performed worse with the M/Mp SAT-based planner than temporal planners on the original model.Another proposed option is to encode actions as instantaneous and restore temporal constraints in post-processing; the authors do not expect high-quality plans but see possible scaling benefits.Source: §4 · pp. 16–17

Problem generation

• The test suite contains 600 random problems across N=8, 21, and 40 qubits and p=1, 2, with 90% or 100% utilization and cutoffs from 10 to 60 minutes.Although the layouts were representative of near-term devices, the benchmarks did not model the available Rigetti chip's actual gate calibration or durations. The planners used default parameters, with LPG represented by its k=10 mode.Source: §5 · pp. 17, 20

Evaluation Result Summary

• LPG solved the most problems, followed by TFD, SGPlan, and POPF; CPT solved only N=8, p=1, and no planner solved N=40, p=2 within 60 minutes.SGPlan alone solved all 100 N=40, p=1 problems, while it failed with an internal error for N=21, p=2.Source: Table 1 · p. 20, §5 · p. 21

Plan quality comparison

• For N=8, p=1, LPG found the best-quality plans against CPT's proven-optimal reference; at N=8, p=2, TFD nearly always led, while LPG performed significantly worse.For N=21, p=1, TFD and POPF were slightly better than LPG; on p=2, SGPlan's plans were overall better than LPG's.Source: Table 2 · p. 21, §5 · p. 23
• For Figure 5’s makespan comparisons at u=1.0 (qualitatively similar at u=0.9), TFD always dominates SGPlan and usually LPG, except at N=8, p=1, where TFD and LPG perform comparably.Source: Figure 5 · p. 22, §5 · p. 23

Planning time comparison

• SGPlan generally returned a single solution quickly, while TFD, LPG, and POPF used their allocated time to seek gradually better plans; CPT proved optimality quickly only on the smallest set.CPT's tight makespan bounds were ineffective at finding a solution on the larger sets.Source: §5 · p. 23

Other planners

• HSP* and VHPOP found no plan even for the smallest problems, whereas YAHSP had preliminary acceptable results up to N=40 reserved for future work.VHPOP ran out of memory quickly, and HSP* found no plan within a two-hour cutoff.Source: §5 · p. 24

Discussion

• The planners span scalability–quality tradeoffs: SGPlan scales quickly with reasonably good plans, TFD searches longest for quality, and LPG and POPF balance these aims.Anytime improvement helps TFD, LPG, and POPF, whereas SGPlan's partitioning ignores temporal aspects of the makespan objective.Source: §5 · p. 24

Plan visualization

• The N=8 Gantt example traces states through gates, swaps, and mixing; TFD's displayed optimal-makespan plan still contains superfluous actions that can be removed in post-processing.The chart uses time on the x-axis and qubit locations on the y-axis; white blocks mark swaps and '+' marks superfluous gates.Source: §5 · pp. 24, 26, Figure 6 · p. 25

• The approach targets quantum-hardware compilation, focusing experiments on MaxCut QAOA while extending in principle to other discrete-optimization QAOA circuits and arbitrary quantum circuits.The authors expect QAOA’s many commuting gates to offer greater potential gains than typical circuits; broader gains over brute force remain an expectation.Source: §6 · p. 26
• Established temporal planners compiled QAOA circuits with reasonable efficiency, demonstrating the approach’s viability.Source: §6 · p. 26
• Optimal-plan quality remains difficult to assess: existing optimal-makespan planners found solutions only for N = 8, p = 1, and no published optimal solution was available.The authors also identify optimization beyond makespan, including device figure-of-merit objectives, as future work.Source: §6 · p. 27
• Avoiding decomposition reduced makespan by approximately 10% on average, and more than half of test instances were scheduled optimally for p = 1.Source: §6 · p. 27
• Future evaluations will compare temporal planning with sorting networks, constraint programming, and tailored heuristics, and explore hybrid compilation methods.The planning framework can represent irregular hardware graphs and diverse gate durations.Source: §6 · pp. 27–28
• Future models may incorporate crosstalk, synthesized gate durations, teleportation, measurement and feedback, error correction, and fault-tolerant gate implementations.The authors also plan to test more planners and make test data and PDDL models available.Source: §6 · pp. 27–28