Pauliopt: Holistic circuit resynthesis using phase polynomials

For a general overview on phase polynomials, please refer to the Phase Polynomial Intermediate representation page. This page provides a brief review of the mixed ZX phase polynomial intermediate representation (IR). Then we show the general idea of synthesis of mixed ZX phase polynomials as well as additional optimizations to minimize resulting CNOT gates at the end of the circuit (CNOT tails).

Mixed ZX phase polynomial IR

The author of [1] refers to an exponentiated Pauli word P, e^{-i \alpha P} as a paulistring. We sometimes use the notation P_\alpha = e^{-i \alpha P} for paulistrings. A Z-phase gadget is a paulistring with only Z operators. That is, e^{-i \theta \bigotimes_j Z_j} for some wires \{j\}. Similarly, an X-phase gadget is given by e^{-i \theta \bigotimes_j X_j}.

A circuit for n qubits with m phase gadgets can be efficiently represented by a (n+2) \times m matrix. The additional 2 rows specify the angle \alpha and type (Z/X) of the phase gadget.

As an example, a single Z-phase gadget e^{-i \alpha_Z Z_0 Z_2 Z_3} on n=4 qubits is represented by the vector

where we used the string label Z for better readability. In practice, we use some one-hot encoding like 0 \leftrightarrow Z and 1 \leftrightarrow X. As an example, the phase gadgets of the circuit (X_1X_2)_{\alpha_X} (Z_0 Z_1 Z_2)_{\alpha_Z} are fully described by

A series of Z- or X- phase gadgets is called a Z- or X- phase polynomial, and the overall circuit description a mixed ZX phase polynomial.

An arbitrary quantum circuit can be rewritten as a series of paulistrings with arbitrary Pauli words. For more information, see the section on mixed ZX phase polynomials on the IR page.

Phase polynomial synthesis

Z and X phase gadgets play particularly well with CNOT gates. We can use the following two rules for phase polynomial synthesis:

• 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).

Let us use this to synthesize the aforementioned (X_1X_2)_{\alpha_X} (Z_0 Z_1 Z_2)_{\alpha_Z} circuit.

It is not clear, a priori, where to add and push-through CNOT gates. There are different possibilities that the author of [1] discusses. It turns out that "naive" synthesis in arXiv:1906.01734 is not fruitful and that "ParitySynth" [3] outperforms "Steiner-GraySynth" [5].

Optimize trailing CNOT gates with RowCol and PermRowCol

In the aforementioend synthesis procedure, CNOT gates are inserted in the circuit. Those CNOT gates may be pushed through the end of the circuit to leave a trailing CNOT circuit tail. This can be optimized further by RowCol or PermRowCol, reducing the CNOT gate count even more.