Efficient and optimal qubit routing for quantum simulation of periodic systems

A crucial step in quantum circuit synthesis is qubit routing; assigning the circuit's qubits to the device's physical qubits and inserting SWAP gates to ensure that the necessary two-qubit gates can be executed. To maximize the performance of limited quantum hardware, it is essential to minimize the overhead from qubit routing. This is at odds with the NP-harness of qubit routing. However, quantum circuits used in the simulation of condensed matter systems and lattice gauge theories often consist of a subcircuit, the circuit unit cell, that is repeated spatially and possibly also temporally. Moreover, the connectivity of quantum hardware is typically spatially periodic. We leverage this double periodicity to efficiently obtain extremely high-quality routing solutions for virtually arbitrarily wide and deep input circuits. We achieve this by formulating the routing problem for a single circuit unit cell as a satisfiability problem, ensuring that the (depth-optimal) solution can be repeated spatiotemporally arbitrarily often without gate collisions. The overhead thus achieved is often remarkably low. For example, we find circuits for geometrically frustrated lattice spin systems that can be routed to square-grid hardware without routing overhead at all. Our work extends the capabilities of limited quantum devices to simulate non-trivial periodic systems of interest and paves the way for leveraging spatiotemporal periodicity in all other steps of quantum circuit synthesis.