[tezthenerd]

Here is a way to see the fallacy of the OMG, its 10^300 variables, thats crazy style of “argument”.

Consider a probabilistic classical algorithm on 500 bits. Perhaps a Monte Carlo simulation of an Ising model for example.

Note first that the most general probability distribution over the 500 classical bits takes 2^500 real numbers to specify. (You have to specify P(000…0) and P(000…1) and… P(111…1)). [You should compare this to the 2^501 real parameters it takes to specify the quantum state of 500 qubits.]

To generate the most general such distribution perhaps you are restricted to using circuits where the gates act on at most n-bits at a time. Each gate can be described by a 2^n x 2^n bistochastic matrix comprised of (n-1)^2 real parameters. [You should compare this to the n^2 real parameters it takes to specify a 2^n x 2^n unitary matrix for a quantum gate acting on n qubits.]

Obviously its nuts to imagine you can generate all classical probability distributions over the 2^500 real parameters, particularly if you’re so mad as to think you are going to do it using a circuit comprised only of these n-bit gates!

Therefore useful classical monte carlo computing is obviously decades away.

(Oh and please trust me, I'm well know in stuff that isn't quantum computing.)

[tezthenerd]

Let me present it a different way.

Someone comes to you with two formal models of computing. Both models involve representing the state of the computer as a vector of real numbers, they both involve finite dimensional subsystems combined with a tensor product, both involve gates defined over the reals also combined via the tensor product and so on. That is, both models are just about evolution of a vector in some (very high) dimensional real vector space according to gates acting on a small number of subsystems. In fact these two models are identical, except for the fact that in model A the readout procedure involves computing a property of the output vector with the 1-norm, while in model B the 2-norm is used.

This is not an analogy, these are valid mathematical formulations of classical and quantum computing, the correspondences (and differences!) are well understood and rigorous.

Now you read an IEEE article that vociferously objects to the feasibility of building a computer based on model B, but all the objections are to do with properties of model B that it fully shares with model A. And model A you know can be very well approximated already in the physical world, which means reality was somehow was not inhibited by those objections. To try and refute the physicality of model B with an argument based on premises already satisfied by model A is silly.

(Note that even if it were the case that complex numbers were necessary for quantum computing, which they are not - see eg. my book Q is for Quantum - you can map the quantum density matrix on n qubits to a real vector over the basis of Hermitian matrices).

[dhammack]

Hey I'm not familiar with this way of comparing classical and quantum computation. Can you point me to some more details? I have Nielson's book but don't remember seeing this analogy before!

[tezthenerd]

I presume its explained in Scott Asronsons book, its implicitly there in Nielsen and Chuang. But the best way to understand it is by example - try to write out how you would describe classical probabilistic computation on two classical bits to mimic the quantum circuit type of picture, and if you succeed the generalization will be obvious.

[xpuente]

> ... as a vector of real numbers...

Using IEEE754?

[SurfaceCode]

Likewise, you don't ever explore the entire state space when you perform quantum computation. As it happens, most states are inaccessible. As shown by Poulin et al. in Physical Review Letters, 106, 170501 (2011), you can only ever explore a very small fraction of quantum states in polynomial time.

Edit: tezthenerd has said pretty much the same thing below. I just included the reference in case you'd like a formal proof.

[atq2119]

Monte Carlo simulation doesn't generate all classical probability distributions though. Attempting to do that would be nuts. Monte Carlo simulation only samples from a single, fixed distribution (or maybe a small number of distribution).

I'm not super convinced by the argument based on number of parameters either, but your analogy doesn't refute it at all.

[tezthenerd]

Its not meant to be an analogy.

We also will not attempt to generate all quantum states on a quantum computer. As with classical monte carlo, we will only ever generate a tiny fraction of the possible quantum states/distributions, and will also sample from a fixed distribution (whatever the quantum circuit outputs, we measure it in a fixed basis and always draw samples from that single, fixed distribution).

We will also achieve robustness against the tyranny of the real numbers in our gate parameters in a very similar way that a classical computer does when it approximates some idealized Monte Carlo algorithm.

[Florin_Andrei]

I mean, heck, you don't even need computers, just play a game of Go. Suddenly you're juggling "variables" in a humongous parameter space.