# Stabilizer state verification and specification from state vector

Given an arbitrary $n$-qudit state vector $|\psi\rangle =\sum_i c_i| i \rangle \in \mathbb{C}_d^n$ for some orthonormal basis $\{|i\rangle\}$, what is the most efficient way one can:

1. Verify whether the state is a stabilizer state (i.e. can be defined by $n \leq m \leq 2n$ stabilizer generators, with equality for $d=2$), and if so,
2. Find the state's stabilizer generators (in the form of some tensor product of local Pauli matrices).
• Presumably you want the stabilizer generators to be tensor products of single-qudit Pauli-like operators? – DaftWullie Jul 24 '18 at 16:13
• Sure. I think this a natural consequence of the definition of a stabilizer state. – SLesslyTall Jul 24 '18 at 16:34
• How are you supplied the state? As a quantum state? As a vector of all coefficients? As a quantum circuit? And do you care in any way about the efficiency of the procedure? – Norbert Schuch Jul 24 '18 at 21:16
• But if states are provided as a list of coefficients, do you not already have a problem with efficiency? – DaftWullie Jul 25 '18 at 10:18
• @NorbertSchuch I think you may have misunderstood me; my "semantic" comment was a purely pedantic point on whether one can call a circuit which is decomposable into Clifford gates as non-Clifford, rather than a claim about the problem of deciding if a given circuit produces a stabilizer state, which I agree is non-trivial. W.r.t efficiency, I am mainly concerned with what is the most efficient method to solve the problem, rather than whether an efficient method in N exists (e.g. if, say, you were certified to be given the minimal basis representation of the state) – SLesslyTall Jul 26 '18 at 7:48

Here's a necessary condition that might help recognise potential stabilizer states. I'll state it for qubits as that's what I'm used to thinking about, but I suspect it can be generalised:

all the non-zero amplitudes of a stabilizer state must have the same magnitude.

To see this, let's assume that the state $|\psi\rangle$ is an $n$-qubit stabilizer state with linearly independent stabilizers $\Lambda=\{K_i\}_{i=1}^n$. In other words, $K_i|\psi\rangle=|\psi\rangle$, $K_i=K_i^\dagger$ and $[K_i,K_j]=0$. Let $x,y\in\{0,1\}^n$ be such that $\langle x|\psi\rangle\neq 0$ and $\langle y|\psi\rangle\neq 0$.

Now consider $$|\psi\rangle\langle \psi|x\rangle=\left(\frac{1}{2^n}\prod_{K\in\Lambda}(\mathbb{I}+K)\right)|x\rangle$$ If we multiply out the terms, there are all the different possible products of subsets of stabilizers, each turning $|x\rangle$ into a (possibly different) basis state. Hence, there is at least one subset $S\subseteq\Lambda$ such that $\left(\prod_{K\in S}K\right)|x\rangle=|y\rangle$ up to a global phase.

Finally, what is the amplitude we're after? $$\langle x|\psi\rangle=\langle x|\left(\prod_{K\in S}K\right)|\psi\rangle=\langle y|\psi\rangle$$ up to a global phase.

Presumably this could put you on a route towards a better-than-brute-force algorithm for determining the stabilizers (I haven't done this myself, hence some vagueness in the statement). If you have a binary string of each of the non-zero basis elements, and the corresponding phase, you know a lot about the group generated by $\Lambda$. A bit of linear algebra should allow you to extract the generators. I would guess that there's even an argument a bit like the one in Simon's algorithm that says you don't need more than $O(n)$ of those basis elements in order to extract the group generators. I'm not sure if this will give you all the information, or just the information about bit-flips. You may also need a Hadamard-rotated version of the state in order to determine the phase flips in the stabilizers.

• Another constraint is that all stabilizer measurements are either deterministic or 50/50 random, even after conditioning on other measurements. For example, this means that $1/2 (|000\rangle +|010\rangle+|100\rangle+|111\rangle)$ is not a reachable state despite it having equal non-zero amplitudes, because the third qubit has a 25% chance of being ON if measured. – Craig Gidney Jul 25 '18 at 19:21
• @CraigGidney Testing all possible stabilizer measurements is probably no more efficient than just testing if your state is an eigenstate for all possible stabilizers, and see if you find the right number. That's doesn't seem efficient. – Norbert Schuch Jul 25 '18 at 21:40
• @NorbertSchuch Correct, but it was only intended to be an observation that could possibly lead to a simple test. Not an entirely self-contained answer. – Craig Gidney Jul 26 '18 at 0:20