Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2408.04007 · Physical Review A

Reducing depth and measurement weights in Pauli-based computation

Filipa C. R. Peres, Ernesto F. Galvão

Published Nov 3, 2025• 0 citations
arXivHTMLPDF

Abstract

Pauli-based computation (PBC) is a universal measurement-based quantum computation model steered by an adaptive sequence of independent and compatible Pauli measurements on separable magic-state qubits. Here, we propose several techniques for reducing the weight of the Pauli measurements and their associated cnot complexity; we also demonstrate how to decrease this model's computational depth. We start by proving new upper bounds on the required weights and computational depth, obtained via a precompilation step. We also propose a heuristic algorithm that can contribute to reductions of over 30% to the average weight of Pauli measurements (and associated cnot count) when simulating and compiling Clifford-dominated random quantum circuits with up to 22 $T$ gates and over 20% for instances with larger $T$ counts. This PBC-compilation scheme, boosted by the heuristic algorithm, outperforms state-of-the-art compilers for the former circuits, reducing the cnot count by 18% to 96% compared with the values achieved by other techniques. In contrast, for the latter circuits with larger $T$ counts, it leads to a number of cnots roughly 30% larger. Finally, inspired by known state-transfer methods, we introduce incPBC, a universal model for quantum computation requiring a larger number of (now incompatible) Pauli measurements of weight at most 2.

DOI
10.1103/d3x5-cgky

Related papers

Pauli-based model of quantum computation with higher-dimensional systems

Filipa C. R. Peres

Pauli-based computation (PBC) is a universal model for quantum computation with qubits where the input state is a magic (resource) state and the computation is driven by a sequence of adaptively chosen and compatible multiqubit Pauli measurements. Here we generalize PBC for odd-prime-dimensional systems and demonstrate its universality. Additionally, we discuss how any qudit-based PBC can be implemented on actual, circuit-based quantum hardware. Our results show that we can translate a PBC on $n\phantom{\rule{4pt}{0ex}}p$-dimensional qudits to adaptive circuits on $n+1$ qudits with $O\left(p{n}^{2}/2\right)$ sum gates and depth. Alternatively, we can carry out the same computation with $O\left(pn/2\right)$ depth at the expense of an increased circuit width. Finally, we show that the sampling complexity associated with simulating a number $k$ of virtual qudits is related to the robustness of magic of the input states. Computation of this magic monotone for qutrit and ququint states leads to sampling complexity upper bounds of, respectively, $O({3}^{1.0848k}{\ensuremath{\epsilon}}^{\ensuremath{-}2})$ and $O({5}^{1.4022k}{\ensuremath{\epsilon}}^{\ensuremath{-}2})$, for a desired precision $\ensuremath{\epsilon}$. We further establish lower bounds to this sampling complexity for qubits, qutrits, and ququints: $\mathrm{\ensuremath{\Omega}}({2}^{0.5431k}{\ensuremath{\epsilon}}^{\ensuremath{-}2})$, $\mathrm{\ensuremath{\Omega}}({3}^{0.7236k}{\ensuremath{\epsilon}}^{\ensuremath{-}2})$, and $\mathrm{\ensuremath{\Omega}}({5}^{0.8544k}{\ensuremath{\epsilon}}^{\ensuremath{-}2})$, respectively.

arXiv:2302.13702•Physical Review A•Sep 13, 2023•9 citations

Normal-Form Characterization of Adaptivity and Entanglement in Pauli-Based Computation

Filipa C. R. Peres, Selman Ipek, Daniel Lovsted +2 more

Pauli-based computation (PBC) is a measurement-based model of quantum computation that samples from output distributions of universal Clifford+$T$ circuits. Here, we provide a normal form (NF) that completely characterizes its adaptive and entanglement structures. These insights unify PBC with one-way quantum computing as dual or `time-reversed' counterparts. We use the NF to advance strategies for distributed computation and investigate magic-state injection rates. We also demonstrate an exponential improvement in the detection of unnecessary magic-state qubits, allowing their efficient removal. Our NF further enables ahead-of-time circuit compilation using PBC, reducing CNOT gate count and quantum memory of random quantum circuits on average by 50% and 40%, respectively, beating other state-of-the-art compilers.

quant-pharXiv:2610.30315•Oct 23, 2026•0 citations

Quantum circuit compilation and hybrid computation using Pauli-based computation

Filipa C. R. Peres, Ernesto F. Galvão

Pauli-based computation (PBC) is driven by a sequence of adaptively chosen, non-destructive measurements of Pauli observables. Any quantum circuit written in terms of the Clifford+ T gate set and having t T gates can be compiled into a PBC on t qubits. Here we propose practical ways of implementing PBC as adaptive quantum circuits and provide code to do the required classical side-processing. Our schemes reduce the number of quantum gates to O ( t 2 ) (from a previous O ( t 3 / log ⁡ t ) scaling) and space/time trade-offs are discussed which lead to a reduction of the depth from O ( t log ⁡ t ) to O ( t ) within our schemes, at the cost of t additional auxiliary qubits. We compile examples of random and hidden-shift quantum circuits into adaptive PBC circuits. We also simulate hybrid quantum computation, where a classical computer effectively extends the working memory of a small quantum computer by k virtual qubits, at a cost exponential in k . Our results demonstrate the practical advantage of PBC techniques for circuit compilation and hybrid computation.

arXiv:2203.01789•Quantum•Oct 3, 2023•14 citations

Space-Time Tradeoffs of Pauli-Based Computation in Distributed qLDPC Architectures

Naphan Benchasattabuse, Michal Hajdušek, Rodney Van Meter

Pauli-based computation (PBC) provides a universal framework for executing fault-tolerant quantum algorithms using Pauli measurements and magic states. In monolithic architectures, the serialized nature of PBC directly ties runtime to a circuit's T-gate count, making it slow on metrics like circuit depth. However, in distributed quantum computing (DQC), the primary bottleneck is remote Bell pair generation. We investigate the tradeoff between error-correcting code block size and execution time of PBC within the Q-Fly architecture at intermediate scale, limiting individual node capacities to reflect near-term constraints while supplying abundant network nodes to minimize routing and compilation effects. We find that large qLDPC code blocks outperform the surface code baseline in terms of execution time by up to an order of magnitude when evaluated against quantum optimization algorithms. By moving groups of qubits to free nodes to bypass the sequential bottleneck of PBC, the large-block architecture minimizes network operations and achieves faster overall execution. This demonstrates that PBC is a competitive model in the distributed regime, establishing it as a practical compilation baseline for qLDPC systems before invoking more efficient transversal or homological gates.

quant-pharXiv:2605.03854•May 6, 2026•0 citations

Improved Strong Simulation of Universal Quantum Circuits

Lucas Kocia

We find a scaling reduction in the stabilizer rank of the twelve-qubit tensored $T$ gate magic state. This lowers its asymptotic bound to $2^{\sim 0.463 t}$ for multi-Pauli measurements on $t$ magic states, improving over the best previously found bound of $2^{\sim 0.468 t}$. We numerically demonstrate this reduction. This constructively produces the most efficient strong simulation algorithm of the Clifford+$T$ gateset to relative or multiplicative error. We then examine the cost of Pauli measurement in terms of its Gauss sum rank, which is a slight generalization of the stabilizer rank and is a lower bound on its asymptotic scaling. We demonstrate that this lower bound appears to be tight at low $t$-counts, which suggests that the stabilizer rank found at the twelve-qubit state can be lowered further to $2^{\sim 0.449 t}$ and we prove and numerically show that this is the case for single-Pauli measurements. Our construction directly shows how the reduction at $12$ qubits is iteratively based on the reduction obtained at $6$, $3$, $2$, and $1$ qubits. This explains why novel reductions are found at tensor factors for these number of qubit primitives, an explanation lacking previously in the literature. Furthermore, in the process we observe an interesting relationship between the T gate magic state's stabilizer rank and decompositions that are Clifford-isomorphic to a computational sub-basis tensored with single-qubit states that produce minimal unique stabilizer state inner products -- the same relationship that allowed for finding minimal numbers of unique Gauss sums in the odd-dimensional qudit Wigner formulation of Pauli measurements.

arXiv:2012.11739•Dec 21, 2020•3 citations

Variance reduction methods in the estimation of Pauli sums

Søren Fuglede Jørgensen, Rafael Emilio Barfknecht, Patrick Ettenhuber +1 more

Accurately estimating expectation values of quantum observables with as few measurements as possible is crucial to many quantum computing applications. We introduce a framework that covers many of existing measurement strategies and introduce heuristics that can be used to enhance randomized schemes, including those based on Pauli grouping with inverse probability weighting and variants of the classical shadow algorithm. We show how to maximize information gain from such schemes, while carefully optimizing the distribution of possible measurements, and show that simple grouping algorithms can get close to, and in some cases exceed, state-of-the-art accuracy for unbiased estimation of expectation values on a standard quantum chemistry benchmark. We show how these randomized methods may be compared to more recent measurement schemes, such as shadow grouping, derandomized shadow, and overlapped grouping measurement, we show how the same strategies can be used to augment these schemes, and we demonstrate that we can reduce measurement costs by up to a factor of two by allowing Clifford measurement circuits for otherwise Clifford-less methods.

quant-pharXiv:2603.20029•Mar 23, 2026•0 citations
Pauli-based computation (PBC) is a universal measurement-based quantum computation model steered by an adaptive sequence of independent and compatible Pauli measurements on separable magic-state qubits. Here, we propose several techniques for reducing the weight of the Pauli measurements and their associated cnot complexity; we also demonstrate how to decrease this model's computational depth. We start by proving new upper bounds on the required weights and computational depth, obtained via a precompilation step. We also propose a heuristic algorithm that can contribute to reductions of over 30% to the average weight of Pauli measurements (and associated cnot count) when simulating and compiling Clifford-dominated random quantum circuits with up to 22 TTT gates and over 20% for instances with larger TTT counts. This PBC-compilation scheme, boosted by the heuristic algorithm, outperforms state-of-the-art compilers for the former circuits, reducing the cnot count by 18% to 96% compared with the values achieved by other techniques. In contrast, for the latter circuits with larger TTT counts, it leads to a number of cnots roughly 30% larger. Finally, inspired by known state-transfer methods, we introduce incPBC, a universal model for quantum computation requiring a larger number of (now incompatible) Pauli measurements of weight at most 2.
Pauli-based computation (PBC) is a universal model for quantum computation with qubits where the input state is a magic (resource) state and the computation is driven by a sequence of adaptively chosen and compatible multiqubit Pauli measurements. Here we generalize PBC for odd-prime-dimensional systems and demonstrate its universality. Additionally, we discuss how any qudit-based PBC can be implemented on actual, circuit-based quantum hardware. Our results show that we can translate a PBC on npn\phantom{\rule{4pt}{0ex}}pnp-dimensional qudits to adaptive circuits on n+1n+1n+1 qudits with O(pn2/2)O\left(p{n}^{2}/2\right)O(pn2/2) sum gates and depth. Alternatively, we can carry out the same computation with O(pn/2)O\left(pn/2\right)O(pn/2) depth at the expense of an increased circuit width. Finally, we show that the sampling complexity associated with simulating a number kkk of virtual qudits is related to the robustness of magic of the input states. Computation of this magic monotone for qutrit and ququint states leads to sampling complexity upper bounds of, respectively, $O({3}^{1.0848k}{\ensuremath{\epsilon}}^{\ensuremath{-}2})$ and $O({5}^{1.4022k}{\ensuremath{\epsilon}}^{\ensuremath{-}2})$, for a desired precision $\ensuremath{\epsilon}$. We further establish lower bounds to this sampling complexity for qubits, qutrits, and ququints: $\mathrm{\ensuremath{\Omega}}({2}^{0.5431k}{\ensuremath{\epsilon}}^{\ensuremath{-}2})$, $\mathrm{\ensuremath{\Omega}}({3}^{0.7236k}{\ensuremath{\epsilon}}^{\ensuremath{-}2})$, and $\mathrm{\ensuremath{\Omega}}({5}^{0.8544k}{\ensuremath{\epsilon}}^{\ensuremath{-}2})$, respectively.
Pauli-based computation (PBC) is a measurement-based model of quantum computation that samples from output distributions of universal Clifford+TTT circuits. Here, we provide a normal form (NF) that completely characterizes its adaptive and entanglement structures. These insights unify PBC with one-way quantum computing as dual or `time-reversed' counterparts. We use the NF to advance strategies for distributed computation and investigate magic-state injection rates. We also demonstrate an exponential improvement in the detection of unnecessary magic-state qubits, allowing their efficient removal. Our NF further enables ahead-of-time circuit compilation using PBC, reducing CNOT gate count and quantum memory of random quantum circuits on average by 50% and 40%, respectively, beating other state-of-the-art compilers.
Pauli-based computation (PBC) is driven by a sequence of adaptively chosen, non-destructive measurements of Pauli observables. Any quantum circuit written in terms of the Clifford+ T gate set and having t T gates can be compiled into a PBC on t qubits. Here we propose practical ways of implementing PBC as adaptive quantum circuits and provide code to do the required classical side-processing. Our schemes reduce the number of quantum gates to O ( t 2 ) (from a previous O ( t 3 / log ⁡ t ) scaling) and space/time trade-offs are discussed which lead to a reduction of the depth from O ( t log ⁡ t ) to O ( t ) within our schemes, at the cost of t additional auxiliary qubits. We compile examples of random and hidden-shift quantum circuits into adaptive PBC circuits. We also simulate hybrid quantum computation, where a classical computer effectively extends the working memory of a small quantum computer by k virtual qubits, at a cost exponential in k . Our results demonstrate the practical advantage of PBC techniques for circuit compilation and hybrid computation.
Pauli-based computation (PBC) provides a universal framework for executing fault-tolerant quantum algorithms using Pauli measurements and magic states. In monolithic architectures, the serialized nature of PBC directly ties runtime to a circuit's T-gate count, making it slow on metrics like circuit depth. However, in distributed quantum computing (DQC), the primary bottleneck is remote Bell pair generation. We investigate the tradeoff between error-correcting code block size and execution time of PBC within the Q-Fly architecture at intermediate scale, limiting individual node capacities to reflect near-term constraints while supplying abundant network nodes to minimize routing and compilation effects. We find that large qLDPC code blocks outperform the surface code baseline in terms of execution time by up to an order of magnitude when evaluated against quantum optimization algorithms. By moving groups of qubits to free nodes to bypass the sequential bottleneck of PBC, the large-block architecture minimizes network operations and achieves faster overall execution. This demonstrates that PBC is a competitive model in the distributed regime, establishing it as a practical compilation baseline for qLDPC systems before invoking more efficient transversal or homological gates.
We find a scaling reduction in the stabilizer rank of the twelve-qubit tensored TTT gate magic state. This lowers its asymptotic bound to 2∼0.463t2^{\sim 0.463 t}2∼0.463t for multi-Pauli measurements on ttt magic states, improving over the best previously found bound of 2∼0.468t2^{\sim 0.468 t}2∼0.468t. We numerically demonstrate this reduction. This constructively produces the most efficient strong simulation algorithm of the Clifford+TTT gateset to relative or multiplicative error. We then examine the cost of Pauli measurement in terms of its Gauss sum rank, which is a slight generalization of the stabilizer rank and is a lower bound on its asymptotic scaling. We demonstrate that this lower bound appears to be tight at low ttt-counts, which suggests that the stabilizer rank found at the twelve-qubit state can be lowered further to 2∼0.449t2^{\sim 0.449 t}2∼0.449t and we prove and numerically show that this is the case for single-Pauli measurements. Our construction directly shows how the reduction at 121212 qubits is iteratively based on the reduction obtained at 666, 333, 222, and 111 qubits. This explains why novel reductions are found at tensor factors for these number of qubit primitives, an explanation lacking previously in the literature. Furthermore, in the process we observe an interesting relationship between the T gate magic state's stabilizer rank and decompositions that are Clifford-isomorphic to a computational sub-basis tensored with single-qubit states that produce minimal unique stabilizer state inner products -- the same relationship that allowed for finding minimal numbers of unique Gauss sums in the odd-dimensional qudit Wigner formulation of Pauli measurements.
Accurately estimating expectation values of quantum observables with as few measurements as possible is crucial to many quantum computing applications. We introduce a framework that covers many of existing measurement strategies and introduce heuristics that can be used to enhance randomized schemes, including those based on Pauli grouping with inverse probability weighting and variants of the classical shadow algorithm. We show how to maximize information gain from such schemes, while carefully optimizing the distribution of possible measurements, and show that simple grouping algorithms can get close to, and in some cases exceed, state-of-the-art accuracy for unbiased estimation of expectation values on a standard quantum chemistry benchmark. We show how these randomized methods may be compared to more recent measurement schemes, such as shadow grouping, derandomized shadow, and overlapped grouping measurement, we show how the same strategies can be used to augment these schemes, and we demonstrate that we can reduce measurement costs by up to a factor of two by allowing Clifford measurement circuits for otherwise Clifford-less methods.