How will Microsoft Majorana quantum chip ??compute??, exactly?

During the 2020 COVID lockdown, I investigated braid theory in the hope it would help me on some research I was conducting in Azure…

Turns out it didn't help me in that domain, but as a fortunate side effect, I stumbled on the crucial role braid theory plays in a promising branch of Quantum Computing: the so-called topological computers, based on ??anyon?? qubits.

Following the important milestone reached last week by Microsoft toward making a topological computer that they call Majorana, I thought some of my readers would be interested to know how quantum braids computation works under the hood.

Majorana, a very standard quantum circuit... with a twist!

Anyon-based quantum computers are very similar to traditional quantum circuits: they use a composition of unitary operators (quantum logic gates) to perform computations/uncomputations. The actual difference lies underneath, "in the silicon": the gates themselves manipulate anyon?qubits.

• The major benefits of the anyons qubits is their stronger resistance to perturbation, often leading to quantum wave collapse (decoherence). The larger the circuit, the greater the risk of collapse.
• The major drawback of anyons qubits is that, to make any good use of them, one has very limited options: we can only ??swap?? them in away that is reminiscent to crossing strands when preparing hair braids.

In a topological quantum computer, quantum gates are made using hundreds of such elementary braiding operations. How are they devised, exactly? It is difficult. One has to perform some kind of brute forcing to exhaust many configurations until one is found that ??approximates?? the expected behavior of the gate within a narrow error margin (say, error is less than 0.002).

Here is a solution found in 2018 by Field and Simula, for the Hadamard gate, the most basic quantum gate one can imagine. Even for such a simple gate, look how large is the number of braiding operations!

In the above picture, we see that 3 strands are involved in the braiding: the underlying mathematical structure, according to braid theory, is called the braid group B2: B means Braid of course, and 2 is the number of unique braiding operations, called generators. Here there are two such generators: the first one is used for crossing the top and middle strands, the second one is for the middle and bottom ones.

To give you a grasp of what can be done with this theory, let me now give you a concrete example, which is much less efficient than standard calculus, but I think excellent for education: verifying the integrity of a Piercing Index string vector!

The Piercing Index (PI)

PI is a simple way to assess a public cloud vulnerability. I announced its availability two years ago.

The machine-readable score of the vulnerability is described as a string vector, following the common practice used (famously) in the Common Vulnerability Scoring System (CVSS).

The PI vector is defined by answering up to 8 questions, called A1 to A8. To make it simple, let's focus on 4 questions only: A1, A2, A7 and A8.

The first two questions are related, so are the last two.

A1 can take 6 different values (as of PI version 1.6), whereas A2 and A7 can take 3 different values, and A8 can take 4 values.

Computing PI integrity using braids

Here are the insights:

1. we want to encode valid PI vectors as braid words which are easy to verify, so that a PI vector is valid if and only if its braid word is.
2. each answer A1, A2, A7, A8 is assigned its own generator s, t, u or v
3. the syntactical logic of the PI string vector is carefully injected into the braid structure, by assigning generators to question in a topological-aware fashion.

Organization of Braid Strands

A defining feature of braid groups is the spatial arrangement of generators operating on strands, which influences their commutation properties.

Far vs. Close Generators

In a braid group:

• Far generators commute: If ai and aj are not adjacent (i.e. ∣ i?j ∣≥2), then ai*aj=aj*ai. Put it another way, the generators commute if they don't share a common strand.
• Close generators obey nontrivial relations: Adjacent generators (generators sharing a common strand) satisfy the braid relation, which is anticommuting (ai*ai+1*ai=ai+1*ai*ai+1, we won't need the details)

Topological strands assignments for PI Vector Components

We assign the generators so as to reflect the specific PI vector structure:

• Questions set 1 (A1 and A2): Since A1 and A2 relate to the same question set, their strands and their generators should be far off in the braid, to denote coupling. For example, if we assign s to A1 and u to A2, their distance is 2, hence s and u commute.
• Questions set 2 (A7 and A8): Similarly, generators t and v (representing A7 and A8) are assigned far off positions ensuring commutation, hence coupling.
• Cross–set anticommutation (eg: A1 and A7): In contrast, A1 and A7 belong to distinct question sets. Thus, we deliberately assign them adjacent generator positions so that they don't commute, as per the braid relation. Since A1 is already assigned s, we assign t to A7. Note that, similarly, A2 and A8 are close together (because u is assigned to A2 and v to A8).

A1 encoding

In the PI version 1.6, the A1 coordinate of the vector can take any of the 6 following values: 1, 1.1, 10, 11, 20, or?22.

We must map these values to 6 distinct integers in such a way that the induced cyclic relation on the generator s (assigned to A1) is non‐trivial and exactly captures 6 states. One natural way to do this is to assign values in an arithmetic progression. For instance, we choose:

1, 7, 13, 19, 25 & 31

The specific choice is rather arbitrary. The mapping is done using a (homothetic) permutation from the interval [0.0, 22.0] to the integers interval [0, 220] (I leave you the details as an exercise).

For each exponent e in this list (other than the first), the relation

s=s^e

implies (after multiplying by s^-1): s^e?1=I. (Where "I" denotes the identity)

Specifically, we have the following values for e-1:

7-1 = 6, 13 -1 =12, 19 -1 = 18, 25 -1 = 24, 31 -1 = 30.

The greatest common divisor of these differences is

gcd(6,12,18,24,30)=6

This guarantees that in the quotient group we have the relation

s^6=I

so that s has cyclic order 6. Consequently,

the different Piercing Index values for A1 are encoded by distinct powers of s in a cyclic group of order 6.

From braid group to quotient braid group: it's (magic) show time!

Critically, observe that, by imposing a constraint on a braid generator, we depart from the canonical structure of a braid group. Since this additional constraint is a cycle, we are now operating in a quotient braid group.

I like to think of this constraint as adding a small dose of magic to the braid group! Why? Because the way it works reminds me a lot of the Chinese linking rings magic trick. Here is an example with s^4=I:

A2, A7 and A8 encodings

Let's carry on with the other Piercing Index vector coordinates.

For A2 and A7, which can take 3 values, we encode all of them with a new set of exponents (1, 4 and 7, for instance) in geometric progression so that gcd(3,6)=3

Hence u (assigned to A2) and t (assigned to A7) have cyclic order 3: u^3=I and t^3=I

Lastly for A8, using the same recipe, we define a cyclic order 4 on v. v^4=I

Braid words

Using the above construction, we are now able to "compute" a braid word for every single Piercing Index vector.

Braid computing

Here are a few examples:

1. PI:1.6/A1:20/A2:1/A7:0.9/A8:0.7 translates into braid word sutv, because 20 is a legal value encoded as s, 1 is a legal value encoded as t, 0.9 is a legal value encoded as t and 0.7 is a legal value encoded as v.
2. PI:1.6/A1:17/A2:1/A8:0.7/A7:0.9 translates into braid word s^12uvt, because 17 is an illegal value encoded, for example (depending on the permutation that you chose as part of the exercise I proposed earlier) as s^12, 1 is a legal value encoded as t like previously, and finally A8 and A7 are swapped so they are encoded as v and t.
3. PI:1.6/A1:20/A2:1/A1:10/A7:0.9/A8:0.7 translates into braid word sustv (notice that s shows up twice). This example is important, because it demonstrates how we use braid words to perform syntactical (topological) validation and not semantical verification, so we don't capture the conflict between values 20 and 10 assigned to A1.

Normal forms

Recall that 3 properties operate in our quotient braid group: commutation, anticommutation (the "braiding relation"), and modulo (the "Chinese link rings").

It means that braid words can be represented into many different forms:

• sutv, for example, is the same as ustv or suvt or even usvt because s and u commute (they are "far away"), so do v and t.
• sutv is also the same as s^49utv^5 because s^48=I and u^4=I

But the good news is that

the braid words of all valid Piercing vectors can be reduced to a single normal form

This normal form, of course, is sutv.

Reduction is performed picking the 3 properties of the quotient braid group where appropriate. This can be done with a terms rewriting system, for example, as I explained in the newsletter I dedicated to Sanskrit.

Verifying PI vectors

Suppose we have a Piercing Index vector verifier taking each Braid word one after the other from a queue.

The verifier would proceed as such to state whether a string is valid or not:

1. Reduce the braid word to its normal form
2. Check that the word is sutv

That's... it! Aren't maths beautiful?

Computational Simplicity

The encoding, while over-kill for the purpose of education, is still computationally simple because:

• Each generator’s valid powers are defined modulo its cyclic order.
• Normalizing a braid word involves reducing exponents modulo 5, 4 or 3, respectively, and applying simple rules like "moving strands around"
• The gcd condition guarantees that the reduced form is unique and that the mapping from PI values to exponents is well defined.

Thus, not only is the validation of a PI vector equivalent to checking whether the braid word meets these relations, but the process itself is streamlined by the cyclic quotient structure.

Conclusion

We have shown how braid groups power the foundations of anyon computing that will be used in topological quantum computers if they ever become a reality. Then, departing from braid groups, we have enriched the playing ground by adding cyclic properties which took us to quotient braid groups.

From that ??beefed up?? computational toolkit, we have formalized an encoding of PI vectors (version?1.6) as braid words in a cyclic quotient braid group featuring 4 generators.

The organization of the braid strands— carefully placing generators corresponding to the same PI question set “far apart” and those corresponding to different sets “close” together—enables the imposition of a structured topology, which detects and invalidates forbidden configurations (aka "syntax errors").

I’m grateful to Marjan Sterjev and his hawk eyes for bringing an error in the choice of an exponent.