Harnessing the Power of Long-Range Entanglement for Clifford Circuit Synthesis

In superconducting architectures, limited connectivity remains a significant challenge for the synthesis and compilation of quantum circuits. We consider models of entanglement-assisted computation where long-range operations are achieved through injections of large Greenberger-Horne-Zeilinger (GHZ) states. These are prepared using ancillary qubits acting as an "entanglement bus," unlocking global operation primitives such as multiqubit Pauli rotations and fan-out gates. We derive bounds on the circuit size for several well-studied problems, such as CZ circuit, CX circuit, and Clifford circuit synthesis. In particular, in an architecture using one such entanglement bus, we give a synthesis scheme for arbitrary Clifford operations requiring at most 2n+1 layers of entangled state injections, which can be computed classically in O(n(3)) time. In a square-lattice architecture with two entanglement buses, we show that a graph state can be synthesized using at most [1/2n]+1 layers of GHZ state injections, and Clifford operations require only [3/2n]+ O(root n) layers of GHZ state injections.