Dynamic qubit allocation and routing for constrained topologies by CNOT circuit re-synthesis
Recent strides in quantum computing have made it possible to execute quantum algorithms on real quantum hardware. When mapping a quantum circuit to the physical layer, one has to consider the numerous constraints imposed by the underlying hardware architecture. Many quantum computers have constraints regarding which two-qubit operations are locally allowed. For example, in a superconducting quantum computer, connectivity of the physical qubits restricts multi-qubit operations to adjacent qubits [1]. These restrictions are known as connectivity constraints and can be represented by a connected graph (a.k.a. topology), where each vertex represents a distinct physical qubit. When two qubits are adjacent, there is an edge between the corresponding vertices.
To run a quantum circuit under those constraints, qubits need to be allocated to different quantum registers, and multi-qubit gates need to be routed accordingly. Recent developments have shown that Steiner-tree based compiling strategies provide a competitive tool to route CNOT gates. However, these algorithms require the qubit allocation to be decided before routing. Moreover, the allocation is fixed throughout the computation, i.e. the logical qubit will not move to a different qubit register. This is inefficient with respect to the CNOT count of the resulting circuit.
In this talk, we will introduce the algorithm PermRowCol [2] for routing CNOTs in a quantum circuit. It dynamically reallocates logical qubits during the computation, and thus results in fewer output CNOTs than the algorithms Steiner-Gauss [3] and RowCol [4]. We will focus on circuits over CNOT only, but this method could be generalized to a routing and allocation strategy on Clifford+T circuits by slicing the quantum circuit into subcircuits composed of CNOTs and single-qubit gates [5].
References
[1] Roberto Stassi, Mauro Cirio, and Franco Nori. “Scalable quantum computer with superconducting circuits in the ultrastrong coupling regime”. In: npj Quantum Information 6.1 (2020). eprint: 1910.14478.
[2] Arianne Meijer van de Griend and Sarah Meng Li. “Dynamic qubit allocation and routing for constrained topologies by CNOT circuit re-synthesis”. In: arXiv preprint (2022) arXiv:2205.00724 .
[3] Aleks Kissinger and Arianne Meijer-van de Griend. “CNOT circuit extraction for
topologically-constrained quantum memories”. In: Quantum Information and Com-
putation 20.7-8 (2020). eprint: 1904.00633.
[4] Bujiao Wu et al. “Optimization of CNOT circuits under topological constraints”. In: arXiv preprint (2021). eprint: 1910.14478.
[5] Vlad Gheorghiu et al. “Reducing the CNOT count for Clifford+ T circuits on NISQ architectures”. In: arXiv preprint (2020) arXiv:2011.12191.
Join the seminar in QNC 1201!
Add event to calendar