MOSAIQC: Mixed-topology-aware Optimization for Scalable Approximate noise-Informed Quantum circuit Cutting

Quantum circuit cutting is a technique used to partition large quantum algorithms into smaller sub-circuits that can be executed on limited-capacity hardware. While effective, existing methods often struggle with scalability, failing to account for the interplay between different cut types (wire vs. gate) or the specific noise and connectivity constraints of heterogeneous quantum processors. MosaiQC addresses these limitations by providing a scalable, heuristic-based framework that jointly optimizes these factors.

MosaiQC employs a hierarchical optimization pipeline designed to balance solution quality with computational speed. The process begins by transforming the quantum circuit and hardware topology into compact graph representations. It then uses a global partitioning heuristic (METIS) to generate a warm-start solution, which is subsequently refined using a Tabu search. A key innovation is the integration of a fast approximate quadratic assignment solver, which allows the framework to map circuit partitions to hardware backends while considering both connectivity and noise-aware costs. By implementing the core optimization logic in C++ via PyBind11, the framework maintains polynomial runtime complexity, making it suitable for large-scale circuits that would be intractable for exact solvers.

As quantum circuits grow toward the thousand-qubit regime, compilation bottlenecks become a critical hurdle. MosaiQC demonstrates that heuristic optimization can effectively manage the trade-off between sampling overhead and execution fidelity. By supporting mixed-topology hardware and combined cut types, the framework provides a practical tool for researchers to execute larger algorithms on current NISQ-era devices, significantly reducing the overhead associated with circuit fragmentation.