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:2302.13702 · Physical Review A

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

Filipa C. R. Peres

Published Sep 13, 2023• 9 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physreva.108.032606

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•14 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

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

Encoder Circuit Optimization for Nonbinary Quantum Error Correction Codes in Prime Dimensions: An Algorithmic Framework

Aditya Sodhani, Keshab K. Parhi

Quantum computers are a revolutionary class of computational platforms with applications in combinatorial and global optimization, machine learning, and other domains involving computationally hard problems. While these machines typically operate on qubits—quantum information elements that can occupy superpositions of the basis$|0\rangle$and$|1\rangle$states—recent advances have demonstrated the practical implementation of higher-dimensional quantum systems (qudits) across various hardware platforms. In these hardware realizations, the higher-order states are less stable and thus remain coherent for a shorter duration than the basis$|0\rangle$and$|1\rangle$states. Moreover, formal methods for designing efficient encoder circuits for these systems remain underexplored. This limitation motivates the development of efficient circuit techniques for qudit systems (d-level quantum systems). Previous works have typically established generating gate sets for higher-dimensional codes by generalizing the methods used for qubits. In this work, we introduce a systematic framework for optimizing encoder circuits for prime-dimension stabilizer codes. This framework is based on novel generating gate sets whose elements map directly to efficient Clifford gate sequences. We demonstrate the effectiveness of this method on key codes, achieving a 13–44% reduction in encoder circuit gate count for the qutrit (d = 3)$[[9,5,3]]_{3}$,$[[5,1,3]]_{3}$, and$[[7,1,3]]_{3}$codes, and a 9–21% reduction for the ququint (d = 5)$[[10,6,3]]_{5}$code when compared to prior work. We also achieved circuit depth reductions up to 42%.

arXiv:2509.25587•IEEE Transactions on Quantum Engineering•Jan 1, 2026•0 citations

Trading Classical and Quantum Computational Resources

Sergey 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•338 citations

Classical Simulability of Quantum Circuits with Shallow Magic Depth

Y. Zhang, Yuxuan Zhang

Quantum magic is a necessary resource for quantum computers to be not efficiently simulable by classical computers. Previous results have linked the of quantum magic, characterized by the number of T gates or the stabilizer rank, to classical simulability. However, the effect of the of quantum magic on the hardness of simulating a quantum circuit remains open. In this work, we investigate the classical simulability of quantum circuits with alternating Clifford and T layers across three tasks: amplitude estimation, sampling, and evaluating Pauli observables. In the case in which all T gates are distributed in a single layer, performing amplitude estimation and sampling to multiplicative error are already classically intractable under reasonable assumptions, but Pauli observables are easy to evaluate. Surprisingly, with the addition of just one T -gate layer or merely replacing all T gates with T 1 / 2 , the Pauli evaluation task reveals a sharp complexity transition from being in P to being GapP-complete. Nevertheless, when the precision requirement is relaxed to 1 / poly ( n ) additive error, we are able to give a polynomial-time classical algorithm to compute amplitudes, Pauli observables, and sampling from log  ( n ) -sized marginal distributions for any magic-depth-1 circuit that is decomposable into a product of diagonal gates. This rules out certain forms of quantum advantage in these circuits. Our research provides new techniques to simulate highly magical circuits while shedding light on their complexity and their significant dependence on the magic depth.

arXiv:2409.13809•PRX Quantum•Feb 28, 2025•11 citations
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(31.0848k\ensuremathϵ\ensuremath−2)O({3}^{1.0848k}{\ensuremath{\epsilon}}^{\ensuremath{-}2})O(31.0848k\ensuremathϵ\ensuremath−2) and O(51.4022k\ensuremathϵ\ensuremath−2)O({5}^{1.4022k}{\ensuremath{\epsilon}}^{\ensuremath{-}2})O(51.4022k\ensuremathϵ\ensuremath−2), for a desired precision \ensuremathϵ\ensuremath{\epsilon}\ensuremathϵ. We further establish lower bounds to this sampling complexity for qubits, qutrits, and ququints: \ensuremathΩ(20.5431k\ensuremathϵ\ensuremath−2)\mathrm{\ensuremath{\Omega}}({2}^{0.5431k}{\ensuremath{\epsilon}}^{\ensuremath{-}2})\ensuremathΩ(20.5431k\ensuremathϵ\ensuremath−2), \ensuremathΩ(30.7236k\ensuremathϵ\ensuremath−2)\mathrm{\ensuremath{\Omega}}({3}^{0.7236k}{\ensuremath{\epsilon}}^{\ensuremath{-}2})\ensuremathΩ(30.7236k\ensuremathϵ\ensuremath−2), and \ensuremathΩ(50.8544k\ensuremathϵ\ensuremath−2)\mathrm{\ensuremath{\Omega}}({5}^{0.8544k}{\ensuremath{\epsilon}}^{\ensuremath{-}2})\ensuremathΩ(50.8544k\ensuremathϵ\ensuremath−2), respectively.
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) 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 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.
Quantum computers are a revolutionary class of computational platforms with applications in combinatorial and global optimization, machine learning, and other domains involving computationally hard problems. While these machines typically operate on qubits—quantum information elements that can occupy superpositions of the basis∣0⟩|0\rangle∣0⟩and∣1⟩|1\rangle∣1⟩states—recent advances have demonstrated the practical implementation of higher-dimensional quantum systems (qudits) across various hardware platforms. In these hardware realizations, the higher-order states are less stable and thus remain coherent for a shorter duration than the basis∣0⟩|0\rangle∣0⟩and∣1⟩|1\rangle∣1⟩states. Moreover, formal methods for designing efficient encoder circuits for these systems remain underexplored. This limitation motivates the development of efficient circuit techniques for qudit systems (d-level quantum systems). Previous works have typically established generating gate sets for higher-dimensional codes by generalizing the methods used for qubits. In this work, we introduce a systematic framework for optimizing encoder circuits for prime-dimension stabilizer codes. This framework is based on novel generating gate sets whose elements map directly to efficient Clifford gate sequences. We demonstrate the effectiveness of this method on key codes, achieving a 13–44% reduction in encoder circuit gate count for the qutrit (d = 3)[[9,5,3]]3[[9,5,3]]_{3}[[9,5,3]]3​,[[5,1,3]]3[[5,1,3]]_{3}[[5,1,3]]3​, and[[7,1,3]]3[[7,1,3]]_{3}[[7,1,3]]3​codes, and a 9–21% reduction for the ququint (d = 5)[[10,6,3]]5[[10,6,3]]_{5}[[10,6,3]]5​code when compared to prior work. We also achieved circuit depth reductions up to 42%.
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.
Quantum magic is a necessary resource for quantum computers to be not efficiently simulable by classical computers. Previous results have linked the of quantum magic, characterized by the number of T gates or the stabilizer rank, to classical simulability. However, the effect of the of quantum magic on the hardness of simulating a quantum circuit remains open. In this work, we investigate the classical simulability of quantum circuits with alternating Clifford and T layers across three tasks: amplitude estimation, sampling, and evaluating Pauli observables. In the case in which all T gates are distributed in a single layer, performing amplitude estimation and sampling to multiplicative error are already classically intractable under reasonable assumptions, but Pauli observables are easy to evaluate. Surprisingly, with the addition of just one T -gate layer or merely replacing all T gates with T 1 / 2 , the Pauli evaluation task reveals a sharp complexity transition from being in P to being GapP-complete. Nevertheless, when the precision requirement is relaxed to 1 / poly ( n ) additive error, we are able to give a polynomial-time classical algorithm to compute amplitudes, Pauli observables, and sampling from log  ( n ) -sized marginal distributions for any magic-depth-1 circuit that is decomposable into a product of diagonal gates. This rules out certain forms of quantum advantage in these circuits. Our research provides new techniques to simulate highly magical circuits while shedding light on their complexity and their significant dependence on the magic depth.