TETRIS-Q: Tiling-based Effective Transient-fault Reduction and Parallelism Optimizations for Quantum Circuit Mapping

Abstract

Quantum circuit mapping on Noisy Intermediate-Scale Quantum (NISQ) devices must satisfy physical connectivity constraints while minimizing both SWAP overhead and exposure to transient faults like decoherence. Existing compilers typically optimize qubit routing and noise-aware placement independently, failing to jointly exploit spatial structure to reduce both SWAP depth and idle-time-induced decoherence. We introduce TETRIS-Q, a mapping framework that partitions the physical qubit topology into local rectangular tiles. This tiling abstraction enables a unified strategy: tile-local mapping minimizes idle qubit lifetimes, while cross-tile parallel scheduling maximizes concurrent two-qubit gate execution. By treating transient-fault probability as a function of idle duration and gate ordering, rather than just circuit depth, TETRIS-Q jointly penalizes SWAP count and cumulative idle time. On grid-heavy architectures, we project a 10–30% reduction in SWAP count [to verify] and measurable fidelity improvements over routing-only baselines [to verify]. This approach demonstrates that spatial tiling offers a robust paradigm for high-fidelity NISQ compilation.

1. Introduction

Compiling quantum algorithms for Noisy Intermediate-Scale Quantum (NISQ) hardware requires mapping logical qubits onto physical qubits with limited connectivity. To execute gates between non-adjacent physical qubits, compilers insert SWAP gates—operations that exchange qubit states—to route interacting qubits into adjacency. While SWAP gates introduce additional circuit depth and gate errors, they also indirectly increase exposure to transient faults (decoherence and relaxation, characterized by T1 and T2 timescales) by extending the duration that idle qubits wait for dependent operations.

Existing quantum compilers generally treat routing minimization and noise-aware placement as separate optimization passes. However, this independent optimization misses opportunities to exploit the spatial locality of quantum interactions. We analyze TETRIS-Q, a framework that introduces a tiling-based abstraction to unify these objectives. By partitioning the physical coupling graph into local tiles, TETRIS-Q simultaneously reduces SWAP overhead, minimizes idle-time-induced decoherence, and increases parallel gate execution.

2. Background

NISQ devices are characterized by tens to hundreds of qubits with limited, nearest-neighbor connectivity and non-negligible error rates. A SWAP gate is typically decomposed into three CNOT gates, making qubit routing a primary source of circuit noise. Transient faults occur when a qubit loses its quantum state due to environmental interaction (decoherence) or energy dissipation (relaxation) over time, particularly when idle.

Prior work has established foundational approaches to these mapping challenges. Li et al. introduced a SWAP-based remapping framework using a shortest-path heuristic (SABRE), establishing the standard qubit mapping formulation [1]. Zulehner et al. proposed A* search over architecture-aware bidirectional mappings to reduce gate count for specific topologies [2]. Murali et al. advanced noise-adaptive compiler mappings, varying routing cost functions based on calibrated device noise to improve fidelity on heterogeneous-error hardware [3]. Sivarajah et al. developed t|ket⟩, a retargetable compiler with routing and scheduling passes, though lacking explicit transient-fault-aware tiling [4]. Tan & Cong formulated layout synthesis as a constrained optimization (SMT/Optimal), proving optimality bounds for small circuits [5]. Despite these advances, none jointly exploit spatial tiling structure to minimize both SWAP depth and idle-time-induced decoherence simultaneously.

3. Analysis

The TETRIS-Q framework proceeds in three stages to jointly optimize routing and transient-fault exposure:

1. Tile decomposition: The physical coupling graph is partitioned into overlapping or non-overlapping rectangular tiles, each containing a small number of physically adjacent qubits. The tile size is parameterized by the device's characteristic decoherence length and connectivity degree. This spatial abstraction localizes noise effects and routing constraints.
2. Tile-local mapping: Logical qubit interactions are assigned to tiles such that frequently interacting logical qubits reside within the same tile, minimizing inter-tile SWAP traffic. Within each tile, a local placement solves a small constrained optimization problem to minimize idle gaps between dependent gates, directly targeting transient-fault exposure.
3. Cross-tile parallel scheduling: Independent two-qubit gates assigned to different tiles are scheduled in the same time slice. SWAP insertions at tile boundaries are deferred or batched to preserve parallelism. The compiler utilizes a cost function that jointly penalizes added SWAP count and cumulative idle time, weighted by T1/T2 calibration data.

By treating transient-fault probability as a function of qubit idle duration and gate execution ordering—rather than merely total circuit depth—TETRIS-Q distinguishes itself from depth-minimization-only compilers.

4. Results

The performance of TETRIS-Q is evaluated on standard benchmark circuits (e.g., QASMBench, SupermarQ) mapped to grid-heavy architectures such as the IBM heavy-hex and Google Sycamore-style topologies. Compared against SABRE- and A*-based baselines, TETRIS-Q is expected to report a 10–30% reduction in total SWAP count [to verify].

Furthermore, the framework is projected to yield measurable fidelity improvements on noise-simulated backends [to verify]. These improvements are attributable to reduced idle-window exposure rather than gate-count reduction alone. Finally, TETRIS-Q is expected to demonstrate increased parallel gate utilization, defined as the fraction of time slices with two or more concurrent two-qubit gates, particularly on circuits exhibiting high logical-locality [to verify].

5. Discussion

Several open questions remain regarding the robustness and generalization of the tiling approach. First, tile granularity sensitivity must be addressed: it is unclear how performance degrades as tile size deviates from the decoherence-length-optimal value, and whether an adaptive tile-sizing policy is required. Second, generalization to non-grid topologies poses a challenge; heavy-hex and all-to-all-limited architectures have irregular local structures, and the tiling abstraction may require topology-specific tile shapes to remain effective. Third, calibration drift means transient-fault rates are time-varying; static tile assignments may not remain valid across calibration cycles, potentially necessitating runtime re-tiling.

Finally, regarding verification status, the source preprint (arXiv 2609.05226v1) could not be independently verified at the time of this analysis [to verify]. The paper's existence and specific method details should be confirmed before broader integration into quantum compilation research pipelines.

6. Conclusion

TETRIS-Q presents a compelling tiling-based abstraction for quantum circuit mapping that unifies the optimization of SWAP overhead and transient-fault exposure. By partitioning the physical topology into local tiles, the framework minimizes idle qubit lifetimes and maximizes parallel gate execution across tiles. This approach demonstrates that spatial tiling offers a robust paradigm for high-fidelity NISQ compilation, moving beyond traditional routing-only or noise-aware-only strategies.

References

[1] G. Li, Y. Ding, and Y. Xie, "Tackling the Qubit Mapping Problem for NISQ-Era Quantum Devices," in Proceedings of the 24th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), 2019. DOI: 10.1145/3297858.3304023

[2] A. Zulehner, A. Paler, and R. Wille, "An Efficient Methodology for Mapping Quantum Circuits to the IBM QX Architectures," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2018. DOI: 10.1109/TCAD.2018.2846658

[3] P. Murali, J. M. Baker, A. Javadi-Abhari, F. T. Chong, and M. Martonosi, "Noise-Adaptive Compiler Mappings for Noisy Intermediate-Scale Quantum Computers," in Proceedings of the 24th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), 2019. DOI: 10.1145/3297858.3304075

[4] S. Sivarajah et al., "t|ket⟩: A Retargetable Compiler for NISQ Devices," Quantum Science and Technology, 2020. DOI: 10.1088/2058-9565/ab8e92

[5] B. Tan and J. Cong, "Optimal Layout Synthesis for Quantum Computing," in Proceedings of the 39th International Conference on Computer-Aided Design (ICCAD), 2020. DOI: 10.1145/3400302.3415640