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:2610.30315

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

Filipa C. R. Peres, Selman Ipek, Daniel Lovsted, Joshua Nevin, Anne Broadbent

quant-phSubmitted Oct 21, 2026• Announced Oct 23, 2026• 0 citations
arXivHTMLPDF

Abstract

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.

AI Summary

Pauli-based computation (PBC) replaces Clifford+$T$ circuits by adaptive, commuting Pauli measurements on magic states. This paper asks how its measurement dependencies and entanglement structure can be characterized without enumerating an exponentially large outcome tree, and how that characterization can inform compilation and resource allocation. The main result is a normal form: every branch’s observables are obtained from an efficiently computed all-zero reference branch by conjugation with outcome-controlled single-qubit $S$ gates. The retained measurement indices are branch-independent. A symplectic-tableau proof establishes covariance through stabilizer elimination and basis extraction. Local-Clifford equivalence makes the entanglement structure branch-invariant. When the reference branch has $t$ independent generators, its rank-one projector defines a stabilizer resource for a dual one-way computation with adaptive $T/ST$-basis measurements; an efficient, invertible outcome map preserves probabilities. The normal form also permits polynomial-time identification and removal of magic-state qubits whose measurement factors are always $I$ or $Z$, replacing exhaustive branch enumeration for this criterion. It enables ahead-of-time adaptive compilation and an enhanced construction that removes uncompute blocks. Reported random-circuit reductions are 40–75% in CNOT count and 20–60% in quantum memory relative to the comparison compilers. The architecture discussion assumes suitable hardware for simultaneous overlapping Pauli measurements; distributed measurements can require serialization despite global commutativity. The implemented enhanced compilers generally serialize gadget measurements rather than exploit complete adaptive layers. Benchmark improvements are not universal: the SAT example uses 448 CNOTs and depth 670, versus 214 and 503 after ZX compilation. Free-qubit detection identifies a sufficient class of removable magic states, not all unnecessary magic.

Little sign of AI-generated textOverclaims

Error found: The detailed normal-form proof establishes unsigned symplectic covariance but does not explicitly establish the sign and outcome bookkeeping needed for the main theorem's exact identity between signed Pauli observables. The claim that the compiler consistently improves memory, CNOT count, and depth over ZX compilation is contradicted by the reported SAT_n11 benchmark, which is worse in all three metrics.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Related papers

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•23 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•1 citation

Reducing depth and measurement weights in Pauli-based computation

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

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.

arXiv:2408.04007•Physical Review A•Nov 3, 2025•1 citation

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•18 citations

Trading Classical and Quantum Computational Resources

Sergey B. Bravyi, Graeme Smith, John A. Smolin

We propose examples of a hybrid quantum-classical simulation where a classical computer assisted by a small quantum processor can efficiently simulate a larger quantum system.First, we consider sparse quantum circuits such that each qubit participates in Oð1Þ two-qubit gates.It is shown that any sparse circuit on n þ k qubits can be simulated by sparse circuits on n qubits and a classical processing that takes time 2 OðkÞ polyðnÞ.Second, we study Pauli-based computation (PBC), where allowed operations are nondestructive eigenvalue measurements of n-qubit Pauli operators.The computation begins by initializing each qubit in the so-called magic state.This model is known to be equivalent to the universal quantum computer.We show that any PBC on n þ k qubits can be simulated by PBCs on n qubits and a classical processing that takes time 2 OðkÞ polyðnÞ.Finally, we propose a purely classical algorithm that can simulate a PBC on n qubits in a time 2 αn polyðnÞ, where α ≈ 0.94.This improves upon the brute-force simulation method, which takes time 2 n polyðnÞ.Our algorithm exploits the fact that n-fold tensor products of magic states admit a low-rank decomposition into n-qubit stabilizer states.

arXiv:1506.01396•Physical Review X•Jun 29, 2016•417 citations

The power of restricted quantum computational models

Mithuna Yoganathan

Restricted models of quantum computation are ones that have less power than a universal quantum computer. We studied the consequences of removing particular properties from a universal quantum computer to discover whether those resources were important.In the first part of the thesis we studied universal quantum computers which are implemented using Clifford gates, adaptive measurements, and magic states. The Gottesman–Knill theorem shows that circuits in this form which do not use magic states can be simulated by a classical computer. We extended this result to show that all circuits in this form can be partially simulated; the same computation can be implemented using a smaller quantum computer with the assistance of some polynomial time classical computation. We also identified a subclass of these computations that can be shown to not be entirely classically simulated by any method, given certain complexity theoretic assumptions are true.In the next part of the thesis we examine the role of entanglement in noisy quantum computations. Entanglement is necessary for noiseless quantum computers to have any quantum advantage, but it is not known whether the same is true for mixed state quantum computers. We show that entanglement, unexpectedly, does play a crucial role in the most well known mixed state computer: the one clean qubit model.Finally, we investigate how closely classical simulation is related to another idea of classicality.This notion captures how easily the final state of a computation can be learnt, given samples of measurements from it. We find an extra condition under which a circuit that is classically simulable is also efficiently learnable.

•Jan 5, 2021•1 citation
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) replaces Clifford+TTT circuits by adaptive, commuting Pauli measurements on magic states. This paper asks how its measurement dependencies and entanglement structure can be characterized without enumerating an exponentially large outcome tree, and how that characterization can inform compilation and resource allocation.
The main result is a normal form: every branch’s observables are obtained from an efficiently computed all-zero reference branch by conjugation with outcome-controlled single-qubit SSS gates. The retained measurement indices are branch-independent. A symplectic-tableau proof establishes covariance through stabilizer elimination and basis extraction. Local-Clifford equivalence makes the entanglement structure branch-invariant. When the reference branch has ttt independent generators, its rank-one projector defines a stabilizer resource for a dual one-way computation with adaptive T/STT/STT/ST-basis measurements; an efficient, invertible outcome map preserves probabilities.
The normal form also permits polynomial-time identification and removal of magic-state qubits whose measurement factors are always III or ZZZ, replacing exhaustive branch enumeration for this criterion. It enables ahead-of-time adaptive compilation and an enhanced construction that removes uncompute blocks. Reported random-circuit reductions are 40–75% in CNOT count and 20–60% in quantum memory relative to the comparison compilers.
The architecture discussion assumes suitable hardware for simultaneous overlapping Pauli measurements; distributed measurements can require serialization despite global commutativity. The implemented enhanced compilers generally serialize gadget measurements rather than exploit complete adaptive layers. Benchmark improvements are not universal: the SAT example uses 448 CNOTs and depth 670, versus 214 and 503 after ZX compilation. Free-qubit detection identifies a sufficient class of removable magic states, not all unnecessary magic.
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.
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.
We propose examples of a hybrid quantum-classical simulation where a classical computer assisted by a small quantum processor can efficiently simulate a larger quantum system.First, we consider sparse quantum circuits such that each qubit participates in Oð1Þ two-qubit gates.It is shown that any sparse circuit on n þ k qubits can be simulated by sparse circuits on n qubits and a classical processing that takes time 2 OðkÞ polyðnÞ.Second, we study Pauli-based computation (PBC), where allowed operations are nondestructive eigenvalue measurements of n-qubit Pauli operators.The computation begins by initializing each qubit in the so-called magic state.This model is known to be equivalent to the universal quantum computer.We show that any PBC on n þ k qubits can be simulated by PBCs on n qubits and a classical processing that takes time 2 OðkÞ polyðnÞ.Finally, we propose a purely classical algorithm that can simulate a PBC on n qubits in a time 2 αn polyðnÞ, where α ≈ 0.94.This improves upon the brute-force simulation method, which takes time 2 n polyðnÞ.Our algorithm exploits the fact that n-fold tensor products of magic states admit a low-rank decomposition into n-qubit stabilizer states.
Restricted models of quantum computation are ones that have less power than a universal quantum computer. We studied the consequences of removing particular properties from a universal quantum computer to discover whether those resources were important.In the first part of the thesis we studied universal quantum computers which are implemented using Clifford gates, adaptive measurements, and magic states. The Gottesman–Knill theorem shows that circuits in this form which do not use magic states can be simulated by a classical computer. We extended this result to show that all circuits in this form can be partially simulated; the same computation can be implemented using a smaller quantum computer with the assistance of some polynomial time classical computation. We also identified a subclass of these computations that can be shown to not be entirely classically simulated by any method, given certain complexity theoretic assumptions are true.In the next part of the thesis we examine the role of entanglement in noisy quantum computations. Entanglement is necessary for noiseless quantum computers to have any quantum advantage, but it is not known whether the same is true for mixed state quantum computers. We show that entanglement, unexpectedly, does play a crucial role in the most well known mixed state computer: the one clean qubit model.Finally, we investigate how closely classical simulation is related to another idea of classicality.This notion captures how easily the final state of a computation can be learnt, given samples of measurements from it. We find an extra condition under which a circuit that is classically simulable is also efficiently learnable.