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

Trapdoored Clifford Operators and Applications

Minki Hhan, Hojune Lee

quant-phcs.CCcs.CRSubmitted Oct 1, 2026• Announced Oct 2, 2026• 2 citations
arXivHTMLPDF

Abstract

Random Clifford operators have numerous applications in quantum computing, including randomized benchmarking, classical shadows, and quantum authentication. However, sampling and implementing uniformly random $n$-qubit Clifford incur near-quadratic complexity due to the size of Clifford group. We introduce a cryptographic way to overcome these barriers: trapdoored Clifford operator distributions whose samples are computationally indistinguishable from uniformly random Cliffords, yet implementing them can be much faster given the trapdoor. We construct a distribution of trapdoored Clifford operators whose elements can be sampled and implemented in near-linear time under a variant of the learning parity with noise assumption. Our constructions allow fast tableau action on Pauli labels for classical simulation, and also can be optimized to admit polylogarithmic-depth implementation. Along the way, we construct trapdoored matrices over finite fields that support efficient multiplication by both a matrix and its inverse, resolving an open question left by Vaikuntanathan and Zamir [SODA'26]. We use these constructions to obtain faster protocols based on random Cliffords. We also explore their applications to the worst-case to average-case reductions for matrix and Clifford problems including the iterated matrix multiplication and Clifford circuit synthesis. In particular, we show the hardness of batching Clifford circuits: synthesizing circuits that apply the same Clifford to multiple registers is at least as hard as worst-case matrix multiplication, even when synthesis succeeds on a small constant fraction of random Cliffords. This extends to approximate implementations by general quantum circuits.

AI Summary

The paper asks whether computational pseudorandomness can replace uniformly random $n$-qubit Cliffords to avoid their near-quadratic sampling and implementation costs. It constructs Clifford distributions computationally indistinguishable from uniform against quantum polynomial-time distinguishers given the signed tableau, while retaining a hidden succinct description enabling faster implementation. Under a sparse-noise dual ring-LPN assumption, sampling and quantum application take $O(n^{1+\delta})$ time or gates for any fixed $\delta>0$, using $O(n^{1+\delta})$ clean ancillas returned to zero. A stronger, quantitatively subexponential-hardness assumption gives $n\operatorname{polylog}n$ bounds. Trapdoors also enable equally fast classical action on Pauli labels. Modified constructions achieve quantum depth $O(\log^3 n)$ under all-to-all connectivity. The construction starts from sparse-error, quasi-cyclic trapdoored matrices, recursively builds triangular matrices supporting fast forward and inverse multiplication, and uses Bruhat decompositions with Mallows sampling to obtain pseudorandom invertible matrices and Clifford operators. Matrix trapdoors support multiplication by $M,M^\top,M^{-1},M^{-\top}$ and exact determinant evaluation in $O(n)$ time. Applications include near-linear Clifford authentication with information-theoretic soundness $2^{-e}+\operatorname{negl}(n)$ for $e$ tag qubits, and worst-to-average-case reductions for matrix products, determinants, and Clifford synthesis. Synthesizing $C^{\otimes n}$ for a constant fraction of random $2n$-qubit Cliffords is shown at least as hard as worst-case binary matrix multiplication, up to polylogarithmic overhead; approximate general circuits yield a quantum reduction. The reductions require nonuniform hardness assumptions. Pseudorandomness does not guarantee exact design properties, and the sampling bounds exclude materializing the full tableau.

Almost certainly largely AI-generatedAI use disclosedStrong assumptions
Many of the constructions and proofs, as well as initial drafts of some sections, were generated by ChatGPT. The authors wrote the current manuscript based on these materials with AI assistance

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

Related papers

Scalable randomized benchmarking of non-Clifford gates

Andrew W. Cross, Easwar Magesan, Lev S. Bishop +2 more

Randomized benchmarking is a widely used experimental technique to characterize the average error of quantum operations. Benchmarking procedures that scale to enable characterization of $n$-qubit circuits rely on efficient procedures for manipulating those circuits and, as such, have been limited to subgroups of the Clifford group. However, universal quantum computers require additional, non-Clifford gates to approximate arbitrary unitary transformations. We define a scalable randomized benchmarking procedure over $n$-qubit unitary matrices that correspond to protected non-Clifford gates for a class of stabilizer codes. We present efficient methods for representing and composing group elements, sampling them uniformly, and synthesizing corresponding $\mathrm{poly}(n)$-sized circuits. The procedure provides experimental access to two independent parameters that together characterize the average gate fidelity of a group element.

arXiv:1510.02720•Bulletin of the American Physical Society•Oct 9, 2015•17 citations

6-qubit optimal Clifford circuits

Sergey B. Bravyi, Joseph A. Latone, Dmitri Maslov

Abstract Clifford group lies at the core of quantum computation—it underlies quantum error correction, its elements can be used to perform magic state distillation and they form randomized benchmarking protocols, Clifford group is used to study quantum entanglement, and more. The ability to utilize Clifford group elements in practice relies heavily on the efficiency of their circuit-level implementation. Finding short circuits is a hard problem; despite Clifford group being finite, its size grows quickly with the number of qubits n, limiting known optimal implementations to n = 4 qubits. For n = 6, the number of Clifford group elements is about 2.1 × 1023. In this paper, we report a set of algorithms, along with their C implementation, that implicitly synthesize optimal circuits for all 6-qubit Clifford group elements by storing a subset of the latter in a database of size 2.1TB (1kB = 1024B). We demonstrate how to extract arbitrary optimal 6-qubit Clifford circuit in 0.0009358 and 0.0006274 s using consumer- and enterprise-grade computers (hardware) respectively, while relying on this database. We use this implementation to establish a new example of quantum advantage by Clifford circuits over CNOT gate circuits and find optimal Clifford 2-designs for up to 4 qubits.

arXiv:2012.06074•npj Quantum Information•Jul 5, 2022•34 citations

Scalable randomised benchmarking of non-Clifford gates

Andrew W. Cross, Easwar Magesan, Lev S. Bishop +2 more

Randomised benchmarking is a widely used experimental technique to characterise the average error of quantum operations. Benchmarking procedures that scale to enable the characterisation of n-qubit circuits rely on efficient procedures for manipulating those circuits and, as such, have been limited to subgroups of the Clifford group. However, universal quantum computers require additional, non-Clifford gates to approximate arbitrary unitary transformations. We define a scalable randomised benchmarking procedure over n-qubit unitary matrices that correspond to protected non-Clifford gates for a class of stabiliser codes. We present efficient methods for representing and composing group elements, sampling them uniformly and synthesising corresponding poly(n)-sized circuits. The procedure provides experimental access to two independent parameters that together characterise the average gate fidelity of a group element. A scalable procedure to determine the error of quantum operations has been developed by researchers in the United States. Andrew Cross and colleagues at the IBM T.J. Watson Research Center have expanded previously used protocols to a broader range of quantum circuits, thereby enabling error benchmarking for all common logical operations used in leading quantum computing protocols. The standard technique for error characterization in these devices is randomized benchmarking, which provides benefits such as insensitivity to measurement errors, but on the other hand only functions in a limited number of circumstances. In their theoretical study, the researchers demonstrate how randomized benchmarking approaches can be expanded to a much broader range of logical operations. The procedure can be readily implemented experimentally, and provides access to important experimental noise parameters in quantum computing.

npj Quantum Information•Apr 26, 2016•97 citations

Efficient Learning of Clifford-Scrambled Product States

Tobias Haug

Clifford circuits acting on product magic states provide a compact ansatz exhibiting extensive magic, volume-law entanglement, and even classically hard sampling under standard complexity assumptions. Here, we efficiently recover its hidden product subsystems from two-copy Bell sampling. Quadratic relations between Bell samples determine the irreducible blocks after removing Pauli stabilizers, and binary linear algebra constructs a Clifford disentangler. For logarithmic-size blocks, approximate learning of the full state is efficient whenever the state remains inverse-polynomially separated from acquiring additional Pauli stabilizers. We efficiently learn $n$-qubit states prepared by random $T$-doped Clifford circuits with $T$-gate density below one via $O(n^2)$ Bell samples, and disentangle hidden product blocks in Clifford-augmented matrix product states. For unitary learning, we exactly learn $T$-depth-one circuits using $O(n^2)$ queries. Finally, we rule out pseudorandom states and unitaries with a product bipartition hidden by Clifford circuits.

quant-pharXiv:2609.27128•Sep 24, 2026•1 citation

Efficient Unitary Designs with a System-Size Independent Number of Non-Clifford Gates

Jonas Haferkamp, Felipe Montealegre‐Mora, Markus Heinrich +3 more

Abstract Many quantum information protocols require the implementation of random unitaries. Because it takes exponential resources to produce Haar-random unitaries drawn from the full n -qubit group, one often resorts to t -designs. Unitary t -designs mimic the Haar-measure up to t -th moments. It is known that Clifford operations can implement at most 3-designs. In this work, we quantify the non-Clifford resources required to break this barrier. We find that it suffices to inject $$O(t^{4}\log ^{2}(t)\log (1/\varepsilon ))$$ O ( t 4 log 2 ( t ) log ( 1 / ε ) ) many non-Clifford gates into a polynomial-depth random Clifford circuit to obtain an $$\varepsilon $$ ε -approximate t -design. Strikingly, the number of non-Clifford gates required is independent of the system size – asymptotically, the density of non-Clifford gates is allowed to tend to zero. We also derive novel bounds on the convergence time of random Clifford circuits to the t -th moment of the uniform distribution on the Clifford group. Our proofs exploit a recently developed variant of Schur-Weyl duality for the Clifford group, as well as bounds on restricted spectral gaps of averaging operators.

arXiv:2002.09524•Communications in Mathematical Physics•Nov 12, 2022•114 citations

Good Stabilizer Codes from Shallow Clifford Circuits with Random Matchings

Emile Anand, Elia Gorokhovsky, Jennifer Hritz +1 more

Encoding quantum information with low circuit overhead is a fundamental challenge in fault-tolerant quantum computation. Random circuits provide a natural mechanism for rapidly spreading logical information through simple gates applied in parallel. Brown and Fawzi showed that random Clifford circuits on two-qubit Clifford gates provide such encoders that achieve the quantum Gilbert-Varshamov rate-distance tradeoff with depth $O(\log^3 n)$. We show that the same asymptotic tradeoff is attained in optimal $O(\log n)$ depth under a gate distribution with a more restricted support. For every fixed $δ>0$ and sufficiently large $n$, if $\frac kn < 1 - H(\frac{d}{n}) - \frac{d}{n}\log_2 3 - δ$, we can construct random circuits of depth $O(\log n)$ which define, with high probability, an $[n,k]$ stabilizer code of distance at least $d+1$, which matches the $Ω(\log n)$ light-cone lower bound for linear distance encoders. Our ensemble employs a random matching circuit architecture consisting of $T$ independent permutation-invariant layers. In each layer, the qubits are paired up by a uniformly random perfect matching, and a random independent two-qubit Clifford gate is applied to each pair. The gate distribution need not be uniform over, or even have full support on, the two-qubit Clifford group; rather, we allow for very general distributions on Clifford gates satisfying three regularity conditions. In particular, the construction can be implemented using $n/2$ CNOT gates on randomly matched pairs in each layer, with parallel one-qubit Clifford twirls. These regularity conditions allow us to reduce the second-moment dynamics of our random circuits to a reversible Markov chain on binary support strings. We establish logarithmic hitting-time bounds for this Markov chain and comparisons of its stationary distribution to prove the coding properties of the circuits.

quant-pharXiv:2608.18536•Aug 20, 2026•1 citation
Random Clifford operators have numerous applications in quantum computing, including randomized benchmarking, classical shadows, and quantum authentication. However, sampling and implementing uniformly random nnn-qubit Clifford incur near-quadratic complexity due to the size of Clifford group.
We introduce a cryptographic way to overcome these barriers: trapdoored Clifford operator distributions whose samples are computationally indistinguishable from uniformly random Cliffords, yet implementing them can be much faster given the trapdoor. We construct a distribution of trapdoored Clifford operators whose elements can be sampled and implemented in near-linear time under a variant of the learning parity with noise assumption. Our constructions allow fast tableau action on Pauli labels for classical simulation, and also can be optimized to admit polylogarithmic-depth implementation. Along the way, we construct trapdoored matrices over finite fields that support efficient multiplication by both a matrix and its inverse, resolving an open question left by Vaikuntanathan and Zamir [SODA'26].
We use these constructions to obtain faster protocols based on random Cliffords. We also explore their applications to the worst-case to average-case reductions for matrix and Clifford problems including the iterated matrix multiplication and Clifford circuit synthesis. In particular, we show the hardness of batching Clifford circuits: synthesizing circuits that apply the same Clifford to multiple registers is at least as hard as worst-case matrix multiplication, even when synthesis succeeds on a small constant fraction of random Cliffords. This extends to approximate implementations by general quantum circuits.
The paper asks whether computational pseudorandomness can replace uniformly random nnn-qubit Cliffords to avoid their near-quadratic sampling and implementation costs. It constructs Clifford distributions computationally indistinguishable from uniform against quantum polynomial-time distinguishers given the signed tableau, while retaining a hidden succinct description enabling faster implementation.
Under a sparse-noise dual ring-LPN assumption, sampling and quantum application take O(n1+δ)O(n^{1+\delta})O(n1+δ) time or gates for any fixed δ>0\delta>0δ>0, using O(n1+δ)O(n^{1+\delta})O(n1+δ) clean ancillas returned to zero. A stronger, quantitatively subexponential-hardness assumption gives npolylog⁡nn\operatorname{polylog}nnpolylogn bounds. Trapdoors also enable equally fast classical action on Pauli labels. Modified constructions achieve quantum depth O(log⁡3n)O(\log^3 n)O(log3n) under all-to-all connectivity.
The construction starts from sparse-error, quasi-cyclic trapdoored matrices, recursively builds triangular matrices supporting fast forward and inverse multiplication, and uses Bruhat decompositions with Mallows sampling to obtain pseudorandom invertible matrices and Clifford operators. Matrix trapdoors support multiplication by M,M⊤,M−1,M−⊤M,M^\top,M^{-1},M^{-\top}M,M⊤,M−1,M−⊤ and exact determinant evaluation in O(n)O(n)O(n) time.
Applications include near-linear Clifford authentication with information-theoretic soundness 2−e+negl⁡(n)2^{-e}+\operatorname{negl}(n)2−e+negl(n) for eee tag qubits, and worst-to-average-case reductions for matrix products, determinants, and Clifford synthesis. Synthesizing C⊗nC^{\otimes n}C⊗n for a constant fraction of random 2n2n2n-qubit Cliffords is shown at least as hard as worst-case binary matrix multiplication, up to polylogarithmic overhead; approximate general circuits yield a quantum reduction. The reductions require nonuniform hardness assumptions. Pseudorandomness does not guarantee exact design properties, and the sampling bounds exclude materializing the full tableau.
Randomized benchmarking is a widely used experimental technique to characterize the average error of quantum operations. Benchmarking procedures that scale to enable characterization of nnn-qubit circuits rely on efficient procedures for manipulating those circuits and, as such, have been limited to subgroups of the Clifford group. However, universal quantum computers require additional, non-Clifford gates to approximate arbitrary unitary transformations. We define a scalable randomized benchmarking procedure over nnn-qubit unitary matrices that correspond to protected non-Clifford gates for a class of stabilizer codes. We present efficient methods for representing and composing group elements, sampling them uniformly, and synthesizing corresponding poly(n)\mathrm{poly}(n)poly(n)-sized circuits. The procedure provides experimental access to two independent parameters that together characterize the average gate fidelity of a group element.
Abstract Clifford group lies at the core of quantum computation—it underlies quantum error correction, its elements can be used to perform magic state distillation and they form randomized benchmarking protocols, Clifford group is used to study quantum entanglement, and more. The ability to utilize Clifford group elements in practice relies heavily on the efficiency of their circuit-level implementation. Finding short circuits is a hard problem; despite Clifford group being finite, its size grows quickly with the number of qubits n, limiting known optimal implementations to n = 4 qubits. For n = 6, the number of Clifford group elements is about 2.1 × 1023. In this paper, we report a set of algorithms, along with their C implementation, that implicitly synthesize optimal circuits for all 6-qubit Clifford group elements by storing a subset of the latter in a database of size 2.1TB (1kB = 1024B). We demonstrate how to extract arbitrary optimal 6-qubit Clifford circuit in 0.0009358 and 0.0006274 s using consumer- and enterprise-grade computers (hardware) respectively, while relying on this database. We use this implementation to establish a new example of quantum advantage by Clifford circuits over CNOT gate circuits and find optimal Clifford 2-designs for up to 4 qubits.
Randomised benchmarking is a widely used experimental technique to characterise the average error of quantum operations. Benchmarking procedures that scale to enable the characterisation of n-qubit circuits rely on efficient procedures for manipulating those circuits and, as such, have been limited to subgroups of the Clifford group. However, universal quantum computers require additional, non-Clifford gates to approximate arbitrary unitary transformations. We define a scalable randomised benchmarking procedure over n-qubit unitary matrices that correspond to protected non-Clifford gates for a class of stabiliser codes. We present efficient methods for representing and composing group elements, sampling them uniformly and synthesising corresponding poly(n)-sized circuits. The procedure provides experimental access to two independent parameters that together characterise the average gate fidelity of a group element. A scalable procedure to determine the error of quantum operations has been developed by researchers in the United States. Andrew Cross and colleagues at the IBM T.J. Watson Research Center have expanded previously used protocols to a broader range of quantum circuits, thereby enabling error benchmarking for all common logical operations used in leading quantum computing protocols. The standard technique for error characterization in these devices is randomized benchmarking, which provides benefits such as insensitivity to measurement errors, but on the other hand only functions in a limited number of circumstances. In their theoretical study, the researchers demonstrate how randomized benchmarking approaches can be expanded to a much broader range of logical operations. The procedure can be readily implemented experimentally, and provides access to important experimental noise parameters in quantum computing.
Clifford circuits acting on product magic states provide a compact ansatz exhibiting extensive magic, volume-law entanglement, and even classically hard sampling under standard complexity assumptions. Here, we efficiently recover its hidden product subsystems from two-copy Bell sampling. Quadratic relations between Bell samples determine the irreducible blocks after removing Pauli stabilizers, and binary linear algebra constructs a Clifford disentangler. For logarithmic-size blocks, approximate learning of the full state is efficient whenever the state remains inverse-polynomially separated from acquiring additional Pauli stabilizers. We efficiently learn nnn-qubit states prepared by random TTT-doped Clifford circuits with TTT-gate density below one via O(n2)O(n^2)O(n2) Bell samples, and disentangle hidden product blocks in Clifford-augmented matrix product states. For unitary learning, we exactly learn TTT-depth-one circuits using O(n2)O(n^2)O(n2) queries. Finally, we rule out pseudorandom states and unitaries with a product bipartition hidden by Clifford circuits.
Abstract Many quantum information protocols require the implementation of random unitaries. Because it takes exponential resources to produce Haar-random unitaries drawn from the full n -qubit group, one often resorts to t -designs. Unitary t -designs mimic the Haar-measure up to t -th moments. It is known that Clifford operations can implement at most 3-designs. In this work, we quantify the non-Clifford resources required to break this barrier. We find that it suffices to inject O(t4log⁡2(t)log⁡(1/ε))O(t^{4}\log ^{2}(t)\log (1/\varepsilon ))O(t4log2(t)log(1/ε)) O ( t 4 log 2 ( t ) log ( 1 / ε ) ) many non-Clifford gates into a polynomial-depth random Clifford circuit to obtain an ε\varepsilon ε ε -approximate t -design. Strikingly, the number of non-Clifford gates required is independent of the system size – asymptotically, the density of non-Clifford gates is allowed to tend to zero. We also derive novel bounds on the convergence time of random Clifford circuits to the t -th moment of the uniform distribution on the Clifford group. Our proofs exploit a recently developed variant of Schur-Weyl duality for the Clifford group, as well as bounds on restricted spectral gaps of averaging operators.
Encoding quantum information with low circuit overhead is a fundamental challenge in fault-tolerant quantum computation. Random circuits provide a natural mechanism for rapidly spreading logical information through simple gates applied in parallel. Brown and Fawzi showed that random Clifford circuits on two-qubit Clifford gates provide such encoders that achieve the quantum Gilbert-Varshamov rate-distance tradeoff with depth O(log⁡3n)O(\log^3 n)O(log3n). We show that the same asymptotic tradeoff is attained in optimal O(log⁡n)O(\log n)O(logn) depth under a gate distribution with a more restricted support. For every fixed δ>0δ>0δ>0 and sufficiently large nnn, if kn<1−H(dn)−dnlog⁡23−δ\frac kn < 1 - H(\frac{d}{n}) - \frac{d}{n}\log_2 3 - δnk​<1−H(nd​)−nd​log2​3−δ, we can construct random circuits of depth O(log⁡n)O(\log n)O(logn) which define, with high probability, an [n,k][n,k][n,k] stabilizer code of distance at least d+1d+1d+1, which matches the Ω(log⁡n)Ω(\log n)Ω(logn) light-cone lower bound for linear distance encoders. Our ensemble employs a random matching circuit architecture consisting of TTT independent permutation-invariant layers. In each layer, the qubits are paired up by a uniformly random perfect matching, and a random independent two-qubit Clifford gate is applied to each pair. The gate distribution need not be uniform over, or even have full support on, the two-qubit Clifford group; rather, we allow for very general distributions on Clifford gates satisfying three regularity conditions. In particular, the construction can be implemented using n/2n/2n/2 CNOT gates on randomly matched pairs in each layer, with parallel one-qubit Clifford twirls. These regularity conditions allow us to reduce the second-moment dynamics of our random circuits to a reversible Markov chain on binary support strings. We establish logarithmic hitting-time bounds for this Markov chain and comparisons of its stationary distribution to prove the coding properties of the circuits.