Stabilizer Rank Project

The Stabilizer Rank is a measure introduced by Bravyi, Smolin & Smith in 2015, and is equal to the number of terms in a covnex sum of stabiliser states such that .

More precisely, we will call the 'exact' stabilizer rank of a state the minimum value of . For any n-qubit state, we can trivially note that as the computational basis states are stabilizer states. Similarly, for all stabilizer states .

BGSS Papers

The notion of the Stabilizer Rank was introduced by Bravyi, Smolin and Smith as a way of potentially clasically simulating Clifford+T quantum circuits. Using the tools of Clifford Reduction, we can rewrite any Cliffod+T circuit using state injection as a sequence of (adaptive) Pauli measurements on magic states where is the number of T gates in the circuit. Classical simulation is efficient for stabilizer states, so if we know the stabilizer rank decomposition we can more easily simulate this resulting 'Pauli Based Computation'. This was discussed in their follow up paper, and my notes on it.

Importantly, in this follow up paper they also introduce two notions.

  1. 'Strength' of simulation:

    When doing a classical simulation of quantum computing, we seek to approximate the output distribution probability. Bravyi defined two notions of this simulation, strong and weak. The former involves simulating for some output with precision; this task requires quantum computers to do and is thus dang hard clasically!

    The latter, weak simulation, involes sampling from a distribution which is close to under the norm. This task is easier, and in particular has a polynomial dependence on the subset of the total qubits we measure.

  2. Approximate Stabilizer Rank

    This is related to the task of weak simulation. In particular, the approximate stabilizer rank of a state is define as the stabilizer rank of a state that approximate .

In their papers, Bravyi and Gosset demonstrated several key features of the stabilizer rank. In particular, they showed that for strong and weak simulation of Clifford+T circuits, the computational complexity scales as where is the number of qubits, the number of T gates and the number of clifford gates.

The also showed that using simualted annealing to find decompositions that the actual stabilizer rank of the T-type magic states grows slowly for up to qubits. Using the fact that , the rank of 7 for 6 qubits gives a bound .

If we instead examine the 'approximate' stabilizer rank, they use the fact that the edge type magic state lives in the space spanned by the non-orthogonal stablizer states , and the generate short random codes such that one can be found with rank which epsilon approximates . \

MRes Project

My masters report looked at the possiblity of using the Stabilizer Rank as a resource measure. We know that, because classical simulation of quantum circuits is believed to be hard, the stabilizer rank, approximate or otherwise, must grow exponentially in the number of T gates. But, Bravyi an Gossett showed that the exponent is surprisingly small, approximately for the apprixmate stabilizer rank. So, this leads us to ask how Stabilizer Rank behaves for other states?

Analytically, I found that we could generate approximate stabilizer rank decompositions for the second class of single-qubit magic state, the 'face-state'. In this case, the exponent is instead given by . This derivation exactly follows the form of the Bravyi Gosset paper, using a 'ternary' basis of stabilizer states.

During my project I developed code in python for generating Stabilizer States, and then for doing brute force search for exact stabilizer rank decomposition. In particular, the code represents Pauli operators as bit binary strings, where the resulting operator is given by . The code then takes combiantions of strings and builds the full group generated by them, testing for unique groups. The resulting unique groups are then translted to a generating set of Pauli operators , and the stabilizer state is the eigenstate of the resulting projector given by .

The conclusion of the project is that the stabilizer rank seems to grow most slowly for the edge-type magic states. The implication here is that Clifford+T is potentially the 'weakest' choice for a restricted gate set; the resources we need to break away from classical simulability are larger, and this in turn implies that T count will blow up when we start trying to a quantum computation that is Classically 'difficult'.

Numeric Extension

Following my project I looked at using the random walk method to try and find approximate decompositions of higher order products of different states. This effort was unfortuantely hampered by the design of my MRes code and the lack of a systemic approach, and my focus instead shifted to looking at State Injection circuits.

I have since completed a rewrite of the code, fixing several bugs and improving the design, under the project name Stabilizer Search. This code is also in the process of being packaged for release on PyPI.

An improtant note when running code on Legion is that the login nodes use newer processors than some of the compute nodes. In partcular, the login nodes have access to an instruction set called AVX, a seriesd of optimisations by intel for performing matrix operations. This means that when compiling code on a login node, you need to specify that the resulting job runs only on nodes that have access to AVX instructions. We can do this by specifying the option -ac-allow=MNOUT. See also the notes on running code on Legion.

In 2017, the project was restructured in to the package stabilizer_search. This package is designed to be extensible and to allow pieces of the code to be replaced with well optimsed C-extensions, interfaced using Cython.The current version implements Brute Force search, and Random Walk search. Stabilizer states are generated using python, where the symplectic representation of Pauli operators is implemented using boolean numpy arrays.

There are several improvements to consider, some of which are currently underway. The code to generate stabilizer groups is currently being reimplemented as a C extension that would allow finding groups on up to 32 qubits, and is realised using long integers and bit-twiddling to achieve the symplectic form. Another optimisation over the python version is a binary guassian elimination algorithm designed to efficiently test for linear independence of the genrators, as opposed to building the full group and testing uniqueness.

Another consideration is multiprocessing. The BruteForce search is naively parallelisable, as the combinations can be distributed between worker processes. These processes would have a shared 'success' element that they check at each search step, but otherwise privately check the overlap of the projector on the target state.

Additionally, it would be good to write 'cythonised' forms of the search funcitons do_brute_force and do_random_walk; this would likely give a good speed advantage for little to no effort relative to writing a C extension and interfacing it.

Earl Campbell's Note

At the Quantum UK conference 2016, I had a chance to chat with Earl Campbell about the stabilizer rank. In particular, he shared a note on extending the 'random codes' method of Bravyi and Gosset to all resource states that live in , the third level of the Clifford heirarchy. This includes both species of one-qubit magic state. In this case, the scaling of the approximate stabilizer rank goes as . This factor when re-aranged agrees exactly with the scaling found by Bravyi & Gosset and by my MRes work. This method relies on the fact that any resource state can be written as where is a Clifford operation and is a stabilizer state.

In a later version of the note, Earl also added an observation about the exact stabilizer rank; a given stabilizer state (or copies of one) is also stabilized by a subgroup of the Clifford group. If we can in turn find a maximal proper normal subgroup of this clifford stabilizer, then the order of the resulting quotient group is an upper bound on the stabilizer rank. This agrees exactly with BSS for 2 qubits, but runs in to trouble as we move to higher orders as the order of any clifford subgroup with generators is .

Examining the Exact Stabilizer Rank

In their paper, BSS found the exact stabilizer ranks for 1-6 copies of the T type magic state by using simulated annealing to walk through the space of real stabilizer states. The decompositions that resulted, however, share an interesting form. To see that, we first write the state in a weird normalisation from which it is immediately apparent n copies of the state can be written as where is the hamming weight of the binary string .

They then build decompositions out of stabilizer states in the computational basis, such as , the set of all bit strings and equal to , the superposition of all even weight strings, and the realted quantity . We can also build states out of graph states , where the graph can be expanded out in the computational basis. These tricks give the decompositions shown in the BSS paper.

An important observation made by Dan is that ANY product state will have a stabilizer rank smaller than . For example, on two qubits we can write , which is a sum of 3 stabilizer states. This in turn gives a scaling for n copies of any resource state, and implies that mixing resources is a good strategy for maximising stabilizer rank.

It would be interesting to try to extend this minimal spanning space for product states to arbitrary states. One current idea is that the two-fold product state is spanned by the stabiliser states and . If we construct the projector on to the +1 eigenspace of these three stabilizer groups, it seems to give the Identity operator. This is slightly suspicious, as we explicitly know that for example the state has . But it's possible that this works for the reduced space , where the generators of the group for an operator basis...?. This is slightly off as the states are vectors on but is an idea worth testing w/ brute force for 3 qubits (namely, can we find a stabilizer rank less than 6 for an arbitrary state on 3 qubits).

Searching using the random walk code gives some interesting examples for how the stabilizer rank grows over 2-4 qubits; here are the results found:

|State|2|3|4| |---|---|---|---| ||2|3|4| |Random|3|4|~6| ||3|4|5| ||3|4|~9|

Bounds on and other observations

In the BSS paper in Appendix C, a bound is proved on the stabilizer rank of magic states: . They do this by constructing a state that has distinct amplitudes in the computational basis. Each stabilizer state has disticnt amplitudes, suggesting that . This implies that .

They then prove that the state can be constructed out of a finite number of magic states . This gives , and taking the square root of each side using the multiplicativity of the stabilizer rank gives the stated bound.

Using a similar argument then, consider an arbitrary -fold product state . This state has distinct amplitudes in the computaitional basis, giving a weak lower bound . This method is worth playing with further. Using the T-count of an arbitrary unitary is one route we could explore, and may in fact give a bound on the approximate stabilizer rank of the edge-type magic states.

In the paper, BSS also make a few other interesting observations. One point is that, for , the state lies in the space spanned by the symmetric stabilizer states only (states invariant under a permutation of qubits. Note: Does this correspond to a permutation of the stabilizers?). This is no longer true for . Why is that? Is that useful at all?

They also note that all the terms in the decompositions they find using simulated annealing live in the field . A similar result perhaps exists for the face-state, though the field would also have a root . These fields could be a way to think about the maths of arbitrary states? The complex element is given by the phase, and the rational root is given by where .

Stabilizer Rank and Gate Synthesis

The stabilizer rank has a few interesting properties. For one, it is Clifford invariant, and monotonically decreasing under Pauli mesurements. This suggests that when we build a gate out of copies of the T magic state, using for example Peter Selinger's synthesis algorithm, the stabilizer rank of the resulting Gate (which is related to a state by the Choi-Jamiolkowski isomorphism) is strictly bounded by the rank of the magic states. Currently, this bound is . There is an interesting interpretation here about the power of approximate gate synthesis with gates.

As a suggestion, it would be interesting to try and evaluate:

  1. The measure of the Clifford group in .
  2. The measure of states synthesis with T gates in .

Stabilizer Rank March Meeting

On March 17th myself, Dan Browne, Earl Campbell and Luke Heyfron met to discuss progress on understanding the Stabilizer Rank measure. The main developments from this meeting include numerical analysis of the generalisation of approximate stabilizer rank via random codes, and an application of the study of symmetric subspaces to attacking how stabilizer rank grows for many copies of a stabilizer state.

Reducing the Hitting Set

We might ask if the example given at the end of the hitting set argument can be used to reduce e.g. to a circuit with only one gate. It is argued that the reduction of a factor of two is maximal. In particular, this argument is based on writing the circuit as a phase polynomial given by a binary matrix. In this case, the circuit is represented by the identity matrix. A Clifford transform of the circuit corresponds to a linear transform on the matrix, in this case giving the actual matrix. We know that the resulting circuit acting on the qubits outside the hitting set must be built of Clifford operations only, and this translates to a criterion of tri-orthogonality. It is also the case that the non-hitting-set chunk must be contained in the dual of the hitting-set component. From dimensionality arguments, we can thus show that the dimension of the hitting-set must be equal to that outside it, giving a bound of for the hitting set of .

However, this is premised on unitary equivalence of circuits. For example, consider synthesising a resource state, which has a circuit that requires 7 gates. No smaller unitary equivalent circuit is known. However, a known case found by Cody Jones can construct a state from a small circuit built out of 4 gates, where the resource state is Clifford equivalent, but the circuits are not. The Clifford invariance of the Stabilizer Rank of a state might serve as an interesting route to examine this difference.

A related conjecture Earl made is that this hitting set for the -fold T gate should be the 'worst-possible' case. More formally where denotes the hitting set of and is the number of qubits.

Symmetric Subspaces

Here, we try to examine if the permutation symmetries of multiple copies of a resource state can help us to bound its stabilizer rank. As described above, this is motivated by the fact that . My results from the stabilizer search package for 3 and 4-fold copies of Haar random states in turn suggest bounds of and for the two cases respectively.

The symmetric subspace of an -qubit state is spanned by a set of states, given by , up to normalisation. In general these sums of equal weight strings are NOT stabilizer states, but can be combined to create them. We will denote these states as where is the weight of the strings in the sum, and the D is chosen for Dicke state.

We note that , a Stabilizer state. For qubits, consider the 4 states where and is the -fold gate. This gives a state . From the sum of roots of unity, we can see that these 4 states span the symmetric subspace, as . This thus gives us a bound which agrees with the numeric result above.

We can extend this argument to 5 qubits, using the 4 states and the fact that are stabilizer staes on qubits. Similarly, this would suggest bounds of

| copies|2|3|4|5| |---|---|---|---|---| ||3|4|5|6|

which translates to a bound on the stabilizer rank of an -fold single qubit state of .

Random Codes

Finally, we note an open question on the what controls the size of the approximate stabilizer rank. As discussed above, this has been generalised for all states and is proportional to where . The states this has been tested have symmetric overlap with sets of stabilizer states used in their random codes, and so we are interested in generalising this argument:

Updates since March

Since the March meeting, we have continued to work on the Stabiliber Rank problem, considering several facets. Numeric tools have improved with a C++ library for generating stabilizer states, and a cythonized version of the random walk, as well as switching to the numpy-accelerated QR decomposition to build projectors. This has been used to confirm the numeric results of Bravyi and Gosset as well as our symmetric subspace ideas on single qubits, all the way to 10 qubits. We now have the following

| copies|1|2|3|4|5|6|7|8|9|10| |---|---|---|---|---|---|---|---|---|---|---| ||2|2|3|4|6|7|14|14|21|28| ||2|3|4|5|6|8|14|24|30|36|

We note that the bounds are never smaller than the multiplicative limit above 7 qubits, and that the stabilizer rank for magicstates and arbitrary states coincides at n=7. This i particularly interesting as it suggests we have found the onset of an exponential growth in the stabilizer rank (reassuringly). The existence of the arbitrary state decompositions suggests a bound on the stabilizer rank of ay circuit built out of Clifford gates and arbitrary single qubit rotations. If we have a set of rotations , each of which occur times, then the stabilizer rank is bounded by

This bound only applies for single qubit states, but we can use the notion of 't-designs' to bound the Stabilizer rank for larger resource states.

A projective -design is a configuration of vectors evenly distributed on the complex unit sphere . Let us define the projector on to the -partite symmetric subspace of , and is the dimension of this subspace given by .

A set of vectors is a projective -design iff

In our case, for an -qubit stabilizer state. Stabilizer states are known to be a projective -design for . We can use this to say that the Stabilizer rank of 3 copies of an arbitrary qubit state is less than or equal to for .

For two qubits, we have an extended result. Consider the fact that the set of -fold copies of Stabilizer states on 2 qubits will span the symmetric subspace if and only if there exists a state in the Symmetric subspace that is not orthogonal to every vector in .

Using the 'Majorana form', we are able to write out the elements of as a sum of permutations of products of two-qubit states. This lets us re-write the inner product we want consider as where is a normalisation constant and is the number of permutations of the individual that build up to the symmetric state on . For this to be always non-zero, it must contain every stabilizer state. Since there are single-qubit stabilizer states, we need (???), and so we can extend this result to copies in the two-qubit state case (???).

Stabilizer Fidelity

The stabilizer fiedlity is a term that appears in the size of the approximate stabilizer rank decompositions of a resource state, and is defined as ^{2} where is the requirement that this is a stabilizer state, and is our n-qubit resource state. As a shorthand, we will denote this as .In particular, for our bound to be tight, we want to ask if .

The proof for single qubit states is relatively straightforward, and is based on the observation that all Stabilizer states are locally-Clifford equivalent to a graph state, and that graph state stabilizers must have a certain weight. (Fill this out with the note, you need to git pull...)

Bravyi & Gosset have shown, however, that this is likely not to be the case for qubit states for large n. This result hasn't been fully shared with us.

A related conjecture is the observation that , which is tight for certain states. Currently we have made little progress on proving this conjecture, but one idea would be to exploit the local-Clifford equivalence to graph states which might allow us to constrain the number of classes of state we need to consider. TThis can be combined, interestingly, with the invariance of the Stabilizer Rank under clifford symmetries.

The Bravyi-Gosset simulator

Mark Howard has, working with the code developed by Bravyi & Gosset, been able to implement the hidden shift simulation using our result to generate the approximate stabilizer rank decompositions of states. One interesting observation is that , which means that we can more efficiently simulate circuits built out of Toffolis with our code.

I have successfully reimplemented the ExponentialSum subroutine of the Bravyi-Gosset simulator in C, leading to a 2x speedup. Further speedup would be possible if we switched much of the mathematics to use chars, and it is possible that there could be more efficient ways to implement the calculation itself as my currently version hews close to the B&G version.

Thoughts on Stabilizer Rank: State of the Union

The stabilizer rank method is all about classical description of a Clifford+Resource picture of quantum mechanics. Given the current focus on contextuality (or, to tie in to Nadish's recent work, logical paradoxes), and it's coincidence with the boundaries of Stabilizer mechanics in odd-prim dimensionality, this makes Stabilizer Rank an intersting way to study the power of quantum computation.

The fact that the stabilizer rank grows slower than might be expected for magic states and arbtirary singlue qubit states is surprisng, but what is not clear is what this tells us about quantum computation. It's clear, from compilation work in the CLifford+T picture, that T-counts grow rapidly. This rapid growth would quickly offset any advantage given to us by the Stabilizer rank, in a sense protecting quantum computing. (It's important to remember, too, that a weak exponential is still eponential).

The advantage in the stabilizer rank is biggest when we have many copies of a state. This in turn trades off against the ballooning resource cost of picking a single non-CLifford gate for our compilation strategy. Naively, the way to maximise the Stabilizer Rank is to use a lot of arbitrary rotations. This is kind of equivalent to saying that the most efficient quantum computation would be if we have full control over the qubits.

Our work on the Stabilizer Rank for arbitrary states suggests that there is little change in stabilizer rank once we go above the third level of the Clifford hierarchy. This is another piece of evidence against any advantage in power from picking gates in higher levels of the hierarchy, but doesn't reflect at all on the resource costs of say synthilalting small-angle rotations versus magic state distillation and gate synethesis. Instead, we just have an abstract observation on the classical complexity of each type of rotation: still exponential, but equal for each rotation type.

What little we know about Stabilizer rank for many qubit states is also interesting. Similarly, the stabilizer rank of a is smaller than that of 4 s, and thus a Toffoli and a T have a similar classical complexity in this picture. It's not clear what this means in terms of picking a universal basis set. (My personal feeling would be a compilation scheme that allows us to mix flavours of diagonal injectable unitary, swapping between T, CS, CCZ and small angle rotations.)

It would also be interesting to extend the Stabilizer rank further into discussions of multiqubit unitaries. One example would be controlled roots of Z< such as those consumed in the QFT subroutine. There are few known gadgets for these kinds of gate other than a slightly odd decomposition given in Nielsen & Chuang, and so an analysis of their Stabilizer Rank could be instructive. This would also give us a neat example of the classical complexity of such a subroutine which is generally considered powerful.


The other side of the coin is using the approximate stabilizer rank for simulation. Again, the ideal scheme would be a simulator that can freely switch between the flavour of \9\mathcal{C}_{3}) gate, decomposing whichever flavour is the most efficient. This would likely tie closely to quesitons of gate synthesis, and would need some interesting heuristics on how to pick which is 'best' at any given moment. In any case, combining T and CCZ simulaion should be easy using a combination of Seilinger's T-syntehsis routine for single qubit unitaries, and the H+Toffioli basis for others.