Publication
Finding Optimal Implementations of Non-native CNOT Gates using SAT
Philipp Niemann; Luca Müller; Rolf Drechsler
In: 13th International Conference on Reversible Computation (RC). International Conference on Reversible Computation (RC-2021), July 7-8, Nagoya, Japan, 2021.
Abstract
Quantum computer architectures place restrictions on the availability of quantum gates. While single-qubit gates are usually available on every qubit, multi-qubit gates like the CNOT gate can only be applied to a subset of all pairs of qubits. Thus, a given quantum circuit usually needs to be transformed prior to its execution in order to satisfy these restrictions. Existing transformation approaches mainly focus on using SWAP gates to enable the realization of CNOT gates that are not natively available in the architecture. As the SWAP gate is a composition of CNOT and single-qubit Hadamard gates, such methods may not yield a minimal solution. In this work, we propose a method to find an optimal implementation of non-native CNOTs, i.e. using the minimal number of native CNOT and Hadamard gates, by using a formulation as a Boolean Satisfiability (SAT) problem. While straightforward representations of quantum states, gates and circuits require an exponential number of complex-valued variables, the approach makes use of´a dedicated representation that requires only a quadratic number of variables, all of which are Boolean. As confirmed by experimental results, the resulting problem formulation scales considerably well—despite the exponential complexity of the SAT problem—and enables us to determine significantly improved realizations of non-native CNOT gates for the 16-qubit IBM QX5 architecture.