A compact and efficient SAT encoding for quantum circuits
Robert Wille, Nils Przigoda, Rolf Drechsler · 2013
Promising applications of quantum computation motivated the consideration of corresponding design methods for this emerging technology. Here, researchers are faced with the problem that signals in quantum circuits may (theoretically) assume an infinite number of states. As a consequence, design approaches based on Boolean satisfiability (SAT) were subject to restrictions so far. In this work, we propose a compact and efficient SAT encoding for quantum circuits that loses these restrictions. For this purpose, a structural analysis is introduced which determines an upper bound on possible quantum states. The applicability of the encoding is exemplarily demonstrated by a SAT-based equivalence checker.