But How Quantum Is the Computation?

What this blog is about?

I can safely assume that anyone reading this blog has at least heard the phrase quantum computation in one form or another. If not, this is a perfectly good time to visit this nice 3Blue1Brown video and get a flavour of what the subject is about.

You have also probably heard the usual headline: quantum computers can make some computations dramatically faster than the classical algorithms we currently know. Factoring large integers is the famous example, and there are already many excellent explainers online about why quantum speedups can occur.

But most of us do not have a quantum computer sitting at home. I am technically cheating here, because there is one in the lab next door, but that is not a particularly scalable solution for everyone reading this blog. You can of course access quantum hardware through cloud services such as IBM Quantum, but our question here is deliberately different.

Suppose you want to run a quantum computation and all you have is your laptop.

Are there quantum computations that look genuinely quantum, but that we can nevertheless simulate efficiently on an ordinary classical computer?

That is the question I want to answer.

I will later give a formal description of what “to simulate classically efficiently” might mean, but for now this is how you can think of it: no matter how big the computation might be, we can run it on a laptop without waiting for the universe to end.

Now, the question of how a quantum computation can be classically simulated is rather multi-faceted and is a frontier question of research. And depending on the intended application, say machine learning with quantum computers (which is of my interest), there are different sets of techniques that one might use. However, for this blog I will talk about the one that is perhaps most easily explained, as well as the one I find most elegant.

By the end of this blog I will have explained a well-known result known as the Gottesman-Knill theorem. Broadly speaking, it says that a certain class of “apparently” quantum computations can be efficiently simulated on a classical computer. This theorem has huge implications in the field and has been used in several forms to derive more advanced results ever since it first appeared in 1998. And it is certainly one of my favourite results in the entire quantum computing literature.

Even though there are enough textbooks and lecture notes available online that cover this theorem and associated topics, I have not come across many that have the 3B1B approach to explaining why any of this is even important. And this is why I prepared this blog. The idea of writing this blog is somewhat inspired by the seminar I gave to educate other (non-quantum) computer scientists in our department about certain fun results in the field, and I have carried over the same vibe in this blog.

As for audience expectations, I will assume that you were seriously attentive in your linear algebra classes (if not, like me, 3B1B has a nice series which is all you will need) and know how to count the number of entries in a matrix. Though I do not think anything more will be needed to grasp the key ideas I will be talking about, feel free to ask ChatGPT if certain ideas are too tedious. I have also included a small exercise within the text for you to “pause and ponder” (honestly, I was simply lazy). Given that this is a blog and not a research paper, I will resort to simplifications that would otherwise get me fired from the job of being a PhD student — were I speaking to my professors — but at the same time they allow a smooth story, and so I will take the risk.

(AI usage note: The idea of the blog and the text, along with all its em-dashes, were human generated. I used AI for coding the interactive components.)

Map of contents

I will start by going over the basic operations that constitute a quantum computation, while also explaining the costs associated with storing and processing those operations classically. By the end, you will see why a naive approach to classical processing of quantum computations is inefficient.

Then I will talk about Pauli strings, which could be thought of as a special data structure, and show how they allow a more efficient representation of the quantum operations suitable for classical computers.

Then I will show how, when you restrict the class of quantum operations, this efficient classical representation made possible by Pauli strings leads to an algorithm that allows you to classically simulate a quantum computation. This is the main result of the Gottesman-Knill theorem.

Quantum computation and classical problems

Broadly speaking, quantum computation consists of having a quantum state, a method for evolving that quantum state with time, and a means of reading out information about the quantum state.

The first thing to learn about is the “state”.

In computer science the word state refers to whatever you are supposed to track. For example, in classical computation the state of the system is simply a bitstring, i.e. a string of $\mathsf{1}$‘s and $\mathsf{0}$‘s. And no matter how fancy your interface looks, at its core it is simply a lot of transistors that are either ‘on’ or ‘off’ in the processor.

So if your computer has $n$ bits available, then the number of different states your computer could be in is simply $2^n$, since for each bit you have two choices. For two bits, for example, the possibilities are $00,01,10,11$.

The corresponding analogue in quantum computation is a “statevector”, which is, in some sense, a different creature.

For a quantum computer with $n$ qubits — which is the quantum analogue of a bit — the statevector is a vector of size $2^n$, where each entry is a complex number and each individual entry is related to the probability of the computer being in that state.

For example, for a $2$-qubit system the state could be expressed as

$\ket{\psi} = c_1 \ket{00} + c_2 \ket{01} + c_3 \ket{10} + c_4 \ket{11}.$

Here the states $\ket{00}, \ket{01}, \ket{10}, \ket{11}$ are the basis vectors, expressible as

$\ket{00} = \begin{bmatrix}1\\0\\0\\0\end{bmatrix}, \ket{01} = \begin{bmatrix}0\\1\\0\\0\end{bmatrix}, \ket{10} = \begin{bmatrix}0\\0\\1\\0\end{bmatrix}, \ket{11} = \begin{bmatrix}0\\0\\0\\1\end{bmatrix},$

and so on.

So indeed you could pack up the statevector in a vector of the form

$\ket{\psi} = \begin{bmatrix}c_1\\c_2\\c_3\\c_4\end{bmatrix},$

and it would mean the same thing.

But what is this expression even telling you?

The above expression tells you that $\ket{\psi}$ has probability $|c_1|^2 = c_1^{*}c_{1}$ (which is always a real number) of being in the state $\ket{00}$, and it has probability $|c_2|^2$ of being in the state $\ket{01}$, and so on. In the literature, $c_1$ is referred to as the amplitude of the state $\ket{00}$ in $\ket{\psi}$. Note that for the probability interpretation to hold, we need the additional condition that all the probabilities must sum to unity. So here

$|c_1|^2 + |c_2|^2 + |c_3|^2 + |c_4|^2 = 1.$

Observe that if only one of the amplitudes is non-zero, say $c_1$ is the only non-zero term, then the state $\ket{\psi}$, although still a quantum state, feels more classical — since the state of the computer is just $\ket{00}$ and not a superposition. This notion of what kind of state feels more quantum than the other is something worth pondering, and I will let you do some thinking of your own until we come back to it later in the blog.

Now if you recall your linear algebra, the choice of basis is not unique. In the above I chose the computational basis, i.e. all the possible basis states resemble possible bitstring values.

However, depending on the problem, you can often choose a different basis. For example, the Hadamard basis has the following basis vectors:

$\{ \ket{++}, \ket{+-}, \ket{-+}, \ket{--} \}.$

The ‘plus’ and ‘minus’ states on a single qubit can be expressed as

$\ket{+} = \frac{\ket{0} + \ket{1}}{\sqrt{2}} \quad \text{and} \quad \ket{-} = \frac{\ket{0} - \ket{1}}{\sqrt{2}}.$

This allows you to derive the two-qubit basis states as tensor products of the two single-qubit states, e.g.

$\ket{++} = \frac{\ket{0} + \ket{1}}{\sqrt{2}} \otimes \frac{\ket{0} + \ket{1}}{\sqrt{2}} = \frac{\ket{00} + \ket{01} + \ket{10} + \ket{11}}{2}.$

If you find the name ‘tensor’ scary, do not worry — all it does is give you a way to say that the first qubit is in some state and the second qubit is in another state. This joint description of the states on two qubits is done by taking a tensor product of the states on the individual qubits. By the way, can you think of a two-qubit state that cannot be represented as a tensor product of two single-qubit states?

I leave it as an exercise to find the vector representation of all the basis vectors in the Hadamard basis. As a hint,

$\ket{++} = \frac{1}{2} \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \end{bmatrix}.$

So in general, for a system of $n$ qubits, you will have $2^n$ basis vectors (of course you can choose the basis as you would like), and the state will thus be described by those basis vectors along with the $2^n$ complex coefficients for each of them. In practice, the computational basis is the one that is most used, but you are free to pick any basis in general. The space of all the states is called the Hilbert space.

What makes a quantum state really distinct from a classical state is the fact that you do not have direct access to the state. What I mean is that if I tell you that the state $\ket{\psi}$ is loaded into the quantum computer, you do not have a way to directly read out its complete statevector. Instead, a measurement in a chosen basis produces one of the corresponding basis outcomes probabilistically.

The best you can do is ask whether the state $\ket{\psi}$ is in a particular basis state. For the two-qubit example, we can ask whether the state $\ket{\psi}$ is in $\ket{00}$. The quantum process by which we do this is called measurement.

In the above case, the measurement operation answers ‘yes’ — the state is in $\ket{00}$ with probability $|\langle \psi | 00 \rangle|^2$ — and ‘no’ — the state is not in $\ket{00}$ with probability $|\langle \psi | 10 \rangle|^2 + |\langle \psi | 01 \rangle|^2 + |\langle \psi | 11 \rangle|^2$.

Here $|\langle \psi | 00 \rangle|$ is simply the scalar obtained by taking the dot product (with conjugation of the coefficients) of the vector $\ket{\psi}$ with the vector $\ket{00}$.

Moreover, once the measurement answers yes, the state of the computer changes to $\ket{00}$. So making the measurement actually changes the state of the system, and you will have no way to retrieve the original state $\ket{\psi}$. This is the main difficulty with quantum states: wanting to know what state they are in ruins the state itself. It also means that if you had planned further operations on $\ket{\psi}$, you will not be able to do them anymore since you no longer have access to the original state.

But what happens when we get the answer ‘no’? How does the state look after the measurement? This is a bit complicated to answer at the moment, but feel free to pause and ponder. An intuitive hint: it must lie entirely in the subspace spanned by $\ket{01},\ket{10},\ket{11}$.

You could also ask whether the state $\ket{\psi}$ was in the state $\ket{++}$, and the answers would follow similarly.

Also, you could ask a question about a single qubit: is the first qubit in $\ket{\psi}$ in the state $\ket{0}$? Observe that this amounts to asking two questions simultaneously: is $\ket{\psi}$ in either of $\ket{00}$ or $\ket{01}$? Using the intuition given already, try to see if you can compute the probability of this.

Here it is worth pausing and highlighting some key facts, which is what most people get wrong at times. You might ask: But why can we not reconstruct the state $\ket{\psi}$ after the measurement? After all, we can always keep a record of the coefficients $c_1, \dots, c_4$.

And indeed you are right. If we keep track of the statevector with all the amplitudes classically — say you write it down in your notebook or on your computer — much like we did above, then the intricacies of the quantum world indeed cannot prevent you from going back to $\ket{\psi}$, because it is simply written on your notebook.

This is the subtle point where the difference between “running a quantum computer” and “classically simulating a quantum computer” comes into play. For a quantum state loaded in an actual quantum computer, you will never have a way to know the amplitude-wise description of the state, because quantum mechanics prevents you from doing so. So the only workaround is to keep track of the statevector classically by noting down all the amplitudes and then simulating what happens when a measurement is to be made.

But then, “Why not keep track of the amplitudes?” Well, there are many reasons, but most importantly observe that the number of amplitudes you will need to keep track of grows exponentially with the number of qubits. So even if you had wanted to, classically simulating the computation would have been practically impossible. And thus there would be no way other than actually doing it on a quantum computer, in which case you are left at the mercy of weird quantum phenomena.

This is also the main problem this blog is supposed to address, and I believe that what I have explained so far gives you enough reason to want to have a classical means of simulating quantum computations even for computations that involve a large number of qubits.

So we have covered states and measurement, two operations that are often conflated in the classical realm — having a bitstring on the computer and reading out that bitstring from the computer are the same thing — and yet they are so different in the quantum realm.

The question now is how to do computation with the state. In classical computers this is done by logic gates — you pass the bitstring through a sequence of gates and get an updated bitstring on the other side. In quantum computation the corresponding analogue is a unitary operation.

From linear algebra you know that a unitary matrix $U$ is one that satisfies $U^{\dagger}U = \mathbb{I}$. So, in general, the unitary is specified by a matrix of size $2^n \times 2^n$ for an $n$-qubit system.

For example, one of the simplest single-qubit gates is the Hadamard gate,

It maps the computational-basis states according to $H\ket0=\ket+$ and $H\ket1=\ket-$.

On an $n$-qubit system, a gate may act only on one or two qubits at a time. A complete quantum computation is therefore usually not specified by writing down one enormous $2^n\times2^n$ matrix. Instead, much like in a classical circuit, we specify a sequence of smaller gates whose combined action gives the overall unitary $U$.

This is already good news from the point of view of merely describing the computation. A circuit containing a reasonable number of one- and two-qubit gates can be written down compactly, even though the full matrix $U$ represented by that circuit would contain exponentially many entries.

But unfortunately this does not yet make the computation easy to simulate.

Suppose we are storing the state directly as its statevector. Even if the next gate acts on only one or two qubits, the state we are updating still contains $2^n$ amplitudes. A classical statevector simulator can exploit the fact that the gate is local—it certainly does not need to construct a fresh $2^n\times2^n$ matrix for every gate—but it still has to update an object whose size grows exponentially with $n$.

So we have arrived at an important distinction: A quantum computation may have a compact classical description even when simulating its evolving quantum state is exponentially expensive.

Let us summarize where the difficulty comes from.

A generic $n$-qubit state requires $2^n$ complex amplitudes if we store it directly. Even when the unitary is given compactly as a sequence of local gates, those gates act on that exponentially large statevector. To reproduce a measurement classically, we must eventually compute the relevant outcome probabilities and, if we want to continue the computation, the corresponding post-measurement state.

So the problem is not that classical computers are incapable of storing complex numbers or multiplying matrices. They are perfectly happy doing both. The problem is that the objects we have chosen to keep track of become exponentially large.

And this suggests that perhaps we have been asking the wrong question. Instead of asking : “How can we make our laptop manipulate a $2^n$-dimensional statevector faster ?”, perhaps we should ask “Do we really need to store the statevector at all ?”

So the main motivation of the blog is now as follows: can we come up with a more clever way to represent the various operations in a quantum computation, and perhaps an even more clever way that will allow us to execute the computation on a laptop without waiting until the end of the universe?

Here, execution of a quantum computation can be thought of as follows: we are given an initial state $\ket{\psi}$, a unitary $U$, and some descriptions of the measurements that you might wish to make. So running a quantum computation would involve evolving the state $\ket{\psi}$ using the unitary $U$, i.e. $U\ket{\psi}$, and then trying to get the probability distribution over the measurement outcomes.

What we mean by classically efficient simulation would be to be able to do: storing the state $\ket{\psi}$, obtaining the state $U\ket{\psi}$, and then being able to get the probability distribution over the measurement outcomes, all of it using resources, i.e. space to store and time to process the computation, that do not scale exponentially with the number of qubits $n$.

A word of caution here: the word “classically simulate” really has too many different meanings in the literature --- which is usual when you leave scientists with their thoughts and enough cookies --- but for the scope of this blog the above is the only description I would use. If you need keywords to search, try looking for “strong simulation”, “weak simulation”, etc.

In what follows I will start by explaining a cool way that would allow you to represent a quantum computation in a more efficient fashion. Following that, I will show that this representation leads to a classical simulation for a certain restricted class of quantum computations.

To give you a teaser, by the end you will be able to simulate a quantum computation on $n$ qubits by tracking bitstrings of size $2n$ instead of $2^n$-sized vectors --- and if that does not impress you, I’m afraid nothing else will :)

Pauli Strings: or the bit-strings of quantum computers

Pauli strings are undoubtedly the single most important concept in this blog, and they will serve as the bricks for building a bridge across the gap of classical inefficiency that we so aim to cover.

Now a Pauli string is a string of Pauli operators; each Pauli operator is a $2 \times 2$ matrix that acts on a single qubit. The string corresponds to the tensor product of Pauli operators acting on each qubit. That’s what happens when physicists adopt a computer scientist’s vocabulary.

Now the Pauli operators can be of four types:

All of them are unitary operators and can be interpreted as gates. Let us take a look at how they act on the state.

The $I$ is the identity and does nothing.

The $X$ operator can be understood as a “bit-flip” operator: $X\ket0=\ket1$ and $X\ket1=\ket0$.

The $Z$ operator is a phase flip: $Z\ket0=\ket0$ and $Z\ket1=-\ket1$, since it adds a $-1$ phase.

The $Y$ operation is basically: $Y = iXZ$, so it does both an $X$ and a $Z$ operation.

Above I showed their action on the computational basis. I leave it as an exercise to derive their action on the Hadamard basis.

Observe that all the operators $P \in \{X,Y,Z,I\}$ have the property that they square to the identity ($P^2 = I$): if you apply them twice you get back the same state.

A Pauli string is simply a tensor product of these single-qubit operators, one letter per qubit. For example, on four qubits, a Pauli string might have the shape $P=X_1I_2Z_3Y_4 = X_1 \otimes I_2 \otimes Z_3 \otimes Y_4$, where the subscripts indicate the qubit the operator is acting on. Since a Pauli operator is a $2 \times 2$ matrix, a Pauli string on $n$ qubits is a matrix of size $2^{n} \times 2^{n}$.

An important property is that of commutation. If you know something about matrices then you know that any two matrices $A$ and $B$ applying $A$ and then $B$ is not same as applying $B$ and then $A$.

Now when it comes to Pauli-strings the possibilities are rather limited i.e they either commute or anticommute : If they commutes then $AB = BA$, while if they anticommute then $AB = -BA$.

For our conventions we will use the notation $A \odot B$, which we will call the ‘commutation signature’, to capture this binary relation, specifically: $A \odot B = \begin{cases}0 & AB = BA \\ 1 & AB = -BA\end{cases}$

What is interesting is that whether two Pauli strings commute or anticommute can be expressed as a linear sum of the commutation signatures of the Pauli operators acting on individual qubits.

For instance, say we have two Pauli strings on a $2$-qubit system $P=X_1Z_2$ and $Q=Z_1X_2$. At qubit 1, $X$ and $Z$ anticommute; at qubit 2, $Z$ and $X$ anticommute. There are two local conflicts. Two is even, so the two minus signs cancel and the full Pauli strings commute.

In terms of the notation $P \odot Q = (X_1 \odot Z_1) \oplus (Z_2 \odot X_2)$, where $\oplus$ indicates addition modulo two or the XOR operation.

More generally, for Pauli strings $Q$ and $P$, we can have the formula

which summarizes the idea that the commutation signature of two Pauli strings is the sum (modulo two) of the local commutation signatures on each individual qubit.

Okay, lots of fun computing commutations. But in the end they are still matrices of size $2^n \times 2^n$, which is still very big for a classical computer. How does it even help us?

You are right, and here is the smart fact that changes the story.

Observe that any Pauli operator can be expressed as $P(p,x,z) = (-i)^p X^x Z^z$

where $p \in \{0,1,2,3\}$ and $x,z \in \{0,1\}$ is a binary string of length 2.

For most of the questions regarded in this blog — especially commutation — the overall phase will not matter. Ignoring that phase, we can therefore identify a Pauli operator with the binary pair $[x\mid z]$. See if you can build all four Pauli operators by picking suitable $x$ and $z$ pairs.

For $n$ qubits we collect the local bits into two length-$n$ binary vectors, $\mathbf x=(x_1,\ldots,x_n)$ and $\mathbf z=(z_1,\ldots,z_n)$, and represent the Pauli string by $[\mathbf x\mid\mathbf z]\in\mathbb F_2^{2n}$. This is the binary, or symplectic, representation of Pauli strings. If the $\mathbb F_2^{2n}$ scares you, all it is saying is that the allowed elements are either $0$ or $1$ and their addition must be done modulo two.

A useful precision point: this binary vector represents the Pauli group modulo overall phases. It is not a faithful representation of the full Pauli group unless the phase information is stored separately, but we can care less about the complex scalar for now.

Now the commutation relation becomes a simple binary calculation.

For $P=[\mathbf{x}(P)\mid\mathbf{z}(P)]$ and $Q=[\mathbf{x}(Q)\mid\mathbf{z}(Q)]$,

Here $\mathbf{x}(P) \cdot \mathbf{z}(Q)$ is the $\mathbb F_2$ dot product, which is the same as a regular dot product except that the sum is taken modulo $2$. This quantity is called the symplectic product.

For example, if we look at the two Pauli strings $P=X_1X_2$ and $Q=Y_1X_2$, their symplectic representations are

In other words, $\mathbf{x}(P)=(1,1)$, $\mathbf{z}(P)=(0,0)$, $\mathbf{x}(Q)=(1,1)$, and $\mathbf{z}(Q)=(1,0)$. Their symplectic product is therefore

The symplectic product is $1$, so $X_1X_2$ and $Y_1X_2$ anticommute. This also matches the local picture: $X_1$ and $Y_1$ anticommute on the first qubit, while the two $X_2$ factors commute on the second.

So we have shown that a question about two exponentially large matrices has become a dot-product calculation on bitstrings of length $2n$. This exponential reduction in the computation is at the core of the classical efficiency of quantum computation that we are trying to achieve.

Pauli strings: or answering classical questions about quantum states.

About states

We will now see how we can use Pauli strings to characterize states and measurements.

Let us start again with the single-qubit Pauli operator $Z$.

We know that the computational basis for a single qubit is ${\ket{0},\ket{1}}$. Now observe that $Z\ket{0}=\ket{0}$, while $Z\ket{1}=-\ket{1}$.

So relative to this basis, $Z$ has very neatly split our two possible basis states into two parts: $\ket{0}$ gets a $+1$ sign, while $\ket{1}$ gets a $-1$ sign.

Let us now try the same thing with $X$. This time the computational basis is not particularly useful. Instead recall the states $\ket{+}=(\ket{0}+\ket{1})/\sqrt2$ and $\ket{-}=(\ket{0}-\ket{1})/\sqrt2$. These satisfy $X\ket{+}=\ket{+}$ and $X\ket{-}=-\ket{-}$.

So the exact same thing has happened again, except that this time the basis being split into the $+$ and $-$ sides is $\{\ket{+},\ket{-}\}$ instead of $\{\ket{0},\ket{1}\}$.

So what we have seen is that, given a single-qubit Pauli operator, we can find a choice of orthonormal basis such that one basis state gets mapped to itself and the other gets mapped to negative times itself.

That was easy enough for one qubit. Let us see what happens when there are two.

Consider the Pauli string $Z_1Z_2$.

The computational basis now consists of the four states $\ket{00},\ket{01},\ket{10},\ket{11}$. Acting with $Z_1Z_2$ gives $Z_1Z_2\ket{00}=+\ket{00}$ and $Z_1Z_2\ket{11}=+\ket{11}$, while, $Z_1Z_2\ket{01}=-\ket{01}$ and $Z_1Z_2\ket{10}=-\ket{10}$.

So again the Pauli string has split our basis into two groups. On the positive side we have $\ket{00}$ and $\ket{11}$, while on the negative side we have $\ket{01}$ and $\ket{10}$.

But something slightly more interesting follows from this. It is not only the individual states $\ket{00}$ and $\ket{11}$ that get a $+1$ sign. Any linear combination of them does.

For example, for arbitrary $a$ and $b$ any state $\ket{00}+b\ket{11}$ satisfies $Z_1Z_2(a\ket{00}+b\ket{11})=a\ket{00}+b\ket{11}$.

Similarly, any state of the form $a\ket{01}+b\ket{10}$ picks up an overall minus sign when $Z_1 Z_2$ acts on it.

So what is the Pauli strings actually doing ? Avoiding mathematical sophistication the naswer simply is this. Given a Pauli string $P$ we can always find an orthonormal basis of the $2^n$-dimensional Hilbert space such that exactly half of those basis states satisfy $P\ket{\phi}=+\ket{\phi}$ and the other half satisfy $P\ket{\phi}=-\ket{\phi}$.

Thus it follows that any linear combination made entirely from the first half also gets $+1$, while any linear combination made entirely from the second half gets $-1$ when acted on by $P$.

Thus intuitively : a Pauli string splits the Hilbert space in half.

Not in the sense that someone has physically taken a pair of quantum scissors to Hilbert space, but in the sense that it divides all the possible directions in that space into two equally large sets: a $+1$ side and a $-1$ side.

However one must be careful to strech the meaning of this quote. You can always build a state by taking a linear combination of states that from both both sides of the split.

For example, for the single-qubit $Z$ operator, $\ket{+}=(\ket{0}+\ket{1})/\sqrt2$ contains one component from the $+1$ side and one from the $-1$ side. Then $Z\ket{+}=\ket{-}$. So the state is neither mapped to itself nor to minus itself: applying $Z$ actually changes it into a different state.

This gives us a useful way of thinking about any state relative to a Pauli string $P$.

There are three possibilities:

• the state lies entirely on the $+$ side, so $P\ket{\psi}=\ket{\psi}$;
• the state lies entirely on the $-$ side, so $P\ket{\psi}=-\ket{\psi}$;
• or the state has components on both sides, in which case applying $P$ changes the state.

So given a Pauli string, we can essentially ask of a state: Are you on my positive side, on my negative side, or somewhere across both?

And as we will see this already allows a Pauli string to describe an entire set of possible quantum states.

For example, suppose I tell you that some two-qubit state $\ket{\psi}$ satisfies $Z_1Z_2\ket{\psi}=\ket{\psi}$ without giving you the exact description of the state.

Even though I may not have told you the exact state, I have already told you quite a lot: it must be some linear combination of $\ket{00}$ and $\ket{11}$ since otherwise the would have either got a nagative sign or been mapped to something else completely.

Likewise, if I tell you that $Z_1Z_2\ket{\psi}=-\ket{\psi}$, then the state must be some linear combination of $\ket{01}$ and $\ket{10}$.

So one Pauli string and its effect on the state gives us a compact way to specifying the possible beasis vectors a state is composed of without writing down the statevector itself. But what if we have two Pauli strings ?

Now let us bring in another Pauli string: $X_1X_2$. We already know that $X\ket{+}=\ket{+}$ and $X\ket{-}=-\ket{-}$. Therefore, on two qubits, $X_1X_2$ gives a $+1$ sign to $\ket{++}$ and $\ket{--}$, because either both signs are positive or both are negative. On the other hand, $\ket{+-}$ and $\ket{-+}$ get a $-1$ sign.

So just like $Z_1Z_2$, the Pauli string $X_1X_2$ also splits the four-dimensional Hilbert space into two halves — only it does so in a different basis. So if I had a told you that a state satisfies either $X_1X_2 \ket{\psi} = \ket{\psi}$ or $X_1X_2 \ket{\psi} = -\ket{\psi}$, you could have guessed what basis vectors $\ket{\psi}$ is composed of.

But now let us do something more interesting. What if we require that both $Z_1Z_2\ket{\psi}=\ket{\psi}$ and $X_1X_2\ket{\psi}=\ket{\psi}$ are satisfied ?

From the first equation, we know that $\ket{\psi}$ has to be a linear combination of $\ket{00}$ and $\ket{11}$. From the second, we know that it has to be a linear combination of $\ket{++}$ and $\ket{--}$. So what kind of state could possibly satisfy both conditions at once ?

Try the state $\ket{\Phi^+}=(\ket{00}+\ket{11})/\sqrt2$.

Applying $Z_1Z_2$ clearly leaves it unchanged. And applying $X_1X_2$ simply swaps $\ket{00}$ and $\ket{11}$, which again leaves the total state unchanged. So $\ket{\Phi^+}$ satisfies both equations.

Interestingly, if we write exactly the same state in the Hadamard basis, it can also be written as $\ket{\Phi^+}=(\ket{++}+\ket{--})/\sqrt2$. This might initially look slightly suspicious — in one basis the state is built from $\ket{00}$ and $\ket{11}$, while in another it is built from $\ket{++}$ and $\ket{--}$.

But that is exactly the point. The state itself has not changed. Only the basis we used to describe it have.

And here something rather nice has happened. The individual condition $Z_1Z_2\ket{\psi}=\ket{\psi}$ described a whole family of states. The individual condition $X_1X_2\ket{\psi}=\ket{\psi}$ also described a whole family. But requiring both simultaneously leaves us with exactly one unique state.

I will leave it as an exercise to convince yourself that there is no other two-qubit state satisfying both equations.

We could also have changed the signs. For example, we could ask for a state satisfying $Z_1Z_2\ket{\psi}=\ket{\psi}$ and $X_1X_2\ket{\psi}=-\ket{\psi}$. Or perhaps $Z_1Z_2\ket{\psi}=-\ket{\psi}$ and $X_1X_2\ket{\psi}=\ket{\psi}$. I leave it as an exercise for you to find states that would satisfy these constraints.

Now what in the world does any of this have to do with efficiently representing a quantum state?

Well, normally the state $\ket{\Phi^+}$ would be stored as a statevector containing $2^2$ complex entries.

But we just discovered that there is another way to specify it uniquely by using the Pauli string that constraints them. Instead of storing the statevector, we can simply store the two Pauli strings $Z_1Z_2$ and $X_1X_2$, and say describe the state $\ket{\psi}$ as a state that satisfies the two constraints.

And this idea generalizes. Given an $n$-qubit state $\ket{\psi}$, if we manage to find $n$ independent, mutually commuting Pauli strings $P_1,\ldots,P_n$ such that each satisfies $P_i\ket{\psi}=\ket{\psi}$, then those equations uniquely identify the state $\ket{\psi}$.

We call these stabilizing equations, the Pauli strings are called stabilizer generators, and $\ket{\psi}$ is called a stabilizer state. The set of Pauli strings that we can make by taking the products of the stabilizer generators is called the stabilizer group of the state, in practise it is common to just mention the generators and the group can then be assumed to be generated from those generators.

The advantage should now be apparent.

Instead of storing a $2^n$-sized vector of complex numbers, we store only $n$ Pauli strings.And from the previous section we know that each Pauli string itself can be represented by a bit string of size $2n$. So instead of an exponentially large description, we need only order $2n^2$ bits, together with the signs. That is a rather dramatic discount.

I did however lie to you slightly. We cannot just pick any $n$ Pauli strings satisfying these equations. They need to obey two important conditions.

First, they should be independent.

Suppose $P_1\ket{\psi}=\ket{\psi}$ and $P_2\ket{\psi}=\ket{\psi}$. Then automatically their product also satisfies $P_1P_2\ket{\psi}=\ket{\psi}$.

So from only two pieces of information I can manufacture a third equation for free and thus it does not add in adding constraints on the state that was not conveyed by the other two.To avoid counting such fake extra information, none of our chosen generators should be obtainable as a product of the others.

Second — and more importantly — all the stabilizer generators must commute.

There is a very quantum-mechanical reason for this. If two Pauli strings $P_1$ and $P_2$ both satisfy $P_1\ket{\psi}=\ket{\psi}$ and $P_2\ket{\psi}=\ket{\psi}$, then they cannot anticommute.

I leave the prove as an exercise (because I have to justify calling this an interactive blog somehow). Start by assuming $P_1P_2 = -P_2P_1$ and plugging that information in the two stabilizing equations.

Its worth noting that the fact two anticommuting Pauli strings cannot satisfy this relations is cloesly related to the Hisenberg uncertainty princeiple. But that’s a story for another day — or you ask ChatGPT.

About measurements

So we have learnt that a way of using Pauli strings to describe certain quantum states. Can we as well use Pauli strings to describe measurements ?

Previously we talked about a measurement of quantum state as asking the probability of observing it on either of the basis states. For example, we given a state $\ket{\psi} = a \ket{0} + b\ket{1}$ has some probability of being in $\ket{0}$ or $ket{1}$. But how can we use a Pauli string to talk about measurements ?

To see this recall that the $Z$ operators is known to satisfy $Z \ket{0} = \ket{0}$ and $Z \ket{1} = -\ket{1}$. Thus the question of whether $\ket{\psi}$ is on $\ket{0}$ or $\ket{1}$ can be translated to whether the $Z$ maps the state to itself or its negative.

Mathematically, measuring the $Z$ on the state $\ket{\psi}$ can be described as the scalar $\braket{\psi | Z | \psi}$. This is the same as evolving the state $\ket{\psi}$ with $Z$ and then taking the inner product of $Z \ket{\psi}$ with $\ket{\psi}$. If you do the computation, you will get a scalar function of $a$ and $b$. But what does this scalar represent?

If the two outcome probabilities are $p(+1)$ and $p(-1)$, then

Since $p(+1)+p(-1)=1$, this also means

We can think of the Pauli string $Z$ as a random variable, which takes the value $+1$ when $Z \ket{\psi} = \ket{\psi}$ and the value $-1$ when $Z \ket{\psi}= -\ket{\psi}$. Then the scalar $\braket{\psi | Z | \psi}$ can be thought of as the expectation value of the random variable. For an arbitrary state, this expectation is somewhere between $[-1,+1]$.

For instance, if you take $a=1,b=0$, then the expectation will be $+1$, which implies that the $Z$ measurement yields $+1$ always, since the state is in $\ket{0}$. For $a=0,b=1$, we get the expectation to be $-1$ since the state is in $\ket{1}$. But other than these two extremes, the expectation will be a function of the coefficients, since the state has non-zero probability of being in either $\ket{0}$ or $\ket{1}$.

As an exercise, try figuring out what measuring the $X$ operator on the state $\ket{\psi}$ might mean. You would like to start by changing the computational basis to the Hadamard basis: $\ket{+}, \ket{-}$.

But how does this idea generalize when we have more than one qubit?

Let us try the Bell state $\ket{\Phi^{+}} = \frac{\ket{00} + \ket{11}}{\sqrt{2}}$. Can we compute the expectation of the Pauli string $Z_{1}$?

It is apparent that any state $\ket{\psi}$ that is a linear combination of $\ket{00}, \ket{01}$ satisfies $Z_{1} \ket{\psi} = \ket{\psi}$, whereas those that are linear combinations of $\ket{10}, \ket{11}$ satisfy $Z \ket{\psi}= -\ket{\psi}$.

Now $\ket{\Phi^{+}}$ seems to be a state that is a linear combination of basis states from the positive and negative side of the Hilbert space as seen by $Z_{1}$. In this particular case, since the weight on each side is equal, the expectation of $Z_{1}$ is $0$.

Now what about the expectation value of $X_{1}X_{2}$? You might find it easy to answer, since you know that this Pauli string is actually a stabilizer of the state, so the whole state $\ket{\Phi^{+}}$ lies on the positive side of the Hilbert space as seen by $X_{1}X_{2}$ and consequently the expectation value is $1$. You can prove it by computing $\braket{\Phi^{+} |X_{1}X_{2}| \Phi^{+}}$ yourself.

This idea generalizes for any $n$-qubit system, although explicitly computing the expectation might require more effort if you proceed by looking at each of the basis vectors a state is composed of.

From the previous discussion, we learned that corresponding to any Pauli string there is a choice of basis such that half of the states stay the same when acted upon by $P$, and the other half gets a $-1$ sign.

The expectation of the Pauli string on the state $\ket{\psi}$, i.e. $\braket{\psi|P|\psi}$, gives us a measure of the overlap of the state with the basis vectors corresponding to the positive and negative side of the Hilbert space as seen by $P$.

For example, if the state $\ket{\psi}$ satisfies $P \ket{\psi}= \ket{\psi}$, it is easy to see that the expectation of $P$ is $+1$; similarly it is $-1$ when $P \ket{\psi}= -\ket{\psi}$ is satisfied. For all other cases it is somewhere between $\pm1$, depending on the degree of overlap on each side of the Hilbert space.

One case of interest is when the state $\ket{\psi}$ has equal total probability weight in the $+1$ and $-1$ eigenspaces of $P$, in which case the expectation is zero.

If we write $\ket{\psi}=\ket{\psi_+}+\ket{\psi_-}$, where the two components lie in the $\pm1$ eigenspaces of $P$, then

However, there is one question to ask. We already learned that using the stabilizing equations we can represent stabilizer states using just their stabilizer generators without storing all the amplitudes in any chosen basis, but can we then directly use the stabilizing equations to answer the question about the expectation values of a Pauli string without inspecting the state directly? As we will see later, we indeed can.

Pauli strings : or how to rotate the state

So far we have covered the state and the measurements. Now what about the unitary?

A brief note here: this part will require us to take exponentials of matrices. In case you are not familiar with this, 3Blue1Brown has a very nice video explaining what a matrix exponential actually means.

Given a Pauli string $P$, we can construct a unitary operation by exponentiating it as $P(\theta)=e^{-i\theta P/2}$. We will call this a Pauli rotation.

And because every Pauli string satisfies $P^2=I$, the exponential takes a particularly simple form: $P(\theta)=\cos\left( \theta/2 \right)I-i\sin\left( \theta/2 \right)P.$

So although $P(\theta)$ is technically a matrix exponential, which is again a matrix of size $2^n \times 2^n$, we really only need two things to describe it: the Pauli string $P$, which requires $2n$ bits to describe, and the angle $\theta$, which is a float.

Let us first see what one of these rotations actually does.

We know that the $X$ operator acting on $\ket{0}$ flips it to $\ket{1}$. So if we apply the Pauli rotation generated by $X$, we obtain $X(\theta)\ket{0}=\cos(\theta/2)\ket{0}-i\sin(\theta/2)\ket{1}$.

So rather than completely flipping $\ket{0}$ into $\ket{1}$, the Pauli rotation creates a weighted combination of the two, where the weights depend on the angle $\theta$. At $\theta=0$ nothing happens. At other angles we gradually move away from $\ket{0}$. At $\theta=\pi$ we obtain $X(\pi)=-iX$, which is the usual $X$ gate up to an irrelevant global phase.

The same idea works for multi-qubit Pauli strings. For example, start with $\ket{00}$ and apply the rotation generated by $X_1X_2$. Since $X_1X_2\ket{00}=\ket{11}$, we obtain

$X_1X_2(\theta)\ket{00}=\cos\left( \theta/2 \right)\ket{00}-i\sin\left( \theta/2 \right)\ket{11}.$

And of course we can apply one Pauli rotation after the other, as $Z_1(\theta_2) \: X_1X_2(\theta) \: \ket{00}$ to build more complicated unitaries.

The useful fact is that, up to an overall global phase, arbitrary unitaries can be built from sequences of Pauli rotations. I will leave the details of such decompositions out of this blog — partly because that is another interesting story by itself, and partly because at some point this blog has to end.

So instead of thinking of a unitary as on enormous $2^n\times2^n$ matrix, we can think of it as a sequence of Pauli rotations

where every $P_i$ is simply a Pauli string and every $\theta_i$ is a number. From the point of view of classical storage this is already rather convenient since instead of an exponentially sized matrix you are storing $2n$ sized bitstrings and float values.

Now, if I insist on describing a completely arbitrary $n$-qubit unitary this way, I might still require exponentially many Pauli rotations. And exponentially many Pauli strings and floats is as good as exponentially many entires of a matrix, ie its too big to be stored on your computer. But most quantum computations of practical relevance are given by circuits containing only polynomially many Pauli rotations which is rather tractable.

As a side note, this way of thinking about unitaries is particularly common when one is doing quantum machine learning since the angles give something tunable much like the parameters in a nueral-network, but more of it later — I have already made enough promises for one blog.

What Did We Learn so far ?

Let us take stock of where we are. We started with three things that seemed rather unpleasant to describe classically: the state, the unitary, and the measurement.

For certain states called the stabilizer states, we learnt that instead of storing $2^n$ amplitudes, we can store $n$ Pauli strings whose stabilizing equations uniquely identify the state. And similarly we learnt how we can use Pauli strings to describe measurements. And for unitaries, we have now seen that instead of storing an enormous matrix we can describe the evolution as a sequence of Pauli rotations, each specified by a Pauli string and an angle.

So for the class of quantum computations we are interested in, our classical description starts looking much less terrifying. Instead of constantly carrying around exponentially large vectors and matrices, we are carrying around things like : bit strings representing Pauli operators, floating-point numbers representing rotation angles.

So if all you wanted to do was describe the quantum computation — for instance to send the instructions to a quantum computer at your friend’s place — things are looking pretty good : You do not need to upload a $2^n\times2^n$ matrix describing the complete unitary and then grow old watching the progress bar.

But unfortunately this still does not solve the problem I promised to solve at the beginning of the blog. We wanted to actually simulate the quantum computation on our laptop. And compactly describing a computation is not the same thing as efficiently simulating it. That distinction is important.

Recall that to simulate we would need not only a classically efficient way to represent the state $\ket{\psi}$ and the unitary $U$, but as well to compute the updates state $U \ket{\psi}$ efficiently, as well compute the measurement outcome probabilities. And the representation above would be of no use if we need turn them back into exponentially large matrices to do this step.

Even if I store the state using stabilizers and store the unitary as a sequence of Pauli rotations, I still need some way of updating my efficient description of the state after application of unitary.

What we would really like is something stronger: Can we perform the computation directly using the Pauli-strings themselve ? If we can do that efficiently, then we genuinely have a classical simulation. Which is what I will describe in the next section.

Pretending to do quantum computation in your classical computer

Simulating the evolution

Let us start with the part of evolving the state. Suppose $\ket{\psi}$ is a stabilizer state and $S$ is one of its stabilizers, so $S\ket{\psi}=\ket{\psi}$.

Now suppose we apply some unitary $U$ to the state. The new state is $U\ket{\psi}$. What stabilizes this new state ? A bit of calculation shows, that $(USU^\dagger)$ is the answer : $(USU^\dagger)\: U \ket{\psi} = US \ket{\psi} = U \ket{\psi}$

This is potentially good news. Remember, our stabilizer generators already uniquely identify the state. So rather than evolving an exponentially large statevector, perhaps we can simply evolve each of its $n$ stabilizer generators under the unitary and keep track of them ? Since the generators specified the state uniquely before the evolution, the evolved generators must specify the state state uniquely after the evolution.

That would be a great idea, no ? Unfortunately, there’s a problem, even though the stabiblizers specify the state uniquely the stabilizers themselves are not simple Pauli strings anymore.

Let us try with an example. Take again our old friend, the Bell state: $\ket{\Phi^+}=(\ket{00}+\ket{11})/\sqrt2$, which we know is stabilized by $X_1X_2$ and $Z_1Z_2$.

Now apply the Pauli rotation $X_1(\theta)$, and we want to know the stabilizer of the evolved state $X_1(\theta)\ket{\Phi^+}$.

For a general stabilizer $S$, the updated stabilizer under a Pauli rotation $P(\theta)$ is given by: $P(\theta)SP(\theta)^\dagger=(cI-isP)S(cI+isP)=c^2S+i c s\,SP-i c s\,PS+s^2PSP.$

where we used $c=\cos(\theta/2)$ and $s=\sin(\theta/2)$ for convenience. Observe that when the generator $P$ and the stabilizer $S$ commute, i.e. $P \odot S = 0$, the evolved stabilizer is simply $S$.

Now for our case, the stabilizer $X_1X_2$ remains unchanged because it commutes with the rotation generator $X_1$. The stabilizer $Z_1Z_2$ becomes $Z_1Z_2 \mapsto \cos(\theta)Z_1Z_2-\sin(\theta)Y_1Z_2$.

So the state $X_1(\theta) \ket{\Phi^+}$ is stabilzied by the $\{X_1X_2, \cos(\theta)Z_1Z_2-\sin(\theta)Y_1Z_2 \}$. And there is our first problem. Before the rotation, the stabilizer was one Pauli string. After a generic rotation, it has become a weighted sum of two Pauli strings. That is no longer something we can represent using one neat $2n$-bit Pauli string.

This example is actually rather mild: only one of the two generators branched. But the general problem is already visible.

Every time we apply another a Pauli rotation, every stabilizer generator that anticommutes with the generator of that rotation can splits into two Pauli strings, and tracking the stabilizer now require tracking both these Pauli strings.

So schematically the Pauli strings that we need to track might grow like : $1\rightarrow2\rightarrow4\rightarrow8\rightarrow\cdots$

So after applying $T$ such Pauli rotations, in the worst case we could therefore need as many as $2^T$ Pauli terms. If $T$ grows with the system size, this need not be polynomial; for example, if $T \approx n$, the number of terms can grow as $\approx 2^{n}$. We have therefore walked straight back into an exponential overhead.

Very nice. We escaped the enormous statevector only to rebuild something enormous out of Pauli strings instead. Quantum mechanics: very considerate.

So we need one more trick. Can we put some restrictions on the Pauli rotations so that when we evolve a stabilizer, it remains a single Pauli string rather than splitting into a sums of many ?. Turns out we can.

And the answer is hiding inside the angle $\theta$. Recall that when $P$ anticommutes with $S$, the evolved stabilizer is $\cos(\theta) \: S - i\sin(\theta) \: PS$. Usually both coefficients are non-zero, which is what creates the troublesome sum. But consider what happens if we restrict $\theta$ to integer multiples of $\pi/2$ :

For $\theta=0$, we trivially get $S$ back.

For $\theta=\pi/2$, the cosine vanishes and we get simply $-iPS$.

For $\theta=\pi$, the sine vanishes and we get $-S$.

For $\theta=3\pi/2$, the cosine again vanishes and we get $+iPS$.

And because $P$ and $S$ are Pauli strings, $\pm iPS$ is itself another Pauli string.

So in every one of these cases, conjugation by the unitary amounts to turning one Pauli string to another Pauli string.

(Here note that we will need to store the sign as well, but again storing a sign is something you can do classically, without much overhead needed)