## Redefining Lexicographical Ordering: Optimizing Pauli String Decompositions for Quantum Compiling

Qunsheng Huang, David Winderl CIT Department of Computer Science Technical University of Munich Garching, Germany keefe.huang@tum.de, david.winderl@tum.de

Arianne Meijer-van de Griend Department of Computer Science University of Helsinki Helsinki, Finland ariannemeijer@gmail.com

Richie Yeung Department of Computer Science University of Oxford Oxford, United Kingdom richie.yeung@cs.ox.ac.uk

All authors contributed equally.

Abstract -In quantum computing, the efficient optimization of Pauli string decompositions is a crucial aspect for the compilation of quantum circuits for many applications, such as chemistry simulations and quantum machine learning. In this paper, we propose a novel algorithm for the synthesis of trotterized timeevolution operators that results in circuits with significantly fewer gates than previous solutions. Our synthesis procedure takes the qubit connectivity of a target quantum computer into account. As a result, the generated quantum circuit does not require routing, and no additional CNOT gates are needed to run the resulting circuit on a target device. We compare our algorithm against Paulihedral and TKET, and show a significant improvement for randomized circuits and different molecular ansatzes. We also investigate the Trotter error introduced by our ordering of the terms in the Hamiltonian versus default ordering and the ordering from the baseline methods and conclude that our method on average does not increase the Trotter error.

target Hamiltonian's time evolution operator (i.e. a product of exponentiated Pauli strings). Additionally, the algorithm takes qubit connectivity into account during synthesis. As a result, the synthesized circuit is already routed and no additional SWAP gates are required to run the circuit on the target device. Along the way, we extend a previous method of ours [5] to more effectively synthesize Clifford tableaus by allowing a final permutation either implemented on the quantum circuit or by a permutation of swaps.

Index Terms -Circuit synthesis, Pauli string, Lexicographical ordering, Phase gadgets, Trotter decomposition, compilation, optimization

## I. INTRODUCTION

With the increasing size and quality of current quantum computers comes a need for efficient compilation algorithms that can process more complicated circuits in polynomial time without generating more operations than necessary. In this paper, we focus on the synthesis of Hamiltonian time evolution operators to quantum circuits constrained under the qubit connectivity of a target quantum computer. These operators can be found in the ubiquitous Ising model as well as algorithms such as the unitary-coupled cluster ansatz (UCC) [1] or the Harrow-Hassidim-Lloyd (HHL) algorithm [2], among others. Similarly, sequences of multiple controlled rotations can also be represented as a sequence of Pauli string operations which are common in e.g. Amplitude Encoding [3], and Linear Combinations of Unitaries [4], among others. Moreover, they form a universal representation, so any quantum algorithm can be rewritten into a product formula that contains only time evolution operators. While time evolution operators in algorithms can be easily determined for classical simulation, transpiling the same operations to gates on a quantum device is not obvious.

In this context, our proposed method synthesizes a quantum circuit from the first-order Suzuki-Trotter decomposition of the

Our experiments show that the introduced algorithm significantly improves the number of CNOTs, the circuit depth, and the CNOT depth with respect to Paulihedral [6] and TKET [7], both in the constrained and unconstrained case. In the case of targeting a restricted architecture, our proposed method improves these metrics up to an order of magnitude for UCCSD ansatzes.

## II. PRELIMINARIES AND RELATED WORK

## A. Pauli Gadgets and Pauli Polynomials

In this work, we consider Trotterized time evolution operators written in the form

$$\stackrel { \lambda } { \mathfrak { e } } \\ \mathfrak { s } = U = e ^ { - i \sum _ { n } \left ( \frac { \theta _ { n } } { 2 } \otimes _ { m } P _ { m } \right ) } \approx \left ( \prod _ { n } e ^ { - i \frac { \theta _ { n } } { 2 r } \otimes _ { m } P _ { m } } \right ) ^ { r }, \ \ ( 1 )$$

where P m is a single-qubit Pauli operator, and r the number of repetitions of the circuit. The tensor of Pauli gates can also be written as a sequence of the letters representing each Pauli gate i.e. representing X ⊗ I ⊗ X ⊗ Y ⊗ Z as XIXYZ . This sequence is also called a Pauli string because it is a word s of arbitrary length over the alphabet { I, X, Y, Z } , or the four Pauli letters .

Following the conventions in [8] and [9], we define a Pauli gadget ϕ with a Pauli string s and angle θ :

$$\phi ( \theta, s ) = \exp \left ( - i \frac { \theta } { 2 } s \right ) \text{ \quad \ \ } \text{(2)}$$

Additionally, we also utilize their convenient graphical representation of the Pauli gadget in the ZX-calculus:

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00354v1-figure-55a72a58-71e5-4f0f-8870-0f780a876854.jpg)

In this representation, each non-identity Pauli letter in s maps to a leg on the corresponding qubit or wire, each attached to a central "spider" containing the angle information, as shown in Equation 3. Then, given a Hamiltonian described by a sum of weighted Pauli strings, we can approximate the corresponding time evolution operator in terms of Pauli gadgets. We refer to such a representation as a Pauli polynomial . For example, given one such arbitrary Hamiltonian H = αIXY X + βIZZI + αIXY Y + βIY Y I , where α, β ∈ R , we could approximate the time evolution operator over a time step t as follows:

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00354v1-figure-618d460c-474b-4b97-bc24-48ad5921ccb7.jpg)

This notation is equivalent to that used in [6] with the difference being that our notation can be considered a dialect of the ZXcalculus [10] and, therefore, all equalities presented in this work can be considered mathematical equations. Additionally, this representation includes well-defined rules for propagating Clifford gates through Pauli gadgets [7, 9] that are key for the proposed methods. The graphical representations of the Clifford operators relevant to this work are then as follows:

$$V = - \oplus - V ^ { \dagger } = \oplus - H = - \oplus - C N O T = \bigoplus ^ { - } _ { ( 5 ) } \bigoplus ^ { - } _ { \text{Synthesis} } N e v e { 1 }$$

$$S = - \bigoplus - \ S ^ { \dagger } = - \bigoplus -,$$

where V := √ X . Then, propagating a CNOT through gadgets with ZZ -legs or ZY -legs is represented as follows:

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00354v1-figure-ab356523-e728-4dda-9dc1-67ff9ff487a0.jpg)

This equality is used to remove legs from Pauli gadgets with a set formulation in the proposed method. The remaining propagation rules used in this work to manipulate legs are:

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00354v1-figure-2637c5da-c1a2-4728-874f-60a5f6ab54f0.jpg)

Once a Pauli polynomial has been specified, an ordering of the Pauli gadgets needs to be determined. Normally, Pauli gadgets can only be reordered in a circuit if they commute, but since the gadgets emerge from a sum in the exponent (see Equation 1), we can reorder the Pauli strings in the sum and, likewise, the corresponding Pauli gadgets, arbitrarily.

However, the transformation in Equation 1 is approximate and results in a small Trotter error . Although arbitrarily reordering the individual Pauli gadgets does not worsen the order of the approximation error in trotterized decompositions, investigations by [11] indicate that the variance in Trotter error when reordering non-commuting terms is not trivial if interaction terms are large.

Investigations by [12], [13], [7], and [14] also indicate that the ordering of terms also impacts the number of entangling gates generated during synthesis, each proposing ordering strategies that reduce both synthesized gate count and theoretical upper bounds for the resultant Trotter error. Additionally, lexicographical ordering, in which the Pauli strings of each component are treated as words and sorted using a strict letter ordering, is shown to be a good heuristic for obtaining gate cancellations between synthesized Pauli gadgets [13], [12].

In this work, similar to the assumptions made in [6] in their Paulihedral implementation, we ignore the Trotter error for arbitrarily ordering Pauli gadgets, focusing mainly on reducing entangling gate count. This choice is grounded in the assumption that entangling gates introduce greater error than that introduced by poor ordering. Furthermore, the effects of poor ordering can be mitigated by limiting time step size and utilizing higher order decomposition methods [15].

Nevertheless, the proposed algorithm can also be used to synthesize the Pauli gadgets in groups. Although, we do not use this feature in our experiments, nor do we provide a grouping heuristic.

## C. Related algorithms

Once a grouping of Pauli gadgets is decided, various algorithms exist to synthesize these sets of gadgets. We use two of these as a baseline to the proposed algorithm.

First, we have [6], which assumes a user-specified grouping and uses the coupling map to group the Pauli gadgets based on cumulative qubit distance and attempts to synthesize each layer such that the gates between layers are maximally canceled.

Secondly, we compare against [7] where Pauli gadgets are optionally re-grouped using graph coloring. Afterwards, each group is synthesized by diagonalizing the Pauli gadgets and then synthesizing them using GraySynth [16]. The idea of [16] is to synthesize the gadgets in order of the Gray code [17], such that each subsequent gadget only requires a single CNOT to be synthesized.

In this paper, we propose an alternative method for ordering and synthesizing a sequence of Pauli gadgets that is inspired by GraySynth [16] and its architecture-aware version [18].

Fig. 1: Action of prepending Clifford gates H S , and CNOT to an n qubit Clifford tableau.

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00354v1-figure-479635d8-0727-4780-80a9-ec835f5234e7.jpg)

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00354v1-figure-f54d89f5-d999-4275-a6bf-afae0ae5bb7a.jpg)

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00354v1-figure-89ab5e2f-94be-4219-89b5-e6c892505f8d.jpg)

## D. Clifford Tableaus

A final component required by our proposed algorithm is Clifford tableau synthesis. The Clifford tableau is a compact representation introduced by [19] that specifies a Clifford circuit or operator. More specifically, an n qubit Clifford circuit can be designated by a 2 n × 2 n matrix and a vector of size 2 n , all in GF (2) and the tableau of an empty circuit is an identity matrix. Appending and prepending Clifford gates to a Clifford operator corresponds to row and column operations on its Clifford tableau. The prepending operations are visualized in Figure 1, and the appending operations act transposed with respect to prepending: they act on the respective columns, rather than the rows.

Given a Clifford tableau, one can synthesize the equivalent quantum circuit as follows, starting with an empty circuit:

- 1) Generate a Clifford gate and its adjoint.
- 2) Append the gate to the circuit and prepend it to the tableau.
- 3) Continue until the Clifford tableau is an identity matrix.

In this paper, we adapted one of our previous algorithms [5], which uses the structure of the RowCol algorithm [20] for CNOT synthesis and applies it to the Clifford tableau synthesis from [21], [22].

## III. METHODS

The proposed algorithm combines the ideas from the related algorithms into a single architecture-aware strategy for synthesizing these trotterized Hamiltonians. The algorithm expects a set of Pauli gadgets that can be decomposed in arbitrary order, and returns a quantum circuit implementing those Pauli gadgets. The structure of this algorithm is an adaptation of GraySynth [16] and its architecture-aware variant [18]. The outline of the algorithm is as follows, with the functions diagonalize and disconnect defined in subsection III-A:

- 1) Choose a qubit q pivot to remove from the problem, according to heuristic h pivot .
- 2) Synthesize any Pauli gadgets that are connected to only a single qubit: diagonalize them and place the R Z ( α ) gate. Then, remove these gadgets from the problem.
- 3) Split the Pauli gadgets into groups based on the letters on the legs on q pivot .
- 4) Take the Pauli gadgets that are not connected to q pivot , i.e. with an I on the leg, and go to step 1 with q pivot removed from the problem.
- 5) Choose another qubit q neighbor that is highly entangled with the chosen qubit according to the remaining Pauli gadgets, according to heuristic h n .
- 6) If there are Pauli gadgets not connected to q neighbor , diagonalize as many Pauli gadgets as possible with respect to the first qubit, and place two CNOT gates between the two qubits to disconnect the first qubit.
- 7) Otherwise, disconnect as many remaining Pauli gadgets as possible by placing at most two single qubit Clifford gates to diagonalize some Pauli gadgets (i.e. convert legs to { Y, Z } , see subsection III-A for specifics) and a CNOT gate between the two chosen qubits to disconnect the gadgets (see [8] for an overview).
- 8) Repeat step 3: split the remaining Pauli gadgets.
- 9) Repeat step 4: go to step 1 with disconnected Pauli gadgets and q pivot removed from the problem.
- 10) Go to step 5 with the remaining remaining Pauli gadgets.

The adjoint of all synthesized Clifford gates are aggregated into a Clifford tableau and later synthesized (e.g. using [5]) and all unfinished Pauli gadgets are updated according to the Clifford gate commutation rules [8] whenever a Clifford gate is synthesized. Additionally, the algorithm can be adjusted to synthesize the Pauli gadgets in the given order by iteratively using this procedure on sets of mutually commuting Pauli gadgets. In which case, the Clifford tableau collects the Clifford gates from all iterations and the Clifford gates are propagated through all subsequent Pauli gadgets, including those in future iterations. Moreover, this algorithm can be trivially made architecture-aware by choosing a q pivot in step 1 that does not disconnect the connectivity graph when removed, and restricting q neighbor in step 5 to neighbors of the chosen qubit.

Intuitively, this algorithm tries to greedily find an optimal lexicographical order for the letters, i.e. colors, on each Pauli gadget, per qubit. Because of the greedy nature, we assume that I always comes first in the alphabet, such that we never unnecessarily introduce entanglement with a new qubit. The exception is when this is needed for routing purposes in the architecture-aware case. Moreover, as explained in the remainder of this section, when placing the Clifford gates, we essentially partially decompose the Pauli gadgets and assume that the gates on the other side of the Pauli gadget will cancel out. This is done by propagating the adjoint of the added Clifford gates through all remaining Pauli gadgets and gathering them in a Clifford tableau to be synthesized as a final optimization step. Thus, all Clifford gates are generated as late as possible, on an as-needed basis. As a result, the algorithm does not need to guess a good gadget ordering a priori. Instead, the ordering emerges from the structure of the synthesis procedure, while grouping gadgets with the same letters on the same qubits together. A simple example that steps through the synthesis process is shown in Figure 2.

## A. Gate placement

To be precise, we diagonalize gadgets with respect to a single qubit as follows: if the gadget has no leg or a green leg on the qubit (i.e. I , or Z ), we are done, otherwise, we place a single qubit Clifford gate and its adjoint according to the following transformations: 1

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00354v1-figure-78316fec-f687-4d2b-8104-f458044efe00.jpg)

The introduced gate is propagated through all following Pauli gadgets, and gathered in the Clifford tableau, following the rules in Figure 1. Note that we choose the rule that diagonalize s as many Pauli gadgets as possible. Typically, not all affected legs are mapped to a green leg and their updated type must be considered.

After diagonalizing, we disconnect as many Pauli gadgets as possible by placing up to a single qubit Clifford gate and two CNOTs. By construction, the first qubit will always be diagonalized. The simplest case is when the second qubit is already disconnected. Then, we can swap the two qubits. However, because we know the type of the Pauli gadget, we can remove one of the CNOTs since it commutes with the Pauli gadget and cancels out. Thus, we have: 1

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00354v1-figure-5a9b5e84-e40e-4c78-a268-6e93ec150297.jpg)

If the second qubit is connected, we can match the legs of the Pauli gadgets under consideration as one of three cases, each corresponding to a different Clifford operation to be applied: 1

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00354v1-figure-1187db05-7799-4eaa-b917-c7cf6871ee2c.jpg)

(

disconnect

X or Y)

Each introduced rule only removes entanglement for two types of legs in the second wire. However, the second wire can contain X Y , or Z legs. Thus, we choose the option where the

1 Here, we use the dashed lines to separate the diagram into different regions: the left-most region contains the gates added to the circuit, the middle region is the updated Pauli gadgets, and the right-most region contains gates that are stored in a Clifford tableau for re-synthesis.

most Pauli gadgets are matched and place the corresponding Clifford gates. Then, we propagate these gates through all remaining Pauli gadgets and prepend them to the Clifford tableau.

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00354v1-figure-61386660-1bbb-4e09-8fcc-0edd597fe0db.jpg)

(a) Initial placement.

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00354v1-figure-c5f39507-22fa-46d0-8022-da48e2351de6.jpg)

(b) Greedily group gadgets α 0 and α 2 .

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00354v1-figure-f6ae7e1f-e60e-43ee-843c-05043496c9d7.jpg)

(c) disconnect gadgets α 0 and α 2 , then diagonalize

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00354v1-figure-72f67c98-4138-4293-bdbc-1e3c6aec232c.jpg)

(d) diagonalize qubit 0 and disconnect it from gadgets α 1 and α 3 .

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00354v1-figure-860c16de-c440-423d-87de-7db3f6fe90ee.jpg)

(e) disconnect qubit 1 from gadgets α 1 and α 3 .

(f) disconnect qubit 3 to synthesize gadget α 1 .

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00354v1-figure-b0f9b0b3-71ef-46b5-b7a8-1f3248a87488.jpg)

(g) disconnect qubit 3 again to synthesize gadget α 3 .

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00354v1-figure-1dabeb0e-1f05-4678-a66b-8d92b0f40e9c.jpg)

Fig. 2: Step-by-step synthesis of time evolution operator H = α IIZZ 0 + α Y XZX 1 + α IIY Z 2 + α Y XZI 3 from initial placement using methods in subsection III-A. 1

## B. Heuristics

The proposed algorithm relies on choosing a good qubit to perform the splitting heuristic on. For our experiments, we have used the following heuristic and cost function:

$$c _ { q } ( s _ { q }, \mathbf g ) & = k \cdot P _ { I } ( s _ { q } [ \mathbf g ] ) & ( 1 0 ) & \quad \text{ans} \mathfrak { s } \\ & \quad + P _ { m a x } ( s _ { q } [ \mathbf g ] ) - P _ { m i n } ( s _ { q } [ \mathbf g ] ), & h _ { \circ }$$

$$h ( g, \mathbf o ) & = \arg \max _ { q \in \mathbf o } ( c _ { q } ( s _ { q }, g ) ), \\ h _ { p i v o t } ( \mathbf g, G ) & = h ( \mathbf g, \{ q \in \text{nodes} ( G ) \ | \ \neg \text{cuts} ( q, G ) \} ),$$

$$h _ { n } ( q _ { p }, \mathbf g, G ) = h ( \mathbf g, \{ q \in \text{nodes} ( G ) \ | \ ( q _ { p }, q ) \in \text{edges} ( G ) \} ), \stackrel { \dots } { \underset { \text{somethi} } { \text{somethi} } }$$

$$\begin{matrix} \end{matrix}$$

where q p is the chosen pivot qubit, s q is the string of Pauli letters of all legs on qubit q , g the set of Pauli gadgets examined, and k describes a weighting factor which we parametrized with k = 10 . P I ( s ) , P max ( s ) and P min ( s ) are all functions acting on the Pauli string and returning a number in N : P I ( s ) counts the amount of Pauli I 's in s , P max ( s ) counts the size of the largest nonI region in s , P min ( s ) determines the size of the smallest nonI region in s .

It is possible to tweak the cost function in our heuristic to be more specific to the target architecture. For example, the cost can be weighted based on the fidelity of the qubits or the gates, or adjusted to prefer gate parallelisation. In principle, any cost function would result in a correct algorithm, but with a different performance in terms of resulting gate count. We expect that the design of an optimal cost function is architecture dependent and leave analysis to future work.

## C. Clifford tableau synthesis up-to-permutation

The last step of our algorithm is the synthesis of the Clifford tableau with the propagated Clifford gates. For this, we use an adaptation of the method proposed by [5]. We extend this algorithm to include the trick from [23] that allows us to synthesize the tableau up-to-permutation; emulating the movement of qubits on the quantum computers. Thus, the resulting circuit might have qubits that are moved to a different register than they were originally placed in. This is a normal phenomenon in quantum circuits that have been routed using SWAP gates and it allows us to reduce CNOT count.

Similar to the proposed algorithm, the Clifford tableau synthesis algorithm [5] uses a heuristic for picking which qubit to synthesize and remove from the problem. While the final Clifford tableau is typically an identity matrix, we can alternatively end the synthesis procedure when the Clifford tableau is a permutation matrix. The permutation then corresponds to a relocation of the qubits on the quantum computer. We do this by introducing a secondary heuristic for choosing which register (i.e. column in the tableau) the chosen qubit goes to, following the strategy from [23]. Lastly, we need to take care that the signs of the qubits are corrected on the new qubit register and not the old one.

When selecting the logical qubit (row), we choose the following heuristic:

̸

̸

̸

̸

$$\bar { h } _ { \text{row} } ( r ) & = \sum _ { i } \left [ \mathbb { I } ( T _ { r, i } \neq 0 \vee T _ { r, i + q } \neq 0 ) \quad \begin{array} { c } ^ { 2 } \text{Note} \\ \text{propagat} \\ \text{Our} \\ \text{pauliop} \end{array} \right ],$$

where T is a Clifford tableau, and q is the number of qubits. This heuristic favors the row with the fewest interactions. When choosing a physical qubit (column), we look for the shortest CNOT distance, which is approximated by summing up the distances of rows along the connectivity graph:

̸

̸

̸

$$h _ { \text{col} } ( c ) = & \sum _ { i } \left [ \mathbb { I } ( T _ { c, i } \neq 0 \vee T _ { c, i + q } \neq 0 ) \cdot d _ { c, i } \\ & + \mathbb { I } ( T _ { c + q, i } \neq 0 \vee T _ { c + q, i + q } \neq 0 ) \cdot d _ { c, i } \right ]$$

̸

Here d i,j , describes the shortest path between i and j , something which can be efficiently precomputed using the Floyd-Warshall algorithm [24, 25].

## D. Runtime Complexity Analysis

The following recurrence relation describes the worst-case runtime of our algorithm:

$$T ( n ) = \begin{cases} 1 & n = 0 \\ 4 T ( n - 1 ) + n q & \text{otherwise} \end{cases} \quad ( 1 3 )$$

where n is the number of gadgets in the Pauli polynomial, and q is the number of qubits. One can see that this is true since our method requires per step at most O ( nq ) many operations to compute the heuristics, reorder the gadgets, and propagate Clifford gates through the Pauli polynomial. Secondly, the worst case in splitting the Pauli polynomial is to select one gadget in one of the recursion steps and partition the rest to the others 2 . Furthermore, we can see that Equation 13 is bound by O ( n q 2 + q 4 ) , which yields the closed-form upper bound in terms of runtime. The term O ( q 4 ) arises from synthesizing the Clifford tableau [5].

## E. CNOT Complexity Analysis

Given that per n of the gadgets, at most q many CNOTs are required to synthesize it entirely, and given that there are at most n gadgets, a bound can be found from the fact that there are at most O ( nq ) CNOTs required to synthesize the whole Pauli polynomial. Since the remaining gadgets are collected in a Clifford tableau, which requires at most O ( q 2 ) many CNOTs among synthesis, we arrive at an overall overhead of O ( nq + q 2 ) CNOTs. We want to emphasize that this bound is quite naive since duplicates are canceled when propagating the CNOTs through the rest of the Pauli Polynomial. So the average bound might be much tighter as indicated by our evaluations.

## IV. EXPERIMENTS

We investigated the performance of the proposed methods on both architectures with all-to-all connectivity (refereed to as complete architectures) and restricted architectures, namely those available in the IBM Software stack . In our experiments, 3 we targeted the following IBM backends: quito (5 qubits), nairobi (7 qubits), guadalupe (16 qubits), mumbai (27 qubits), and ithaca (65 qubits).

2 Note that this would be equivalent to decomposing one gadget and propagating the gates throughout the rest of the Pauli polynomial.

3 Our implementation can be found on Github: https://github.com/daehiff/ pauliopt/tree/new\_methods.

All experiments were run using a process pool where each combination of circuit and synthesis strategy was distributed as tasks in a multi-threaded manner. Each synthesis strategy ran completely serially with no other innate parallelism.

For the randomized experiments, we synthesized 20 random Pauli polynomials with increasing gadget count for each architecture. The leg count was uniformly sampled from { 1 ..q } , where q is the size of the given architecture. The leg positions were randomly selected and its Pauli letter was uniformly sampled from { X,Y,Z } . The gadget angle was uniformly sampled from { π, π 2 , π 4 , π 8 , π 16 } .

Additionally, we synthesized the molecules present in pytket's UCCSD test set. These correspond to Hamiltonians used to estimate the ground state energy of small molecules and were used as benchmarks in [7, 26].

We compare the proposed methods against Paulihedral [6] and the UCCSD pair-wise and set-based synthesis methods in [8]. As a baseline, we included a naive Steiner tree-based decomposition which did not use any reordering. An additional routing step utilizing pytket [26] is used for methods that are not architecture-aware. To compare apples with apples, all circuits are synthesized to the gateset { CNOT , U 3 } and evaluated on CNOT count, circuit depth, and CNOT depth.

Since the gadget ordering found by our algorithm affects the Trotter error, we also calculated the Trotter error of all methods for random circuits and two molecules: H2 (in 631g with parity encoding) and H4 (in sto3g with parity encoding).

## A. Random Pauli polynomials

We present the average CNOT count, circuit depth, and two-qubit gate depth of the synthesized circuit in Figure 4 and Figure 5, for restricted and complete architectures respectively. For both cases, the proposed algorithm improves across the board for deep circuits (&gt;50 gadgets). We hypothesize that this is a consequence of collecting operations in a Clifford tableau, which avoids the construction of the full CNOT ladder (i.e. sequence of CNOTs) in gadget synthesis as we propagate the second half of the ladder through the remainder of the polynomial. Thus, subsequent gadgets can now produce transverse two-qubit gates. Interestingly, we see that for shallow circuits (&lt;50 gadgets), the proposed method performs worse on CNOT count, we attribute this to the greedy choosing of rows with large numbers of I legs, effectively routing rotations through long chains of I . Additionally, the proposed algorithm uses a naive initial placement of the qubits while both Paulihedral and TKET are able to find a better qubit mapping as a starting point for synthesis.

## B. UCCSD molecular ansatzes

Comparison of the three metrics for the various examined algorithms can be found in Table I, Table II, and Table III. In this experiment, we synthesized each molecule for the smallest IBM device that would fit the circuit. We applied a time-out of 60 minutes but we found that in some cases the threads had been suspended resulting in incorrect runtimes. For a fair

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00354v1-figure-ebb2d914-819d-4546-ac99-d8966d9eb972.jpg)

t

Fig. 3: Unitary overlap between the exact time evolution operator and the synthesized circuit for 20 random Pauli polynomials (aggregated) and the molecules H2\_P\_631g and H4\_P\_sto3g .

comparison, we decided to only present the molecules for which all methods finished and to omit runtime results.

From the tables, we can see that the proposed algorithm shows a clear improvement over the other examined methods; the only exception is the three smallest molecules. We hypothesize that this is, once again, due to the lack of qubit mapping and the greedy heuristic .

## C. Evaluation of the Trotter error

As the chosen ordering of Pauli gadgets is determined heuristically, the new order may increase the resulting Trotter error. Hence, we investigated the unitary overlap of the exact time evolution operator U exact = exp ( -i θ 2 H ) and the synthesized circuit U circuit , as in Equation 14:

$$\text{overlap} = \langle 0 | \, U _ { \text{exact} } U _ { \text{circuit} } ^ { \dagger } \, | 0 \rangle \, \text{ \quad \ \ } ( 1 4 )$$

We used 20 randomly generated Pauli polynomials with six qubits and 160 gadgets. Each gadget had uniformly distributed legs across the six qubits with a type in [ X,Y,Z ] . The rotation angle was uniformly sampled from: [ π / 32 , π / 64 , π / 128 ] . Additionally, we performed this investigation on molecules H2\_P\_631g and H4\_P\_sto3g from pytket's UCCSD test set [7]. For those molecules, we again picked the angles of the individual gadgets at random from the set [ π / 32 , π / 64 , π / 128 ] to facilitate a fair comparison among the experiments.

We examined the overlap for all cases over multiple timesteps in [0 : 2 π ] , and the results are plotted in Figure 3. We omit TKET UCCSD (pair) from the figure as it does not change the ordering of the Pauli gadgets and the Trotter error would be equal to that of naive synthesis. Across the various cases, we see that the proposed method is comparable to default Trotterization. Still, the best possible performance of each algorithm depends on the molecule's structure.

## V. CONCLUSION

In this work, we introduce a novel method for architectureaware Pauli polynomial synthesis, which propagates synthesized gates through the remainder of the polynomial. As a consequence, we introduce an alternative lexicographical grouping methodology that emerges from the structure of the

TABLE I: CNOT Count for different synthesis methods UCCSD molecule benchmark set on different IBM architectures. The smallest value in the row is in bold font.

| Molecule.     | Backend.   |   # Qubits. | Naive   | Paulihedral   | TKET (set)   | TKET (pair)   | Proposed   |
|---------------|------------|-------------|---------|---------------|--------------|---------------|------------|
| H2_P_sto3g    | quito      |           2 | 4       | 4             | 4            | 4             | 5          |
| H2_BK_sto3g   | quito      |           4 | 64      | 52            | 24           | 38            | 35         |
| H2_JW_sto3g   | quito      |           4 | 62      | 64            | 36           | 38            | 38         |
| H2_P_631g     | nairobi    |           6 | 1 190   | 1 056         | 671          | 1 086         | 433        |
| H4_P_sto3g    | nairobi    |           6 | 1 214   | 1 072         | 709          | 1 125         | 471        |
| H2_JW_631g    | guadalupe  |           8 | 894     | 783           | 458          | 691           | 414        |
| H2_BK_631g    | guadalupe  |           8 | 1 042   | 862           | 435          | 702           | 443        |
| H4_BK_sto3g   | guadalupe  |           8 | 2 042   | 1 697         | 1 532        | 1 613         | 878        |
| H4_JW_sto3g   | guadalupe  |           8 | 1 896   | 1 505         | 1 175        | 1 686         | 883        |
| NH_BK_sto3g   | guadalupe  |          12 | 12 660  | 7 231         | 9 299        | 11 164        | 4 788      |
| LiH_BK_sto3g  | guadalupe  |          12 | 11 210  | 8 681         | 8 682        | 10 980        | 4 250      |
| LiH_JW_sto3g  | guadalupe  |          12 | 10 108  | 7 858         | 5 793        | 8 149         | 4 331      |
| NH_JW_sto3g   | guadalupe  |          12 | 12 880  | 7 645         | 5 779        | 9 089         | 4 884      |
| H2O_P_sto3g   | guadalupe  |          12 | 19 218  | 12 381        | 17 527       | 20 089        | 8 077      |
| BeH2_P_sto3g  | guadalupe  |          12 | 19 950  | 12 405        | 18 717       | 19 761        | 8 482      |
| CH2_P_sto3g   | guadalupe  |          12 | 38 344  | 22 345        | 32 667       | 40 180        | 14 909     |
| H2O_JW_sto3g  | guadalupe  |          14 | 19 668  | 12 816        | 11 193       | 17 362        | 7 967      |
| H2O_BK_sto3g  | guadalupe  |          14 | 23 986  | 14 417        | 19 585       | 23 090        | 8 675      |
| CH2_BK_sto3g  | guadalupe  |          14 | 34 352  | 20 890        | 35 847       | 35 106        | 12 919     |
| BeH2_JW_sto3g | guadalupe  |          14 | 27 602  | 20 315        | 19 296       | 25 952        | 12 181     |
| BeH2_BK_sto3g | guadalupe  |          14 | 30 786  | 22 887        | 34 138       | 35 030        | 12 419     |
| CH2_JW_sto3g  | guadalupe  |          14 | 31 244  | 19 913        | 17 744       | 25 863        | 13 433     |
| H4_P_631g     | guadalupe  |          14 | 58 612  | 36 203        | 38 959       | 61 530        | 24 224     |
| H4_JW_631g    | mumbai     |          16 | 26 382  | 21 083        | 15 012       | 25 416        | 11 727     |
| H4_BK_631g    | mumbai     |          16 | 29 146  | 23 136        | 22 365       | 26 366        | 13 852     |
| NH3_JW_sto3g  | mumbai     |          16 | 46 902  | 33 483        | 35 769       | 49 657        | 23 182     |
| NH3_BK_sto3g  | mumbai     |          16 | 57 254  | 35 990        | 56 862       | 63 328        | 25 280     |
| HCl_JW_sto3g  | mumbai     |          20 | 19 854  | 9 430         | 9 780        | 13 108        | 5 807      |
| HCl_BK_sto3g  | mumbai     |          20 | 21 746  | 9 867         | 10 571       | 13 499        | 6 306      |

proposed algorithm. We additionally describe an extension to the architecture-aware synthesis introduced in [5] that allows Clifford tableau synthesis up-to-permutation. We observe that the introduced method outperforms other examined methods on both restricted and complete architectures and, for the small set of test cases observed, does not seem to introduce significant Trotter error when compared with similar algorithms.

Although investigation of the Trotter error associated with the proposed method is preliminary, we note that the error introduced by the noisy gates in the resulting circuits of alternative methods vastly outweighs the potential difference in Trotter error in cases where the proposed method worsens Trotter error. Considering the scale of improvement in gate counts and depth as observed with our method, reducing Trotter error will become a factor in fault tolerant devices.

workstation for the largest, deepest circuits in our experiments. Although this can be partially attributed to unoptimized python code, algorithmic improvements may be necessary for future larger devices. Methodologies such as 'parallel-in-time' may be interesting to investigate if the cost of propagated Clifford tableaus through synthesized regions is low and does not impact performance significantly. The current algorithm can also beextended to support the synthesis of higher-order symmetric product formulas mentioned in [14] or other higher-order decompositions [28, 29, 30]. Additionally, the algorithm can be represented as row additions in a 2 q × g matrix, where q is the number of qubits and g the number of Pauli gadgets, which suggests that an efficient GPU implementation is possible.

Nevertheless, there are several areas for future improvement. One key weakness of our introduced algorithm is the cost function for pivot selection; for shallow regions, it removes interactions inefficiently. This means that the final recursions in the algorithm likely introduce unnecessary two-qubit operations. This can be addressed by improving or tuning the cost function or by introducing methods such as reverse traversal [27] to improve the initial qubit mapping. The current algorithm also does not find a good qubit placement during synthesis, incorporating a scheme similar to PermRowCol may be further improve its overall performance.

We additionally note that the time to solution for the proposed method is not ideal, taking up to 30 minutes on a local

In summary, the architecture-aware synthesis of Pauli gadgets offers a powerful alternative to existing methods to synthesize Pauli-based product formulas on restricted architectures; architecture-conforming algorithms reduce routing overhead tremendously, a key step to enable effective quantum hardware usage in the near term.

TABLE II: Circuit depth for different synthesis methods UCCSD molecule benchmark set on different IBM architectures. The smallest value in the row is in bold font.

| Molecule.     | Backend.   |   # Qubits. | Naive   | Paulihedral   | TKET (set)   | TKET (pair)   | Proposed   |
|---------------|------------|-------------|---------|---------------|--------------|---------------|------------|
| H2_P_sto3g    | quito      |           2 | 9       | 9             | 9            | 8             | 4          |
| H2_BK_sto3g   | quito      |           4 | 85      | 76            | 42           | 68            | 47         |
| H2_JW_sto3g   | quito      |           4 | 87      | 87            | 55           | 75            | 53         |
| H2_P_631g     | nairobi    |           6 | 1 461   | 1 150         | 646          | 1 143         | 444        |
| H4_P_sto3g    | nairobi    |           6 | 1 497   | 1 170         | 680          | 1 181         | 466        |
| H2_JW_631g    | guadalupe  |           8 | 908     | 783           | 496          | 815           | 339        |
| H2_BK_631g    | guadalupe  |           8 | 979     | 796           | 423          | 786           | 369        |
| H4_BK_sto3g   | guadalupe  |           8 | 1 814   | 1 667         | 1 316        | 1 669         | 656        |
| H4_JW_sto3g   | guadalupe  |           8 | 1 851   | 1 449         | 950          | 1 590         | 677        |
| NH_BK_sto3g   | guadalupe  |          12 | 10 742  | 6 494         | 6 685        | 9 463         | 2 986      |
| LiH_BK_sto3g  | guadalupe  |          12 | 9 659   | 6 812         | 6 213        | 9 690         | 2 760      |
| LiH_JW_sto3g  | guadalupe  |          12 | 9 219   | 6 926         | 4 278        | 7 813         | 2 944      |
| NH_JW_sto3g   | guadalupe  |          12 | 11 390  | 6 480         | 4 338        | 8 612         | 3 145      |
| H2O_P_sto3g   | guadalupe  |          12 | 16 365  | 9 627         | 11 470       | 15 340        | 4 655      |
| BeH2_P_sto3g  | guadalupe  |          12 | 16 977  | 10 179        | 11 822       | 15 450        | 5 053      |
| CH2_P_sto3g   | guadalupe  |          12 | 32 899  | 18 201        | 21 278       | 31 610        | 9 049      |
| H2O_JW_sto3g  | guadalupe  |          14 | 18 907  | 11 074        | 8 295        | 15 770        | 4 420      |
| H2O_BK_sto3g  | guadalupe  |          14 | 20 285  | 11 989        | 13 347       | 19 074        | 4 616      |
| CH2_BK_sto3g  | guadalupe  |          14 | 29 604  | 17 397        | 22 198       | 27 314        | 7 361      |
| BeH2_JW_sto3g | guadalupe  |          14 | 25 671  | 16 772        | 12 702       | 22 939        | 7 061      |
| BeH2_BK_sto3g | guadalupe  |          14 | 26 175  | 17 404        | 21 184       | 27 319        | 6 749      |
| CH2_JW_sto3g  | guadalupe  |          14 | 28 816  | 16 954        | 11 872       | 22 688        | 7 525      |
| H4_P_631g     | guadalupe  |          14 | 49 277  | 28 669        | 25 782       | 47 166        | 12 722     |
| H4_JW_631g    | mumbai     |          16 | 25 820  | 17 934        | 10 752       | 23 024        | 6 390      |
| H4_BK_631g    | mumbai     |          16 | 26 139  | 16 739        | 15 712       | 22 429        | 5 707      |
| NH3_JW_sto3g  | mumbai     |          16 | 45 910  | 28 846        | 23 085       | 40 676        | 9 734      |
| NH3_BK_sto3g  | mumbai     |          16 | 49 835  | 28 640        | 34 055       | 46 464        | 10 121     |
| HCl_JW_sto3g  | mumbai     |          20 | 16 055  | 8 452         | 7 829        | 11 069        | 3 029      |
| HCl_BK_sto3g  | mumbai     |          20 | 18 055  | 7 901         | 8 449        | 11 116        | 3 113      |

TABLE III: 2 qubit gate depth for different synthesis methods UCCSD molecule benchmark set on different IBM architectures. The smallest value in the row is in bold font.

| Molecule.     | Backend.   |   # Qubits. | Naive   | Paulihedral   | TKET (set)   | TKET (pair)   | Proposed   |
|---------------|------------|-------------|---------|---------------|--------------|---------------|------------|
| H2_P_sto3g    | quito      |           2 | 4       | 4             | 4            | 4             | 3          |
| H2_BK_sto3g   | quito      |           4 | 64      | 52            | 24           | 38            | 35         |
| H2_JW_sto3g   | quito      |           4 | 62      | 64            | 36           | 38            | 38         |
| H2_P_631g     | nairobi    |           6 | 1 172   | 872           | 517          | 893           | 332        |
| H4_P_sto3g    | nairobi    |           6 | 1 196   | 884           | 549          | 923           | 344        |
| H2_JW_631g    | guadalupe  |           8 | 739     | 619           | 381          | 560           | 272        |
| H2_BK_631g    | guadalupe  |           8 | 822     | 607           | 330          | 572           | 301        |
| H4_BK_sto3g   | guadalupe  |           8 | 1 518   | 1 316         | 1 113        | 1 231         | 523        |
| H4_JW_sto3g   | guadalupe  |           8 | 1 532   | 1 112         | 815          | 1 159         | 552        |
| NH_BK_sto3g   | guadalupe  |          12 | 9 552   | 5 250         | 5 937        | 7 791         | 2 433      |
| LiH_BK_sto3g  | guadalupe  |          12 | 8 476   | 5 488         | 5 516        | 8 010         | 2 261      |
| LiH_JW_sto3g  | guadalupe  |          12 | 7 959   | 5 672         | 3 665        | 6 005         | 2 385      |
| NH_JW_sto3g   | guadalupe  |          12 | 10 130  | 5 195         | 3 712        | 6 830         | 2 608      |
| H2O_P_sto3g   | guadalupe  |          12 | 14 429  | 7 893         | 10 570       | 13 450        | 4 015      |
| BeH2_P_sto3g  | guadalupe  |          12 | 15 012  | 8 241         | 10 994       | 13 435        | 4 372      |
| CH2_P_sto3g   | guadalupe  |          12 | 29 062  | 14 602        | 19 596       | 27 773        | 7 740      |
| H2O_JW_sto3g  | guadalupe  |          14 | 16 941  | 9 112         | 7 205        | 12 912        | 3 683      |
| H2O_BK_sto3g  | guadalupe  |          14 | 18 572  | 10 000        | 12 128       | 16 404        | 3 877      |
| CH2_BK_sto3g  | guadalupe  |          14 | 26 998  | 14 388        | 20 581       | 23 437        | 6 182      |
| BeH2_JW_sto3g | guadalupe  |          14 | 22 751  | 13 953        | 11 345       | 18 938        | 5 908      |
| BeH2_BK_sto3g | guadalupe  |          14 | 23 501  | 14 489        | 19 583       | 23 515        | 5 628      |
| CH2_JW_sto3g  | guadalupe  |          14 | 25 891  | 14 032        | 10 520       | 18 618        | 6 398      |
| H4_P_631g     | guadalupe  |          14 | 44 163  | 23 662        | 23 556       | 41 739        | 10 984     |
| H4_JW_631g    | mumbai     |          16 | 23 012  | 15 236        | 9 246        | 18 842        | 5 267      |
| H4_BK_631g    | mumbai     |          16 | 23 576  | 14 038        | 14 132       | 18 558        | 4 585      |
| NH3_JW_sto3g  | mumbai     |          16 | 41 306  | 24 436        | 20 783       | 34 266        | 7 937      |
| NH3_BK_sto3g  | mumbai     |          16 | 45 843  | 23 905        | 31 523       | 40 274        | 8 400      |
| HCl_JW_sto3g  | mumbai     |          20 | 14 686  | 7 195         | 6 785        | 9 104         | 2 677      |
| HCl_BK_sto3g  | mumbai     |          20 | 16 773  | 6 623         | 7 475        | 9 165         | 2 720      |

10

10

10

10

10

5

4

3

2

1

Paulihedral

CNOT count

Naive Steiner tree decomp.

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00354v1-figure-f646d865-6369-43aa-8610-cfbb08c8e58f.jpg)

TKET UCCSD (set)

Circuit depth

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00354v1-figure-a9f3e536-bd5b-4403-a207-58868144f699.jpg)

CNOT count

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00354v1-figure-96f006e1-dbbb-4dbc-8fbf-e64b2f6d7c2f.jpg)

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00354v1-figure-3e18a9a6-6e6f-4c61-9d6a-2a81ccdaeaaf.jpg)

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00354v1-figure-ec75f31f-2a82-4bc6-a257-6286d943ae96.jpg)

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00354v1-figure-0bdeeddb-2f33-4e7a-b63c-06791155b12e.jpg)

Paulihedral

Naive Steiner tree decomp.

CNOT depth

(a) Quito (5 Qubits) Circuit depth

(b) Nairobi (7 Qubits) Circuit depth

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00354v1-figure-8f8e5f5c-2683-4ef2-8746-b8cff3e25234.jpg)

TKET UCCSD (pair)

Proposed

CNOT\_depth

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00354v1-figure-c3f139e1-9d22-4ca1-ab3d-db46be03850d.jpg)

CNOT depth

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00354v1-figure-4f447b18-a863-42c5-b7d9-812fbc338e17.jpg)

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00354v1-figure-3e954a1e-0be2-413e-a475-f26a51cb777a.jpg)

(c) Guadalupe (16 Qubits) Circuit depth

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00354v1-figure-079bc365-9f12-40e5-bbe9-898f856171c5.jpg)

TKET UCCSD (set)

TKET UCCSD (pair)

CNOT depth

CNOT depth

Proposed

300

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00354v1-figure-30d655d1-20b2-410c-b46a-ceca87d5118e.jpg)

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00354v1-figure-496a9cb9-8257-417b-b6de-c017d9e802bc.jpg)

(d) Mumbai (27 Qubits) Circuit depth

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00354v1-figure-f0d8a2d8-76f3-4528-b4f5-d0820f509bde.jpg)

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00354v1-figure-06b9e0b8-bda3-44b8-ab73-5b758b518a55.jpg)

(e) Ithaca (65 Qubits)

Fig. 4: Comparison of examined synthesis methods on CNOT count, circuit depth and 2-qubit gate depth for different IBM quantum computers.

10

10

10

10

10

5

4

3

2

1

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00354v1-figure-cfcedb24-4112-4338-a3fc-f2d2c684d9b6.jpg)

(e) Complete (65 Qubits)

Fig. 5: The performance of the different synthesis methods on different metric for different size architectures with all-to-all connectivity (complete).

## REFERENCES

- [1] A. Anand, P. Schleich, S. Alperin-Lea, P. W. K. Jensen, S. Sim, M. Díaz-Tinoco, J. S. Kottmann, M. Degroote, A. F. Izmaylov, and A. Aspuru-Guzik, 'A quantum computing view on unitary coupled cluster theory,' Chemical Society Reviews , vol. 51, no. 5, p. 1659-1684, 2022. [Online]. Available: http://dx.doi.org/10.1039/D1CS00932J
- [2] A. W. Harrow, A. Hassidim, and S. Lloyd, 'Quantum algorithm for linear systems of equations,' Physical Review Letters , vol. 103, no. 15, Oct. 2009. [Online]. Available: http://dx.doi.org/10.1103/PhysRevLett.103.150502
- [3] M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information: 10th Anniversary Edition . Cambridge University Press, Jun. 2012. [Online]. Available: http://dx.doi.org/10.1017/CBO9780511976667
- [4] A. M. Childs and N. Wiebe, 'Hamiltonian simulation using linear combinations of unitary operations,' Quantum Information &amp; Computation , vol. 12, no. 11-12, pp. 901924, 2012.
- [5] D. Winderl, Q. Huang, A. M.-v. de Griend, and R. Yeung, 'Architecture-Aware Synthesis of Stabilizer Circuits from Clifford Tableaus,' 2023. [Online]. Available: https://arxiv.org/abs/2309.08972
- [6] G. Li, A. Wu, Y. Shi, A. Javadi-Abhari, Y. Ding, and Y. Xie, 'Paulihedral: a generalized block-wise compiler optimization framework for quantum simulation kernels,' in Proceedings of the 27th ACM International Conference on Architectural Support for Programming Languages and Operating Systems , ser. ASPLOS '22. ACM, Feb. 2022. [Online]. Available: http: //dx.doi.org/10.1145/3503222.3507715
- [7] A. Cowtan, W. Simmons, and R. Duncan, 'A Generic Compilation Strategy for the Unitary Coupled Cluster Ansatz,' 2020. [Online]. Available: https: //arxiv.org/abs/2007.10515
- [8] A. Cowtan, S. Dilkes, R. Duncan, W. Simmons, and S. Sivarajah, 'Phase Gadget Synthesis for Shallow Circuits,' Electronic Proceedings in Theoretical Computer Science , vol. 318, p. 213-228, May 2020. [Online]. Available: http://dx.doi.org/10.4204/EPTCS.318.13
- [9] R. Yeung, 'Diagrammatic Design and Study of Ansätze for Quantum Machine Learning,' 2020. [Online]. Available: https://arxiv.org/abs/2011.11073
- [10] J. van de Wetering, 'ZX-calculus for the working quantum computer scientist,' 2020. [Online]. Available: https://arxiv.org/abs/2012.13966
- [11] H. R. Grimsley, D. Claudino, S. E. Economou, E. Barnes, and N. J. Mayhall, 'Is the Trotterized UCCSD Ansatz Chemically Well-Defined?' Journal of Chemical Theory and Computation , vol. 16, no. 1, p. 1-6, Dec. 2019. [Online]. Available: http://dx.doi.org/10.1021/acs.jctc.9b01083
- [12] M. B. Hastings, D. Wecker, B. Bauer, and M. Troyer, 'Improving Quantum Algorithms for Quantum Chemistry,'
- 2014. [Online]. Available: https://arxiv.org/abs/1403.1539
- [13] A. Tranter, P. J. Love, F. Mintert, and P. V. Coveney, 'A Comparison of the Bravyi-Kitaev and Jordan-Wigner Transformations for the Quantum Simulation of Quantum Chemistry,' Journal of Chemical Theory and Computation , vol. 14, no. 11, p. 5617-5630, Sep. 2018. [Online]. Available: http://dx.doi.org/10.1021/acs.jctc.8b00450
- [14] T. Tomesh, K. Gui, P. Gokhale, Y. Shi, F. T. Chong, M. Martonosi, and M. Suchara, 'Optimized Quantum Program Execution Ordering to Mitigate Errors in Simulations of Quantum Systems,' in 2021 International Conference on Rebooting Computing (ICRC) . IEEE, Nov. 2021. [Online]. Available: http: //dx.doi.org/10.1109/ICRC53822.2021.00013
- [15] G. H. Low, V. Kliuchnikov, and N. Wiebe, 'Wellconditioned multiproduct Hamiltonian simulation,' 2019. [Online]. Available: https://arxiv.org/abs/1907.11679
- [16] M. Amy, P. Azimzadeh, and M. Mosca, 'On the controlled-NOT complexity of controlled-NOT-phase circuits,' Quantum Science and Technology , vol. 4, no. 1, p. 015002, Sep. 2018. [Online]. Available: http://dx.doi.org/10.1088/2058-9565/aad8ca
- [17] F. Gray, 'Pulse code communication,' 1953, uS Patent 2,632,058. [Online]. Available: http://www.google.com/ patents/US2632058
- [18] A. Meijer-van de Griend and R. Duncan, 'ArchitectureAware Synthesis of Phase Polynomials for NISQ Devices,' Electronic Proceedings in Theoretical Computer Science , vol. 394, p. 116-140, Nov. 2023. [Online]. Available: http://dx.doi.org/10.4204/EPTCS.394.8
- [19] S. Aaronson and D. Gottesman, 'Improved simulation of stabilizer circuits,' Physical Review A , vol. 70, no. 5, Nov. 2004. [Online]. Available: http://dx.doi.org/10.1103/ PhysRevA.70.052328
- [20] B. Wu, X. He, S. Yang, L. Shou, G. Tian, J. Zhang, and X. Sun, 'Optimization of CNOT circuits on limitedconnectivity architecture,' Physical Review Research , vol. 5, no. 1, jan 2023. [Online]. Available: https: //doi.org/10.1103%2Fphysrevresearch.5.013065
- [21] E. Van Den Berg, 'A simple method for sampling random Clifford operators,' in 2021 IEEE International Conference on Quantum Computing and Engineering (QCE) . IEEE, Oct. 2021. [Online]. Available: http: //dx.doi.org/10.1109/QCE52317.2021.00021
- [22] C. Gidney, 'Stim: a fast stabilizer circuit simulator,' Quantum , vol. 5, p. 497, Jul. 2021. [Online]. Available: http://dx.doi.org/10.22331/q-2021-07-06-497
- [23] A. Meijer-van de Griend and S. M. Li, 'Dynamic Qubit Routing with CNOT Circuit Synthesis for Quantum Compilation,' Electronic Proceedings in Theoretical Computer Science , vol. 394, p. 363-399, Nov. 2023. [Online]. Available: http://dx.doi.org/10.4204/EPTCS.394. 18
- [24] R. W. Floyd, 'Algorithm 97: Shortest path,' Communications of the ACM , vol. 5, no. 6,
- p. 345-345, Jun. 1962. [Online]. Available: http://dx.doi.org/10.1145/367766.368168
- [25] S. Warshall, 'A Theorem on Boolean Matrices,' Journal of the ACM , vol. 9, no. 1, p. 11-12, Jan. 1962. [Online]. Available: http://dx.doi.org/10.1145/321105.321107
- [26] S. Sivarajah, S. Dilkes, A. Cowtan, W. Simmons, A. Edgington, and R. Duncan, 't|ket 〉 : a retargetable compiler for NISQ devices,' Quantum Science and Technology , vol. 6, no. 1, p. 014003, Nov. 2020. [Online]. Available: http://dx.doi.org/10.1088/2058-9565/ab8e92
- [27] G. Li, Y. Ding, and Y. Xie, 'Tackling the Qubit Mapping Problem for NISQ-Era Quantum Devices,' in Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems , ser. ASPLOS '19. ACM, Apr. 2019. [Online]. Available: http: //dx.doi.org/10.1145/3297858.3304023
- [28] A. M. Childs, Y. Su, M. C. Tran, N. Wiebe, and S. Zhu, 'Theory of Trotter Error with Commutator Scaling,' Physical Review X , vol. 11, no. 1, Feb. 2021. [Online]. Available: http://dx.doi.org/10.1103/PhysRevX.11.011020
- [29] J. Ostmeyer, 'Optimised Trotter decompositions for classical and quantum computing,' Journal of Physics A: Mathematical and Theoretical , vol. 56, no. 28, p. 285303, jun 2023. [Online]. Available: https: //dx.doi.org/10.1088/1751-8121/acde7a
- [30] G. H. Low, Y. Su, Y. Tong, and M. C. Tran, 'Complexity of Implementing Trotter Steps,' PRX Quantum , vol. 4, no. 2, May 2023. [Online]. Available: http://dx.doi.org/10.1103/PRXQuantum.4.020323
Qunsheng Huang David Winderl Arianne Meijer-van de Griend Richie Yeung
Redefining Lexicographical Ordering: Optimizing Pauli String Decompositions for Quantum Compiling
In quantum computing, the efficient optimization of Pauli string
decompositions is a crucial aspect for the compilation of quantum circuits for
many applications, such as chemistry simulations and quantum machine learning.
In this paper, we propose a novel algorithm for the synthesis of trotterized
time-evolution operators that results in circuits with significantly fewer
gates than previous solutions. Our synthesis procedure takes the qubit
connectivity of a target quantum computer into account. As a result, the
generated quantum circuit does not require routing, and no additional CNOT
gates are needed to run the resulting circuit on a target device. We compare
our algorithm against Paulihedral and TKET, and show a significant improvement
for randomized circuits and different molecular ansatzes. We also investigate
the Trotter error introduced by our ordering of the terms in the Hamiltonian
versus default ordering and the ordering from the baseline methods and conclude
that our method on average does not increase the Trotter error.