Are quantum computers more powerful than classical computers and the stabiliser rank story. (part 1)

Of course, quantum computers are more powerful than classical computers, but how do you prove it! Until recently there was not much known except for some oracle separation results. In 2017, we got the already infamous Bravyi-Gosset-Koenig result that proved quantum computers can solve some problems in constant time that for a classical computer require logarithmic time. But we really want to know that quantum computers offer an exponential speedup such as Shor’s algorithm suggests.

Asking for a proof of an exponential speedup is a lot to ask for! We would need to show that all possible classical algorithms are incapable of efficiently simulating a quantum computer. This is really hard. But if we have a concrete family of classical algorithms, then surely we should try to understand if they could possibly offer an efficient simulation!

This brings us to stabiliser rank and related simulation methods. Let’s define some terms. Given a state \Psi we define the stabiliser rank \chi(\Psi) to be the smallest number of terms needed to write \Psi as a sum of stabiliser states. More formally,

Definition of stabiliser rank:
Suppose \psi is a pure n -qubit state. The exact stabilizer rank \chi(\psi) is the smallest integer k such that \psi can be written as

\vert \psi \rangle = \sum_{\alpha=1}^{k} c_\alpha \vert \phi_\alpha \rangle

for some n -qubit stabilizer states \phi_\alpha and some complex coefficients c_\alpha .

These decompositions were first studied by Garcia- Markov-Cross and applications to simulation were first explored in more depth by Bravyi-Smith-Smolin. The Gottesman-Knill theorem allows us to efficiently simulate a Clifford circuit acting on a stabiliser state. This can be extended to simulation of an arbitrary state \Psi undergoing a Clifford circuit with runtime proportional to \chi(\Psi) (assuming we know the decomposition). We also know that a universal quantum computation can be gadgetized into a Clifford circuit with a supply of single qubit magic states \Psi = \psi^{\otimes t} where t scales polynomially with the number of gates in the original quantum computation.

So if quantum computers are more powerful than classical computers, then we expect \chi( \psi^{\otimes t}) to scale exponentially with t . If \chi( \psi^{\otimes t}) instead scales polynomially with t then BQP=BPP (you can classically efficiently simulate quantum computers). But also the classical simulation method allows for postselection, so it would actually entail postBQP=BPP, which entails NP=P.

Surely, this is a simple statement that the quantum community should be able to prove. Surely, stabiliser rank simulators are not going to show BQP=BPP. Surely, surely we can prove the following conjecture:

The stabiliser rank conjecture:
For every nonstabiliser state \psi , there exists a \alpha >0 such that

e^{\alpha t} \leq \chi( \psi^{\otimes t} )

holds for all integer t .

Clearly, one has that \chi( \psi^{\otimes t}) \leq \chi( \psi)^t , but the problem is that \chi( \psi^{\otimes t}) \ll \chi( \psi)^t and that we have almost no lower bounds on the stabiliser rank. Consider, a 1-qubit non-stabiliser state

\vert \psi \rangle = \alpha \vert 0 \rangle + \beta \vert 1 \rangle

But when we consider 2 copies of the state we have

\vert \psi^{\otimes 2} \rangle = \alpha^2 \vert 0 0 \rangle + \alpha \beta \sqrt{2} \vert \Psi^+ \rangle + \beta^2 \vert 1 1 \rangle

where

\vert \Psi^+ \rangle = ( \vert 0 1 \rangle + \vert 1 0 \rangle ) / \sqrt{2}

This is a decomposition with 3 stabiliser terms and so

\vert \psi^{\otimes 2} \rangle \leq 3

for all single qubit \psi . Ok, what about for more copies? Amongst many results in our recent Bravyi-Browne-Calpin-Campbell-Gosset-Howard (herein BBCCGH) is a proof that

\vert \psi^{\otimes t} \rangle \leq t+1 for t \leq 5

(see Sec V.A of arXiv_V1). The stabiliser rank grows linearly! Not exponentially, but linearly! OK, this scaling holds up until only five copies, but I find this remarkable. Incidentally, the proof has a nice connection to the fact that the Clifford group forms a 3-design. Beyond five copies, the numerics look exponential, but the numerics are heuristic, inconclusive and only go slightly further than five copies!

Do we have any lower bounds on stabiliser rank! Deep in Bravyi-Smith-Smolin (Appendix C) is tucked away a neat result showing that for the \vert T \rangle state (an especially important single-qubit state) we know the stabiliser rank must scale at least as fast as \Omega( \sqrt{t} ) for t copies. We are hoping for an exponential lower bound and yet the best we find is a square root. Not even a linear lower bound! I find this shocking. And I assure you, it is not for lack of many smart people spending many, many hours trying to get a better lower bound. In Sec V.D. of BBCCGH, we (I say “we” but this part was all Sergey) show an exponential lower bound but with an additional (and quite strong) constraint on the allowed stabiliser states in the decomposition. The proof technique is really interesting and hints at routes forward to solving the full problem.

There are also a whole bunch of cool open problems revolving around the approximate stabiliser rank (introduced by Bravyi-Gosset) and which BBCCGH show is connected to a quantity called “the extent” (see Def 3 of BBCCGH). I want to say more about these open problems but this post has already gone on too long. More to follow in part 2!

Leave a comment