1. Compilation/

  2. Phase Polynomial Intermediate Representation

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 UU containing only (CNOT, RZR_Z) gates is called a phase polynomial. Such a circuit can be fully described by mapping computational basis states ∣x⟩=∣x1,..,xn⟩|\boldsymbol{x}\rangle = |x_1, .., x_n\rangle on nn qubits with xi∈{0,1}x_i \in \{0, 1\} as

∣x⟩=e−iθ2(1−2⋅PTx)∣Px⟩.|\boldsymbol{x}\rangle = e^{-i \frac{\boldsymbol{\theta}}{2} \left(1 -2 \cdot P_T \boldsymbol{x}\right)} |P \boldsymbol{x}\rangle.

Let us go through each of the components:

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

When additional phase gates RZ(θ)=e−iθ2ZR_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 PTP_T. First, let us note that the action of a phase gate on a computational basis state is given by

RZ(θ)∣x⟩=e−iθ2(1−2x)∣x⟩.R_Z(\theta) |x\rangle = e^{-i \frac{\theta}{2} (1-2x)} |x \rangle.

A CNOT gate may alter the current state ∣x⟩|\boldsymbol{x}\rangle of the circuit, and we call the values of x\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 ∣x1,x2⟩|x_1, x_2\rangle and apply a CNOT1,2\text{CNOT}_{1, 2} gate,

CNOT1,2∣x1,x2⟩=∣x1,x1⊕x2⟩,\text{CNOT}_{1, 2} |x_1, x_2\rangle = |x_1, x_1 \oplus x_2\rangle,

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 RZ2(θ)R_Z^2(\theta) rotation on the second qubit collects its current parity x1⊕x2x_1 \oplus x_2,

RZ2(θ)∣x1,x1⊕x2⟩=e−iθ2(1−2(x1⊕x2))∣x1,x1⊕x2⟩.R_{Z_2}(\theta) |x_1, x_1 \oplus x_2\rangle = e^{-i \frac{\theta}{2} (1-2(x_1 \oplus x_2))} |x_1, x_1 \oplus x_2\rangle.

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

PT=(11);P=(1011),P_T = \begin{pmatrix} 1 & 1 \end{pmatrix}; P = \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix},

and, in particular, as the following phase polynomial:

U∣x1,x2⟩=e−iθ2⋅(1−2(11)(x1x2))∣(1011)(x1x2)⟩.U |x_1, x_2\rangle = e^{-i \frac{\theta}{2} \cdot \left(1 - 2 \begin{pmatrix} 1 & 1 \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \end{pmatrix} \right)} |\begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \end{pmatrix}\rangle.

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

Collecting the phase polynomial description by going through an example circuit and noting the current parities at each point of the circuit. 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 θ1(x1⊕x2)\theta_1 (x_1 \oplus x_2), θ2(x1⊕x2⊕x3)\theta_2 (x_1 \oplus x_2 \oplus x_3), and θ3(x1⊕x3⊕x4)\theta_3 (x_1 \oplus x_3 \oplus x_4), corresponding to the parity table

(110011101011),\begin{pmatrix}1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 \end{pmatrix},

as well as the parity matrix

(1110101100100001),\begin{pmatrix}1 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix},

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θ⨂jZje^{-i \theta \bigotimes_j Z_j} for some wires {j}\{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θZZZe^{-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 ZZ phase polynomials. This is not a universal description and restricts to (CNOT,RZ)(\text{CNOT}, R_Z) circuits. We can, however, additionally define XX phase polynomials, which consist of XX 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θ:=e−iθ2PP_\theta := e^{-i \frac{\theta}{2} P} for arbitrary Pauli words PP 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

Decomposing a Y rotation as ZXZ

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

Decomposing a Z rotation as HXH

Further, note that the Hadmard gate is just

Decomposing a H gate as ZXZ

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

Decomposing a XYZ rotation

An efficient intermediate representation for mixed ZX phase polynomials is given by the (n+2)×m(n+2) \times m matrix, where mm is the number of phase gadgets and nn 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)θ1,(ZZI)θ2,(XXX)θ3,(ZZZ)θ4)((ZIZ)_{\theta_1}, (ZZI)_{\theta_2}, (XXX)_{\theta_3}, (ZZZ)_{\theta_4}) can be described by

(ZZXZθ1θ2θ3θ4111101111011).\begin{pmatrix} Z & Z & X & Z \\ \theta_1 & \theta_2 & \theta_3 & \theta_4 \\ 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 \end{pmatrix}.

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 CNOT12\text{CNOT}_{12} through the above mixed ZX phase polynomial alters the first and second qubit rows and yields

(ZZXZθ1θ2θ3θ4101001011011).\begin{pmatrix} Z & Z & X & Z \\ \theta_1 & \theta_2 & \theta_3 & \theta_4 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 \end{pmatrix}.

These simple rules can be used to synthesize mixed ZX phase polynomials by inserting 1=CNOTijCNOTij\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 RZR_Z and RXR_X gates. There are different strategies on how to do this, see the compilation tab and, in particular, reference [6].