arXiv:2610.01848
Trapdoored Clifford Operators and Applications
Minki Hhan, Hojune Lee
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.
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.