Speaker
Description
Quantum circuit decomposition under restricted hardware connectivity is fundamentally a search problem: the compiler must choose useful qubit partitions, map them to a target topology, and synthesize high-quality local decompositions without exploding routing cost. This talk presents two complementary advances for connectivity-aware quantum compilation. First, we introduce an all-partitions framework based on convex-set enumeration, followed by exact set cover solving to choose globally effective partitions. In practice, this turns partition selection into a solver-friendly optimization problem that scales far better than naive enumeration and substantially improves all-to-all decomposition, topology-aware compilation, and SeqPAM routing in BQSKit. Second, we present an OSR-guided graph-search method for small-block decomposition. Starting from the current best circuit, the search can insert CNOTs at any beneficial location, uses optimistic large-step updates when improvements appear, and combines Operator Schmidt Rank with a surplus-weighted tail term, $\kappa$, to break plateaus that rank alone cannot resolve. A minimum-CNOT certification step based on exhaustive search remains practical for $3$--$5$ qubit partitions and provides a strong local optimization primitive. Across benchmark circuits, these ideas reduce CNOT counts relative to existing BQSKit-based flows while also suggesting a natural path toward parallel and accelerator-friendly implementations.