Phase Polynomial Intermediate Representation

The act of synthesizing a circuit from a phase polynomial description in terms of its parity matrix, parity table and phase angles is a quantum compilation step. We use synthesis and compilation interchangeably here.

Phase polynomial synthesis methods

There is a variety of methods for phase polynomial synthesis proposed in the literature. We try to go through them in historical order without guarantees for completeness. We sometimes use terms to refer to algorithms that are not necessarily established but help keeping an overview over the various methods. Some of those terms are taken from one of the more recent works by van de Griend [6].

GraySynth: GraySynth [1] is one of the earlier works on phase polynomial synthesis. It does not take into account restricted qubit connectivities.

GadgetSynth: In GadgetSynth [2], each phase gadget is synthesized with a ladder of CNOTs. This is not efficient for phase polynomials consisting of multiple consecutive phase gadgets but can be handy when individual phase gadgets are encountered in a circuit. The canonical way to decompose a phase gadget e^{-i \frac{\theta}{2} ZZZZ} is by means of two CNOT ladders enclosing an RZ gate:

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

However, there is ambiguity and one can also do the following decomposition that has shorter depth.

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

This ambiguity can be leveraged for depth optimization or different contexts in which the phase gadget might appear in a circuit.

Steiner-GraySynth: In Steiner-GraySynth [3], connectivity is taken into account. The name Steiner-GraySynth is taken from the pauliopt paper [6], but the paper itself references [11] as Steiner-GraySynth. Ironically, [3] explicitly does not compute Steiner trees, so the name is a bit confusing.

ParitySynth: ParitySynth [4] utilizes the fact that Z phase gadgets commute and tries to find the optimal ordering before synthesizing an architecture aware phase polynomial. It utilizes an approximate algorithm to compute Steiner trees, see algorithm 3 in the paper.

Pauliopt: The pauliopt paper [6] (see Pauliopt: Holistic circuit resynthesis) mixes a variety of techniques in one holistic synthesis pass for compilation, thereby achieving better results than simply applying each individual component. In particular, it mixes ParitySynth or Steiner-GraySynth together with other approaches such as RowCol and PermRowCol.

T-gate optimization

We differentiate methods that focus on T-gate minimization

TODD: Third Order Duplicate and Destroy (TODD) is a method introduced in [8], and improved & reinvented in [9] with better runtimes and T-gate counts. It manipulates the input (Clifford + T) circuit into an initial (CNOT, T) circuit that can be described by phase polynomials, and a final Clifford sub-circuit for which we do not care in the context of optimizing T-gates. The goal is to find an alternative and equivalent parity table P_T with a minimal number of columns. This is done algebraically by reformulating the problem in terms of a order-3 symmetric tensor and finding its low rank decomposition. Since the problem of finding the tensor rank of the symmetric tensor is NP-complete and the problem of minimizing the T-gate count is NP-hard, the authors propose heuristics that work well in practice.

AlphaTensor: The algebraic tensor optimization problem in TODD can be tackled by reinforcement learning methods and has been shown to perform competitively in [10]. Additionally, this method makes good use of so-called "gadgets" that utilize auxiliary qubits, clifford gates and measurement corrections in order to lower the T-gate count. Without aux qubits, [9] still has an edge in most cases of the op-T-mize benchmark.