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

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

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 Ttype 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 nonorthogonal 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 singlequbit magic state, the 'facestate'. 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 edgetype 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
acallow=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 Cextensions, 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 bittwiddling 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 onequbit magic state. In this case, the scaling of the approximate stabilizer rank goes as . This factor when rearanged 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 16 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 twofold 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 24 qubits; here are the results found:
State234  234 Random34~6 345 34~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 Tcount of an arbitrary unitary is one route we could explore, and may in fact give a bound on the approximate stabilizer rank of the edgetype 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 facestate, 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 ChoiJamiolkowski 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:
 The measure of the Clifford group in .
 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 triorthogonality. It is also the case that the nonhittingset chunk must be contained in the dual of the hittingset component. From dimensionality arguments, we can thus show that the dimension of the hittingset 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 'worstpossible' 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 4fold 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
 copies2345  3456
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 numpyaccelerated 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
 copies12345678910  22346714142128 23456814243036
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 'tdesigns' 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 twoqubit states. This lets us rewrite 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 nonzero, it must contain every stabilizer state. Since there are singlequbit stabilizer states, we need (???), and so we can extend this result to copies in the twoqubit 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 nqubit 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 locallyClifford 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 localClifford 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 BravyiGosset 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 BravyiGosset 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 oddprim 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 Tcounts 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 nonCLifford 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 smallangle 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.
Simulation
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 Tsyntehsis routine for single qubit unitaries, and the H+Toffioli basis for others.