<p>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.</p>

<p>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 <a href="http://arxiv.org/abs/quant-ph/9807006" rel="nofollow">this paper</a> by Gottesman and <a href="http://arxiv.org/abs/quant-ph/0406196" rel="nofollow">this follow-up paper</a> 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.</p>

<p>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 <a href="http://arxiv.org/abs/quant-ph/0307130" rel="nofollow">Hein, Eisert and Briegel</a> and <a href="http://arxiv.org/abs/quantph/0305170" rel="nofollow">Schlingemann</a> 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.</p>

<p>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 <a href="http://arxiv.org/abs/0902.0514" rel="nofollow">here</a>).</p>

<p>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 <a href="http://arxiv.org/abs/quant-ph/0510135" rel="nofollow">here</a> and <a href="http://arxiv.org/abs/quant-ph/0703143" rel="nofollow">here</a>). These papers give an explicit encoding for encoding braids in a cluster state.</p>

<p>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.</p>

CC BY-SA 3.0
2011-07-12T22:00:05.570Z
Ross Duncan and Lucas Dixon would be a good start to investigate. Thank you for your time!
Joshua Herman
CC BY-SA 3.0
2011-07-12T22:10:54.750Z
@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
CC BY-SA 3.0
2011-07-14T09:32:26.103Z
Yes, looking into them with their $O(n^2/ log(n)) $ complexity would be very fast. Thanks again!
Joshua Herman
CC BY-SA 3.0
2011-08-08T13:24:38.883Z
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
CC BY-SA 3.0
2011-07-12T20:52:30.780Z
2011-07-14T00:39:06.537Z
2011-07-14T00:39:06.537Z
Joe Fitzsimons
<p>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.</p>

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

<p>See <a href="http://arxiv.org/pdf/1101.4722.pdf" rel="nofollow">http://arxiv.org/pdf/1101.4722.pdf</a> for a very simlar model.</p>

CC BY-SA 3.0
2011-07-12T01:45:54.037Z
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 
CC BY-SA 3.0
2011-07-12T17:50:46.873Z
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
<ds.algorithms><reference-request><quantum-computing><implementation><topology>
Computational Library to compute Quantum Cluster States
Joshua Herman
# Computational Library to compute Quantum Cluster States

(Asked by: username_0 on 2011-07-12)

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.

**Tags:** ds.algorithms, reference-request, quantum-computing, implementation, topology

> **Comments:**
> **username_1**: The answer to this question is going to depend heavily on what you're doing with them. Can you give some more details?  
> **username_0**: 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.  

---

## 1 answers

### Answer by username_2 on 2011-07-12. Score: 6 | Accepted answer

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](http://arxiv.org/abs/quant-ph/9807006) by Gottesman and [this follow-up paper](http://arxiv.org/abs/quant-ph/0406196) 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](http://arxiv.org/abs/quant-ph/0307130) and [Schlingemann](http://arxiv.org/abs/quantph/0305170) 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](http://arxiv.org/abs/0902.0514)).

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](http://arxiv.org/abs/quant-ph/0510135) and [here](http://arxiv.org/abs/quant-ph/0703143)). 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.

> **Comments:**
> **username_0**: Ross Duncan and Lucas Dixon would be a good start to investigate. Thank you for your time!  
> **username_2**: @Joshua: No problem, though if I were you, I would make sure I was familiar with the stabilizer techniques first. They're extremely powerful.  
> **username_0**: Yes, looking into them with their $O(n^2/ log(n)) $ complexity would be very fast. Thanks again!  
> **username_3**: 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?  

---

