7
$\begingroup$

An N-qubit stabilizer state is a state that can be produced by starting from the $|0\rangle^{\otimes N}$ state and applying only H, CNOT, and S gates. How many N-qubit stabilizer states are there?

Because every stabilizer state can be represented as a graph states, which has an edge (or not) between each pair out of N nodes and also one of 24 possible Clifford operations on each node, there are at most $2^{(N^2)} 24^N$ stabilizer states over $N$ qubits. But a stabilizer state can have multiple graph state representations. What's a corresponding lower bound on the stabilizer state count, and what's the exact count?

$\endgroup$

3 Answers 3

14
$\begingroup$

There are $S(n) = 2^n \prod_{i=1}^n (2^i + 1)$ $n$-qubit stabilizer states, as per Corollary 21 of D. Gross, Hudson's Theorem for finite-dimensional quantum systems, J. Math. Phys. 47, 122107 (2006).

Here's a simple approximation of $S(n)$:

$$S(n) \approx \sqrt{2}^{(n+1)(n+2)}$$

This approximation is within a factor of 2 of the real anwer for all $n$. It starts too high but by $n=3$ it's a bit too low and as $n$ goes to infinity it limits to being about 20% too low. Multiplying it by 1.192115 gets a much better estimate for large $n$.

$\endgroup$
1
$\begingroup$

For arbitrary $d$ (modular qudits), the number of stabilizer states is seen to scale similarly. Corollary 1 says that for $c=2.17$

\begin{equation} \label{eq:nkd_count_order_states_intro} d^{\frac{n(n+3)}{2}} \ \le S(n,d) \ < \ \ d^{\frac{n(n+3)}{2}+c}. \end{equation}

$\endgroup$
1
$\begingroup$

In the paper for Aaronson-Gottesman algorithm, the expression for the number of stabiliser states is given with an accessible proof.

$$ 2^n \prod_{k=0}^{n-1} (2^{n-k}+1)$$

Thanks to Oscar Higgott for bringing my attention to it.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.