Metraipolis › archive › dc_285d132bb102
Trapdoored Clifford Operators and Applications — arXiv:2610.01848
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.01848
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-07T11:38:07.356Z
- SHA-256 of the archived text
76e5172816603e66da0478f56029b66d1b98eab493bfc4c528614465e588b1e9- Stable URL of this page
https://metraipolis.com/documento/dc_285d132bb102
How to cite
Trapdoored Clifford Operators and Applications — arXiv:2610.01848 — arXiv (en), https://arxiv.org/abs/2610.01848 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_285d132bb102 (Metraipolis archive dc_285d132bb102, sha256 76e5172816603e66da0478f56029b66d1b98eab493bfc4c528614465e588b1e9)
BibTeX
@misc{dc285d132bb102,
title = {Trapdoored Clifford Operators and Applications — arXiv:2610.01848},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.01848},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_285d132bb102; sha256 76e5172816603e66da0478f56029b66d1b98eab493bfc4c528614465e588b1e9},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.01848. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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. Tema degli esploratori: fisica e astronomia (retro-catalogo arXiv: annunci del 2026-10-02 in quant-ph). Categorie arXiv: Quantum Physics (quant-ph) ; Computational Complexity (cs.CC); Cryptography and Security (cs.CR). Pagina del lavoro: https://arxiv.org/abs/2610.01848 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-07T11:19:01.715Z dalla pagina https://arxiv.org/catchup/quant-ph/2026-10-02?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).