Adaptive Quantum Homeopathy

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, named Quantum Homeopathy, 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. Inspired by the principle of homeopathy, our method applies a k-design only to a subsystem of size Θ(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 varepsilon-approximate unitary k-design on n qubits. We prove that this construction achieves full quantum security against adaptive adversaries using only {O}\(k² logvarepsilon^-1\) non-Clifford gates. If one requires security only against polynomial-time adaptive adversaries, the non-Clifford cost decreases to {O}\(k + log^1+c varepsilon^-1\). This is optimal, since we show that at least Ω(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.