Shortest Path in Pauli Forest -- An Algorithm for Decomposing Pauli Exponentials to Quantum Circuits

Arianne Meijer-van de Griend, Lauri Vuorenkoski

Authors on Pith no claims yet

Pith reviewed 2026-05-07 17:29 UTC · model grok-4.3

classification 🪐 quant-ph

keywords Pauli exponentialsquantum circuit synthesisCNOT optimizationqubit placementmolecular ansatzePauli forestcircuit decomposition

0 comments

The pith

The Shortest Path in Pauli Forest algorithm decomposes Pauli exponentials into quantum circuits with fewer CNOT gates by also choosing optimal initial qubit placement on the device.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces an algorithm to turn Pauli exponentials, which appear in many quantum algorithms, into quantum circuits that fit the connectivity of actual hardware. It models the task as finding shortest paths inside a Pauli forest structure and uses that search to pick the best starting positions for each qubit. If the method works as described, it produces circuits with lower total CNOT count and faster synthesis times on the tested examples. This matters because CNOT gates are the dominant error source on current devices, so any reliable reduction helps make algorithms like molecular simulation more practical.

Core claim

The Shortest Path in Pauli Forest algorithm performs architecture-aware synthesis of Pauli exponentials while simultaneously solving for the initial qubit placement; on random Pauli exponentials and on molecular ansatze it produces circuits with lower CNOT count and shorter runtime than prior synthesis techniques.

What carries the argument

The Shortest Path in Pauli Forest algorithm, which reduces the decomposition problem to a shortest-path search over a forest whose nodes are Pauli strings and whose edges reflect allowed two-qubit interactions on the target device.

Load-bearing premise

The reported reductions in CNOT count and runtime generalize beyond the specific random Pauli exponentials and molecular ansatze examined on the chosen device connectivities.

What would settle it

A side-by-side count of CNOT gates on a fresh collection of Pauli exponentials drawn from larger molecular Hamiltonians, using the identical device topology and the same baseline synthesis methods, that shows no consistent advantage for the new algorithm.

Figures

Figures reproduced from arXiv: 2605.03545 by Arianne Meijer-van de Griend, Lauri Vuorenkoski.

**Figure 1.** Figure 1: Example of the decomposition of a single Pauli gadget restricted to view at source ↗

**Figure 2.** Figure 2: Example of optimal mapping with line topology 0-1-2-3. view at source ↗

**Figure 3.** Figure 3: Example of connectivity tree constructed on 16-grid topology. view at source ↗

**Figure 4.** Figure 4: Example of gadget mapped to tree before pruning. view at source ↗

**Figure 5.** Figure 5: Results on line topology with 16 qubits. Lexicographical ordering view at source ↗

**Figure 9.** Figure 9: Results on 16 qubit Pauli exponentials mapped to 127 qubit Brisbane view at source ↗

**Figure 8.** Figure 8: Time taken by algorithms in different topologies. Lexicographical view at source ↗

read the original abstract

Decomposing Pauli exponentials efficiently to quantum circuits has been the subject of intense research in recent years. Pauli exponentials are an essential component of many different quantum algorithms. Due to the error-prone nature of current and near term quantum devices, it is crucial that quantum circuits are as compact as possible. Several different types of algorithms have been developed to decompose Pauli exponentials into as short circuits as possible. We propose a novel algorithm for architecture-aware synthesis of Pauli exponentials that also determines the initial qubit placement on the device. We call this the Shortest Path in Pauli Forest algorithm. The results show an improved CNOT count and runtime for both random Pauli exponentials and molecular ans\"atze.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The Shortest Path in Pauli Forest algorithm folds qubit placement into Pauli exponential synthesis and claims CNOT/runtime gains, but those gains rest on unspecified baselines.

read the letter

The paper's main move is to treat decomposition of Pauli exponentials and initial qubit placement as a single shortest-path problem on a structure they call the Pauli forest. This is a reasonable way to avoid the usual two-stage pipeline where synthesis ignores the device graph and routing then adds extra CNOTs. For people compiling variational quantum algorithms or Trotterized Hamiltonians, that joint optimization is the practical point worth noticing.

Circularity Check

0 steps flagged

No circularity: algorithmic proposal with independent empirical validation

full rationale

The paper introduces a new algorithm (Shortest Path in Pauli Forest) for architecture-aware synthesis of Pauli exponentials and reports empirical improvements in CNOT count and runtime on random instances and molecular ansätze. No derivation chain exists that reduces a claimed result to its own inputs by construction, self-definition, or load-bearing self-citation. The central claims rest on the algorithm's description and experimental comparisons, which are presented as independent outputs rather than tautological renamings or fitted predictions. This is a standard self-contained algorithmic contribution with no detectable circular steps.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

No information on free parameters, axioms, or invented entities is available from the abstract alone; full manuscript required to audit these elements.

pith-pipeline@v0.9.0 · 5423 in / 1234 out tokens · 70960 ms · 2026-05-07T17:29:55.069402+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Reference graph

Works this paper leans on

16 extracted references · 15 canonical work pages · 1 internal anchor

[1]

Quantum computing in the NISQ era and beyond.Quantum, 2:79, 2018

J. Preskill, “Quantum Computing in the NISQ era and beyond,” Quantum, vol. 2, p. 79, Aug. 2018, arXiv:1801.00862 [quant-ph]. [Online]. Available: http://arxiv.org/abs/1801.00862

work page internal anchor Pith review arXiv 2018
[2]

Decoherence, the measurement problem, and interpretations of quantum mechanics

M. Schlosshauer, “Decoherence, the measurement problem, and interpretations of quantum mechanics,”Reviews of Modern Physics, vol. 76, no. 4, pp. 1267–1305, Feb. 2005, publisher: American Physical Society. [Online]. Available: https://link.aps.org/doi/10.1103/RevModPhys.76.1267

work page Pith review doi:10.1103/revmodphys.76.1267 2005
[3]

Error- Divisible Two-Qubit Gates,

D. R. P ´erez, P. Varosy, Z. Li, T. Roy, E. Kapit, and D. Schuster, “Error- Divisible Two-Qubit Gates,”Physical Review Applied, vol. 19, no. 2, p. 024043, Feb. 2023, publisher: American Physical Society. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevApplied.19.024043

work page doi:10.1103/physrevapplied.19.024043 2023
[4]

Tackling the Qubit Mapping Problem for NISQ-Era Quantum Devices,

G. Li, Y . Ding, and Y . Xie, “Tackling the Qubit Mapping Problem for NISQ-Era Quantum Devices,” inProceedings of the Twenty-F ourth International Conference on Architectural Support for Programming Languages and Operating Systems. Providence RI USA: ACM, Apr. 2019, pp. 1001–1014. [Online]. Available: https://dl.acm.org/doi/10.1145/3297858.3304023

work page doi:10.1145/3297858.3304023 2019
[5]

Phase Gadget Synthesis for Shallow Circuits,

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, pp. 213– 228, May 2020, arXiv:1906.01734 [quant-ph]. [Online]. Available: http://arxiv.org/abs/1906.01734

work page arXiv 2020
[6]

Faster and shorter synthesis of Hamiltonian simulation circuits,

T. G. d. Brugi `ere and S. Martiel, “Faster and shorter synthesis of Hamiltonian simulation circuits,” Apr. 2024, arXiv:2404.03280 [quant-ph]. [Online]. Available: http://arxiv.org/abs/2404.03280

work page arXiv 2024
[7]

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

Q. Huang, D. Winderl, A. Meijer-van de Griend, and R. Yeung, “Redefining Lexicographical Ordering: Optimizing Pauli String Decompositions for Quantum Compiling,” in2024 IEEE International Conference on Quantum Computing and Engineering (QCE), vol. 01, Sep. 2024, pp. 885–896. [Online]. Available: https://ieeexplore.ieee.org/document/10821336/?arnumber=10821336

work page arXiv 2024
[8]

Paulihedral: a generalized block-wise compiler optimization framework for Quantum simulation kernels,

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,” inProceedings of the 27th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, ser. ASPLOS ’22. New York, NY , USA: Association for Computi...

work page doi:10.1145/3503222.3507715 2022
[9]

Graph Optimization Perspective for Low-Depth Trotter-Suzuki Decomposition,

A. T. Schmitz, N. P. D. Sawaya, S. Johri, and A. Y . Matsuura, “Graph Optimization Perspective for Low-Depth Trotter-Suzuki Decomposition,” May 2023, arXiv:2103.08602 [quant-ph]. [Online]. Available: http://arxiv.org/abs/2103.08602

work page arXiv 2023
[10]

Cowtan, W

A. Cowtan, W. Simmons, and R. Duncan, “A Generic Compilation Strategy for the Unitary Coupled Cluster Ansatz,” Aug. 2020, arXiv:2007.10515 [quant-ph]. [Online]. Available: http://arxiv.org/abs/2007.10515

work page arXiv 2020
[11]

Improved simulation of stabilizer circuits.Physical Review A, 70(5), 2004

S. Aaronson and D. Gottesman, “Improved simulation of stabilizer cir- cuits,”Physical Review A, vol. 70, no. 5, p. 052328, Nov. 2004. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevA.70.052328

work page doi:10.1103/physreva.70.052328 2004
[12]

Architecture-Aware Synthesis of Stabilizer Circuits from Clifford Tableaus,

D. Winderl, Q. Huang, A. M.-v. d. Griend, and R. Yeung, “Architecture-Aware Synthesis of Stabilizer Circuits from Clifford Tableaus,” Oct. 2024, arXiv:2309.08972. [Online]. Available: http://arxiv.org/abs/2309.08972

work page arXiv 2024
[13]

Circuit optimization of Hamiltonian simulation by simultaneous diagonalization of Pauli clusters,

E. v. d. Berg and K. Temme, “Circuit optimization of Hamiltonian simulation by simultaneous diagonalization of Pauli clusters,”Quantum, vol. 4, p. 322, Sep. 2020, arXiv:2003.13599 [quant-ph]. [Online]. Available: http://arxiv.org/abs/2003.13599

work page arXiv 2020
[14]

On the controlled-NOT complexity of controlled-NOT–phase circuits,

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: https://iopscience.iop.org/article/10.1088/2058-9565/aad8ca

work page doi:10.1088/2058-9565/aad8ca 2018
[15]

PauliForest: Connectivity-Aware Synthesis and Pauli-Oriented Qubit Mapping for Near-Term Quantum Simulation,

Y . Li, Y . Zhang, H. Deng, M. Chen, and Z. Li, “PauliForest: Connectivity-Aware Synthesis and Pauli-Oriented Qubit Mapping for Near-Term Quantum Simulation,”IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 44, no. 6, pp. 2119–2129, Jun. 2025. [Online]. Available: https://ieeexplore.ieee.org/abstract/document/10771974

work page arXiv 2025
[16]

Phase polyno- mials synthesis algorithms for nisq architectures and beyond,

V . Vandaele, S. Martiel, and T. Goubault de Brugi `ere, “Phase polyno- mials synthesis algorithms for nisq architectures and beyond,”Quantum Science & Technology, vol. 7, no. 4, p. 045027, 2022. TABLE I RESULTS ONUCCSDMOLECULAR ANS ¨ATZE. CNOT count CNOT depth Ansatzs Backend Qubits Gadgets SPPF LO diff % SPPF LO diff % time diff. % H2 BK sto3g quito 4 1...

2022