  Satisfiability Testing (SAT) techniques are well-established in classical
computing where they are used to solve a broad variety of problems, e.g., in
the design of classical circuits and systems. Analogous to the classical realm,
quantum algorithms are usually modelled as circuits and similar design tasks
need to be tackled. Thus, it is natural to pose the question whether these
design tasks in the quantum realm can also be approached using SAT techniques.
To the best of our knowledge, no SAT formulation for arbitrary quantum circuits
exists and it is unknown whether such an approach is feasible at all. In this
work, we define a propositional SAT encoding that, in principle, can be applied
to arbitrary quantum circuits. However, we show that due to the inherent
complexity of representing quantum states, constructing such an encoding is not
feasible in general. Therefore, we establish general criteria for determining
the feasibility of the proposed encoding and identify classes of quantum
circuits fulfilling these criteria. We explicitly demonstrate how the proposed
encoding can be applied to the class of Clifford circuits as a representative.
Finally, we empirically demonstrate the applicability and efficiency of the
proposed encoding for Clifford circuits. With these results, we lay the
foundation for continuing the ongoing success of SAT in classical circuit and
systems design for quantum circuits.
