We give an efficient randomized algorithm for approximating an arbitrary element of SU(2) by a product of Clifford+T operators, up to any given error threshold e > 0. Under a mild hypothesis on the...
We give an efficient randomized algorithm for approximating an arbitrary element of SU(2) by a product of Clifford+T operators, up to any given error threshold ε>0. Under a mild hypothesis on the distribution of primes, the algorithm's expected runtime is polynomial in log(1/ε). If the operator to be approximated is a z-rotation, the resulting gate sequence has T-count K+4log2(1/ε), where K is approximately equal to 10. We also prove a worst-case lower bound of K+4log2(1/ε), where K=−9, so that our algorithm is within an additive constant of optimal for certain z-rotations. For an arbitrary member of SU(2), we achieve approximations with T-count K+12log2(1/ε). By contrast, the Solovay-Kitaev algorithm achieves T-count O(logc(1/ε)), where c is approximately 3.97.
We give an efficient randomized algorithm for approximating an arbitrary element of $\SU(2)$ by a product of Clifford+T operators, up to any given error threshold ϵ>0. Under a mild hypothesis on the distribution of primes, the algorithm's expected runtime is polynomial in log(1/ϵ). If the operator to be approximated is a z-rotation, the resulting gate sequence has T-count K+4log2(1/ϵ), where K is approximately equal to 10. We also prove a worst-case lower bound of K+4log2(1/ϵ), where K=−9, so that our algorithm is within an additive constant of optimal for certain z-rotations. For an arbitrary member of $\SU(2)$, we achieve approximations with T-count K+12log2(1/ϵ). By contrast, the Solovay-Kitaev algorithm achieves T-count O(logc(1/ϵ)), where c is approximately 3.97.
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.
Approximating a given unitary operator into a discrete set of gates is of great importance in quantum computation. This problem can be seen as a source quantization problem where the unitary operator is considered as the source. Elements of the Clifford hierarchy can be implemented fault-tolerantly using quantum gate teleportation. This motivates the development of algorithms that quantize unitary operators into Clifford hierarchy elements. In this paper, we present a fast algorithm for approximating arbitrary n-qubit unitaries with Clifford matrices. The algorithm relies on the Clifford transvection decomposition of the Clifford group. The algorithm greedily applies Clifford transvections taking the input unitary closer to the identity matrix. To make the algorithm fast, we take advantage of the Pauli basis representation for unitary matrices to parallelize matrix distance computations. The complexity of the proposed algorithm is O(n 4n). Based on simulation results, the proposed algorithm outperforms the state of the art method.
We study the Clifford+T synthesis of quantum multiplexers U=⨁i=12nUi: an n-qubit control register selects which single-qubit gate Ui∈SU(2) acts on the target qubit. For each block Ui, consider the minimum even T-count needed to approximate it within diamond distance ε without ancillae, and let m be the largest of these costs. For an arbitrary multiplexer U, we construct an approximation of U within the same distance using at most m+O(2n(m+1))T gates. With one control qubit, the cost is m+O(1) and no ancillae are required. We also prove a lower bound that allows the Clifford+T circuit to use any number of clean ancillae initialized to zero and returned exactly to zero. For fixed n and independent Haar-random blocks, the minimum T-count among these circuits lies between (3−δ)log2(1/ε) and (3+δ)log2(1/ε) for every fixed δ>0, except with probability O(εcn,δ) as ε→0. The optimal leading coefficient is therefore the same as for a single Haar-random SU(2) gate. In the lower-bound proof, unitarity forces pairs of off-diagonal blocks describing transitions in opposite directions to satisfy cancellation relations with residuals of order ε2. We combine these relations with the arithmetic of Clifford+T circuits to bound the Haar measure of targets compatible with each pair of off-diagonal blocks. As an application, we obtain ancilla-free approximations of Haar-random SU(4) gates within diamond distance ε, using at most (9+δ)log2(1/ε)T gates for every fixed δ>0, except with probability O(εcδ) with cδ>0.