Phase Polynomial Intermediate Representation

Korbinian Kottmann

Compilation/
Phase Polynomial Intermediate Representation

Phase Polynomial Intermediate Representation

Phase polynomials are circuits $U$ consisting of CNOT and RZ gates (phase gates). Such circuits can be efficiently described in terms of their action on computational basis states $|\boldsymbol{x}\rangle = |x_1, .., x_{n}\rangle$ with $x_i \in \{0, 1\}$ in terms of the parity table $P_T$ , parity matrix $P$ , and phase angles $\boldsymbol{\alpha}$ from the phase gates:

|\boldsymbol{x}\rangle = e^{-i \frac{\boldsymbol{\alpha}}{2} \left(1 -2 \cdot P_T \boldsymbol{x} \right)} |P \boldsymbol{x}\rangle.

If not specified otherwise, the phase polynomial intermediate representation refers to this description. However, the exponent of the phase factor $p(\boldsymbol{x}) = \frac{\boldsymbol{\alpha}}{2} \left(1 -2 \cdot P_T \boldsymbol{x} \right)$ is also sometimes referred to as the phase polynomial. There are also X phase polynomials that are used in mixed ZX phase polynomials [5]. You may also sometimes see the term phase gadget [2], which refers to a simple phase polynomial consisting of one Pauli gate $e^{-i \alpha \bigotimes_j Z_j}$ acting on any number of qubits. X-phase gadgets are equivalently defined as $e^{-i \alpha \bigotimes_j X_j}$ gates.

Inputs

Circuit on $n$ qubits consisting of CNOT gates and $m$ phase gates.

Outputs

$n \times m$ binary parity table $P_T$ with $(P_T)_{ij} \in \{0, 1\}$
$n \times n$ binary parity matrix $P$ with $P_{ij} \in \{0, 1\}$
$m$ angles $\boldsymbol{\alpha}$

Example

Let us look at the circuit


x_0: ─╭X──RZ(1.1)─╭●─────────────────────────╭●───────┤  
x_1: ─╰●──────────╰X──RZ(2.2)─╭●──────────╭●─╰X───────┤  
x_2: ─────────────────────────╰X──RZ(3.3)─╰X──RZ(4.4)─┤

and its corresponding phase polynomial description:

\begin{align*} P_T &= \begin{pmatrix} 1 & 1 & 0 \\ 1 & 0 & 0 \\ 1 & 0 & 1 \\ 0 & 0 & 1 \end{pmatrix} ; \\ P &= \begin{pmatrix} 1 & 1 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix} ; \\ \boldsymbol{\alpha} &= (1.1, 2.2, 3.3, 4.4). \end{align*}

In particular, the phase factor in the exponent reads

\begin{align*} & \frac{1}{2} \boldsymbol{\alpha} \cdot \left(1 - 2P_T \boldsymbol{x} \right) \\ = & \frac{1}{2}\begin{pmatrix} 1.1 \\ 2.2 \\ 3.3 \\ 4.4 \end{pmatrix} \left(1 - 2 \begin{pmatrix} 1 & 1 & 0 \\ 1 & 0 & 0 \\ 1 & 0 & 1 \\ 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} x_0 \\ x_1 \\ x_2 \end{pmatrix} \right) \\ = & \frac{1}{2}\begin{pmatrix} 1.1 \\ 2.2 \\ 3.3 \\ 4.4 \end{pmatrix} \left(1 - 2 \begin{pmatrix} x_0 \oplus x_1 \\ x_0 \\ x_0 \oplus x_2 \\ x_2 \end{pmatrix} \right) \\ \end{align*}

and is composed of the phase vector $\boldsymbol{\alpha}$ , the binary parity table $P_T$ , and $\boldsymbol{x} = (x_0, x_1, x_2)$ .

The logical state $\boldsymbol{x}$ transforms according to the parity matrix as $P \boldsymbol{x}$ ,

|\begin{pmatrix} 1 & 1 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} x_0 \\ x_1 \\ x_2 \end{pmatrix} \rangle = |x_0 \oplus x_1, x_1, x_2\rangle.

Overall, we have

U |x_0, x_1, x_2\rangle= e^{-i \frac{1}{2}\left( 1.1 (1-2(x_0 \oplus x_1)) + 2.2 (1 - 2x_0) + 3.3 (1-2(x_0 \oplus x_2)) + 4.4 (1 - 2x_2) \right)} |x_0 \oplus x_1, x_1, x_2\rangle,

Typical usage

Z phase polynomials are utilized for compilation and CNOT routing [1] [2] [3] [4].

Any (Clifford + T) circuit can be transformed into an initial $(CNOT, T)$ circuit that can be described by (Z-) phase polynomials and a remaining Clifford circuit. Optimizing the initial $(CNOT, R_Z)$ part can be used to optimize T-gate counts as is done in [7] [8] [9] [10].

Mixed ZX phase polynomials can be used for quantum compilation of universal quantum circuits [5] [6].

References

[1] "On the CNOT-complexity of CNOT-PHASE circuits", Matthew Amy, Parsiad Azimzadeh, Michele Mosca, arXiv:1712.01859, 2017

[2] "Phase Gadget Synthesis for Shallow Circuits", Alexander Cowtan, Silas Dilkes, Ross Duncan, Will Simmons, Seyon Sivarajah, arXiv:1906.01734

[3] "Architecture-Aware Synthesis of Phase Polynomials for NISQ Devices", Arianne Meijer-van de Griend, Ross Duncan, arXiv:2004.06052, 2020

[4] "Phase polynomials synthesis algorithms for NISQ architectures and beyond", Vivien Vandaele, Simon Martiel, Timothée Goubault de Brugière arXiv:2104.00934, 2021

[5] "Annealing Optimisation of Mixed ZX Phase Circuits", Stefano Gogioso, Richie Yeung, arXiv:2206.11839, 2022

[6] "Towards a generic compilation approach for quantum circuits through resynthesis", Arianne Meijer - van de Griend, arXiv:2304.08814v1, 2023

[7] "Polynomial-time T-depth Optimization of Clifford+T circuits via Matroid Partitioning", Matthew Amy, Dmitri Maslov, Michele Mosca, arXiv:1303.2042, 2013.

[8] "An Efficient Quantum Compiler that reduces T count", Luke Heyfron, Earl T. Campbell, arXiv:1712.01557, 2017

[9] "Lower T-count with faster algorithms", Vivien Vandaele arXiv:2407.08695, 2024.

[10] "Quantum Circuit Optimization with AlphaTensor", Francisco J. R. Ruiz, Tuomas Laakkonen, Johannes Bausch et al, arXiv:2402.14396, 2024.

[11] "Quantum circuit optimizations for NISQ architectures", Beatrice Nash, Vlad Gheorghiu, Michele Mosca, arXiv:1904.01972, 2019

Cite this page

@misc{PennyLane-PhasePolynomial,
title={Phase Polynomial Intermediate Representation},
howpublished={\url{https://pennylane.ai/compilation/phase-polynomial-intermediate-representation}},
year={2025}
}

Page author(s)

Korbinian Kottmann

Quantum simulation & open source software

Why PennyLane

Getting Started

Documentation

Ecosystem

Phase Polynomial Intermediate Representation

Example

Typical usage

References

Cite this page

Page author(s)