ABSTRACT The quantum gate teleportation mechanism allows for the fault‐tolerant implementation of “Clifford hierarchies” of gates assuming, among other things, a fault‐tolerant implementation of the Pauli gates. We discuss how this method can be extended to assume the fault‐tolerant implementation of any orthogonal unitary basis of operators, in such a way that each of these bases can be used to implement its own hierarchy of gates. Noticing that all of these hierarchies are defined through the same algebraic construction, we study this construction from a group‐theoretic perspective. This allows us to deduce general results concerning all the hierarchies. We also discuss alternative hierarchies, study their properties, and compute some of their first few levels.
ABSTRACT The quantum gate teleportation mechanism allows for the fault‐tolerant implementation of “Clifford hierarchies” of gates assuming, among other things, a fault‐tolerant implementation of the Pauli gates. We discuss how this method can be extended to assume the fault‐tolerant implementation of any orthogonal unitary basis of operators, in such a way that each of these bases can be used to implement its own hierarchy of gates. Noticing that all of these hierarchies are defined through the same algebraic construction, we study this construction from a group‐theoretic perspective. This allows us to deduce general results concerning all the hierarchies. We also discuss alternative hierarchies, study their properties, and compute some of their first few levels.
The Clifford hierarchy is a nested sequence of sets of quantum gates that can be fault-tolerantly performed using gate teleportation within standard quantum error correction schemes. The groups of Pauli and Clifford gates constitute the first and second ‘levels’, respectively. Non-Clifford gates from the third level or higher, such as the T gate, are necessary for achieving fault-tolerant universal quantum computation. Since it was defined 26 years ago by Gottesman–Chuang, two questions have been studied by numerous researchers. First, precisely which gates constitute the Clifford hierarchy? Second, which subset of the hierarchy gates admit efficient gate teleportation protocols? We completely solve both questions in the practically relevant case of the Clifford hierarchy for gates of one qubit or one qudit of prime dimension. We express every such hierarchy gate uniquely as a product of three simple gates, yielding also a formula for the size of every level. These results are a consequence of our finding that all such hierarchy gates can be expressed in a certain form that guarantees efficient gate teleportation. Our decomposition of Clifford gates as a unique product of three elementary Clifford gates is of broad applicability.
The Clifford hierarchy is a nested sequence of sets of quantum gates that can be fault-tolerantly performed using gate teleportation within standard quantum error correction schemes. The importance of these gates has motivated numerous studies of their structure. Zeng-Chen-Chuang conjectured in 2007 that all hierarchy gates are generalised semi-Clifford, i.e. take the form C1ΠDC2 for Clifford gates C1,C2, a permutation gate Π, and a diagonal gate D; Beigi-Shor proved in 2008 that this holds for all third-level gates.
We construct a five-qubit gate that is in the fifth level of the Clifford hierarchy but is not generalised semi-Clifford. Rather than simply present and verify our counterexample to the generalised semi-Clifford conjecture, we show how its form can be deduced. Our counterexample also demonstrates that the Clifford hierarchy is not closed under inverses.
Fault-tolerant quantum computation is a basic problem in quantum computation, and teleportation is one of the main techniques in this theory. Using teleportation on stabilizer codes, the most well-known quantum codes, Pauli gates and Clifford operators can be applied fault-tolerantly. Indeed, this technique can be generalized for an extended set of gates, the so called Ck hierarchy gates, introduced by Gottesman and Chuang (Nature, 402, 390-392). Ck gates are a generalization of Clifford operators, but our knowledge of these sets is not as rich as our knowledge of Clifford gates. Zeng et al. in (Phys. Rev. A 77, 042313) raise the question of the relation between Ck hierarchy and the set of semi-Clifford and generalized semi-Clifford operators. They conjecture that any Ck gate is a generalized semi-Clifford operator. In this paper, we prove this conjecture for k=3. Using the techniques that we develop, we obtain more insight on how to characterize C3 gates. Indeed, the more we understand C3, the more intuition we have on Ck, k≥4, and then we have a way of attacking the conjecture for larger k.
Fault-tolerant quantum computation is a basic problem in quantum computation, and teleportation is one of the main techniques in this theory. Using teleportation on stabilizer codes, the most well-known quantum codes, Pauli gates and Clifford operators can be applied fault-tolerantly. Indeed, this technique can be generalized for an extended set of gates, the so called Ck hierarchy gates, introduced by Gottesman and Chuang (Nature, 402, 390-392). Ck gates are a generalization of Clifford operators, but our knowledge of these sets is not as rich as our knowledge of Clifford gates. Zeng et al. in (Phys. Rev. A 77, 042313) raise the question of the relation between Ck hierarchy and the set of semi-Clifford and generalized semi-Clifford operators. They conjecture that any Ck gate is a generalized semi-Clifford operator. In this paper, we prove this conjecture for k=3. Using the techniques that we develop, we obtain more insight on how to characterize C3 gates. Indeed, the more we understand C3, the more intuition we have on Ck, k≥4, and then we have a way of attacking the conjecture for larger k.
The Clifford hierarchy C1⊂C2⊂⋯ was introduced by Gottesman and Chuang (arXiv:quant-ph/9908010) to characterize gates that admit fault-tolerant implementation by gate teleportation. Yet, despite its rich mathematical structure and the attention it has received in recent years, little is known about Ck for k>3. Most progress has focused on identifying structural properties of restrictions of the hierarchy, such as diagonal gates and gates on systems of small dimension d or with few qudits.
The generalized semi-Clifford conjecture, proposed by Zeng et al. (arXiv:0712.2084), states that every gate in ∪kCk is, up to multiplication by Cliffords, the product of a permutation and a diagonal matrix. Beigi and Shor proved the case d=2, k=3 (arXiv:0810.5108) and Pllaha et al. found an alternative proof by exploiting fixed points of the conjugation map induced by (a Clifford correction of) U∈C3 on the span of maximal stabilizer subgroups (arXiv:2006.14040). By extending their fixed-point arguments to the group Γ1(U) generated by UPU† and beyond, we prove the conjecture for k≤4 and any prime dimension d.
Our proof centers on conjugation groups Γ1(U),Γ2(U),… of U∈Ck, which we expect to be a useful tool in the study of the Clifford hierarchy more generally. We also show a natural sufficient condition on such groups for gates in higher levels to be generalized semi-Clifford.
Quantum gate teleportation is a key technique in fault-tolerant quantum computation that uses resource states to implement logical gates. Here, we develop a theory of magic gate teleportation (MGT), a form of quantum gate teleportation that uses non-stabilizer resource states to implement non-Clifford unitary gates on arbitrary input states without revealing information about those states. This setting is motivated by the canonical approach to implementing logical non-Clifford gates in fault-tolerant quantum computation. We uncover a hidden structure within MGT---after backpropagating the Pauli measurements, MGT protocols can be viewed as encoding the input state into a stabilizer code heralded by the measurement outcomes, followed by a logical non-Clifford gate. Using this structure, we construct MGT protocols for any resource state obtained by applying commuting Pauli rotations to a stabilizer state, and provide an efficient algorithm for synthesizing their circuit implementations. Conversely, we prove that directly useful single-qubit resource states are necessarily Clifford-equivalent to diagonal states, and establish the same constraint for multi-qubit resource states used in a broad class of MGT protocols. In particular, the output state distilled from the [[5,1,3]] protocol is not directly useful for any MGT protocols, though it can be probabilistically converted into directly useful states. Finally, we identify conditions under which the feedforward operators can be implemented by Pauli operators, shedding light on the paradigm of algorithmic fault tolerance and simplifying the feedforward operations needed for quantum computing.