Factoring a quantum state

Question

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:

|0000>/2 - |0011>/2 + |0100>/2 - |0111>/2

and factor it into a more compact form using tensor products, like this:

|0> x (|0> + |1>) x (|00> - |11>) / 2

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

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>).

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

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

http://stackoverflow.com/questions/2267146/what-is-the-fastest-factorization-algorithm — Ashalynd, Apr 27 '14 at 17:58
@Ashalynd That is an algorithm to factor integers into primes. What I want is more analogous to [polynomial factorization](http://en.wikipedia.org/wiki/Factorization_of_polynomials), though still different. — Craig Gidney, Apr 27 '14 at 18:00
Should this algorithm be implemented using a [quantum programming language](https://en.wikipedia.org/wiki/Quantum_programming#Quantum_computing_language), or should it be implemented using a traditional programming language? — Anderson Green, Apr 27 '14 at 18:06
@AndersonGreen A normal programming language. I want to use it to visualize the state of a quantum computation, but since I don't have a quantum computer it would not be useful for the factoring algorithm itself to be quantum. — Craig Gidney, Apr 27 '14 at 18:13
@Strilanc See also: http://stackoverflow.com/questions/4595156/software-simulation-of-a-quantum-computer — Anderson Green, Apr 27 '14 at 18:14
@AndersonGreen Thanks. I have already written a very basic simulator ( http://jsfiddle.net/xkCLq/24/embedded/result/ ), but before I work on the massive lack of optimizations I want to work on visualizing the state better. — Craig Gidney, Apr 27 '14 at 18:17
Isn't the running time of your approach asymptotic to 4^b, where b is the number of qubits? The loop structure looks to me like, for each subset of qubits (2^b), for each setting of those qubits (2^c where c is the size of the subset), compute the conditional state of the other qubits (2^(b-c) coefficients) and compare. — David Eisenstat, Apr 27 '14 at 19:24
@DavidEisenstat Sounds about right. Like I said, `n^c`, which is `(2^b)^c`, was just a half-thought lower bound that was already bad and likely to be worse. — Craig Gidney, Apr 27 '14 at 20:07
Ah, so `n` is the number of qubits, not the number of classical states. — David Eisenstat, Apr 27 '14 at 20:09
@Craig: Can you give me a hint why "that is an algorithm to factor integers"? — Hans-Peter Stricker, Jul 22 '16 at 11:28
@HansStricker Since the full problem was NP-hard, I focused on "is a specific contiguous set of qubits indicated by the user separable from the rest?". [You can see it in action in Quirk's amplitude displays.](http://algorithmicassertions.com/quirk#circuit=%7B%22cols%22%3A%5B%5B%22Y%5Et%22%2C%22X%5Et%22%5D%2C%5B%22Amps2%22%5D%2C%5B%5D%2C%5B1%2C%22%E2%80%A2%22%2C%22X%22%5D%2C%5B%22Amps2%22%5D%2C%5B%5D%5D%7D) — Craig Gidney, Jul 22 '16 at 15:25

score 3 · Accepted Answer · edited Jun 20 '20 at 09:12

It looks like an efficient algorithm is going to be hard:

From wikipedia:

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.

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.

Sevag Gharibian, Strong NP-Hardness of the Quantum Separability Problem, Quantum Information and Computation, Vol. 10, No. 3&4, pp. 343-360, 2010. arXiv:0810.4507

Factoring a quantum state

1 Answers1

Linked