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
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.
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.