# Algorithm for finding Pauli stabilizers of a code

Given the zero logical $$|0_L\rangle$$ and one logical $$|1_L\rangle$$ for an $$[[n,1,d]]$$ code is there a well known/ efficient algorithm for determining which Pauli operators stabilize the code?

• How are $|0_L\rangle$ and $|1_L\rangle$ given to the program? A stabilizer tableau? A state vector? Oct 3, 2022 at 2:14
• @CraigGidney I was thinking just as vectors in $\mathbb{C}^{2^n}$ Oct 3, 2022 at 2:38
• And what would you consider efficient? The input size is growing exponentially in the number of qubits, which seems like a pretty big problem for efficiency. Oct 3, 2022 at 2:58
• @CraigGidney Currently I am working with $|0_L>$ and $|1_L>$ in $\mathbb{C}^{2^n}$ for $n \leq 30$ really $n \leq 20$ and all the coefficients of $|0_L>, |1_L>$ are either $0, 1, -1$. And the level of efficiency I've been working with is exactly the "dumb" algorithm that unknown described: literally just applying all $4^n$ Paulis and keeping the ones that stabilize both $|0_L>$ and $|1_L>$. I don't know much about algorithms and all that so by efficient I guess I just mean anything that can do that task faster than the "dumb" algorithm I'm currently using. Oct 3, 2022 at 14:46
• the stabilizers should form a group; so there should be a much smaller set of generators that produces the full list. GAP can find a minimal set of generators for a group but you'll need to convert your list to something GAP can process. Oct 3, 2022 at 15:04

There are two parts to this question: converting from a state vector representation to a stabilizer representation, and then determining the Paulis that transition between two stabilizer states.

# State vector to stabilizer tableau

This functionality is implemented in stim.TableauSimulator.set_state_from_state_vector.

The conversion is performed by iteratively finding Clifford operations that map the initial state vector to the state $$|000...0\rangle$$, and then running those operations backwards in a stabilizer simulator to recover the original state as a stabilizer tableau. As written it takes $$O(n^22^n)$$ time where $$n$$ is the number of qubits. It could be improved by reducing the size of the state vector as the algorithm progresses, instead of keeping it at full size the whole time.

The steps are:

1. Find a non-zero entry in the state vector, then apply Pauli X gates to permute the vector so that the found non-zero amplitude ends up as the amplitude of the $$|000..0\rangle$$.
2. Find a second non-zero entry in the state vector. If there is none, goto 6. Otherwise let $$k_2$$ be the index of that entry.
3. If $$k_2$$'s binary representation has more than one 1, use CNOT operations between the bit positions of those 1s to cancel all but one 1 out. This rewrites the state vector and rewrites $$k_2$$.
4. $$k_2$$ is now a power of 2. Apply S gates to qubit $$\log_2(k_2)$$ until the amplitude of $$|k_2\rangle$$ is equal to the amplitude of $$|000..0\rangle$$. Then apply a Hadamard to qubit $$\log_2(k_2)$$. If this fails, or if there are any non-zero amplitudes between 0 and $$k_2$$ after it's done, the input wasn't a stabilizer state.
5. Goto 2.
6. Run accumulated operations backwards to get stabilizer state.

# From two stabilizer tableaus to a Pauli product

A stabilizer tableau representing a state can be placed into a canonical form by prepending operations which do nothing to the 0 state into the tableau (CX, CZ, and S). Because Pauli operations only affect the signs of the tableau, the Paulis being different doesn't interfere with reaching the canonical form.

So, given two stabilizer tableaus, perform state canonicalization on them. If they actually represented the same state, then they now have identical contents except for their signs. Multiply together the destabilizers for each stabilizer whose sign differs between the two tableaus. The result is a Pauli product by which they differ.

# Putting it all together; almost

Given $$|0_L\rangle$$ and $$|1_L\rangle$$ you can find a set of stabilizers for each, and find a Pauli product which accounts for the differences between the two stabilizer sets. This should be the logical X operator, though I'm not positive that's guaranteed.

I'm not sure whether or not this counts as finding the code, since you still don't have a "good" set of stabilizer generators. Almost all the hard work of making a code is finding good generators that can be measured efficiently, and we've done none of that.