# Symbolic synthesis of Clifford circuits and beyond

Matthew Amy,1 Owen Bennett-Gibbs,2 and Neil J. Ross3
1 School of Computing Science, Simon Fraser University
2 Department of Mathematics and Statistics, McGill University
3 Department of Mathematics and Statistics, Dalhousie University

###### Abstract

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
$C_{1}HC_{2}$, where $C_{1}$ and $C_{2}$ 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.

##  1 Introduction

The circuit model is ubiquitous in quantum computing, from hardware assembly
code to the high-level description of algorithms. Quantum compilation
typically amounts to a series of circuit-to-circuit transformations, lowering
a circuit, described programmatically in a _circuit description language_ over
a high-level gate set, down through a series of progressively restrictive gate
sets with more fault-tolerance and hardware constraints. Accordingly, quantum
algorithms are frequently described at the level of quantum circuits, plugging
together inputs and outputs of large, complicated circuits. An exception is
the classical oracles used in many quantum algorithms, which are often
described at the level of classical programs or Boolean logic, and then
_synthesized_ as a high-level quantum circuit.

Despite this, the circuit model is often a less than ideal representation of
quantum computations. Semantically, circuits expose little information about a
computation to the naked eye, particularly when low-level gate sets like
Clifford+$T$ are used. Likewise, reasoning about quantum circuits is often a
difficult affair involving re-write rules derived from circuit _relations_.
Complete sets of relations are only known for a small number of low-level non-
universal gate sets [28, 3, 22], or higher-level gate sets [10, 21] which
result in a large degree of overhead when compiled. Even with complete sets of
relations, simplification of quantum circuits using re-write rules is costly
and highly local, yielding results which are typically far from optimal.

Recently, alternative models of quantum computation such as those based on
diagrammatic calculi [12, 7], have risen in popularity. These models have seen
success in circuit simplification, among other applications, due in part to
more effective re-writing methods. However, as most existing quantum computers
ultimately run on circuit-like languages, a key component in using such models
for circuit transformations is the ability to synthesize or _extract_ a
circuit back from the representation. This problem has seen a great deal of
attention recently in the context of graphical calculi, resulting in methods
for the extraction of Clifford and Clifford+$T$ circuits from ZX diagrams
admitting a _generalized flow_ [17, 8], as well as theoretical results
studying the hardness of this extraction problem [15].

In this paper, we study the problem of synthesizing a unitary circuit given a
symbolic expression of a linear operator as a _sum-over-paths_ or _path sum_
[2]. As any linear operator between $2^{n}$-dimensional Hilbert spaces is
representable in this form, we first consider the problem of deciding whether
a path sum representations a unitary transformation and show that it is
generically coNP-hard. Restricting to path sums representing Clifford
operators we show that the unitarity problem is in P, and that a unitary
circuit can be synthesized in time polynomial in the number of qubits. This
extraction algorithm produces circuits of the form $C_{1}HC_{2}$, where
$C_{1}$ and $C_{2}$ are Hadamard-free circuits decomposable as a product of s,
x, cz, and cnot gates, and $H$ is a layer of Hadamard gates. As a consequence
we obtain a simple, constructive proof of the $7$-stage Bruhat decomposition
of the Clifford group [11, 23].

For non-Clifford operations, we give a heuristic for the unitary synthesis of
general sums. While our heuristic does not always produce a circuit even if
the path sum represents a unitary operator, it succeeds often in practice and
typically returns efficient, natural circuits. Alongside circuit optimization,
this heuristic has applications to the _decompilation_ of quantum circuits,
whereby a circuit over a low-level gate set such as Clifford+$T$ is re-written
over a higher-level gate set such as multiply-controlled Toffoli gates. We
further demonstrate the capability of our algorithm by synthesizing the
typical quantum Fourier transform circuit directly from its specification as a
sum-over-paths.

##  2 Path sums

We begin by briefly reviewing the theory of _path sums_ [2, 31]. A _path sum
representation_ of a linear operator
$\Psi:\mathbb{C}^{2^{m}}\rightarrow\mathbb{C}^{2^{n}}$ is an expression for
$\Psi$ as a sum indexed by binary variables such as

$\Psi\ket{\vec{x}}=\mathcal{N}\sum_{\vec{y}\in\mathbb{Z}_{2}^{k}}e^{2\pi
iP(\vec{x},\vec{y})}\ket{f(\vec{x},\vec{y})},$ (1)

where $\mathcal{N}\in\mathbb{C}\setminus\\{0\\}$ is a _normalization factor_ ,
and $P:\mathbb{Z}_{2}^{m}\times\mathbb{Z}_{2}^{k}\rightarrow\mathbb{R}$ and
$f:\mathbb{Z}_{2}^{m}\times\mathbb{Z}_{2}^{k}\rightarrow\mathbb{Z}_{2}^{n}$
are real- and Boolean-valued multilinear polynomials, respectively. The path
sum in Equation 1 is said to be _amplitude-balanced_ because the normalization
factor $\mathcal{N}$ is independent of $\vec{x}$ and $\vec{y}$. We sometimes
denote the path sum representation of an operator $\Psi$ by $\ket{\Psi}$.

Equation 1 provides a representation the operator $\Psi$ in the sense that
instantiating the binary variables $\vec{x}$ and $\vec{y}$ on both sides of
the equality yields a true equation. For this reason, we think of a path sum
as a symbolic description of the action of a linear operator on computational
basis states.

######  Example 2.1.

The phase gates s and t, as well as the Hadamard gate h, can be represented by
path sums as follows, where $\omega=e^{i\pi/4}$:

  * •

$\textsc{s}\ket{x}=i^{x}\ket{x}$,

  * •

$\textsc{t}\ket{x}=\omega^{x}\ket{x}$, and

  * •

$\textsc{h}\ket{x}=\frac{1}{\sqrt{2}}\sum_{y}(-1)^{xy}\ket{y}$.

As path sums involve arithmetic and polynomials over Boolean variables in
various rings, it is useful to recall that Boolean algebra can be embedded in
any (unital) ring $\mathcal{R}$ using the _lifting_ construction defined in
[2, Lemma 7.1.6] and reproduced below.

$\displaystyle\hskip 50.00008pt\overline{0}$ $\displaystyle=0_{\mathcal{R}}$
$\displaystyle\overline{f\land g}$
$\displaystyle=\overline{f}\cdot\overline{g}$ $\displaystyle\hskip
20.00003pt\overline{1}$ $\displaystyle=1_{\mathcal{R}}$
$\displaystyle\overline{f\oplus g}$
$\displaystyle=\overline{f}+\overline{g}-(2\cdot\overline{f}\cdot\overline{g})$

Lifting allows one to use Boolean expressions of variables inside path sums
coherently, leading to more natural expressions, as in the following example.

######  Example 2.2.

The gates cnot and tof admit the following path sum representations:

  * •

$\textsc{cnot}\ket{x_{1}x_{2}}=\ket{x_{1}}\ket{x_{1}\oplus x_{2}}$ and

  * •

$\textsc{tof}\ket{x_{1}x_{2}x_{3}}=\ket{x_{1}}\ket{x_{2}}\ket{x_{1}\oplus(x_{2}\cdot
x_{3})}$.

The sum-over-paths representations of linear operators has been studied
extensively in the context of quantum information [13, 9, 27, 24, 19, 14].
Recent work on the connection to graphical calculi [20, 31] has shown that
path sums form a universal model for linear operators over $2^{n}$-dimensional
Hilbert spaces through direct translations from universal graphical calculi
such as the ZH-calculus [7].

######  Proposition 2.3 (Unversality).

Any linear operator $\Psi:\mathbb{C}^{2^{m}}\rightarrow\mathbb{C}^{2^{n}}$
admits a representation as a path sum.

######  Example 2.4.

Path sums can represent linear operators between spaces of different
dimensions. The operators
$\eta:\mathbb{C}\rightarrow\mathbb{C}^{2}\otimes\mathbb{C}^{2}$ and
$\varepsilon:\mathbb{C}^{2}\otimes\mathbb{C}^{2}\rightarrow\mathbb{C}$, which
act, respectively, as the unit and counit in the category FdHilb [31], can be
written as the following path sums:

  * •

$\eta\ket{}=\sum_{y}\ket{yy}$ and

  * •

$\varepsilon\ket{x_{1}x_{2}}=\frac{1}{2}\sum_{y}(-1)^{y(x_{1}+x_{2})}\ket{}$.

When a path sum represents a row or column vector as above, we drop any empty
$\ket{}$. A path sum with a single output dimension, representing a
$\mathbb{C}$-valued linear map, is said to be _dimensionless_.

In contrast to graphical calculi, which have a _compositional_ structure, path
sums are effectively _global_ expressions of a linear operator. In other
words, the composition (sequential or parallel) of two linear operators is
reified into an expression of the form of Equation 1. This is accomplished
through the substitution of _free variables_ — variables that are not summed
over, corresponding to inputs of the operator as elements of the computational
basis. We denote the free variables of a path sum $\ket{\Psi}$ by
$FV(\ket{\Psi})$. A path sum with free variables may be thought of as a
symbolic state vector in indeterminates $\vec{x}=FV(\ket{\Psi})$. Hence we use
the notation $\ket{\Psi(\vec{x})}$ to denote a path sum expression for the
operator $\Psi$ with free variables $\vec{x}$. We use $\ket{\Psi(x)}$ to
denote a path sum with a distinguished free variable $x$.

Through the lifting operation described above, we can define a notion of
substitution for path sums with free variables. In particular, given a free
variable $x$ appearing in a path sum we may substitute $x$ with any Boolean
expression $f$ in all relevant contexts (the phase or the state).

######  Definition 2.5 (Substitution).

Let $\ket{\Psi(x)}$ be a path sum with free variable $x$ and let $f$ be a
Boolean expression. Then the _substitution_ of $x$ with $f$ is denoted
$\ket{\Psi(f)}$.

Reasoning with local binders and free variables in the path sums requires care
to avoid variable capture. For instance, let $\ket{\Psi(x)}=\sum_{y}\ket{x}$.
It can be observed that $\ket{\Psi(x)}$ represents the linear operator
$\Psi=2I$. However, if $x$ is substituted with the free variable $y$, the
$\sum_{y}$ captures $y$, giving the path sum $\ket{\Psi(y)}=\sum_{y}\ket{y}$,
representing the vector $\ket{0}+\ket{1}$. We assume that substitution is
capture-avoiding unless otherwise noted.

A variable may also be _bound_ by summing over its possible values. A bound
variable may be locally viewed as a free variable by pulling the summation
outside of an expression. Indeed, if $\ket{\Psi(x)}$ is a path sum with free
variable $x$, then $\sum_{x}\ket{\Psi(x)}$ is a path sum with free variables
$FV(\ket{\Psi})\setminus\\{x\\}$. We sometimes refer to bound variables as
_path_ variables.

######  Example 2.6.

Recall that the Hadamard gate can be represented as
$\textsc{h}\ket{x}=\frac{1}{\sqrt{2}}\sum_{y}(-1)^{xy}\ket{y}$. Alternatively,
the Hadamard gate can also be written as
$\textsc{h}\ket{x}=\sum_{y}\ket{\Psi(x,y)}$ where
$\ket{\Psi(x,y)}=\frac{1}{\sqrt{2}}(-1)^{xy}\ket{y}$ is a path sum in the free
variables $x$ and $y$.

By Proposition 2.3, any linear operator admits a path sum representation. In
particular, the composition or tensor product of any two linear operators can
also be represented as a path sum. The following proposition gives explicit
expression for these constructions in the language of path sums.

######  Proposition 2.7 (Parallel & Sequential composition).

Let $\Psi:\mathbb{C}^{2^{m}}\rightarrow\mathbb{C}^{2^{n}}$ and
$\Phi:\mathbb{C}^{2^{s}}\rightarrow\mathbb{C}^{2^{t}}$ be two linear operators
and let
$\Psi\ket{\vec{x}}=\mathcal{N}\sum_{\vec{y}\in\mathbb{Z}_{2}^{k}}e^{2\pi
iP(\vec{x},\vec{y})}\ket{f(\vec{x},\vec{y})}$ and
$\Phi\ket{\vec{w}}=\mathcal{M}\sum_{\vec{z}\in\mathbb{Z}_{2}^{l}}e^{2\pi
iQ(\vec{w},\vec{z})}\ket{g(\vec{w},\vec{z})}$ be expressions of $\Psi$ and
$\Phi$ as path sums. Then

$\displaystyle\Psi\otimes\Phi\ket{\vec{x}}\ket{\vec{w}}$
$\displaystyle=\mathcal{NM}\sum_{\vec{y}\in\mathbb{Z}_{2}^{k}}\sum_{\vec{z}\in\mathbb{Z}_{2}^{l}}e^{2\pi
i\left[P(\vec{x},\vec{y})+Q(\vec{w},\vec{z})\right]}\ket{f(\vec{x},\vec{y})}\otimes\ket{g(\vec{w},\vec{z})}$
$\displaystyle\Phi\circ\Psi\ket{\vec{x}}$
$\displaystyle=\mathcal{N}\sum_{\vec{y}\in\mathbb{Z}_{2}^{k}}e^{2\pi
iP(\vec{x},\vec{y})}\ket{\Phi(f(\vec{x},\vec{y}))}$

as path sums, where the latter is well-formed if and only if $s=n$.

The parallel and sequential composition of path sums provides a method to
compute a symbolic expression for a circuit over a set of basic gates with
known path sums. Moreover, for typical gate sets of interest, this
representation has size polynomial in the size of the circuit. We give one
such result below [2, Corollary 2.15] for the class of circuits which will be
most relevant for the purposes of this paper.

######  Proposition 2.8 (Efficiency for Clifford+$T$).

Any circuit over Clifford+$T$ gates of volume $V$ can be expressed as a path
sum which has size polynomial in $V$ and can be computed in time polynomial in
$V$.

### Equational reasoning

A major utility of the path sum representation [2] comes from the ability to
perform _equational reasoning_. Complete equational theories of Clifford
unitaries [2] and more general stabilizer operations [31] have previously been
developed. We reformulate these theories here using locally free variables to
simplify their presentation.

######  Proposition 2.9.

Let $\Psi$ be a path sum such that $y\notin FV(\Psi)$ and let $f$ be a Boolean
expression such that $x,y\notin FV(f)$. Then the following equations hold.

$\displaystyle\sum_{y}\ket{\Psi}$ $\displaystyle=2\ket{\Psi}$ (2)
$\displaystyle\sum_{x,y}(-1)^{y(x+f)}\ket{\Psi(x)}$
$\displaystyle=2\ket{\Psi(f)}$ (3)
$\displaystyle\sum_{y}i^{y}(-1)^{yf}\ket{\Psi}$
$\displaystyle=\omega\sqrt{2}(-i)^{f}\ket{\Psi}$ (4)
$\displaystyle\sum_{y}\ket{\Psi(y)}$ $\displaystyle=\sum_{y}\ket{\Psi(y+f)}$
(5)

Equations 2, 3 and 4 are restatements of [2, Proposition 3.1]. Equation 5 is a
generalization of the (ket) rule given in [31, Figure 3] and can be derived
from Equation 3 as follows:

$\displaystyle\sum_{y}\ket{\Psi(y)}$
$\displaystyle=\sum_{y}\left[\frac{1}{2}\sum_{x,z}(-1)^{z(x+(y+f))}\ket{\Psi(y)}\right]$
By Equation 3 where $x,z\notin FV(f)\cup FV(\Psi)$
$\displaystyle=\sum_{x}\left[\frac{1}{2}\sum_{y,z}(-1)^{z(y+(x+f))}\ket{\Psi(y)}\right]$
Basic arithmetic $\displaystyle=\sum_{x}\ket{\Psi(x+f)}$ By Equation 3
$\displaystyle=\sum_{y}\ket{\Psi(y+f)}$ Since $y\notin FV(f)\cup FV(\Psi)$

The first equality above uses the instance
$\sum_{x,z}(-1)^{z(x+f^{\prime})}\ket{\Psi(y)}=2\ket{\Psi(y)}$ of Equation 3,
where $f^{\prime}=y+f$ and $\ket{\Psi(y)}$ is viewed as a path sum with zero
occurrences of the free variable $x$.

######  Example 2.10.

Consider the dimensionless path sum $\frac{1}{\sqrt{2}}\sum_{y}i^{y}$. By
Equation 4 it follows that $\frac{1}{\sqrt{2}}\sum_{y}i^{y}=\omega.$ Hence,
Equation 4 symbolically encodes the fact that $\omega=\frac{1+i}{\sqrt{2}}$.

### Relationship to post-selected circuits

As with the ZX-calculus and variants, path sum expressions correspond
naturally to circuits with ancillas and postselection. Given a path sum
expression of a linear operator
$\Psi:\mathbb{C}^{2^{m}}\rightarrow\mathbb{C}^{2^{n}}$ of the form of Equation
1, a circuit implementing $\Psi$ up to a constant scalar factor can be
achieved through postselection as follows. First, prepare $k$ ancillary qubits
in the state
$\frac{1}{\sqrt{2}^{k}}\sum_{\vec{y}\in\mathbb{Z}_{2}^{k}}\ket{\vec{y}}$ by
applying Hadamard gates to the $\ket{0}^{\otimes k}$ state. The symbolic state
is then prepared up to some garbage $\ket{g(\vec{x},\vec{y})}$ via the unitary
transformation

$\Psi_{PS}:\ket{\vec{x}}\otimes\ket{\vec{y}}\mapsto e^{2\pi
iP(\vec{x},\vec{y})}\ket{f(\vec{x},\vec{y})}\otimes\ket{g(\vec{x},\vec{y})}.$

Finally, the garbage is discarded by postselecting $\textsc{h}^{\otimes
m+k-n}\ket{g(\vec{x},\vec{y})}=\mathcal{N}^{\prime}\sum_{\vec{z}}(-1)^{\vec{z}\cdot
g(\vec{x},\vec{y})}\ket{\vec{z}}$ on $\vec{z}=\vec{0}$.

Since postselected quantum circuits are believed to be strictly more powerful
than non-postselected circuits [1], the rest of this paper focuses on the
question of synthesizing unitary circuits for path sums representing unitary
transformations, up to normalization.

##  3 Unitarity testing

We are interested in the synthesis of _unitary_ quantum circuits implementing
a path sum. As a path sum may represent an arbitrary linear operator, a
natural question to ask is whether a given path sum represents a unitary
transformation, and hence can be extracted to a unitary circuit. We call this
the _unitarity testing_ problem for path sums and formulate it as a decision
problem below.

######  Definition 3.1 (UNITARY).

_UNITARY_ is the set of path-sums $\ket{\Psi}$ where $\Psi$ is a unitary
transformation.

The unitarity problem is clearly decidable since we can always explicitly
compute a matrix representation of $\Psi$ from a path sum $\ket{\Psi}$.
However, since the size of the corresponding matrix is exponential in $n$,
this solution is not efficient. As we show in this section, one should not
hope for an efficient solution in general.

Recall that the complexity class co-NP consists of the decision problems whose
complement belongs to NP, and hence is widely believed to be intractable. A
canonical complete problem for co-NP is the tautology problem, recognizing the
set of propositional formulas over the connectives $\\{\neg,\land,\lor\\}$
which are satisfied by every variable assignment. We view a propositional
formula in $n$ distinct free variables as a function
$\mathbb{Z}_{2}^{n}\rightarrow\mathbb{Z}_{2}$, using the standard
interpretation $\neg x:=1+x$, $x\land y:=xy$ and $x\lor y:=x+y-xy$. The
application of $\varphi$ to some $\vec{x}\in\mathbb{Z}_{2}^{n}$ is denoted by
$\varphi(\vec{x})$.

######  Definition 3.2 (Tautology).

A propositional formula $\varphi$ in $n$ variables is a _tautology_ if
$\varphi(\vec{x})=1$ for every $\vec{x}\in\mathbb{Z}_{2}^{n}$, written
$\varphi\equiv 1$.

######  Definition 3.3 (TAUT).

_TAUT_ is the set of all propositional formulas that are tautologies.

######  Theorem 3.4 (Karp’s 21 NP-complete problems).

The TAUT problem is co-NP-complete.

To reduce TAUT to UNITARY, our goal is to encode a propositional formula
$\varphi$ as a path sum representing the linear operator
$\Phi\ket{\vec{x}}=\varphi(\vec{x})\ket{\vec{x}}$ which is the identity if
$\varphi\equiv 1$, and non-unitary otherwise. To do so we establish an
encoding of $\varphi$ as a dimensionless path sum of the form
$\varphi(\vec{x})=\mathcal{N}\sum_{\vec{y}}(-1)^{P(\vec{x},\vec{y})},$ where
$P$ is a multilinear Boolean polynomial.

It can readily be observed that
$x=2^{-1}\sum_{y\in\mathbb{Z}_{2}}(-1)^{y(1+x)}$ for any $x\in\mathbb{Z}_{2}$.
This gives an immediate encoding of any propositional formula in a path sum by
extending the lifting discussed in Section 2 to propositional negation and
disjunction via the equations $\overline{\neg\varphi}=1-\overline{\varphi}$,
$\overline{\varphi\lor\psi}=\overline{\varphi}+\overline{\psi}-\overline{\varphi}\cdot\overline{\psi},$
and then setting

$\varphi(\vec{x})=2^{-1}\sum_{y}(-1)^{y(1+\overline{\varphi}(\vec{x}))}.$

However, the lifting of a propositional formula $\varphi$ may generally have
size exponential in the size of $\varphi$. To obtain a polynomial size
encoding we rely on the _Tseytin transformation_ [29].

Given two propositional formulas $\varphi$ and $\psi$, we write
$\varphi\leftrightarrow\psi$ for the logical equality of $\varphi$ and $\psi$,
which is satisfied by an assignment $\vec{x}$ if and only if
$\varphi(\vec{x})=\psi(\vec{x})$. The Tseytin transformation takes a
propositional formula $\varphi$ with $k$ distinct subterms and returns an
equisatisfiable conjunction of at most $O(k)$ constant-depth formulas by
assigning a fresh propositional variable to the value of each subterm. For
instance, given a propositional formula $\varphi=x_{1}\land(x_{2}\lor\neg
x_{3})$, the Tseytin transformation of $\varphi$, denoted
$\mathcal{T}(\varphi)$, is

$\displaystyle\mathcal{T}(\varphi)=z_{1}\land(z_{1}\leftrightarrow x_{1}\land
z_{2})\land(z_{2}\leftrightarrow x_{2}\lor
z_{3})\land(z_{3}\leftrightarrow\neg x_{3}).$

Note that $FV(\varphi)\subseteq FV(\mathcal{T}(\varphi))$ and that the
satisfying assignments of $\varphi$ and $\mathcal{T}(\varphi)$ are in a 1-to-1
correspondence and agree on $FV(\varphi)$.

Given a propositional formula $\varphi$, we can encode the Tseytin
transformation $\mathcal{T}(\varphi)$ of $\varphi$ in a dimensionless sum over
the free variables of $\varphi$ using the following encoding of logical
equality

$(\varphi\leftrightarrow\psi)(\vec{x})=\sum_{y}(-1)^{y\overline{\varphi}(\vec{x})+y\overline{\psi}(\vec{x})}.$

Note that for a clause of the Tseytin transformation $z\leftrightarrow\varphi$
where $\varphi$ has constant depth, $\overline{\varphi}$ has constant size. If
we denote the clauses of $\mathcal{T}(\varphi)$ by $z_{1}\leftrightarrow
c_{1},\dots,z_{k}\leftrightarrow c_{k}$, we may encode $\mathcal{T}(\varphi)$
as a polynomial-size sum by taking the product of each clause and distributing
over the summations:

$\displaystyle\mathcal{T}(\varphi)(\vec{x},\vec{z})=z_{1}\prod_{i}(z_{i}\leftrightarrow
c_{i})(\vec{x})$
$\displaystyle=2^{-1}\sum_{y}(-1)^{y(1+z_{1})}\prod_{i}2^{-1}\sum_{y_{i}}(-1)^{y_{i}(z_{i}+\overline{c_{i}}(\vec{x}))}$
$\displaystyle=2^{-(k+1)}\sum_{y}\sum_{\vec{y}\in\mathbb{Z}_{2}^{k}}(-1)^{y(1+z_{1})+\sum_{i}y_{i}(z_{i}+\overline{c_{i}}(\vec{x}))}.$

Finally, since the satisfying assignments of $\varphi$ and
$\mathcal{T}(\varphi)$ are in a 1-to-1 correspondence, we see that

$\varphi(\vec{x})=\sum_{\vec{y}}\mathcal{T}(\varphi)(\vec{x},\vec{z})=2^{-(k+1)}\sum_{y}\sum_{\vec{y}\in\mathbb{Z}_{2}^{k}}\sum_{\vec{z}\in\mathbb{Z}_{2}^{k}}(-1)^{y(1+z_{1})+\sum_{i}y_{i}(z_{i}+\overline{c_{i}}(\vec{x}))}.$

######  Proposition 3.5.

Let $\varphi$ be a propositional formula in $n$ variables and let
$\mathcal{T}(\varphi)=z_{1}\land(\bigwedge_{i=1}^{k}z_{i}\leftrightarrow
c_{i})$. Then for any $\vec{x}\in\mathbb{Z}_{2}^{n}$,

$\displaystyle\varphi(\vec{x})$
$\displaystyle=2^{-(k+1)}\sum_{y}\sum_{\vec{y}\in\mathbb{Z}_{2}^{k}}\sum_{\vec{z}\in\mathbb{Z}_{2}^{k}}(-1)^{y(1+z_{1})+\sum_{i}y_{i}(z_{i}+\overline{c_{i}}(\vec{x}))}$

where the sum on the right hand size has size polynomial in $k$.

######  Remark 3.6.

The encoding of $\varphi$ in Proposition 3.5 is interesting because it gives a
polynomial-size expression _in the same variables as $\varphi$_. This is in
constrast to the propositional Tseytin transformation which gives an encoding
over a superset of free variables, and hence only remains equi-satisfiable. In
particular, $\mathcal{T}(\cdot)$ does not preserve tautologies, whilst our
encoding does when viewed as a $\\{0,1\\}$-valued function.

Given the encoding of $\varphi$ above, we can now prove co-NP-hardness of the
unitarity testing problem by a reduction from TAUT.

######  Theorem 3.7.

The unitarity testing problem is co-NP-hard

###### Proof.

By many-one reduction from TAUT to UNITARY. Given a propositional formula
$\varphi$ in $n$ variables, define
$\Psi:\mathbb{Z}_{2}^{n}\rightarrow\mathbb{Z}_{2}^{n}$ to be the linear
operator given by $\Psi\ket{\vec{x}}=\varphi(\vec{x})\ket{\vec{x}}.$ By
Proposition 3.5, $\Psi$ admits the following representation as a path sum

$\Psi\ket{\vec{x}}=2^{-(k+1)}\sum_{y}\sum_{\vec{y}\in\mathbb{Z}_{2}^{k}}\sum_{\vec{z}\in\mathbb{Z}_{2}^{k}}(-1)^{y(1+z_{1})+\sum_{i}y_{i}(z_{i}+\overline{c_{i}}(\vec{x}))}\ket{\vec{x}}$

which has size polynomial in the number of subterms of $\varphi$. Hence all
that remains is to show that $\Psi$ is unitary if and only if $\varphi$ is a
tautology. If suffices to observe that, for any
$\vec{x}\in\mathbb{Z}_{2}^{n}$,
$\Psi\ket{\vec{x}}=\varphi(\vec{x})\ket{\vec{x}}=\ket{\vec{x}}$ if
$\varphi(\vec{x})=1$ and $\vec{x}\in\mathbb{Z}_{2}^{n}$,
$\Psi\ket{\vec{x}}=\varphi(\vec{x})\ket{\vec{x}}=0$ otherwise. In particular,
if $\varphi(\vec{x})=1$ for all $\vec{x}\in\mathbb{Z}_{2}$, then $\Psi=I_{n}$.
Otherwise, there exists $\vec{x}\in\mathbb{Z}_{2}$ such that
$\Psi\ket{\vec{x}}=0$ and hence $\Psi$ is non-unitary, as required. ∎

##  4 Clifford synthesis

In this section we look at the problems of synthesis and unitarity testing in
the restricted case of Clifford operations. The synthesis of Clifford circuits
has applications both to randomized benchmarking, as well as to the design and
analysis of error correction circuits. We first review the definition of the
Clifford group.

######  Definition 4.1 (Pauli group).

The $n$-qubit _Pauli group_ $\mathcal{P}_{n}$ is the group of $n$-fold tensor
products of Pauli operators $\\{I,X,Y,Z\\}$.

######  Definition 4.2 (Clifford group).

The $n$-qubit _Clifford group_ is the group $\mathcal{C}_{n}=\\{U\in
U_{2^{n}}\mid U\mathcal{P}_{n}U^{\dagger}=\mathcal{P}_{n}\\}$.

A well-known consequences of the Gottesman-Knill theorem is the fact that, up
to global phases, the Clifford group is generated by
$\\{\textsc{h},\textsc{s},\textsc{cnot}\\}$. We may use this fact to give a
convenient path sum representation of Clifford operations.

######  Proposition 4.3.

Every Clifford operator $\Psi:\mathbb{C}^{2^{n}}\rightarrow\mathbb{C}^{2^{n}}$
can be written as a sum of the form

$\Psi\ket{\vec{x}}=\frac{\omega^{l}}{\sqrt{2^{k}}}\sum_{\vec{y}\in\mathbb{Z}_{2}^{k}}i^{L(\vec{x},\vec{y})}(-1)^{Q(\vec{x},\vec{y})}\ket{f(\vec{x},\vec{y})}$
(6)

where $l\in\mathbb{Z}_{8}$,
$L:\mathbb{Z}_{2}^{n}\times\mathbb{Z}_{2}^{k}\rightarrow\mathbb{Z}_{4}$ is
linear,
$Q:\mathbb{Z}_{2}^{n}\times\mathbb{Z}_{2}^{k}\rightarrow\mathbb{Z}_{2}$ is
pure quadratic, and
$f:\mathbb{Z}_{2}^{n}\times\mathbb{Z}_{2}^{k}\rightarrow\mathbb{Z}_{2}$ is
affine.

###### Proof.

As the Clifford group generators $\textsc{cnot},\textsc{s}$, and h can be
written in the form of Equation 6, it only remains to show that the
composition of two such sums can be written in the form of Equation 6. It
suffices to note that substitution of a variable with an affine Boolean
expression does not increase the degree of $Q$ or $f$, while substitution in
$L$ produces a quadratic form with degree $2$ terms divisible by $2$. ∎

We call an expression of the form of Equation 6 a _Clifford_ path sum. In the
context of _stabilizer states_ — states $\ket{\psi}=C\ket{\vec{0}}$ for some
$C\in\mathcal{C}_{n}$ — this representation is well-known by various names,
including the _quadratic form expansion_ [14] and the _affine representation_
[16, 26]. Through the inclusion of free parameters we can represent stabilizer
states, Clifford unitaries, or Clifford circuits with ancillas in this form.

We next define a _normal form_ for Clifford path sums which will be useful for
circuit synthesis.

######  Definition 4.4 (Normal form).

A Clifford path sum for $\Psi$ is in _normal form_ if, up to a reordering of
qubits,

$\Psi\ket{\vec{x}}=\frac{\omega^{l}}{\sqrt{2^{k}}}\sum_{\vec{y}\in\mathbb{Z}_{2}^{k}}i^{L(\vec{x},\vec{y})}(-1)^{Q(\vec{x},\vec{y})}\ket{\vec{y}}\otimes\ket{f(\vec{x},\vec{y})},$
(7)

where $l\in\mathbb{Z}_{8}$,
$L:\mathbb{Z}_{2}^{n}\times\mathbb{Z}_{2}^{k}\rightarrow\mathbb{Z}_{4}$ is
linear,
$Q:\mathbb{Z}_{2}^{n}\times\mathbb{Z}_{2}^{k}\rightarrow\mathbb{Z}_{2}$ is
pure quadratic, and
$f:\mathbb{Z}_{2}^{n}\times\mathbb{Z}_{2}^{k}\rightarrow\mathbb{Z}_{2}$ is
affine.

The normal form above corresponds to re-writing the sum over a minimal set of
vectors spanning the affine subspace of $\mathbb{Z}_{2}^{n}$ given by
$\\{f(\vec{x},\vec{y})\mid\vec{y}\in\mathbb{Z}_{2}^{k}\\}$. The following
proposition states that Equations 2, 3, 4 and 5 suffice to re-write a unitary
Clifford path sum into normal form.

######  Proposition 4.5.

Let $\ket{\Psi}$ be a Clifford path sum. There exists a re-writing procedure
which will terminate with $\ket{\Psi}$ in normal form if $\Psi$ is unitary and
runs in time polynomial in the size of $\ket{\Psi}$.

###### Proof.

For each path variable $y_{i}$, if there exists $j$ such that
$f_{j}(\vec{x},\vec{y})=y_{i}\oplus f^{\prime}(\vec{x},\vec{y})$, Equation 5
can be applied to substitute $y_{i}$ with $y_{i}\oplus
f^{\prime}(\vec{x},\vec{y})$. If no such $j$ exists, either $\Psi$ is unitary
and one of Equations 2, 3 and 4 necessarily applies to eliminate $y_{i}$ [2],
or no rule applies and $\Psi$ is non-unitary. ∎

######  Remark 4.6.

Proposition 4.5 also holds for non-square
$\Psi:\mathbb{C}^{2^{m}}\rightarrow\mathbb{C}^{2^{n}}$ with $m\leq n$ so long
as $\Psi$ is an _isometry_ — that is, if $\Psi$ corresponds to a Clifford
circuit with some ancillas or fixed inputs.

######  Corollary 4.7.

The unitarity testing problem for Clifford path sums is in P.

###### Proof.

Given a Clifford path sum $\ket{\Psi}$, we can construct a path sum
representation of $\Psi^{\dagger}$ efficiently using $\eta$, $\epsilon$, and
negating $L$. Then by Proposition 4.5 we can normalize the path sum
representations of $\Psi\Psi^{\dagger}$ and $\Psi^{\dagger}\Psi$ each in
polynomial time. If either fails to produce a normal form, then one of
$\Psi\Psi^{\dagger}$ or $\Psi^{\dagger}\Psi$ is non-unitary and hence $\Psi$
is non-unitary. If both are reduced to normal form, it suffices to observe
that we can check whether a Clifford path sum in normal form represents the
identity transformation in polynomial time. ∎

It is now straightforward to compute a circuit implementing a (unitary)
Clifford path sum from its normalized form. If we decompose $f$, $L$, and $Q$
as $f(\vec{x},\vec{y})=f_{x}(\vec{x})+f_{y}(\vec{y})+\vec{b}$,
$L(\vec{x},\vec{y})=L_{x}(\vec{x})+L_{y}(\vec{y})$, and
$Q(\vec{x},\vec{y})=Q_{x}(\vec{x})+Q_{y}(\vec{y})+\sum_{i=1}^{k}y_{i}R_{i}(\vec{x})$
then the normal form can be written as the following sequence of
transformations:

$\displaystyle\ket{\vec{x}}$
$\displaystyle\mapsto\omega^{l}i^{L_{x}(\vec{x})}(-1)^{Q_{x}(\vec{x})}\ket{\vec{x}}$
$\displaystyle\ket{\vec{x}}$
$\displaystyle\mapsto\ket{R(\vec{x})}\ket{f_{x}(\vec{x})}$
$\displaystyle\ket{R(\vec{x})}\ket{f_{x}(\vec{x})}$
$\displaystyle\mapsto\frac{1}{\sqrt{2^{k}}}\sum_{\vec{y}\in\mathbb{Z}_{2}^{k}}(-1)^{\sum_{i}y_{i}R_{i}(\vec{x})}\ket{\vec{y}}\ket{f_{x}(\vec{x})}$
$\displaystyle\ket{\vec{y}}\ket{f_{x}(\vec{x})}$
$\displaystyle\mapsto\ket{\vec{y}}\ket{f_{x}(\vec{x})+f_{y}(\vec{y})+\vec{b}}$
$\displaystyle\ket{\vec{y}}\ket{f(\vec{x},\vec{y})}$ $\displaystyle\mapsto
i^{L_{y}(\vec{y})}(-1)^{Q_{y}(\vec{y})}\ket{\vec{y}}\ket{f(\vec{x},\vec{y})}$

This gives a circuit of the form $U(\textsc{h}^{\otimes
k}\otimes\textsc{i}_{n-k})V$ where $U$ and $V$ are generalized permutations
contained in the Clifford group. Moreover,
$\ket{\vec{x}}\mapsto\ket{R(\vec{x})}\ket{f_{x}(\vec{x})}$ is the only
operator which may be non-unitary, and in particular is unitary if and only if
$\Psi$ is. Note that the unitarity of $\Psi$ hence forces $\\{R_{i}\\}$ to be
linearly independent and for $R_{i}$ to be non-zero. This is summarized in
Algorithm 1.

Algorithm 1 Clifford synthesis algorithm

  1. 1.

Normalize $\ket{\Psi}$ in the form
$\frac{\omega^{l}}{\sqrt{2^{k}}}\sum_{\vec{y}\in\mathbb{Z}_{2}^{k}}i^{L(\vec{x},\vec{y})}(-1)^{Q(\vec{x},\vec{y})}\ket{\vec{y}}\otimes\ket{f(\vec{x},\vec{y})}$
up to qubit reordering.

  2. 2.

Decompose $f$, $L$, and $Q$ as
$f(\vec{x},\vec{y})=f_{x}(\vec{x})+f_{y}(\vec{y})+\vec{b}$,
$L(\vec{x},\vec{y})=L_{x}(\vec{x})+L_{y}(\vec{y})$ and
$Q(\vec{x},\vec{y})=Q_{x}(\vec{x})+Q_{y}(\vec{y})+\sum_{i}y_{i}R_{i}(\vec{x})$
where each $R_{i}$ is linear.

  3. 3.

Synthesize circuits for the following linear transformations:

     * •

$D\ket{\vec{x}}=i^{L_{x}(\vec{x})}(-1)^{Q_{x}(\vec{x})}\ket{\vec{x}}$

     * •

$U\ket{\vec{x}}=\ket{R(\vec{x})}\ket{f_{x}(\vec{x})}$

     * •

$V\ket{\vec{y}}\ket{f_{x}(\vec{x})}=\ket{\vec{y}}\ket{f_{x}(\vec{x})+f_{y}(\vec{y})+\vec{b}}$

     * •

$P\ket{\vec{y}}\ket{f(\vec{x},\vec{y})}=i^{L_{y}(\vec{y})}(-1)^{Q_{y}(\vec{y})}\ket{\vec{y}}\ket{f(\vec{x},\vec{y})}$

  4. 4.

Return $\omega^{l}PV(\textsc{h}^{\otimes k}\otimes\textsc{i}_{n-k})UD$ with
qubits appropriately reordered.

######  Theorem 4.8.

Let $\Psi:\mathbb{C}^{2^{n}}\rightarrow\mathbb{C}^{2^{n}}$ be expressed as a
Clifford path sum. If $\Psi$ is unitary, then Algorithm 1 produces a circuit
over $\\{\omega,\textsc{cnot},\textsc{x},\textsc{cz},\textsc{s},\textsc{h}\\}$
implementing $\Psi$ in time polynomial in the size of the expression.
Moreover, this circuit can be written up to global phase as an $8$-stage
circuit of the form

$\textsc{s}\cdot\textsc{cz}\cdot\textsc{cnot}\cdot\textsc{h}\cdot\textsc{cnot}\cdot\textsc{x}\cdot\textsc{cz}\cdot\textsc{s}$

###### Proof.

That $\Psi=\omega^{l}PV(\textsc{h}^{\otimes k}\otimes\textsc{i}_{n-k})UD$
follows by an easy calculation.

By Proposition 4.5, $\Psi$ can be written up to a permutation of qubits in
normal form in polynomial time. Since $L_{x}$ and $L_{y}$ are linear, and
$Q_{x}$ and $Q_{y}$ are pure quadratic, $D$ and $P$ can each be synthesized
using a single stage each of s and cz gates — one $\textsc{s}^{m}$ gate for
each non-zero term of $L_{\\{x,y\\}}$ and one cz gate for each non-zero term
of $Q_{\\{x,y\\}}$. Likewise, since $f_{y}(\vec{y})$ is linear, $V$ can be
synthesized in time polynomial in $n$ using a single stage each of cnot and x
gates — one gate for each non-zero entry of $f_{y}(\vec{y})$ and $\vec{b}$.
Finally, $U\ket{\vec{x}}=\ket{R(\vec{x})}\otimes\ket{f_{x}(\vec{x})}$ can be
synthesized over $\\{\textsc{cnot}\\}$ in polynomial time using Gaussian
elimination if and only if $U$ is invertible. Moreover, since

$U=\omega^{-l}(\textsc{h}^{\otimes
k}\otimes\textsc{i}_{n-k})V^{\dagger}P^{\dagger}\Psi D^{\dagger},$

it follows that $U$ is invertible if and only if $\Psi$ is unitary. ∎

We give a diagrammatic presentation of Theorem 4.8 showing the circuit
schematically below.

$\Qcircuit@C=.5em@R=.7em{\lstick{x_{1}}&\qw\gate{S^{L_{x}(x_{1})}}\multigate{5}{(-1)^{Q_{x}(\vec{x})}}\multigate{5}{U}\gate{H}\ctrl{3}\qw\qw\multigate{2}{(-1)^{Q_{y}(\vec{y})}}\gate{S^{L_{y}(y_{1})}}\qw\rstick{y_{1}}\qw\\\
\vdots\rstick{\;\;\;\;\ddots}\vdots\\\
\lstick{x_{k}}\qw\gate{S^{L_{x}(x_{k})}}\ghost{(-1)^{Q_{x}(\vec{x})}}\ghost{U}\gate{H}\qw\ctrl{1}\qw\ghost{(-1)^{Q_{y}(\vec{y})}}\gate{S^{L_{y}(y_{k})}}\qw\rstick{y_{k}}\qw\\\
\lstick{x_{k+1}}\qw\gate{S^{L_{x}(x_{k+1})}}\ghost{(-1)^{Q_{x}(\vec{x})}}\ghost{U}\qw\multigate{2}{X^{f_{y}(y_{1})}}\multigate{2}{X^{f_{y}(y_{k})}}\gate{X^{b_{1}}}\qw\qw\qw\rstick{f_{1}(\vec{x},\vec{y})}\qw\\\
\vdots\vdots\\\
\lstick{x_{n}}\qw\gate{S^{L_{x}(x_{n})}}\ghost{(-1)^{Q_{x}(\vec{x})}}\ghost{U}\qw\ghost{X^{f_{y}(y_{1})}}\ghost{X^{f_{y}(y_{k})}}\gate{X^{b_{n-k}}}\qw\qw\qw\rstick{f_{n-k}(\vec{x},\vec{y})}\qw}$

### Discussion

In [23] a $7$ stage decomposition of the Clifford group of the form
$\textsc{s}\cdot\textsc{cz}\cdot\textsc{c}\cdot\textsc{h}\cdot\textsc{c}\cdot\textsc{cz}\cdot\textsc{s}$
was given, where c is circuit implementing an affine permutation. As affine
permutations require both cnot and x gates to implement without ancillas — and
moreover x can not be written in the form
$\textsc{s}\cdot\textsc{cz}\cdot\textsc{cnot}\cdot\textsc{h}\cdot\textsc{cnot}\cdot\textsc{cz}\cdot\textsc{s}$
— our projective decomposition reduces the equivalent $9$-stage projective
decomposition of [23] to $8$ stages.

It can also be observed that with a minor modification, Algorithm 1 suffices
to synthesize Clifford circuits with ancillas, including circuits for
preparing stabilizer states. In particular, if
$\Psi:\mathbb{C}^{2^{m}}\rightarrow\mathbb{C}^{2^{n}}$ is an isometric
Clifford path sum with $m\leq n$, the only modification needed is in the
synthesis of $U\ket{\vec{x}}=\ket{R(\vec{x})}\otimes\ket{f_{x}(\vec{x})}$. If
indeed $m\leq n$, then a Clifford circuit with ancillas exists and can be
synthesized if and only if $\\{R_{i}\\}\cup\\{(f_{x})_{i}\\}$ contains $m$
linearly independent (row) vectors. This produces a $5$-stage circuit of the
form
$\textsc{h}\cdot\textsc{cnot}\cdot\textsc{x}\cdot\textsc{cz}\cdot\textsc{s}$
for the preparation of an arbitrary stabilizer state up to global phase. This
stabilizer state decomposition was previously given in [26].

##  5 General synthesis

We now consider the more challenging problem of synthesizing a unitary circuit
from an arbitrary path sum. Our method attempts to iteratively reduce the
number of summed variables in a path sum by alternately applying generalized
permutations and Hadamard gates to the symbolic state. Recall that a
_(unitary) generalized permutation_ is a permutation matrix whose nonzero
entries are elements of $\mathbb{T}=\\{z\in\mathbb{C}\mid|z|=1\\}$. The
generalized permutations are generated by the gates

$\Lambda_{k}(X):\ket{\vec{x}}\ket{y}\mapsto\ket{\vec{x}}\ket{y\oplus\prod_{i}x_{i}}\quad\mbox{
and }\quad\Lambda_{k}(R_{Z}(\theta)):\ket{\vec{x}}\mapsto e^{2\pi
i\theta\prod_{i}x_{i}}\ket{\vec{x}}.$

Together with the Hadamard gate this forms an exactly universal set as it
includes every single-qubit unitary along with the cnot gate.

The following fact forms the basis of our synthesis algorithm. It gives a
condition on a path sum which allows a summed variable to be eliminated by
multiplication with a Hadamard gate.

######  Proposition 5.1.

Let $\Psi:\mathbb{C}^{2^{m}}\rightarrow\mathbb{C}^{2^{n}}$ be a linear
operator where

$\hskip
60.00009pt\Psi\ket{\vec{x}}=\mathcal{N}\sum_{z\in\mathbb{Z}_{2}}\sum_{\vec{y}\in\mathbb{Z}_{2}^{k}}(-1)^{zQ(\vec{x},\vec{y})}e^{2\pi
iP(\vec{x},\vec{y})}\ket{z}\otimes\ket{f(\vec{x},\vec{y})}.$

Then
$(\textsc{h}\otimes\textsc{i}_{n-1})\Psi\ket{\vec{x}}=\sqrt{2}\mathcal{N}\sum_{\vec{y}\in\mathbb{Z}_{2}^{k}}e^{2\pi
iP(\vec{x},\vec{y})}\ket{Q(\vec{x},\vec{y})}\otimes\ket{f(\vec{x},\vec{y})}.$

###### Proof.

By Equation 3, since
$(\textsc{h}\otimes\textsc{i}_{n-1})\Psi\ket{\vec{x}}=\frac{1}{\sqrt{2}}\mathcal{N}\sum_{z}\sum_{\vec{y}}(-1)^{zQ(\vec{x},\vec{y})+zz^{\prime}}e^{2\pi
iP(\vec{x},\vec{y})}\ket{z^{\prime}}\otimes\ket{f(\vec{x},\vec{y})}$ ∎

Note that Proposition 5.1 is essentially an inversion of the h gate,
$\textsc{h}^{\dagger}:\sum_{z}(-1)^{xz}\ket{z}\mapsto\ket{x}$. We say that a
variable $z$ is _reducible_ in the path sum $\ket{\Psi}$ if $\ket{\Psi}$ is in
the form of Proposition 5.1.

######  Definition 5.2 (Reducible).

A variable $z$ is _reducible_ in an expression of
$\Psi:\mathbb{C}^{2^{m}}\rightarrow\mathbb{C}^{2^{n}}$ if, up to qubit
reordering, it has the form

$\hskip
60.00009pt\Psi\ket{\vec{x}}=\mathcal{N}\sum_{z\in\mathbb{Z}_{2}}\sum_{\vec{y}\in\mathbb{Z}_{2}^{k}}(-1)^{zQ(\vec{x},\vec{y})}e^{2\pi
iP(\vec{x},\vec{y})}\ket{z}\otimes\ket{f(\vec{x},\vec{y})}.$

At a high level, our algorithm proceeds by attempting to synthesize a
generalized permutation which will leave some path variable reducible. If the
process terminates with remaining summed variables, or an unsynthesizeable
ground term $e^{2\pi iP(\vec{x})}\ket{f(\vec{x})}$, the algorithm fails to
produce a circuit. Algorithm 2 gives the high-level algorithm in pseudo-code.

Algorithm 2 General path sum synthesis algorithm

  1. 1.

Normalize $\ket{\Psi}$ using Equations 2, 3 and 4

  2. 2.

For each remaining path variable $y$ in $\ket{\Psi}$

    1. (a)

If there exists a generalized permutation $U$ such that $y$ is reducible in
$U^{\dagger}\ket{\Psi}$,

      1. i.

$\ket{\Psi}\leftarrow(\textsc{h}\otimes\textsc{i}_{n-1})U^{\dagger}\ket{\Psi}$

      2. ii.

Emit $U(\textsc{h}\otimes\textsc{i}_{n-1})$

      3. iii.

Return to step $1$

  3. 3.

If path variables remain or $\Psi$ is non-unitary, fail. Otherwise, synthesize
and emit $\Psi^{\dagger}$.

Finding such a generalized permutation is highly non-trivial. Our method
applies a series of symbolic simplifications, corresponding to
$\Lambda_{k}(X)$ and $\Lambda_{k}(R_{Z}(\theta))$ gates, to the term $e^{2\pi
iP(\vec{x},\vec{y})}\ket{f(\vec{x},\vec{y})}$. If these simplifications fail
to leave any variable reducible, we fall back to an exponential-time procedure
aimed at computing a substitution of the form in Equation 5 which will make
some variable reducible. These heuristics are described in Appendix A.

##  6 Experiments

To test the performance and utility of our synthesis methods, we implemented
Algorithms 1 and 2 in the feynman111Available at
https://github.com/meamy/feynman. software package. In this section, we
briefly detail our investigations into applications to the optimization and
decompilation of circuits, and to specification-based synthesis. All Clifford
circuits synthesized have been checked for correctness using the method of
[2]. For Algorithm 2, as the method of [2] often fails to verify circuits
extracted using Equation 5, we instead validated correctness of our synthesis
procedure by verifying the individual synthesis steps each on 1000 randomly
generated unitary path sums extracted from Clifford+$T$ circuits. Table 1
gives some statistics from experiments re-synthesizing random circuits.

| $n$ | # gates | # circuits | avg. time (s) | avg. change (+/-) | success
---|---|---|---|---|---|---
Clifford | 20 | 500 | 1000 | 0.137 | +19.2% | –
| 20 | 1000 | 1000 | 0.481 | -12.9% | –
| 50 | 500 | 1000 | 0.264 | +90.7% | –
| 50 | 1000 | 1000 | 1.518 | +129.1% | –
Clifford+$T$ | 20 | 100 | 1000 | 0.010 | +48.9% | 99.9%
| 20 | 200 | 1000 | 0.045 | +93.7% | 94.9%
| 20 | 300 | 1000 | 0.097 | +115.9% | 74.7%
| 50 | 100 | 1000 | 0.016 | +33.5% | 100.0%
| 50 | 200 | 1000 | 0.044 | +49.0% | 100.0%
| 50 | 300 | 1000 | 0.104 | +79.4% | 99.6%
Table 1: Re-synthesis results for randomly generated circuits on $n$ qubits.
Avg. change gives the average percent increase (+) or decrease (-) in gate
count.

### Circuit optimization

One of the key factors in phase folding optimizations [4, 25] is the placement
of Hadamard gates. It was shown in [5] that the $T$-count in a Clifford+$T$
circuit can be upper bounded by $O(hn^{2})$, where $h$ is the number of
Hadamard layers in the circuit. As our Clifford synthesis algorithm produces
circuits with just a single layer of Hadamard gates, it is natural to ask
whether we can optimize $T$-count by reducing the number of Hadamard layers in
Clifford+$T$ circuits.

We implemented a Clifford sub-circuit normalization method (the -clifford pass
in feynopt) using Algorithm 1 to re-synthesize simple greedily chosen Clifford
sub-circuits. We tested the effect on $T$-count optimization by applying
Clifford normalization together with phase folding and compared it against
[18] on the benchmark set of [4]. In all but 4 benchmarks, the same $T$-count
was achieved by normalizing greedily chosen Clifford sub-circuits and applying
phase polynomial optimizations. In two of those cases, qcla-com7 and csla-
mux3, our method produced lower $T$-count circuits — $94$ (down from $95$) and
$60$ (down from $62$), respectively. For the other two cases, ham15-med and
adder8, our method produced worse results — $230$ (up from $212$) and $215$
(up from $173$), respectively.

More broadly, we might expect to be able to optimize a circuit by
resynthesizing its simplified path sum using the general synthesis algorithm
Algorithm 2. This is often effective when the path sum is simple, as in the
resynthesized circuits corresponding to sub-circuits of the adder8 benchmark,
but as the path sum becomes increasingly complex extraction typically performs
worse than human designs. We leave it as an avenue for future work to make
symbolic synthesis practical for circuit optimization, and in particular to
develop effective peephole optimization procedures.

$\Qcircuit@C=.5em@R=.5em@!R{&\qw\ctrl{2}\qw\ctrl{2}\qw\ctrl{2}\qw\qw\\\
\qw\ctrl{1}\targ\ctrl{1}\targ\ctrl{1}\qw\qw\\\
\qw\targ\ctrl{-1}\targ\ctrl{-1}\targ\qw\qw}\raisebox{-13.00005pt}{$\quad\longrightarrow\quad$}\Qcircuit@C=.5em@R=.5em@!R{&\qw\ctrl{1}\qw\qw\\\
\qw\targ\qw\qw\\\ \qw\ctrl{-1}\qw\qw}$

$\Qcircuit@C=.5em@R=.5em@!R{&\qw\ctrl{2}\qw\ctrl{2}\qw\ctrl{2}\qw\qw\\\
\qw\ctrl{1}\qw\ctrl{1}\qw\ctrl{1}\qw\qw\\\
\qw\targ\ctrl{1}\targ\ctrl{1}\targ\qw\qw\\\
\qw\qw\targ\qw\targ\qw\qw\qw}\raisebox{-20.00003pt}{$\quad\longrightarrow\quad$}\Qcircuit@C=.5em@R=.5em@!R{&\qw\qw\ctrl{2}\qw\qw\qw\\\
\qw\qw\ctrl{1}\qw\qw\qw\\\ \qw\ctrl{1}\targ\ctrl{1}\qw\qw\\\
\qw\targ\qw\targ\qw\qw}$

### Decompilation

An interesting application of our symbolic synthesis algorithm is to the
_decompilation_ of quantum circuits. Classically, decompilation is the process
of translating a program in a low-level language to equivalent high-level
source code, typically used for reverse engineering or recompilation. As the
gate set targeted by Algorithm 2 is quite high-level, in many cases it can be
used to effectively decompile lower-level circuits. This decompilation can
potentially help developers to examine the high-level structure of a low-level
circuit, and also allow optimizations targeting higher level gate sets to be
performed on circuits written over low-level gate sets, such as Clifford+$T$.
Below we give some examples of standard circuits from the literature
decompiled using Algorithm 2. The decompiler can be accessed with the
-decompile option in feynopt.

$\Qcircuit<EMAIL_ADDRESS>\qw\gate{T}\targ\ctrl{1}\qw\gate{T^{\dagger}}\ctrl{-1}\ctrl{1}\qw\targ\qw\qw\\\
\qw\gate{H}\gate{T}\targ\ctrl{-2}\gate{T}\qw\targ\ctrl{-2}\gate{H}\qw\qw}\raisebox{-15.29999pt}{$\quad\longrightarrow\quad$}\Qcircuit@C=.5em@R=.8em@!R{&\qw\ctrl{1}\qw\qw\\\
\qw\ctrl{1}\qw\qw\\\ \qw\targ\qw\qw}$

$\Qcircuit<EMAIL_ADDRESS>\qw\gate{T}\targ\gate{T^{\dagger}}\targ\qw}\raisebox{-9.00002pt}{$\quad\longrightarrow\quad$}\Qcircuit@C=.5em@R=.2em@!R{&\qw\ctrl{1}\qw\qw\\\
\qw\gate{S}\qw\qw}$

$\Qcircuit@C=.5em@R=.2em@!R{&\ctrl{3}\qw\ctrl{3}\qw\qw\\\
\ctrl{2}\qw\ctrl{2}\qw\qw\\\ \qw\ctrl{2}\qw\ctrl{2}\qw\\\
\targ\ctrl{1}\targ\ctrl{1}\qw\\\
\qw\targ\qw\targ\qw}\raisebox{-20.00003pt}{$\quad\longrightarrow\quad$}\Qcircuit@C=.5em@R=.2em@!R{&\qw\ctrl{4}\qw\qw\\\
\qw\ctrl{3}\qw\qw\\\ \qw\ctrl{2}\qw\qw\\\ \qw\qw\qw\qw\\\ \qw\targ\qw\qw}$

$\Qcircuit@C=.5em@R=.05em@!R{&\qw\qw\qw\qw\ctrl{3}\qw\qw\qw\qw\qw\\\
\qw\qw\qw\qw\ctrl{2}\qw\qw\qw\qw\qw\\\
\qw\qw\ctrl{1}\qw\qw\qw\ctrl{1}\qw\qw\qw\\\
\gate{H}\gate{T}\targ\gate{T^{\dagger}}\gate{iX}\gate{T}\targ\gate{T^{\dagger}}\gate{H}\qw}\raisebox{-20.70006pt}{$\quad\longrightarrow\quad$}\Qcircuit@C=.5em@R=.1em@!R{&\qw\ctrl{3}\ctrl{3}\ctrl{1}\ctrl{3}\qw\qw\\\
\qw\ctrl{2}\ctrl{2}\gate{S^{\dagger}}\ctrl{2}\qw\qw\\\
\qw\ctrl{1}\qw\qw\ctrl{1}\qw\qw\\\
\qw\ctrl{0}\ctrl{0}\gate{S^{\dagger}}\targ\gate{S}\qw}$

The bottom right circuit above is a relative phase Toffoli gate implementation
taken from [6]. The utility of decompilation is apparant here, as both the
fact that it implements a Toffoli up to phase and the exact form of the
relative phase can be readily observed from the decompiled circuit.

### Specification-based synthesis

In [2] it was noted that path sums offer a convenient form of logical
specification for many quantum computations, being very close to the
“textbook” specification. Algorithm 2 gives a method of synthesizing a circuit
directly from such a specification. Such specifications include not only
classical reversible functions such as
$\ket{x_{1}x_{2}x_{3}}\mapsto\ket{x_{1}x_{2}(x_{3}\oplus x_{1}x_{2})}$, which
can be synthesized by existing reversible circuit synthesis methods, but also
classical functions “in the phase,” up to relative phases, or inside
superpositions. We illustrate this by using Algorithm 2 to synthesize the
quantum Fourier transform.

Recall that the $n$-qubit quantum fourier transform can be expressed as
$QFT_{n}\ket{\vec{x}}=\frac{1}{\sqrt{2^{n}}}\sum_{\vec{y}\in\mathbb{Z}_{2}^{n}}\omega_{2^{n}}^{\vec{x}\vec{y}}\ket{\vec{y}}$
where $\vec{x}\vec{y}$ is the integer product of $\vec{x}$ and $\vec{y}$. In
the $3$ qubit case, expanding the integer multiplication to a multilinear
polynomial we have

$QFT_{3}\ket{x_{1}x_{2}x_{3}}=\frac{1}{\sqrt{2^{3}}}\sum_{y_{1},y_{2},y_{3}}\omega^{x_{3}y_{3}}i^{x_{3}y_{2}+x_{2}y_{3}}(-1)^{x_{3}y_{1}+x_{2}y_{2}+x_{1}y_{3}}\ket{y_{1}y_{2}y_{3}}$

where $y_{1}$ is reducible, and in particular

$(\textsc{h}\otimes\textsc{i}_{2})QFT_{3}\ket{x_{1}x_{2}x_{3}}=\frac{1}{\sqrt{2^{2}}}\sum_{y_{1},y_{2}}\omega^{x_{3}y_{3}}i^{x_{3}y_{2}+x_{2}y_{3}}(-1)^{x_{2}y_{2}+x_{1}y_{3}}\ket{x_{3}y_{2}y_{3}}.$

While neither of $y_{2}$ or $y_{3}$ are reducible above, the
$\omega^{x_{3}y_{3}}$ and $i^{x_{3}y_{2}}$ terms can be eliminated by applying
controlled-$\textsc{t}^{\dagger}$ and -$\textsc{s}^{\dagger}$ gates,
respectively, leaving $y_{2}$ reducible:

$(\Lambda(\textsc{s}^{\dagger})\otimes\textsc{i})(\textsc{swap}\otimes\textsc{i})(\textsc{i}\otimes\Lambda(\textsc{t}^{\dagger}))(\textsc{swap}\otimes\textsc{i})(\textsc{h}\otimes\textsc{i}_{2})QFT_{3}\ket{x_{1}x_{2}x_{3}}=\frac{1}{\sqrt{2^{2}}}\sum_{y_{1},y_{2}}i^{x_{2}y_{3}}(-1)^{x_{2}y_{2}+x_{1}y_{3}}\ket{x_{3}y_{2}y_{3}}.$

After eliminating $y_{2}$, the process repeats for $y_{1}$, leaving a final
permutation to be synthesized.

A $5$ qubit $QFT$ circuit synthesized with our implementation is shown
verbatim below, where $R_{k}:=R_{Z}(1/2^{k})$. We were able to synthesize
instances on up to 50 qubits in just seconds on a desktop computer.

$\Qcircuit@C=.5em@R=.05em@!R{&\qw\link{4}{-2}\qw\qw\qw\qw\qw\qw\qw\qw\qw\qw\qw\qw\qw\ctrl{4}\ctrl{3}\ctrl{2}\ctrl{1}\gate{H}\qw\\\
\qw\qw\qw\link{2}{-1}\qw\qw\qw\qw\qw\qw\qw\qw\ctrl{3}\ctrl{2}\ctrl{1}\gate{H}\qw\qw\qw\measure{R_{2}}\qw\qw\\\
\qw\qw\qw\qw\qw\qw\qw\qw\qw\ctrl{2}\ctrl{1}\gate{H}\qw\qw\measure{R_{2}}\qw\qw\qw\measure{R_{3}}\qw\qw\qw\\\
\qw\qw\qw\link{-2}{-1}\qw\qw\qw\ctrl{1}\gate{H}\qw\measure{R_{2}}\qw\qw\measure{R_{3}}\qw\qw\qw\measure{R_{4}}\qw\qw\qw\qw\\\
\qw\link{-4}{-2}\qw\qw\qw\gate{H}\measure{R_{2}}\qw\measure{R_{3}}\qw\qw\measure{R_{4}}\qw\qw\qw\measure{R_{5}}\qw\qw\qw\qw\qw}$

##  7 Conclusion

In this paper we looked at the problem of synthesis of unitary quantum
circuits from symbolic expressions as sums-over-paths. We showed that we
cannot hope to efficiently synthesize a circuit from a general path sum
efficiently, as the problem of checking whether there the path sum represents
a unitary transformation is itself co-NP-hard. A stronger result was given
recently for the extraction of ZX-diagrams [15], though their work did not
address the complexity of the potentially easier problem of unitarity testing.
The problem of unitarity testing for ZX-diagrams is likewise believed to be
intractable [30].

For the restricted case of Clifford operations, we showed that a circuit can
be synthesized efficiently in the form $C_{1}HC_{2}$ for Hadamard-free
Clifford circuits $C_{1}$ and $C_{2}$. For more general path sums we gave a
heuristic based on symbolic manipulation and simplification of the sum. We
experimentally validated our method, showing that most path sums corresponding
to unitary transformations can in fact be synthesized. Moreover, our algorithm
is capable of producing natural, high-level circuit designs for some path
sums, including the quantum Fourier transform. It remains as a course of
future work however to develop a complete synthesis algorithm, as well as to
reduce the cost of synthesized circuits.

## References

  * [1] S. Aaronson.  Quantum computing, postselection, and probabilistic polynomial-time.  Proceedings of the Royal Society A, 461(2063):3473–3482, 2005.
  * [2] M. Amy.  Towards large-scale functional verification of universal quantum circuits.  In Proceedings of the 15th International Conference on Quantum Physics and Logic, QPL’18, pages 1–21, 2018.
  * [3] M. Amy, J. Chen, and N. J. Ross.  A Finite Presentation of CNOT-Dihedral Operators.  In Proceedings of the 14th International Conference on Quantum Physics and Logic, QPL’17, pages 84–97, 2017.
  * [4] M. Amy, D. Maslov, and M. Mosca.  Polynomial-Time T-depth optimization of Clifford+T circuits via matroid partitioning.  IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 33(10):1476–1489, 2014.
  * [5] M. Amy and M. Mosca.  T-count optimization and Reed-Muller codes.  IEEE Transactions on Information Theory, 65(8):4771–4784, 2019\.
  * [6] M. Amy and N. J. Ross.  The phase/state duality in reversible circuit design.  Physical Review A, 104:052602, 2021.
  * [7] M. Backens and A. Kissinger.  ZH: A complete graphical calculus for quantum computations involving classical non-linearity.  In Proceedings of the 15th International Conference on Quantum Physics and Logic, QPL’18, pages 23–42, 2018.
  * [8] M. Backens, H. Miller-Bakewell, G. de Felice, L. Lobski, and J. van de Wetering.  There and back again: A circuit extraction tale.  Quantum, 5:421, Mar. 2021.
  * [9] D. Bacon, W. van Dam, and A. Russell.  Analyzing algebraic quantum circuits using exponential sums, 2008.
  * [10] X. Bian and P. Selinger.  Generators and relations for $U_{n}(\mathbb{Z}[1/2,i])$.  In Proceedings of the 18th International Conference on Quantum Physics and Logic, QPL’21, pages 145–164, 2021.
  * [11] S. Bravyi and D. L. Maslov.  Hadamard-free circuits expose the structure of the Clifford group.  IEEE Transactions on Information Theory, 67:4546–4563, 2021.
  * [12] B. Coecke and R. Duncan.  Interacting quantum observables.  In Proceeds of the The 35th International Colloquium on Automata, Languages and Programming, ICALP’08, pages 298–310, Berlin, Heidelberg, 2008. Springer Berlin Heidelberg.
  * [13] C. M. Dawson, A. P. Hines, D. Mortimer, H. L. Haselgrove, M. A. Nielsen, and T. J. Osborne.  Quantum computing and polynomial equations over the finite field $\mathbb{Z}_{2}$.  Quantum Information and Computation, 5(2):102–112, 2005.
  * [14] N. de Beaudrap and S. Herbert.  Fast stabiliser simulation with quadratic form expansions.  Available from arXiv:2109.08629, Sep. 2021.
  * [15] N. de Beaudrap, A. Kissinger, and J. van de Wetering.  Circuit Extraction for ZX-diagrams can be #P-hard.  Available from arXiv:2202.09194, 2022.
  * [16] J. Dehaene and B. De Moor.  Clifford group, stabilizer states, and linear and quadratic operations over gf(2).  Phys. Rev. A, 68:042318, Oct 2003.
  * [17] R. Duncan, A. Kissinger, S. Perdrix, and J. van de Wetering.  Graph-theoretic Simplification of Quantum Circuits with the ZX-calculus.  Quantum, 4:279, June 2020.
  * [18] A. Kissinger and J. van de Wetering.  Reducing the number of non-clifford gates in quantum circuits.  Phys. Rev. A, 102:022406, Aug 2020.
  * [19] D. E. Koh, M. D. Penney, and R. W. Spekkens.  Computing quopit Clifford circuit amplitudes by the sum-over-paths technique.  Quantum Information and Computation, 17(13&14):1081–1095, 2017\.
  * [20] L. Lemonnier, J. van de Wetering, and A. Kissinger.  Hypergraph simplification: Linking the path-sum approach to the ZH-calculus.  In Proceedings of the 17th International Conference on Quantum Physics and Logic, QPL’20, 2020.
  * [21] S. M. Li, N. J. Ross, and P. Selinger.  Generators and relations for the group $O_{n}(\mathbb{Z}[1/2])$.  In Proceedings of the 18th International Conference on Quantum Physics and Logic, QPL’21, pages 210–264, 2021.
  * [22] J. Makary, N. J. Ross, and P. Selinger.  Generators and relations for real stabilizer operators.  In Proceedings of the 18th International Conference on Quantum Physics and Logic, QPL’21, pages 14–36, 2021.
  * [23] D. L. Maslov and M. Roetteler.  Shorter stabilizer circuits via Bruhat decomposition and quantum circuit transformations.  IEEE Transactions on Information Theory, 64:4729–4738, 2018.
  * [24] A. Montanaro.  Quantum circuits and low-degree polynomials over ${{\mathbb{F}}_{\mathsf{2}}}$.  Journal of Physics A: Mathematical and Theoretical, 50(8):084002, 2017.
  * [25] Y. Nam, N. J. Ross, Y. Su, A. M. Childs, and D. Maslov.  Automated Optimization of Large Quantum Circuits with Continuous Parameters.  npj Quantum Information, 4(1):23, 2018.
  * [26] M. V. d. Nest.  Classical simulation of quantum computation,the gottesman-knill theorem, and slightly beyond.  Quantum Information and Computation, 10(3&4):0258–0271, 2010.
  * [27] T. Rudolph.  Simple encoding of a quantum circuit amplitude as a matrix permanent.  Physical Review A, 80:054302, Nov 2009.
  * [28] P. Selinger.  Generators and relations for n-qubit Clifford operators.  Logical Methods in Computer Science, Volume 11, Issue 2, 2015\.
  * [29] G. S. Tseitin.  On the complexity of derivation in propositional calculus.  In Automation of reasoning, pages 466–483. Springer, 1983.
  * [30] J. van de Wetering, 2021.  Private communication.
  * [31] R. Vilmart.  The Structure of Sum-Over-Paths, its Consequences, and Completeness for Clifford.  In Foundations of Software Science and Computation Structures, volume 12650 of FoSSaCS’21, pages 531–550, Luxembourg, Luxembourg, 2021\.

##  Appendix A Finding generalized permutations

In this appendix we detail our method for finding a generalized permutation in
step 2.(a) of Algorithm 2.

Compared to Clifford operators, simplification via Proposition 2.9 may not
always leave the path sum in a reducible state. For instance, the path sum
expression below, corresponding to a unitary transformation, is fully reduced
with respect to Equations 2, 3 and 4:

$\frac{1}{\sqrt{2^{2}}}\sum_{y_{1},y_{2}}i^{x_{2}y_{1}-x_{2}y_{2}}(-1)^{x_{1}y_{1}+x_{1}y_{2}+x_{2}y_{1}y_{2}}\ket{y_{1}}\ket{y_{2}}$

However, neither $y_{1}$ nor $y_{2}$ are reducible due to the quadratic terms
$x_{2}y_{1}$ and $x_{2}y_{2}$ in the exponent of $i$. At the moment, it is
unclear how to proceed symbolically to find a generalized permutation that
will make either path variable reducible in the above expression.

Our heuristic method of producing a generalized permutation proceeds in
increasingly costly circuit stages in an attempt to synthesize as efficient
circuits as possible. Rather than attempt to synthesize a distinct generalized
permutation for every path variable $y$ as described in Algorithm 2, we first
apply a sequence of simplification stages generically to both reduce the
redundant synthesis work, and produce simpler circuits in practice. The
sequence of stages is given in Algorithm 3, and the individual synthesis steps
are described in detail below.

Algorithm 3 Generalized permutation synthesis heuristic

  1. 1.

Apply affine simplifications to the output state $\ket{f(\vec{x},\vec{y})}$

  2. 2.

Apply non-linear simplifications to the phase $e^{2\pi iP(\vec{x},\vec{y})}$

  3. 3.

Apply non-linear simplifications to the output state
$\ket{f^{\prime}(\vec{x},\vec{y})}$

  4. 4.

Apply non-linear simplifications to the phase $e^{2\pi
iP^{\prime}(\vec{x},\vec{y})}$

  5. 5.

If no path variable is reducible, attempt degree reduction on each variable

### Affine simplifications

As $X$ and $CNOT$ gates are relatively inexpensive, the first stage of our
generalize permutation synthesis attempts to simplify the output
$\ket{f(\vec{x},\vec{y})}$ of the path sum as much as possible using only
these affine transformations. In order to reduce the number of high-degree
terms, which would otherwise require expensive multiply-controlled Toffoli
gates, we perform affine simplifications on a _linearization_ of $f$.
Specifically, we write each $f_{i}(\vec{x},\vec{y})$ as a sparse vector
$\vec{u_{i}}\in\mathbb{Z}_{2}^{2^{n+k}}$ using reverse lexociographic order
for the encoding of monomials, then set
$A=\begin{bmatrix}u_{1}\;u_{2}\;\dots\;u_{n}\end{bmatrix}^{T}$ and use
Gaussian elimination to compute a sequence of $CNOT$ gates reducing $A$ to
echelon form. The example below illustrates our method.

######  Example A.1.

Consider the path sum $\ket{x_{1}}\ket{x_{2}}\ket{x_{3}\oplus
x_{1}x_{2}}\ket{x_{4}\oplus x_{1}x_{2}}$. This could naturally by synthesized
using two non-linear Toffolis to eliminate the $x_{1}x_{2}$ terms from the
third and forth qubits. The resulting circuit is shown below:

$\Qcircuit@C=.5em@R=.5em@!R{\lstick{x_{1}}&\ctrl{2}\ctrl{3}\rstick{x_{1}}\qw\\\
\lstick{x_{2}}\ctrl{1}\ctrl{2}\rstick{x_{2}}\qw\\\
\lstick{x_{3}}\targ\qw\rstick{x_{3}\oplus x_{1}x_{2}}\qw\\\
\lstick{x_{4}}\qw\targ\rstick{x_{4}\oplus x_{1}x_{2}}\qw\\\ }$

Alternatively, we can write the output as a (sparse) linear system over all
monomials in $x_{1},x_{2},x_{3},x_{4}$ as shown below:

$\begin{matrix}&x_{1}x_{2}&x_{4}&x_{3}&x_{2}&x_{1}\\\ \hline\cr
x_{1}&0&0&0&0&1\\\ x_{2}&0&0&0&1&0\\\ x_{3}\oplus x_{1}x_{2}&1&0&1&0&0\\\
x_{4}\oplus x_{1}x_{2}&1&1&0&0&0\end{matrix}$

We use reverse lexicographic order so that reduction to echelon form will
prioritize the number of high degree terms. Reducing this to echelon form
results in a single $CNOT$ gate and reduces the state to
$\ket{x_{1}}\ket{x_{2}}\ket{x_{3}\oplus x_{1}x_{2}}\ket{x_{4}\oplus x_{3}}$.
Synthesizing this remaining transformation gives the overall circuit

$\Qcircuit@C=.5em@R=.5em@!R{\lstick{x_{1}}&\qw\ctrl{2}\qw\rstick{x_{1}}\qw\\\
\lstick{x_{2}}\qw\ctrl{1}\qw\rstick{x_{2}}\qw\\\
\lstick{x_{3}}\ctrl{1}\targ\ctrl{1}\rstick{x_{3}\oplus x_{1}x_{2}}\qw\\\
\lstick{x_{4}}\targ\qw\targ\rstick{x_{4}\oplus x_{1}x_{2}}\qw\\\ }$

### Phase simplifications

To reduce and simplify the number of terms in the phase $e^{2\pi
iP(\vec{x},\vec{y})}$ of a path sum controlled $R_{Z}$ gates with continuous
parameters are used. In particular, given an $n$-dimensional path sum $e^{2\pi
i\theta\prod_{i}x_{i}}\ket{\vec{x}}$, we can reduce the phase term by applying
a $\Lambda_{n}(R_{Z}(-\theta))$ gate, since

$\Lambda_{n}(R_{Z}(-\theta)):e^{2\pi
i\theta\prod_{i}x_{i}}\ket{\vec{x}}\mapsto\ket{\vec{x}}.$

As the output of the path sum is in some state $\ket{f(\vec{x},\vec{y})}$, to
apply the above rule we first need to apply a _change of frame_ by setting
$f_{i}(\vec{x},\vec{y})=z_{i}$ and writing the phase polynomial
$P(\vec{x},\vec{y})$ as $P^{\prime}(\vec{x},\vec{y},\vec{z})$. This is
achieved by, for each $f_{i}$, letting $l$ be the _largest_ (non-zero) degree
term of $f_{i}$ and substituting $l\leftarrow z_{i}\oplus l\oplus
f_{i}(\vec{x},\vec{y})$ in the path sum.

######  Example A.2.

Consider the irreducible path sum
$\frac{1}{\sqrt{2}}\sum_{y_{1}}\omega^{-x_{1}}i^{x_{1}y_{1}-x_{2}y_{1}}(-1)^{x_{1}x_{2}y_{1}}\ket{x_{1}\oplus
x_{2}}\ket{y_{1}}$. Substituting $[x_{2}\leftarrow z_{1}\oplus x_{1}$,
$y_{1}\leftarrow z_{2}]$ gives the re-framed path sum

$\omega^{-x_{1}}i^{-z_{1}z_{2}}(-1)^{x_{1}z_{2}}\ket{z_{1}}\ket{z_{2}}.$

Applying a controlled $S$ gate to eliminate the term $i^{-z_{1}z_{2}}$ and
rolling back the substitutions gives

$\omega^{-x_{1}}(-1)^{x_{1}y_{1}}\ket{x_{1}\oplus x_{2}}\ket{y_{1}}.$

The variable $y_{1}$ is now reducible, so we can finish synthesis by applying
a Hadamard to the second qubit, then synthesizing the final generalized
permutation $\ket{x_{1}x_{2}}\mapsto\omega^{-x_{1}}\ket{x_{1}\oplus
x_{2}}\ket{x_{1}}$. The resulting circuit is given below:

$\Qcircuit@C=.5em@R=.5em@!R{\lstick{x_{1}}&\qw\link{1}{-1}\qw\targ\qw\ctrl{1}\rstick{x_{1}\oplus
x_{2}}\qw\\\
\lstick{x_{2}}\qw\link{-1}{-1}\gate{T^{\dagger}}\ctrl{-1}\gate{H}\gate{S^{\dagger}}\rstick{y_{1}}\qw\\\
}$

In our implementation, we apply phase simplifications both before and after
non-linear simplifications in the state. This is so that we can effectively
utilize high degree terms in the state to simplify high degree terms in the
phase with phase gates on fewer qubits. The following example illustrates this
effect.

######  Example A.3.

Consider the path sum
$\omega^{x_{3}+x_{1}x_{2}}i^{-x_{1}x_{2}x_{3}}\ket{x_{1}}\ket{x_{2}}\ket{x_{3}\oplus
x_{1}x_{2}}$. Eliminating the $x_{1}x_{2}$ term in qubit $3$ before
simplifying the phase results in the following circuit:

$\Qcircuit@C=.5em@R=.5em@!R{\lstick{x_{1}}&\qw\ctrl{1}\ctrl{2}\ctrl{2}\rstick{x_{1}}\qw\\\
\lstick{x_{2}}\qw\gate{T}\ctrl{1}\ctrl{1}\rstick{x_{2}}\qw\\\
\lstick{x_{3}}\qw\gate{T}\gate{S^{\dagger}}\targ\rstick{x_{3}\oplus
x_{1}x_{2}}\qw\\\ }$

However, by re-framing the sum with the substitution $[x_{1}\leftarrow
z_{1},x_{2}\leftarrow z_{2},z_{1}z_{2}\leftarrow z_{3}\oplus x_{3}]$ we find

$\omega^{x_{3}+x_{1}x_{2}}i^{-x_{1}x_{2}x_{3}}\ket{x_{1}}\ket{x_{2}}\ket{x_{3}\oplus
x_{1}x_{2}}\equiv\omega^{z_{3}}\ket{z_{1}}\ket{z_{2}}\ket{z_{3}}$

which can now be simplified with a single $T$ gate. Note that the substitution
is applied left to right, rather than as a simultaneous substitution. The
resulting circuit is shown below:

$\Qcircuit@C=.5em@R=.5em@!R{\lstick{x_{1}}&\qw\ctrl{2}\qw\rstick{x_{1}}\qw\\\
\lstick{x_{2}}\qw\ctrl{1}\qw\rstick{x_{2}}\qw\\\
\lstick{x_{3}}\qw\targ\gate{T}\rstick{x_{3}\oplus x_{1}x_{2}}\qw\\\ }$

The final substitution $z_{1}z_{2}\leftarrow z_{3}\oplus x_{3}$ may seem
counter-intuitive, as we could instead substitute $x_{3}\leftarrow z_{3}\oplus
z_{1}z_{2}$. We choose a monomial of maximal degree to substitute in order to
avoid inadvertently increasing the degreee of the phase polynomial. For
instance, if the initial path sum was instead
$\omega^{x_{3}}\ket{x_{1}}\ket{x_{2}}\ket{x_{3}\oplus x_{1}x_{2}}$,
substituting $x_{3}\leftarrow z_{3}\oplus z_{1}z_{2}$ results in a re-framed
sum of
$\omega^{z_{3}+z_{1}z_{2}}i^{-z_{1}z_{2}z_{3}}\ket{z_{1}}\ket{z_{2}}\ket{z_{3}}$
and the final circuit

$\Qcircuit@C=.5em@R=.5em@!R{\lstick{x_{1}}&\qw\ctrl{2}\ctrl{1}\ctrl{2}\rstick{x_{1}}\qw\\\
\lstick{x_{2}}\qw\ctrl{1}\gate{T}\ctrl{1}\rstick{x_{2}}\qw\\\
\lstick{x_{3}}\qw\targ\gate{T}\gate{S^{\dagger}}\rstick{x_{3}\oplus
x_{1}x_{2}}\qw\\\ }$

By substituting the highest degree monomial instead, we avoid this issue and
synthesize the simpler circuit placing the $T$ gate to the left of the
Toffoli.

### Non-linear simplifications

The non-linear simplification step of our synthesis algorithm reduces the
number of non-linear terms in the output $\ket{f(\vec{x},\vec{y})}$ by
applying multiply-controlled Toffoli gates $\Lambda_{k}(X)$ via the rule

$\Lambda_{k}(X):\ket{\vec{x}}\ket{f\oplus\prod_{i}x_{i}}\mapsto\ket{\vec{x}}\ket{f}.$

Our method for non-linear simplifications uses a naïve heuristic whereby a set
of variables

$V=\\{v\mid f_{i}(\vec{x},\vec{y})=v\text{ for some }i\\}$

is computed. Any term in $f(\vec{x},\vec{y})$ which is a product of variables
contained in $V$ is then eliminated with an appropriately controlled Toffoli
gate.

This method is far from optimal, and in particular misses cases which can be
factorized as a cascade of Toffoli gates. While better reversible synthesis
methods exist, the lack of a known permutation to synthesize a priori in our
case makes it difficult to apply such methods directly. An interesting avenue
for future work would be to re-synthesize the permutation discovered through
this process of simplification using state-of-the-art methods.

### Degree reduction

In many cases, the simplifications previously described fail to leave some
path variable in a reducible position. When this happens, our last resort is
to fall back to an exponential time procedure we call _degree reduction_. The
idea of is to reduce the degree of the (non-Boolean) parts of a phase
polynomial restricted to a particular variable, as these terms serve as
roadblocks for reduction. This can in some cases be accomplished by applying
variable substitutions in such a way as to cancel out terms involving a
particular variable.

To illustrate degree reduction, recall the irreducible path sum expression
from the beginning of this section,

$\frac{1}{\sqrt{2^{2}}}\sum_{y_{1},y_{2}}i^{x_{2}y_{1}-x_{2}y_{2}}(-1)^{x_{1}y_{1}+x_{1}y_{2}+x_{2}y_{1}y_{2}}\ket{y_{1}}\ket{y_{2}}$

The exponent of $i$ cannot be directly reduced via simple phase
simplifications, as both terms depend on $x_{2}$. However, we can _indirectly_
eliminate one of these terms by applying Equation 5, substituting $y_{1}$ with
$y_{1}\oplus y_{2}$:

$\displaystyle\frac{1}{\sqrt{2^{2}}}$
$\displaystyle\sum_{y_{1},y_{2}}i^{x_{2}y_{1}-x_{2}y_{2}}(-1)^{x_{1}y_{1}+x_{1}y_{2}+x_{2}y_{1}y_{2}}\ket{y_{1}}\ket{y_{2}}$
$\displaystyle=\frac{1}{\sqrt{2^{2}}}\sum_{y_{1},y_{2}}i^{x_{2}(y_{1}\oplus
y_{2})-x_{2}y_{2}}(-1)^{x_{1}(y_{1}\oplus y_{2})+x_{1}y_{2}+x_{2}(y_{1}\oplus
y_{2})y_{2}}\ket{y_{1}\oplus y_{2}}\ket{y_{2}}$ by Equation 5
$\displaystyle=\frac{1}{\sqrt{2^{2}}}\sum_{y_{1},y_{2}}i^{x_{2}y_{1}}(-1)^{x_{1}y_{1}+x_{2}y_{2}}\ket{y_{1}\oplus
y_{2}}\ket{y_{2}}$

The final expression above can be simplified to
$\frac{1}{\sqrt{2^{2}}}\sum_{y_{1},y_{2}}i^{x_{2}y_{1}}(-1)^{x_{1}y_{1}+x_{2}y_{2}}\ket{y_{1}}\ket{y_{2}}$
by applying a $CNOT$ gate, which leaves $y_{2}$ in a reducible position. The
resulting circuit is given below:

$\Qcircuit@C=.5em@R=.5em@!R{\lstick{x_{1}}&\qw\gate{H}\ctrl{1}\qw\targ\rstick{y_{1}\oplus
y_{2}}\qw\\\ \lstick{x_{2}}\qw\qw\gate{S}\gate{H}\ctrl{-1}\rstick{y_{2}}\qw\\\
}$

The above example is relatively easy to spot, but more complicated cases may
require substitution of multiple variables, or even non-linear substitutions.
Our heuristic revolves around computing a type of _cover_ for the quotient
$2(P/y)$, where $y$ is the candidate for degree reduction.

######  Lemma A.4.

Let $P\in\mathbb{R}[y,x_{1},\dots,x_{n}]$ such that $4(P/y)\equiv 0\mod 2$. If
there exists a set $S\subseteq\\{1,\dots,n\\}$ such that $4(P/x_{i})\equiv
0\mod 2$ for all $i\in S$ and

$\sum_{i\in S}2(P/x_{i})\equiv 2(P/y)\mod 2$

then $2(P[x_{i}\leftarrow\overline{x_{i}\oplus y}\mid i\in S]/y)\equiv 0\mod
2$

###### Proof.

First recall that $\overline{x\oplus y}=x+y-2xy$. Hence

$2P[x_{i}\leftarrow\overline{x_{i}\oplus y}\mid i\in S]=2P+\sum_{i\in
S}2y(P/x_{i})+\sum_{i\in S}4x_{i}y(P/x_{i})$

Taking the quotient by $y$ we see

$\displaystyle 2(P[x_{i}\leftarrow\overline{x_{i}\oplus y}\mid i\in S]/y)$
$\displaystyle=2(P/y)+\sum_{i\in S}2(P/x_{i})+\sum_{i\in S}4x_{i}(P/x_{i})$
$\displaystyle\equiv 2(P/y)+2(P/y)\mod 2$ $\displaystyle\equiv 0\mod 2$

∎

In the context of path sums, Lemma A.4 tells us that if $e^{2\pi
iP(\vec{x},\vec{y})}$ can be written as $i^{y_{i}Q(\vec{x},\vec{y})}e^{2\pi
iR(\vec{x},\vec{y})}$ for some $i$, and there exists a subset of path
variables $\\{y_{j}\mid j\neq i\\}$ such that $e^{2\pi
iP(\vec{x},\vec{y})}=i^{y_{j}Q_{j}(\vec{x},\vec{y})}e^{2\pi
iR_{j}(\vec{x},\vec{y})}$ and
$i^{\sum_{j}Q_{j}(\vec{x},\vec{y})}=i^{Q(\vec{x},\vec{y})}$, then the
simultaneous substitution $y_{j}\leftarrow y_{j}\oplus y_{i}$ will eliminate
the term $i^{y_{i}Q(\vec{x},\vec{y})}$. Additional simplifications in the
state may then be further required to leave the path sum in a reducible state,
as in the previous above.