  Path sums are a convenient symbolic formalism for quantum operations with
applications to the simulation, optimization, and verification of quantum
protocols. Unlike quantum circuits, path sums are not limited to unitary
operations, but can express arbitrary linear ones. Two problems, therefore,
naturally arise in the study of path sums: the unitarity problem and the
extraction problem. The former is the problem of deciding whether a given path
sum represents a unitary operator. The latter is the problem of constructing a
quantum circuit, given a path sum promised to represent a unitary operator.
  In this paper, we show that the unitarity problem is co-NP-hard in general,
but that it is in P when restricted to Clifford path sums. We then provide an
algorithm to synthesize a Clifford circuit from a unitary Clifford path sum.
The circuits produced by our extraction algorithm are of the form C1-H-C2,
where C1 and C2 are Hadamard-free circuits and H is a layer of Hadamard gates.
We also provide a heuristic generalization of our extraction algorithm to
arbitrary path sums. While this algorithm is not guaranteed to succeed, it
often succeeds and typically produces natural looking circuits. Alongside
applications to the optimization and decompilation of quantum circuits, we
demonstrate the capability of our algorithm by synthesizing the standard
quantum Fourier transform directly from a path sum.
