  Quantum error correction is necessary for large-scale quantum computing. A
promising quantum error correcting code is the surface code. For this code,
fault-tolerant quantum computing (FTQC) can be performed via lattice surgery,
i.e., splitting and merging patches of code. Given the frequent use of certain
lattice-surgery subroutines (LaS), it becomes crucial to optimize their design
in order to minimize the overall spacetime volume of FTQC. In this study, we
define the variables to represent LaS and the constraints on these variables.
Leveraging this formulation, we develop a synthesizer for LaS, LaSsynth, that
encodes a LaS construction problem into a SAT instance, subsequently querying
SAT solvers for a solution. Starting from a baseline design, we can gradually
invoke the solver with shrinking spacetime volume to derive more compact
designs. Due to our foundational formulation and the use of SAT solvers,
LaSsynth can exhaustively explore the design space, yielding optimal designs in
volume. For example, it achieves 8% and 18% volume reduction respectively over
two states-of-the-art human designs for the 15-to-1 T-factory, a bottleneck in
FTQC.
