Teleportation-based Synthesis for Quantum Computers

    Hardware constraints in modern quantum architecture pose a major obstacle to large-scale quantum computing. Due to the restrictions of qubit connectivity, most quantum algorithms cannot be directly performed on current quantum systems. To execute the two-qubit gates in these algorithms, additional logic must be inserted to move the qubits being acted next to each other. Traditional protocols for solving the quantum routing problem use SWAP gates, which swap the states of any two connected qubits. Ideally, the routing solution aims to minimize the number of gates or the depth of gates, but finding an optimal solution is an NP-hard task.

    New developments in quantum hardware technology may allow for better solutions. The latest generation of quantum computers has mid-circuit measurement and feed-forward capability. With this technology, quantum circuits can use quantum teleportation to efficiently swap qubits that are not directly connected. In our research, we implemented two transpiler passes that use teleportation for routing. One improves upon an existing algorithm for small and intermediate-scale quantum circuits. The other uses a completely novel approach to maintain the strict guarantee that every CNOT gate can be implemented in constant depth.