1. Compilation/

  2. Phase Polynomial Intermediate Representation

Phase Polynomial Intermediate Representation

Phase polynomials are circuits UU consisting of CNOT and RZ gates (phase gates). Such circuits can be efficiently described in terms of their action on computational basis states ∣x⟩=∣x1,..,xn⟩|\boldsymbol{x}\rangle = |x_1, .., x_{n}\rangle with xi∈{0,1}x_i \in \{0, 1\} in terms of the parity table PTP_T, parity matrix PP, and phase angles α\boldsymbol{\alpha} from the phase gates:

∣x⟩=e−iα2(1−2⋅PTx)∣Px⟩.|\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(x)=α2(1−2⋅PTx)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α⨂jZje^{-i \alpha \bigotimes_j Z_j} acting on any number of qubits. X-phase gadgets are equivalently defined as e−iα⨂jXje^{-i \alpha \bigotimes_j X_j} gates.

Inputs

  • Circuit on nn qubits consisting of CNOT gates and mm phase gates.

Outputs

  • n×mn \times m binary parity table PTP_T with (PT)ij∈{0,1}(P_T)_{ij} \in \{0, 1\}
  • n×nn \times n binary parity matrix PP with Pij∈{0,1}P_{ij} \in \{0, 1\}
  • mm 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:

PT=(110100101001);P=(110010001);α=(1.1,2.2,3.3,4.4).\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

12α⋅(1−2PTx)=12(1.12.2 3.3 4.4)(1−2(110100101001)(x0x1x2))=12(1.12.2 3.3 4.4)(1−2(x0⊕x1x0x0⊕x2x2))\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 PTP_T, and x=(x0,x1,x2)\boldsymbol{x} = (x_0, x_1, x_2).

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

∣(110010001)(x0x1x2)⟩=∣x0⊕x1,x1,x2⟩.|\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∣x0,x1,x2⟩=e−i12(1.1(1−2(x0⊕x1))+2.2(1−2x0)+3.3(1−2(x0⊕x2))+4.4(1−2x2))∣x0⊕x1,x1,x2⟩,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)(CNOT, T) circuit that can be described by (Z-) phase polynomials and a remaining Clifford circuit. Optimizing the initial (CNOT,RZ)(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

Korbinian Kottmann

Quantum simulation & open source software