Trapdoored Clifford operators enable faster quantum circuit tasks
Trapdoored Clifford Operators and Applications
Computational ComplexityCryptography and Security
Summary
Performing certain quantum computations randomly can be very slow because of the complexity involved. The authors present a method to create special 'trapdoored' Clifford operators that look random but can be computed much faster with a secret key. This method speeds up simulations and practical protocols that use these operators, while relying on a widely studied computational assumption. They also show that efficiently creating certain quantum circuits is as hard as some toughest matrix problems, even when only a few cases need to be correct.
What this means in practice
- •For quantum software engineers: Speed up implementing and simulating randomized quantum protocols using trapdoored Clifford operators with efficient sampling.
- •For quantum hardware developers: Use polylogarithmic-depth Clifford circuits derived from trapdoored operators for more efficient quantum device benchmarking.
Authors
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.