10

Are there examples of quantum algorithms only composed of Clifford operations that show [...] A reduction in the "same spirit" of the $n^{800}→n$ for instance. No. An $n$ qubit Clifford+measure circuit with $m$ operations can be simulated in $O(n^2m)$ time (arXiv:quant-ph/0406196) with small constant factors (arXiv:2103.02202).


9

Let $\mathcal{G}_n$ denote the Pauli group on $n$ qubits. An $n$-qubit state $|\psi\rangle$ is called a stabilizer state if there exists a subgroup $S \subset \mathcal{G}_n$ such that $|S|=2^n$ and $A|\psi\rangle = |\psi\rangle$ for every $A\in S$. For example, $(|00\rangle+|11\rangle)/\sqrt2$ is a stabilizer state, because it is a $+1$ eigenstate of the ...


7

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 are some simple-to-state bounds on $S(n)$: $2^{(n^2 + 3n)/2} \leq S(n) \leq 3 \cdot 2^{(n^2 + 3n)/2}$


6

Quantum advantage using Clifford gates Gottesman-Knill theorem applies to stabilizer circuits only, not to all circuits consisting of Clifford gates. The former satisfy the stronger requirements of having a stabilizer input state and using only stabilizer basis measurements. Note that availability of magic states enables one to apply non-Clifford gates using ...


6

To obtain the stabilisers of a graph state, from its adjacency matrix: Change all 1s to Zs Change all 0s to identity operators Put X operators on the diagonal Each row then represents a stabiliser of the graph state, and any nontrivial stabiliser is a product of one or more rows.


6

It is not necessary to define the group as commuting —$\def\ket#1{\lvert#1\rangle}$ by virtue of every element in the group stabilising the state $\ket{\psi}$, this property follows. Because we are considering subgroups of the $N$-qubit Pauli group, any two elements either commute or anti-commute. Let $P \in \mathcal P_N$ be an operator which ...


4

The state $\psi$ (this is denoting the density matrix, even though it's a pure state) can be described as a sum of all the products of the stabilizers. We are promised that $X_i$ is not in the stabilizer, so every term in the sum of $\psi$, when multiplied by $X_i$, returns a tensor product of terms that is not just identity. Hence, it has zero trace. Thus, $...


4

First of all, keep in mind that there is no efficient way of generating them, simply because the number of stabiliser states increases super-exponentially with the number of qudits $n$ (like $p^{O(n^2)}$). Second, I can only give you hints how to do it here, since a detailed treatise would take too long. Sorry. As far as I know, there is also no literature ...


4

I think stim is the right tool for the job here, because it gives you access to the stabilizer generators and also it defines stim.PauliString which you can use to represent the stabilizers and more easily implement the manipulations being described in the paper. Ultimately, it will be up to you to translate what the paper wants into a specific combination ...


4

No, it's not possible. For example, being able to directly measure $X+Y$ would allow you to prepare T states and thereby perform T gates, which are not stabilizer operations. If the fact that $X$ and $Y$ don't commute bothers you, then note that preparing $|+\rangle^{\otimes n}$ and then measuring $\sum_{k=0}^{n-1} Z_k$ and getting a result of $n-2$ would ...


4

TL/DR The dimension of the stabilizer $\mathcal{S}$ is $2^{n}$ because there are exactly $n$ generators to make the dimension of the stabilizer's eigenspace exactly $1$. Then, each element in $\mathcal{S}$ is a unique combination of the generators for a total of $2^{n}$ combinations. Long version It's easy to show that the stabilizer $\mathcal{S}$ forms a ...


3

You can pretty easily prove by counting that specifying a stabilizer operation or a stabilizer state requires $\Omega(n^2)$ bits. If you're not tracking some of those bits, your simulator is definitely wrong. So clearly tracking one generator or ten generators ($\Theta(n)$ bits) is not enough. The tricky trouble then is that for certain gates we don't know ...


3

You need to watch out when you say 'stabilizer' or 'stabilizers' because there is a little bit of ambiguity in that terminology$^{1}$. The stabilizer $\mathcal{S}$ of a state $|\psi \rangle$ is the group of $n$-qubit Paulis of which $|\psi \rangle$ is a $+1$ eigenstate. That is, $|\psi \rangle$ is the shared $+1$ eigenspace of all these operators. We can ...


3

The way that I'd do it is to write out the stabilizers in a $10\times 8$ matrix in this case (number of rows= number of stabilizers, number of columns is double the number of qubits). For each row, take a stabilizer and write out, for the first 4 columns, if there's an $X$ on a given qubit, and in the last 4 columns, if there's a $Z$ on a given qubit (...


3

To cite from my answer from over at physics.SE: The W state is not a stabilizer state - for a stabilizer state, the 1-site reduced density matrices must be maximally mixed or pure, which they aren't. Or, to phrase it without reduced density matrices: For a stabilizer state, if you measure $X$, $Y$, or $Z$ for any single qubit, the probability of getting ...


3

If you start with one graph state, which is an eigenstate of stabilizer (each of which comprises an X tensored with a bunch of Zs), then the other eigenstates of those stabilizers are the original state acted on by Z rotations (take all possible combinations). To see this note the commutation and anticommutation relations between a tensor product of Zs and ...


3

As of v1.6: You can use stim.TableauSimulator.peek_observable_expectation to get this value. Before v1.6 Because Stim's C++ API is explicitly not guaranteed to be stable over time, I'm going to initially give my answer in terms of its Python API. There are a few methods you can use to determine the expected value of an observable. Probably the easiest is to ...


3

Every $n$-qubit pure quantum state has at most $2^n$ stabilizers. There are at least two approaches to proving this bound. One makes explicit use of the language of symplectic bilinear forms and the other eschews it while using essentially the same ideas. Below, I write out the former including a short summary of the relevant definitions and the key lemma ...


3

It's possible to perform a CCCZ by consuming a $|W_{8}\rangle$ state. The key idea is to use the state $\text{AND}_{1,2} \cdot \text{AND}_{1,3} \cdot \text{AND}_{2,3} \cdot \text{AND}_{1,2,3} \cdot |+\rangle^{\otimes 3}$ (where $\text{AND}$ allocates a $|0\rangle$ qubit and then targets it with a NOT gate controlled by the indicated qubits). This state has ...


2

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 ...


2

The post-selection idea can be made to work without involving an entangled state. All that matters is that the initial state, before post-selection, has some overlap with the correct final state. I'm unsure how to find or prove that a specific easy-to-prepare state has overlap with every possible stabilizer state. It seems like just ensuring each qubit is ...


2

I'm not sure I understand the question, since this seems quite straightforward. Graph states are Clifford states, so for a state on $n$ qubits, the set of stabilizers has $n$ generators looking like $$i^k P_1\otimes\ldots\otimes P_n$$ where $k\in\{0,1,2,3\}$ and the $P$'s are Pauli $X,Y,$ or $Z$ operators. (For graph states, these stabilizers look like $\...


2

Here are a couple of observations which will hopefully clarify things. Only some states have Pauli stabilisers. You have correctly identified that not all states have Pauli stabilisers. An example of a state that does not have any Pauli stabilisers (apart from the identity operator of course, which we typically ignore) is $\lvert A \rangle = \tfrac{1}{\...


2

Let's make a few observations first: Since an $N$-qubit stabilizer state can be generated starting from $| 0 \rangle^{\otimes N}$ and applying H, CNOT, and S gates, we make the following observations. By simply applying the Hadamard on all qubits, one can generate the state $ | + \rangle^{\otimes N}$ which is maximally coherent (under the free operations ...


2

As stated in the Schuch's answer: the W state is not a stabilizer state. We can also find some operators which can "stabilizer" $W_{3}$. You can refer to Entanglement detection in the stabilizer formalism Page 9 Eq. 59 for $W_{3}$, and Efficient estimation of multipartite quantum coherence Eq.A.8 - A.11 in Appendix A for $W_{3}$ and $W_{4}$. You ...


2

As you say, non-degenerate codes have a lot of well-understood machinery that's brought in from the classical side. That helps us from a conceptual stance, and a mathematical one (making rigorous results easier to prove), although, in terms of practical implementation, doesn't necessarily mean that one is easier to implement than the other. Errors in a ...


2

With the help of Craig Gidney and some others, I was able to pin down the procedure to calculate the entropy. Here are the steps. Create your circuit with a stabilizer simulator This can be done with whatever simulator you want. As Craig mentioned in his answer, Stim is a great tool for the job. The rest of the answer in this section will assume you're using ...


2

A partial explanation is motivated by the proof in Theorem 1 (bottom of page 2). Assuming two locally non-commuting stabilizing operators, using the Cauchy-Schwarz inequality, for pure product states it is shown that $$\langle S_{l}^{(GHZ_N)} + S_{m}^{(GHZ_N)} \rangle \leq 1.$$ But since we also assume these are stabilizer operators (GHZ eigenstate with ...


2

You can use stim for this, although you do have to write the stabilizer projection procedure for yourself. Write some methods to project a system into the +1 eigenstate of several stabilizers: from typing import List import stim def find_compatible_tableau(stabilizers: List[stim.PauliString]) -> stim.Tableau: num_qubits = max(len(e) for e in ...


2

In a recent work Lovitz and Steffan (theorem 3.5) showed that for any non-stabilizer $n$-qubit state, there is a constant $\delta>0$, such that for every $n\geq 2$, $$\chi_\delta(\psi^{\otimes n})\geq \frac{\sqrt{n}}{2\log_2 n}.$$


Only top voted, non community-wiki answers of a minimum length are eligible