Love, Logical Gates, and Unrealistic Expectations

I have a confession. I watch YouTube recaps of movies and TV shows (at double speed) and then discuss them as if I had actually watched them. My wife hates it.

We were at a party, and she overheard me discussing Game of Thrones.

“He’s a phony! He hasn’t watched a single episode!”

“I’m not sure what she’s talking about. Anyways, can you believe Arya killed the Night King?”

I recently “watched” Materialists. It’s about Lucy Mason, a matchmaker whose clients shop for partners by spec sheet: height, age, income, even star sign. One wants a 6′4″ man in his forties who earns over $500,000 and has a good hairline. She calls such guys “unicorns.”

This is a lot like my job.

I’m looking for quantum error-correcting code unicorns. The main difference is my boxes are different: large code distance, high encoding rate, low-weight checks, low qubit degree, and cheap logical gates.

Of these, that last box has been on my mind a lot lately, and it’s the focus of our recent paper. What expectations should I have when searching for a code in this respect? Am I’m being as unrealistic as Lucy’s clients?

Some of Jerry Seinfeld’s best/worst reasons for breaking up with someone. I’m trying not to bring the same standards to choosing quantum error-correcting codes.

What are we looking for?

We know of codes that make for excellent quantum memories. They pack many logical qubits into relatively few physical ones, protect them with a large code distance, and allow for errors to be checked in an efficient way: each check involves only a few physical qubits, and each physical qubit participates in only a few checks. Several boxes checked already. Not quite a unicorn, but close.

The problem is that computation is another story. Intuitively, the more logical qubits we pack into a shared physical system, the harder it can become to operate on one without disturbing the others. This can make it difficult to implement addressable logical gates.

There are several ways to implement such gates, and I won’t survey them here. But, among the cheapest are those implemented using only physical single-qubit gates and qubit permutations. The latter means rearranging the physical qubits, or sometimes just relabelling them in software. Note that, whether or not permutations are cheap is hardware dependent, but for neutral atom platforms they can be. Because the information is encoded collectively, these simple physical operations can produce various gates, including entangling logical gates.

These gates have a lot going for them. The single-qubit operations fit into one parallel layer. They require no extra qubits or measurements. And when permutations are performed by physical rearrangement or software relabelling, they don’t spread errors between physical qubits. Single-qubit gates are also typically among the lowest error operations available on hardware.

If you add one restriction—that the physical single-qubit gates must be Cliffords—these cheap gates become automorphism gates. The restriction is useful because we have tools for finding codes that support them. We can construct such codes analytically or search for them numerically. We’re much less good at doing the same for arbitrary single-qubit rotations. That combination of cheap implementation and tractable code design has made automorphism gates increasingly popular. They play a key role in most modern quantum computing architectures, for example, Mitten codes, IBM’s tour de Gross, and the Pinnacle architecture.

These architectures use them both directly to perform logical gates and alongside the more resource-intensive method of code surgery to reduce its overhead. Surgery involves joint measurements between encoded systems, often with additional resource states and repeated measurement rounds. The aim is to let automorphism gates handle as much of the computation as possible, reducing how much surgery is needed.

Naturally, when searching for a code, we’d like a large automorphism group: a large collection of distinct logical operations available through these cheap physical ingredients.

High rate, large distance, simple checks, and now a large automorphism group. Add it to the list.

Four things I learned

In our work we set out to understand how much automorphism gates can offer, and what a code has to give up to support them. Below are some things I learned (for a complete story you’ll need to read the paper).

(1) How much can you ask of one code?

Suppose I temporarily relax the other items on my checklist. I’ll allow as many physical qubits as needed and put aside concerns about encoding rate and check weight. Fix only the number of logical qubits, k. How large an automorphism group could a code possibly have?

For stabilizer codes encoding k > 2 logical qubits, we determine the largest attainable automorphism group. In a suitable logical basis, it consists of all operations built from addressable logical phase gates (S) and controlled-NOT gates (CNOT). We also construct codes that attain this maximum. So this is a ceiling we can actually reach. (The cases k = 1 and k = 2 are special; we discuss them in the paper.)

CSS codes are an important family of quantum error-correcting codes. They allow bit-flip and phase-flip errors to be checked separately, and include most widely studied codes. CSS codes can also attain this maximum.

The S gate changes the relative phase between a qubit’s two basis states by a quarter turn. CNOT flips a target qubit conditional on the state of the control qubit, and can generate entanglement. Addressability means we can apply S to any chosen logical qubit and CNOT to any chosen control–target pair. All combinations of these gates make up the group.

So, is that a lot?

It depends what you mean by “a lot.” Compared with the full logical Clifford group, this group contains exponentially fewer gates. But it shares a useful feature with the full Clifford group: adding just one suitable non-Clifford gate type makes it universal. Together, these gates let us approximate any quantum computation as accurately as we like.

Clients could always ask Lucy for someone a little taller or a little wealthier. But with automorphism gates, there’s a clear limit to what you can ask for.

(2) The anatomy of a good match

The automorphism gates of CSS codes have a useful structure. Every automorphism combines physical single-qubit Cliffords and permutations to produce a logical gate. For a CSS code, we find that—apart from a special case discussed in the paper—the Clifford layer and the permutation are each on their own valid logical gates. We can apply either part independently while preserving the encoding.

This makes studying CSS automorphisms much simpler. We can study which logical gates come from physical single-qubit Cliffords, study which come from permutations, and then combine the answers.

The two ingredients also have complementary capabilities. Physical single-qubit Cliffords cannot implement logical CNOT or SWAP gates. In the generic CSS setting, their largest attainable logical group is generated by addressable S and CZ gates, where CZ is a two-qubit entangling phase gate.

Permutations fill the other role. Their largest attainable logical group is generated by all addressable CNOTs, but they cannot implement logical S or CZ gates. Together, the two ingredients can attain the maximum automorphism group from the previous section.

Like good partners, they can each stand on their own—and together, they complete each other.

(3) High standards, higher qubit counts

In the first result, I gave my ideal code an unlimited physical-qubit budget. Now it’s time to put that budget back into the picture.

For a stabilizer code encoding k > 2 logical qubits, supporting all addressable logical CNOTs through automorphisms requires at least

n≥2k−1n \geq 2^k-1

physical qubits. That’s exponential growth. Since the maximum automorphism group contains all these CNOTs, reaching that maximum inherits the same cost. This extends earlier bounds on phantom codes.

This bound is tight: a certain type of phantom code attains it.

The other ingredient from the previous section is considerably cheaper. Supporting all addressable logical S and CZ gates through physical single-qubit Cliffords requires only

n≥k(k+1)2.n \geq \frac{k(k+1)}{2}.

We also attain this quadratic bound with complete-graph codes. Their construction uses one physical qubit to store each logical qubits parity and one physical qubit for each pair of qubits to store the pairwise parities—whether the corresponding bits agree or differ. This information allows physical single-qubit phase gates to implement logical CZs.

There is an important qualification. The bounds hold at every code distance, but our constructions attain these exact minima at distance one, where some single-qubit errors can go undetected. We can increase the distance through concatenation: encoding each physical qubit in a suitable additional code. This preserves the gate capabilities and adds physical qubits. Finding the optimal cost at a specified higher distance remains open.

So a gate can be cheap to apply while demanding an expensive code.

As with finding a partner, the details of the wish list matter. For quantum codes, the full set of addressable CNOTs is a much more expensive request than all addressable S and CZ gates.

(4) Looking for love in the wrong metrics

S and CZ have something important in common: they are diagonal gates. They change the relative phases between basis states without mixing those states. We wondered whether their relatively low qubit cost extends to diagonal non-Clifford gates.

It does. Here we expand the physical toolbox beyond automorphisms, allowing diagonal single-qubit rotations that needn’t be Cliffords.

For example, we construct codes supporting all addressable logical T, controlled-S, and controlled-controlled-Z (CCZ) gates using only physical single-qubit phase rotations. T applies an eighth-turn phase, while the controlled gates make phase changes depend on additional qubits. Supporting this whole collection requires only cubically many physical qubits.

More generally, the polynomial scaling persists at every fixed level t of the Clifford hierarchy, a sequence of gate classes extending beyond Cliffords. We can support all addressable diagonal logical gates at that level using

n=O(kt)n = O(k^t)

physical qubits. Our complete-hypergraph codes attain the corresponding bounds by extending the pairwise-parity construction to larger subsets of logical qubits. As before, the exact minima occur at distance one, and suitable concatenation increases the distance while preserving the gates.

So being non-Clifford doesn’t automatically make a gate set expensive in physical qubits. In this setting, the sharp cost separation lies between diagonal gates and CNOT-type gates.

There’s another misleading metric: group size. These diagonal non-Clifford groups can contain many more logical operations than the entire CNOT group, yet require polynomially many physical qubits where the CNOT group requires exponentially many.

Neither the Clifford label nor the group’s size tells me what the relationship will cost.

A few love stories I’ve actually watched—and would recommend: About Time, The Big Sick, Midnight in Paris, The Spectacular Now, and Scott Pilgrim vs. the World.

Happily ever after, subject to constraints

So how did this project change my approach to matchmaking code construction?

Automorphism gates are not something to blindly maximize. Achieving the maximum comes at the price of an encoding rate that falls rapidly as k grows. Maximum gate sets may still be worthwhile for moderate k, especially as hardware scales. But, when high rate is a priority, I should choose automorphisms selectively, targeting the expensive operations I want them to replace.

I also need to look at the structure of the logical action. Neither Cliffordness nor logical-group size reliably predicts physical-qubit cost.

There are plenty of questions left. Here are a few I’m particularly keen to answer:

  • How does the minimum qubit cost depend on distance?
  • How much can we save by asking for a smaller gate set—for example, CNOTs between only selected logical pairs?
  • Can we extend the theory to arbitrary physical single-qubit gates? These retain the appeal of simple, depth-one circuits. We need better methods for finding and analyzing codes that support them.
  • How should we uses automorphisms? They can perform logical gates directly or help make code surgery cheaper. What combination gives the greatest benefit for a particular workload and hardware platform?
  • What changes if we allow more general physical two-qubit gates? These could act within a codeblock or between blocks. Which new logical operations become possible, and what do they cost in connectivity, circuit depth, and error spreading?

If you’ve only skimmed this post, feel free to discuss it at your next party as though you read every word. Just make sure my wife isn’t there.

1 thought on “Love, Logical Gates, and Unrealistic Expectations”

Your thoughts here.