<p>It looks like an efficient algorithm is going to be hard:</p>
<p>From <a href="http://en.wikipedia.org/wiki/Separable_state#Separability_criterion" rel="nofollow noreferrer">wikipedia</a>:</p>
<blockquote>
<p>The problem of deciding whether a state is separable in general is
sometimes called the separability problem in quantum information
theory. It is considered to be a difficult problem. It has been shown
to be NP-hard.</p>
<p>Gurvits, L., Classical deterministic complexity of Edmonds’ problem and quantum entanglement, in Proceedings of the 35th ACM Symposium on Theory of Computing, ACM Press, New York, 2003.</p>
<p>Sevag Gharibian, Strong NP-Hardness of the Quantum Separability Problem, Quantum Information and Computation, Vol. 10, No. 3&amp;4, pp. 343-360, 2010. arXiv:0810.4507</p>
</blockquote>
Factoring a quantum state
<p>I'm looking for algorithms that take an arbitrary quantum state made up of a sum of weighted classical states made up of bits, like this:</p>

<pre><code>|0000&gt;/2 - |0011&gt;/2 + |0100&gt;/2 - |0111&gt;/2
</code></pre>

<p>and factor it into a more compact form using tensor products, like this:</p>

<pre><code>|0&gt; x (|0&gt; + |1&gt;) x (|00&gt; - |11&gt;) / 2
</code></pre>

<p>I want to use the algorithm as a way of visualizing/simplifying the state of a (simulated) quantum circuit.</p>

<p>For individual qubits I know I can just pair all the states with the state where the bit is flipped and check that every pair has the same x:y relation between the states. In the example above, flipping the second bit always gives you a state with a 1:1 weighting, so the second bit factors out as (1|0> + 1|1>).</p>

<p>But extending that approach to detect entangled bits (like the third and fourth in the example) causes it to take at least <code>Ω(n^c)</code> time (probably more, I haven't thought it all the way through), where <code>n</code> is the number of states and <code>c</code> is the number of entangled bits. Since <code>n</code> is already growing exponentially with the number of bits that's... not ideal.</p>

<p>Are there better algorithms? Representations easier to factor from/to? How useful is changing the basis? Links to papers would be great.</p>