Adaptively secure unitary designs with constant non-Clifford cost

Abstract

Randomness is a fundamental resource in quantum information, with crucial applications in cryptography, algorithms, and error correction. A central challenge is to construct unitary $k$-designs that closely approximate Haar-random unitaries while minimizing the costly use of non-Clifford operations. In this work, we present a protocol able to generate unitary $k$-designs on $n$ qubits, secure against any adversarial quantum measurement, with a system-size-independent number of non-Clifford gates. Our construction applies a $k$-design only to a subsystem of size $\Theta (k)$, independent of $n$. This ``seed'' design is then ``diluted'' across the entire $n$-qubit system by sandwiching it between two random Clifford operators. The resulting ensemble forms an $\epsilon$-approximate unitary $k$-design on $n$ qubits. We prove that this construction achieves full quantum security against adaptive adversaries using only $\tilde{O}(k^2\log {\epsilon }^{-1})$ non-Clifford gates. If one requires security only against polynomial-time adaptive adversaries, the non-Clifford cost decreases to $\tilde{O}(k+{\log }^{1+c}{\epsilon }^{-1})$. This is optimal, since we show that at least $\Omega (k)$ non-Clifford gates are required in this setting. Compared to existing approaches, our method significantly reduces non-Clifford overhead while strengthening security guarantees to adaptive security as well as removing artificial assumptions between $n$ and $k$. These results make high-order unitary designs practically attainable in near-term fault-tolerant quantum architectures.

5 pages + 14 appendix

References in corpus (26)

• Improved Simulation of Stabilizer Circuits
• Black holes as mirrors: quantum information in random subsystems
• Fast Scramblers
• The foundations of statistical mechanics from entanglement: Individual states vs. averages
• On the quantum, classical and total amount of correlations in a quantum state
• Scalable Noise Estimation with Random Unitary Operators
• Restrictions on Transversal Encoded Quantum Gate Sets
• Evenly distributed unitaries: on the structure of unitary designs
• Magic state distillation with low overhead
• Quantum certification and benchmarking
• Random Quantum Circuits are Approximate 2-designs
• Local random quantum circuits are approximate polynomial-designs
• Random Quantum Circuits and Pseudo-Random Operators: Theory and Applications
• Multiqubit Clifford groups are unitary 3-designs
• Relating quantum privacy and quantum coherence: an operational approach
• Towards low overhead magic state distillation
• Efficient unitary designs with a system-size independent number of non-Clifford gates
• Learning t-doped stabilizer states
• Learning efficient decoders for quasi-chaotic quantum scramblers
• Learning and Testing Algorithms for the Clifford Group
• Unscrambling Quantum Information with Clifford decoders
• Clifford Dressed Time-Dependent Variational Principle
• Pseudorandom unitaries are neither real nor sparse nor noise-robust
• Complexity-constrained quantum thermodynamics
• Operational interpretation of the Stabilizer Entropy
• Designs from magic-augmented Clifford circuits