# Computational Library to compute Quantum Cluster States

I want to write a simulator for a quantum computing model that I am working on and I was wondering what would be the correct library / implementation strategy to implement quantum cluster states? Specifically I want to compute a cluster state of a specific topological quantum computation. I am investigating algorithms using this model and I would like to have a toy implementation for a presentation. The specific algorithm would perform similarly to this.

1. Encode the given knot algorithm into a set of braids and create a cluster state of those braids
2. Perform measurement on those braids
3. Return a element of $Z_{n} \in_{1,0}$
4. Perform a classical operation on the knot.
5. Perform another operation until the knot is in a desired state.

See http://arxiv.org/pdf/1101.4722.pdf for a very simlar model.

• The answer to this question is going to depend heavily on what you're doing with them. Can you give some more details? – Peter Shor Jul 12 '11 at 1:45
• I think I will have to rewrite this once I have the theory down. I will try to get back to this question in a few weeks. – Joshua Herman Jul 12 '11 at 17:50

As Peter mentions in the comments, it seems impossible to give an authoritive answer without knowing what exactly you are planning on doing with them. That said, there are at least a few places I can point you which may be of some use.

Firstly, Pauli measurements on cluster states can be efficiently simulated on a classical computer. This is a direct result of the Gottesman-Knill theorem (see this paper by Gottesman and this follow-up paper by Gottesman and Aaronson), which Clifford group circuits can be efficiently evaluated via the stabilizer formalism. So it may be that stabilizers are the way you want to go.

However, if you want to be a little less general, and restrict yourself to graph states (a general name for cluster states on general graphs) then there are two papers by Hein, Eisert and Briegel and Schlingemann which describe how Pauli measurements performed on a graph state result in states which are locally equivalent to graph states, and provide rules for these transformations. Thus it is quite possible to work with graphs as your data structure, as long as you do not intend to leave the Clifford group.

Finally, Ross Duncan and Lucas Dixon have taken a category theoretic approach for automated reasoning about graphs and have produced some nice proof of concept software using this approach (see here).

Also, I would point out that Raussendorf, Harrington and Goyal have previously looked at implementing topological computations via measurements on cluster states (they use it to achieve fault-tolerance in cluster states in a very beautiful way), and so you might be interested in their work (see here and here). These papers give an explicit encoding for encoding braids in a cluster state.

UPDATE: I notice you have just added the forth point. The Raussendorf-Harrington-Goyal papers I linked to above do provide a very nice way of doing topological quantum computing via cluster states, which allows classical operations on the knots to be done within the Clifford group, and hence the stabilizer and graph transformation approaches I previously mentioned can be used to efficiently simulate these operations.

• Ross Duncan and Lucas Dixon would be a good start to investigate. Thank you for your time! – Joshua Herman Jul 12 '11 at 22:00
• @Joshua: No problem, though if I were you, I would make sure I was familiar with the stabilizer techniques first. They're extremely powerful. – Joe Fitzsimons Jul 12 '11 at 22:10
• Yes, looking into them with their $O(n^2/ log(n))$ complexity would be very fast. Thanks again! – Joshua Herman Jul 14 '11 at 9:32
• I'm working on a fast simulator/implementation of the measurement calculus, although I allow arbitrary measurement angles which takes me out of stabilizer calculus territory into an exponential complexity. Is there some demand for such a slower but more general simulator? – Beef Aug 8 '11 at 13:24