The Eastin-Knill theorem and transversal gates

Short answer: The Eastin-Knill theorem, published in Physical Review Letters in 2009, shows that a quantum code able to detect an arbitrary error on any single physical subsystem cannot have a universal set of transversal encoded gates. Transversal gates are attractive because they do not spread errors within a code block, so fault-tolerant schemes need other methods to complete a universal gate set. This is a theory result about code design.

What defines a transversal operator?

A transversal operator is defined by its specific coupling pattern across physical subsystems. By definition, these operators do not couple physical subsystems within the same code block. Instead, an operator is considered transversal if it exclusively couples subsystems within the same part of a transversal partition. This partition ensures that each part contains one subsystem from each code block. Consequently, a transversal operator couples no subsystem of a code block to any but the corresponding subsystem in another code block. This structural constraint is the fundamental characteristic that distinguishes transversal gates from other encoded operations.

Why are transversal gates considered fault tolerant?

Transversal gates play an important role in the theory of fault-tolerant quantum computation due to their simplicity and robustness to noise. Because they do not couple subsystems within the same code block, such operators do not spread errors within code blocks. This property makes them inherently fault tolerant. While transversal operators can spread errors between code blocks, thereby increasing the number of locations at which a code block’s error might have originated, the total number of errors necessary to cause a failure remains unchanged. This is because errors on different code blocks are treated independently. In contrast, non-transversal operators might convert an error on a single subsystem into multiple errors within the same block, potentially causing failure.

What does the theorem prove about universality?

The theorem addresses a long-standing conjecture that transversal encoded gate sets cannot be universal. The authors show that the ability of a quantum code to detect an arbitrary error on any single physical subsystem is incompatible with the existence of a universal, transversal encoded gate set for the code. In other words, such a code cannot have a universal gate set made only of transversal gates.

How does this impact fault-tolerant computation strategies?

The authors note that other methods of ensuring fault tolerance are required, as some encoded gates cannot be implemented transversally. A strategy relying solely on transversal gates therefore cannot reach universality for codes with single-error detection. The theorem does not prohibit transversal gates. It says non-transversal techniques or other fault-tolerance mechanisms must supply the rest of a universal gate set.

FAQ

Can transversal gates be used in fault-tolerant quantum computation?

Transversal gates are valued for their simplicity and robustness to noise. They are inherently fault tolerant because they do not spread errors within code blocks. However, they cannot constitute a universal set for codes that detect single-subsystem errors.

What is the core incompatibility identified in the theorem?

The core incompatibility is between a code's ability to detect arbitrary errors on any single physical subsystem and the existence of a universal, transversal encoded gate set. If the code detects single-subsystem errors, a universal transversal gate set cannot exist.

Do transversal operators couple subsystems within the same code block?

No. By definition, transversal operators do not couple physical subsystems within the same code block. They exclusively couple subsystems within the same part of a transversal partition, linking corresponding subsystems across different code blocks only.

Does the theorem prohibit all non-transversal operations?

No. The theorem does not prohibit non-transversal operations. It states that transversal gates alone cannot be universal for codes with single-error detection. Other methods of ensuring fault tolerance are required to implement the remaining encoded gates.

Is the universality of transversal gates a solved problem?

For codes of this kind, yes. The paper addresses a long-standing conjecture that transversal encoded gate sets cannot be universal. The authors show that for codes capable of detecting arbitrary single-subsystem errors, a universal transversal gate set is incompatible with the code's error-detection capability.