Phase Polynomial Intermediate Representation

We give detailed definitions and descriptions of the terms phase polynomial, phase gadget and mixed ZX phase polynomial.

Phase polynomial

A circuit U containing only (CNOT, R_Z) gates is called a phase polynomial. Such a circuit can be fully described by mapping computational basis states |\boldsymbol{x}\rangle = |x_1, .., x_n\rangle on n qubits with x_i \in \{0, 1\} as

Let us go through each of the components:

The matrix P is the so-called parity matrix and tracks the logical manipulation of the input vector |\boldsymbol{x}\rangle. For circuits containing only CNOT gates, it is a full description and its own intermediate representation (IR).

When additional phase gates R_Z(\theta) = e^{-i \frac{\theta}{2} Z} are involved, we need to additionally track the accumulated phase of the circuit. This is done in the so-called parity table P_T. First, let us note that the action of a phase gate on a computational basis state is given by

A CNOT gate may alter the current state |\boldsymbol{x}\rangle of the circuit, and we call the values of \boldsymbol{x} the current parity at that point in the circuit. Whenever there is a phase gate, we collect the current parity on the qubit the gate is acting on. The collection of those parities is the parity table.

This is best understood by going through a simple example: Let us start with the state |x_1, x_2\rangle and apply a \text{CNOT}_{1, 2} gate,

where the action is simply adding the control qubit value to the target qubit value, see the parity matrix IR for more details.

Now, applying an R_Z^2(\theta) rotation on the second qubit collects its current parity x_1 \oplus x_2,

Overall, we can describe the action of the circuit U = (\text{CNOT}_{12}, R_{Z_2}(\theta)) with

and, in particular, as the following phase polynomial:

We can go through a more detailed example by hand by simply noting the current parities in the circuit whenever they are altered.

By noting the current parities inside the circuit at each point of a new gate we can directly read out the parity table and parity matrix. Image taken from [4].

In particular, we get the phase factors \theta_1 (x_1 \oplus x_2), \theta_2 (x_1 \oplus x_2 \oplus x_3), and \theta_3 (x_1 \oplus x_3 \oplus x_4), corresponding to the parity table

as well as the parity matrix

which is just the collection of final parities at the end of the circuit.

Phase gadget

A phase gadget is a qml.MultiRZ gate consisting of a single exponentiated Pauli-Z word, e^{-i \theta \bigotimes_j Z_j} for some wires \{j\}.

Such a phase gadget can be decomposed as a single RZ gate enclosed by a CNOT ladder on either side. For example, we can decompose e^{-i \theta ZZZ} as the following:

0: ─╭●───────────╭●─┤  
1: ─╰X─╭●─────╭●─╰X─┤  
2: ────╰X──RZ─╰X────┤  

A canonical way to decompose phase gadgets is described in the phase gadget synthesis paper [2]. We can view a phase polynomial as multiple phase gadgets. Or, vice versa, a phase gadget as the simplest phase polynomial. It is often more efficient to synthesize / compile multiple phase gadgets as a whole phase polynomial, see compilation.

Mixed ZX phase polynomial

If not otherwise specified, phase polynomials typically refer to Z phase polynomials. This is not a universal description and restricts to (\text{CNOT}, R_Z) circuits. We can, however, additionally define X phase polynomials, which consist of X phase gadgets instead. Then we can define a mixed ZX phase polynomial intermediate representation that is in principle universal. First we note that the gate set of arbitrary Pauli word rotations P_\theta := e^{-i \frac{\theta}{2} P} for arbitrary Pauli words P is universal. Then we can see that mixed ZX phase polynomials are universal as we can transform any Pauli word rotation into a mixed ZX phase polynomial. This is because we can rewrite an arbitrary Y rotation gate into Z and X phase gadgets

Similarly, we can rewrite an arbitrary Z rotation gate into Z and X phase gadgets

Further, note that the Hadmard gate is just

Overall, we can rewrite arbitrary paulistrings into Z and X phase gadgets. Take for example (XYZ)_\alpha and use the former two tricks to rewrite it as the following:

An efficient intermediate representation for mixed ZX phase polynomials is given by the (n+2) \times m matrix, where m is the number of phase gadgets and n is the number of qubits. The additional 2 parameters are the corresponding angle and the specification of whether it is a Z or X phase gadget.

For example, the circuit ((ZIZ)_{\theta_1}, (ZZI)_{\theta_2}, (XXX)_{\theta_3}, (ZZZ)_{\theta_4}) can be described by

This representation is particularly ameanable to be combined with CNOT circuits as we can define the following two rules for commuting CNOT gates through a mixed ZX phase polynomial:

• push a CNOT through a Z-phase gadget: add target qubit value to control qubit value (modulo 2)
• push a CNOT through a X-phase gadget: add control qubit value to target qubit value (modulo 2).

E.g., pushing \text{CNOT}_{12} through the above mixed ZX phase polynomial alters the first and second qubit rows and yields

These simple rules can be used to synthesize mixed ZX phase polynomials by inserting \mathbb{1} = \text{CNOT}_{ij}\text{CNOT}_{ij} and pushing through one of the two CNOT gates. This is done in such a way as to retrieve a mixed ZX phase polynomial with unit vectors as columns, which correspond to simple single qubit R_Z and R_X gates. There are different strategies on how to do this, see the compilation tab and, in particular, reference [6].