[bollu]

I do not believe this. What will one do about intermetidate computations which can have complex coefficients? In general, you'd need some way to change the gates/ unitary matrices themselves to be purely real. So you'd need to find an isomorpism from U(n) into a subgroup of SO(poly(n)) for this claim to work. Why does such an isomorphism exist?

[IIAOPSW]

Its simple. Start with your circuit and add one ancila qubit. Then in your set of basis gates (universal for quantum computation), replace every phase shifting operation with a controlled X rotation targeted on that ancila.

For example, lets just use the cliffords plus arbitrary phase rotation {X,Y,Z,H,R(theta)}. X,Z and H are all real. Y is real up to an irrelevant global phase (if you really want to implement it anyway, just do X,Z on the target and then flip the ancila with an additional X). All that's left to handle is R(theta). Map R(theta) into a (real) controlled rotation in X (to wit: C-X(theta)). Thus we have a set of gates, universal for quantum computation, using only real numbers.

If you don't believe in arbitrary rotations X(theta) without intermediate imaginary operations, just pretend I used the T gate instead to extend the Cliffords. Either way you can construct a set which is universal for QC with only real numbers.

Why should it work? Simple. In your math, if you replace every i with |i> your equations are still the same. You've just substituted one squiggle on the page for another that works the same way. The Riemann sphere is just like the Bloch sphere. Complex numbers are a qubit the universe gives you for free.

[bollu]

I am super confused. Why can't I take this purely classical circuit and run it on a classical computer? Somewhere, there should be some blowup into exponential time?

[IIAOPSW]

The state space still grows like 2^n in the number of qubits. Again, all this mapping does is rename some variables from "imaginary number" to "degree of freedom on an imaginary system". But, the computer doesn't care what you call your vars.