An important task required to build a scalable, fault-tolerant quantum computer is to efficiently represent an arbitrary single-qubit rotation by fault-tolerant quantum operations. Traditionally, the method for decomposing a single-qubit unitary into a discrete set of gates is Solovay-Kitaev decomposition, which in practice produces a sequence of depth O(log c (1/ )), where c ∼ 3.97 is the state-of-the-art. The proven lower bound is c = 1, however an efficient algorithm that saturates this bound is unknown. In this paper, we present an alternative to Solovay-Kitaev decomposition employing state distillation techniques which reduces c to between 1.12 and 2.27, depending on the setting. For a given single-qubit rotation, our protocol significantly lowers the length of the approximating sequence and the number of required resource states (ancillary qubits). In addition, our protocol is robust to noise in the resource states. Given recent progress in quantum algorithms, quantum error correction, and quantum hardware, a scalable quantum computer is becoming closer and closer to reality. For many proposed quantum computer architectures, e.g., topological systems based on the braiding of non-Abelian anyons [1] [2] [3] [4] [5] or the surface code model based on code deformation [6, 7] , so-called Clifford operations and stabilizer state preparations or measurements can be implemented efficiently and accurately. However, these operations alone are not sufficient for quantum universality since they can be simulated classically [8] [9] [10] . One technique to achieve quantum universality is to use magic state distillation [11] [12] [13] to augment the set with a single non-Clifford operation, e.g., the single-qubit π/8 gate, T . This augmented set can be used to approximate any single-qubit unitary using Solovay-Kitaev decomposition [14] . The Solovay-Kitaev theorem [15] states that for any and single-qubit gate U , U can be approximated to precision using Θ(log c (1/ )) gates drawn from a universal, discrete gate set, where c is a small constant. Stateof-the-art implementations of Solovay-Kitaev decomposition result in c ∼ 3.97 [14, 16] , resulting in an average decomposition sequence with hundreds to thousands of T gates [16] . Each T gate requires a number of copies of a quantum magic state |H (Hadamard +1-eigenstate), where the number depends on the specific state distillation protocol and purity of the state [11] [12] [13] . Therefore, it is especially important to minimize the number of T gates when decomposing a rotation, since each T gate requires additional ancillary qubits for implementation. In this paper, we present an alternative protocol to Solovay-Kitaev decomposition that allows the implemen- * Guillaume.Duclos-Cianci@USherbrooke.ca † ksvore@microsoft.com tation of single-qubit rotations through the use of distilled magic |H states. We show that the resources required by our protocol are substantially fewer than the resources required by state-of-the-art implementations of Solovay-Kitaev decomposition [16] , in both the number of gates and the number of quantum magic states necessary to apply an arbitrary single-qubit unitary. Solovay-Kitaev decomposition [14] [15] [16] enables the approximation of any gate using an approximately universal set of elementary gates, e.g., {H, T, Λ(X)}, where Λ(X) denotes the controlled-NOT gate. In particular, one can approximate any single-qubit unitary operation using the set {H, T }. Magic state distillation is then used to produce the magic |H states necessary to implement the T gate. We call a state |ψ magic if given n noisy copies of |ψ and the ability to perform perfect Clifford operations, we can obtain, or "distill", a purer copy of |ψ from a Clifford circuit applied to the n noisy copies of |ψ . We can then obtain even purer states which are arbitrarily close to the perfect state by applying the protocol recursively [11] [12] [13] . These distilled states can be used to implement nonClifford operations, e.g., the T gate, as described below. We briefly review how to perform an arbitrary rotation about the Z-axis using a resource state, and how to apply the T gate. We assume that Clifford operations are applied perfectly, since they can be implemented faulttolerantly, and that the resource states are very close to pure. One can use the protocols of [11, 12] to perform the initial distillation in order to obtain arbitrarily pure resource states for input. We focus on the +1 eigenstate arXiv:1210.1980v1 [quant-ph]
REF and shown to enable approximation of any single-qubit unitary.
A State Distillation Protocol to Implement Arbitrary Single-qubit Rotations
Phys. Rev. A 88, 042325 (2013)
Physics Computer Science