# Simulate Surface /Topological Code with Majorana - Huge Complexity Saving

This article "Correcting coherent errors with surface codes" is talking in the methods section, about simulating topological codes / surface codes, using Majorana equivalent. It is also explained in the supplementary material of the article.

I found out that simulating coherent errors with surface codes with d>10 is almost impossible because of huge run-time. But here, they easily simulate coherent error with d=37, which doesn't make sense to me at all.

My question is - where is the catch? how is it possible to simulate such a big surface code with arbitrary coherent error?

And if so, why this method is not so common? It should change the world of surface codes simulation.

EDIT: also this one is getting very big $$d$$ with FLO of Majorana

EDIT: This article: "Classical simulation of noninteracting-fermion quantum circuits" (2002) is talking about matrices in size of $$O(n*n)$$, and I don't understand why those matrices are not exponential in $$n$$.

One of the conclusions of the paper is that probabilistic Pauli error models are a good approximation. They show that the cheaper simpler thing works fine.

The actual reason you wouldn't use this method is because, although it's cool to directly do unitary errors, the errors you can apply are too restrictive. They apply the same unitary operation to every qubit at the same time. They don't do varying noise spread out over time and propagated around by a circuit. They don't account for the effects of decoding.

It's also relatively slow. In Table 1 they say it takes a ~second to sample a single-shot distance 49 surface code. That's 100000x slower than Stim's sample rate for this circuit.

Basically, these kinds of expensive unitary simulations are important to do... because you want to validate that you can get away with cheaper methods.

• Actually I’d rephrase Ron Cohen’s question slightly: Clifford gate based simulators like stim have a space complexity that’s quadratic in the number of qubits (just need to keep tableaus in memory). However these guys are simulating non Clifford gates without exponential memory complexity. What’s the catch?
– Lior
Feb 28 at 22:02
• Also I agree about the fact that applying a uniform rotation is artificial (and in fact I don’t even fully understand why it has any effect at all, I’d expect it to be equivalent to a change in global reference frame), but in this case there is a huge difference between the coherent and incoherent errors
– Lior
Feb 28 at 22:05
• @Lior Exponential is worse than quadratic so I don't quite see the issue. Additionally, surface codes are a very well behaved stabilizer circuit. If you specialize a stabilizer simulator to a surface code memory qubit, you only need linear space in the number of qubits. In fact, Stim does this after its initial circuit analysis. Once it's producing samples it's only using linear memory in the number of measurements + qubits. Feb 28 at 22:16
• @Lior Uniform rotation is a relevant error mechanism because in practice there can be things like stray magnetic fields that are roughly uniform over all the qubits, causing them to precess together. But in practice you use dynamical decoupling to cancel out things like that. Feb 28 at 22:18
• What I meant is: from the code distances they are running, it seems like they manage to avoid exponential complexity while still doing non Clifford gates. How?
– Lior
Feb 28 at 22:27

In my understanding, the paper leverages the fact that Gaussian states can be represented with the $$O(n^2)$$ covariance matrix, and, for a limited set of Fermioninc Linear Optics operations (state prep, tensoring, rotation and measurement/projection based on a majorana modes) you can also update the matrix efficiently:

Thus the catch is that FLO is not universal, you can only simulate with it very specific kinds of circuits and thus noise models. For any other kind of noise model, you'll have to use a different approach.

The operations are

• Thank you. Can you show which type of operations are allowed? Where is it declared? What is the reason it can Z rotations OR X rotations? Mar 9 at 12:44
• The supported operations are listed in my answer: - initialize majorana modes in |0> - rotate around a majorana mode with an angle - this is good for the noise - apply a projector - this is used for measurement basically Are you trying to work out in Pauli "language" what these operations mean instead of the majorana mode "language"? Mar 11 at 9:20

According to "Classical simulation of noninteracting-fermion quantum circuits" from 2002, as long as your 2 qubits gate are from the form of:

Which can be seen as no mixing between $${00,11}$$ and $${01,10}$$ states.

If you think of $$U$$ as a propagator of Hamiltonian $$U=e^{iHt}$$, so H is Hamiltonian which is sum of 3 Hamiltonians:

You can use this assumption, to build the matrix of the whole circuit, which is normally $$2^n*2^n$$ too big matrix, as a matrix in a size that is polynomial in n. Then, all you have to do to get the results of your calculations is to perform polynomial operations.

This is done using converting qubits to the creation and anhelation operators of Majoranas.

The assumption about the form of $$U$$ above is causing many terms of the calculation to vanish to zero, left only with operators on each site $$i$$ in the $$n$$ sites separately.

Another form of restriction there, is demanding that the sum of 1s in the state will preserve, so every term in the matrix which does not preserve the sum of 1s vanishes.