Technical Summary: MOSAIQC

Problem Statement

Current quantum computers, particularly those in the Noisy Intermediate-Scale Quantum (NISQ) era, lack the qubit resources and fidelity required to execute most practical quantum algorithms. To circumvent these hardware limitations, "quantum circuit cutting" (or circuit knitting) has emerged as a technique to divide large algorithms into smaller partitions executable on available hardware. However, this approach introduces a significant sampling overhead that scales exponentially with the number of cuts required for exact state reconstruction.

Existing optimization frameworks for determining cut locations face several critical limitations:

1. Scalability: Exact methods (e.g., Mixed Integer Programming, SMT solvers) often exhibit factorial or exponential computational complexity, rendering them infeasible for circuits approaching the thousand-qubit regime.
2. Cut Type Limitations: Many heuristics optimize for either wire cuts or gate cuts in isolation, rarely combining both within a single optimization procedure.
3. Hardware Awareness: Most approaches assume homogeneous hardware partitions and neglect the specific noise characteristics and connectivity constraints of heterogeneous quantum backends, leading to suboptimal execution fidelity.
4. Trade-offs: Balancing the minimization of sampling overhead with the maximization of hardware fidelity (noise reduction) is a complex multi-objective problem that existing scalable heuristics often fail to address jointly.

Methodology

The paper presents MosaiQC, a heuristic optimization framework designed to jointly optimize sampling overhead, hardware-aware placement, and mixed gate/wire cuts while maintaining polynomial runtime complexity. The framework operates through a hierarchical, four-stage optimization pipeline:

1. Graph Representation

To reduce computational overhead, the quantum circuit and hardware topology are transformed into compact graph representations rather than relying on repeated Directed Acyclic Graph (DAG) evaluations.

• Connectivity Graph: Represents qubits as nodes and 2-qubit gates as edges, weighted by gate counts.
• Temporal Dependencies: Stored separately to efficiently evaluate wire cuts when partitions share qubits.
• Hardware Topology: Modeled as a weighted graph where edge weights incorporate noise metrics (e.g., $1-q$ and $2-q$ gate errors) and routing costs (estimated via Floyd-Warshall shortest paths).

2. Initial Partitioning (Warm-Start)

The framework utilizes the METIS library to perform global graph partitioning. This step generates an initial solution that satisfies hardware capacity constraints, providing a high-quality starting point for subsequent refinement. This stage primarily addresses gate cuts or wire cuts individually to establish a baseline.

3. Local Refinement

A Tabu Search algorithm iteratively refines the initial partition through local moves:

• Adding nodes to partitions (subject to capacity).
• Moving nodes between partitions.
• Swapping nodes at partition boundaries.
• Mixed Cut Evaluation: The cost function explicitly accounts for both gate and wire cuts. The overhead is calculated as $Overhead = (GateCost)^g \cdot 16^w$, where $g$ and $w$ are the counts of gate and wire cuts, respectively. To optimize computation, the logarithm of this cost is used during the search.
• Local Evaluation Strategy: Instead of re-evaluating the global graph, the framework uses a local wire-cut lookup strategy based on qubit-level graph representations, significantly reducing complexity to $O((a+1)p \log p)$ for overlapping partitions.

4. Hardware-Aware Partition Assignment

To optimize execution fidelity, MosaiQC employs a Quadratic Assignment Problem (QAP) solver using the Frank-Wolfe algorithm.

• Objective: Find a permutation matrix that maps circuit partitions to hardware backends to maximize expected fidelity (minimize noise).
• Scoring: The algorithm minimizes the trace of the product of the circuit partition matrix and the hardware noise topology matrix. Noise weights are transformed logarithmically ($w = \ln(1 - \epsilon_{noise})$) to handle different scales effectively.
• Adaptive Cost Function: To balance the computational cost of QAP evaluations with optimization quality, the framework uses an adaptive cost function ($S_{adapt}$) that normalizes cut overhead against the QAP placement score. QAP evaluations are performed at set intervals rather than every iteration.

Key Contributions

The paper claims the following specific contributions:

1. Joint Optimization Framework: A heuristic framework that optimizes mixed wire and gate cuts within a single procedure, a capability rarely demonstrated in existing scalable tools.
2. Local Wire Cut Evaluation: A strategy based on qubit-level graph representations that reduces the computational complexity of repeated DAG-based optimization.
3. Heterogeneous Hardware Support: An abstraction layer supporting quantum backends with varying qubit capacities and noise characteristics, allowing for mixed-size hardware partitions.
4. Hardware-Aware Placement: A method using doubly weighted graph matching (solved via Frank-Wolfe) to place partitions on hardware, explicitly optimizing for noise reduction.
5. Scalable Hybrid Strategy: A combination of global METIS partitioning for warm-start initialization and local Tabu Search refinement, achieving polynomial runtime complexity $O(k \cdot n_q + m \cdot n_q^3)$.

Results

The framework was evaluated against the Qiskit circuit-cutting add-on (using Dijkstra's algorithm) and exhaustive search methods across various benchmarks (e.g., Adder, BV, AQFT, QAOA, VQE) and circuit sizes (6 to 1000 qubits).

• Runtime Performance: MosaiQC achieved a 2.88× geometric mean speedup in runtime compared to the baseline. Crucially, it successfully optimized circuits up to 1000 qubits, whereas the baseline frequently timed out or encountered memory overflows.
• Sampling Overhead: The framework demonstrated an average 16.84% reduction in the number of cuts compared to the baseline. This resulted in a geometric mean improvement in sampling overhead of approximately $5.38 \cdot 10^{11}\times$ (due to the exponential nature of the overhead).
• Fidelity Improvement: The hardware-aware placement strategy showed a strong Pearson correlation ($r \approx 0.83 - 0.87$) between the QAP score and measured fidelity. In fidelity benchmarks, MosaiQC achieved a mean local fidelity improvement of +19.56% ± 6.17% over the baseline when the noise weight was prioritized.
• Convergence: The hybrid warm-start approach significantly reduced the number of iterations required for convergence compared to refinement-only approaches, preventing the optimizer from getting trapped in local minima early in the search.

Significance and Claims

The authors position MosaiQC as a necessary evolution in quantum compilation tools. They claim that as quantum circuits scale toward the thousand-qubit regime, the optimization of cut placement itself must not become a computational bottleneck.

The paper asserts that MosaiQC demonstrates a superior trade-off between run speed and solution quality, adding fundamental features (mixed cuts, heterogeneous hardware support, and noise-aware placement) that are excluded by most competitors. While acknowledging that practical circuit cutting remains fundamentally constrained by the exponential sampling overhead required for reconstruction, the authors argue that MosaiQC establishes a practical foundation for scalable circuit cutting in future heterogeneous quantum computing systems. The work suggests that scalable heuristic optimization can substantially reduce the computational overhead of circuit-cut placement, enabling the execution of algorithms that would otherwise be infeasible on current hardware.