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

• URL: http://arxiv.org/abs/2605.03545v1
• Date: Tue, 05 May 2026 09:16:29 GMT
• Title: Shortest Path in Pauli Forest -- An Algorithm for Decomposing Pauli Exponentials to Quantum Circuits
• Abstract summary: We propose a novel algorithm for architecture-aware synthesis of Pauli exponentials.<n>The results show an improved CNOT count and runtime for both random Pauli exponentials and molecular anstze.
• Score: 1.7188280334580195
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• 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ätze.

Related papers

• Verifiable quantum advantage in extremely low depth [52.51019642214249]
  We give a problem that is solvable by shallow quantum circuits, hard for computation in time under lattice-based assumptions.<n>We prove that shallow quantum circuits have sufficient structure to solve certain classically hard tasks whose solutions can be verified efficiently.
  arXiv  Detail & Related papers  (2026-09-01T15:54:34Z)
• PauliEngine: High-Performant Symbolic Arithmetic for Quantum Operations [39.36424353588699]
  We introduce PauliEngine, a high-performance C++ framework that provides efficient primitives for Pauli string, commutators, symbolic phase tracking, and structural transformations.<n>PauliEngine supports both numerical and symbolic coefficients and is accessible through a Python interface.
  arXiv  Detail & Related papers  (2026-01-05T16:00:44Z)
• Pauli Propagation: A Computational Framework for Simulating Quantum Systems [0.0]
  We provide a comprehensive account of Pauli propagation, tracing its algorithmic structure from its bit-level implementation to its high-level user applications.<n>We present Pauli propagation.jl, a Julia software package that can perform rapid Pauli propagation simulation straight out-of-the-box.
  arXiv  Detail & Related papers  (2025-05-27T17:52:57Z)
• Quantum many-body simulations with PauliStrings.jl [0.0]
  We present the Julia package PauliStrings for quantum many-body simulations.<n>It performs fast operations on the Pauli group by encoding Pauli strings in binary.<n>We show that this representation allows for easy encoding of any geometry.
  arXiv  Detail & Related papers  (2024-10-12T21:18:47Z)
• On the Constant Depth Implementation of Pauli Exponentials [49.48516314472825]
  We decompose $Zotimes n$ exponentials of arbitrary length into circuits of constant depth using $mathcalO(n)$ ancillae and two-body XX and ZZ interactions.<n>We prove the correctness of our approach, after introducing novel rewrite rules for circuits which benefit from qubit recycling.
  arXiv  Detail & Related papers  (2024-08-15T17:09:08Z)
• Quantum simulation of Pauli channels and dynamical maps: algorithm and implementation [0.0]
  We propose a quantum algorithm for simulating Pauli channels and extend it to encompass Pauli dynamical maps. A parametrized quantum circuit is employed to accommodate for dynamical maps.
  arXiv  Detail & Related papers  (2023-07-31T22:57:29Z)
• A single $T$-gate makes distribution learning hard [56.045224655472865]
  This work provides an extensive characterization of the learnability of the output distributions of local quantum circuits. We show that for a wide variety of the most practically relevant learning algorithms -- including hybrid-quantum classical algorithms -- even the generative modelling problem associated with depth $d=omega(log(n))$ Clifford circuits is hard.
  arXiv  Detail & Related papers  (2022-07-07T08:04:15Z)
• Pauli String Partitioning Algorithm with the Ising Model for Simultaneous Measurement [0.0]
  We propose an efficient algorithm for partitioning Pauli strings into subgroups, which can be simultaneously measured in a single quantum circuit. Our partitioning algorithm drastically reduces the total number of measurements in a variational quantum eigensolver for a quantum chemistry.
  arXiv  Detail & Related papers  (2022-05-09T01:49:21Z)
• Synthesis of Quantum Circuits with an Island Genetic Algorithm [44.99833362998488]
  Given a unitary matrix that performs certain operation, obtaining the equivalent quantum circuit is a non-trivial task. Three problems are explored: the coin for the quantum walker, the Toffoli gate and the Fredkin gate. The algorithm proposed proved to be efficient in decomposition of quantum circuits, and as a generic approach, it is limited only by the available computational power.
  arXiv  Detail & Related papers  (2021-06-06T13:15:25Z)
• Boundaries of quantum supremacy via random circuit sampling [69.16452769334367]
  Google's recent quantum supremacy experiment heralded a transition point where quantum computing performed a computational task, random circuit sampling. We examine the constraints of the observed quantum runtime advantage in a larger number of qubits and gates.
  arXiv  Detail & Related papers  (2020-05-05T20:11:53Z)
• Circuit optimization of Hamiltonian simulation by simultaneous diagonalization of Pauli clusters [1.0587959762260986]
  Quantum circuits for exact time evolution of single Pauli operators are well known, and can be extended trivially to sums of commuting Paulis. In this paper we reduce the circuit complexity of Hamiltonian simulation by partitioning the Pauli operators into mutually commuting clusters. We show that the proposed approach can help to significantly reduce both the number of CNOT operations and circuit depth for Hamiltonians arising in quantum chemistry.
  arXiv  Detail & Related papers  (2020-03-30T16:29:40Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.