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:2203.01789 · Quantum

Quantum circuit compilation and hybrid computation using Pauli-based computation

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

Published Oct 3, 2023• 23 citations
arXivHTMLPDF

Abstract

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.

DOI
10.22331/q-2023-10-03-1126

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

Blind Quantum Computation with a Small Quantum Server

Daniel Lovsted, Filipa C. R. Peres, Joshua Nevin +2 more

Blind quantum computation (BQC) allows low-resource clients to securely delegate computations to a quantum server, but server resource costs scale with the computation size, posing a bottleneck for implementations. By leveraging Pauli-based computation (PBC), we achieve BQC with a server whose size depends only on the non-Clifford gate count. Our protocol inherits fault tolerance and qubit virtualization from PBC and reveals that classical-client BQC is possible even in the absence of classical simulability. Finally, we present an entanglement-based dual protocol that performs a resource state computation with a dramatically reduced execution cost.

quant-pharXiv:2609.20729•Sep 18, 2026•1 citation

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

Synthesizing Circuits from Tableaus

anne mara

Quantum computers are only as powerful as the compilers that optimize the circuits they run. As quantum hardware scales, reducing gate counts and circuit depth becomes critical for practical computation. This work implements a core synthesis algorithm in OCaml that maps arbitrary Cliffords to circuits, a fundamental building block in quantum circuit compilation. The Clifford synthesis implementation is designed around how LambdaPC thinks about quantum computation, through Pauli operators. It frames synthesis as a search problem: given a Clifford tableau, find a path to the identity by applying gates. Working factor by factor, it reduces each Pauli pair (P, Q) to a canonical (Z_i, X_i) form using single-qubit Clifford gates and TQE gates, until the full tableau is decomposed into an executable circuit. The main challenge was working within LambdaPC's typed representation, where n-qubit Paulis are encoded as nested pairs. This required helper functions to extract Pauli data from those structures and pattern-matching logic to find minimal gate sequences, laying the groundwork for end-to-end Clifford compilation in LambdaPC.

•Jun 8, 2026•0 citations
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 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 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.
Blind quantum computation (BQC) allows low-resource clients to securely delegate computations to a quantum server, but server resource costs scale with the computation size, posing a bottleneck for implementations. By leveraging Pauli-based computation (PBC), we achieve BQC with a server whose size depends only on the non-Clifford gate count. Our protocol inherits fault tolerance and qubit virtualization from PBC and reveals that classical-client BQC is possible even in the absence of classical simulability. Finally, we present an entanglement-based dual protocol that performs a resource state computation with a dramatically reduced execution cost.
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 computers are only as powerful as the compilers that optimize the circuits they run. As quantum hardware scales, reducing gate counts and circuit depth becomes critical for practical computation. This work implements a core synthesis algorithm in OCaml that maps arbitrary Cliffords to circuits, a fundamental building block in quantum circuit compilation. The Clifford synthesis implementation is designed around how LambdaPC thinks about quantum computation, through Pauli operators. It frames synthesis as a search problem: given a Clifford tableau, find a path to the identity by applying gates. Working factor by factor, it reduces each Pauli pair (P, Q) to a canonical (Z_i, X_i) form using single-qubit Clifford gates and TQE gates, until the full tableau is decomposed into an executable circuit. The main challenge was working within LambdaPC's typed representation, where n-qubit Paulis are encoded as nested pairs. This required helper functions to extract Pauli data from those structures and pattern-matching logic to find minimal gate sequences, laying the groundwork for end-to-end Clifford compilation in LambdaPC.