# Proof that encoder for a stabilizer code is in the Clifford group

Given a stabilizer code on $$n$$ qubits defined by a set of stabilizers $$S_1,\cdots S_m$$; The encoder $$E$$ is a matrix in $$U(2^n)$$ (unitary group) such that $$S_i E v = E v$$. I'm pretty sure that $$E$$ is always in the clifford group (a subgroup of $$U$$) and I think the proof shouldn't be too hard but I can't think of it. Does anyone know how to show this or a reference.

Assuming the encoder itself doesn't have to be fault tolerant, you can do the proof constructively.

1. Prepare the code space by projecting each of the stabilizers into the +1 eigenstate.

• For each stabilizer $$S$$:
• Measure $$S$$.
• If you're in the -1 eigenspace of $$S$$, apply Pauli gates to flip the stabilizer (but not other stabilizers). E.g. stim can compute these Paulis for you via stim.TableauSimulator.measure_kickback.
2. Perform an observable swap between the physical qubit you want to encode and the logical observables.

• Perform the Paulis making up a logical $$X$$ all controlled by the physical qubit.
• Apply a Hadamard to the physical qubit.
• Perform the Paulis making up a logical $$Z$$ all controlled by the physical qubit.
• Apply a Hadamard to the physical qubit.
• Perform the Paulis making up a logical $$X$$ all controlled by the physical qubit.

Okay, so actually that strategy is not quite Clifford, because it uses measurements. But you can replace each measurement with a controlled flipping of an ancilla (e.g. flip an ancilla conditioned on the stabilizer), and then the conditional Paulis can be controlled by the ancilla. Then just throw away the ancillae at the end.

For example, consider the distance two surface code which has stabilizers $$X_1 X_2$$ and $$X_3 X_4$$ and $$Z_1 Z_2 Z_3 Z_4$$ and the logical observable pair $$Z_1 Z_2$$ and $$X_1 X_3$$. Here's an encoding circuit:

The first half of the circuit is "measuring" the stabilizers onto ancillae and then applying Pauli kickbacks dependent on the results to get all of the stabilizers into the +1 eigenstate. The hardest part was finding the Pauli kickbacks; I just fiddled around with each one until the result become deterministic.

The second half of the circuit is preparing a magic state to inject (this part isn't Clifford because I wanted to show that the state can be arbitrary) and then observable swapping it into the logical observables.

• but are all these operations in the Clifford group? I can implement the encoder using the standard form of the stabilizers but that uses more complex gates (CCX or CCCX for example) which are in higher hierarchy Clifford groups not the standard one – unknown May 20 at 18:30
• @unknown Measuring a Pauli observable only requires stabilizer operations. You can "measure onto an ancillae" by using phase kickback from a series of controlled X, Y, and Z gates. – Craig Gidney May 20 at 18:32
• So it seems that the answer is "yes" the encoder is in the Clifford group. The left hand side part (encoder) uses controlled gates based on a single qubit; I think that condition alone is enough to prove that it's in Clifford. Come to think of it the standard form of stabilizer codes I just checked only needs single qubit controlled gates (so I take back what I said about CCX and CCCX gates). That could be the path for a proof but there's probably a more abstract and direct proof. – unknown May 20 at 18:59
• @unknown Well a stabilizer code uses stabilizer states, and stabilizer states are the states that can be produced by a stabilizer circuit, and Clifford circuits can produce everything a stabilizer circuit can produce... – Craig Gidney May 20 at 19:13
• is it that simple? or an accidental case of circular logic? what's a "stabilizer circuit"? stabilizers themselves are in the Pauli group (subgroup of Clifford) but certainly the encoder isn't in Pauli. – unknown May 20 at 19:28