Friday, March 18, 2016

Classical emulation of a quantum computer

I am now resuming my scheduled topics and I will start a small series on classical-quantum debate. I will start with a very interesting paper by Brian R La Cour and Granville E Ott talking about the possibility of emulating a quantum computer with purely classical means. I met Brian last year at a conference but I did not attend his presentation due to a scheduling conflict. However, after that I looked up his research and I found it most intriguing. 

The modern trend in quantum mechanics is not on discussing how counterintuitive the theory is or on Bohr-Einstein debate, but on how to use it to create useful applications not possible using classical means. One such application is a quantum computer which holds the promise of a massive speedup compared with classical ones. So the race is on to build such a thing, but to be of any value you need to have many quantum bits. However, the quantum states are very brittle and decoherence is your enemy. Against this background, here is this proposal by La Cour and Ott who say that you do not actually need quantum mechanics and you can emulate qbits using classical resources!!! Moreover, they built a working prototype. So what is going on here?

First, let me say this proposal does not contradict in any way quantum mechanics and the resulting system is pure classical. However, the scheme is quite clever and is able to realize the quantum algorithms speedups. The idea is that the computer is not digital, but analog using waves which naturally obey the superposition principle.

Here is the clever encoding scheme of a qbit corresponding to two complex numbers \(\alpha\) and \(\beta\):

\(\psi(t) = \alpha e^{i \omega_0 t} + \beta e^{-i \omega_0 t}\)

To recover \(\alpha\) and \(\beta\) from the signal one multiplies the signal with \(e^{\pm i \omega_0 t}\) and then applies a low pass filter.

To add more qbits, they use increasing signal frequencies: \(\omega_i = 2^i \omega_0\) and this ultimately provides the practical limitation of the scheme due to a finite amount of bandwidth.  This scheme cannot accommodate more than 40 qbits, but a 10 qbit system has the same processing power as a 1 GHz standard digital computer. While there is a speedup due to using quantum algorithms, there is also a slowdown due to signal extraction: the inner product of two wavefunctions is computed as a time integral of length \(2\pi /\omega_0\). \(\omega_0\) has to be small to accommodate as many qbits as possible.

But while there is superposition and a Hilbert space is present in the emulation scheme, there is no randomness and no true quantum behavior, so what can be achieved with this emulation? Surprisingly a lot because all quantum gate operations can be implemented.

The inherent determinism of the computation can be "fixed" by adding a random noise. But why do that? This makes sense if it helps speed up the extraction of partial information (remember that the inner product requires a lengthy time integration). More interesting is the realization of the teleportation protocol. The key sentence in the paper is this:

"although Alice is in possession of Bobʼs qubit, she does not manipulate it."

For separated systems, you do not actually get correlations higher than the Bell limit simply because there are no separated systems in this embedding scheme. So in a way it is cheating to call this teleportation; physically that can be achieved only with quantum mechanics. However the goal is to obtain a quantum computer able to process quantum algorithms and the actual algorithm is implementable in this embedding.

Apart from practical applications (which are rather modest due to the practical limit of 40 qubit) , this research is most valuable in opening up new roads in exploring foundations and computability. If a quantum computer is realizable with classical resources, why stop here and not realize a Popescu-Rohrlich box computer? Does anything like a PR box computer and a PR box algorithm exist? Nobody explored such concepts before because PR boxes do not exist in nature. But now we see that quantum algorithms do not rely on separated correlations. What is the relationship between a PR box and superposition? Does superposition prevent the existence of a PR box? And can we prove false the Church-Turing thesis?


  1. Surely you understand why it's not interesting - the capacity needed in the classical "emulator" grows exponentially. To emulate the memory of 100 bits, which is needed for almost any useful quantum computer, one needs 2^{100} complex amplitudes, and each of them needs at least several elementary particles to be materialized in the "classical emulator", so we're already above the capacity of the Solar System.

    1. A signal duration of 10 seconds can accommodate 40 qubits; 10 hours correspond to 50 qubits, a one-year would give you 60 qubits, and the age of the universe increases that to 95 qubits.

      I would be interested to see what Scott Aaronson thinks about this approach.

    2. Why don't you read e.g. his Democritus book then? It's pretty good and also contains quite a detailed discussiobn of the algorithms that are accessible to classical computers, to quantum computers, or verified by some of these computers or oracles etc. etc., the big difference in the complexity of these classes, and so on.

      While it's plausible that we would disagree with Aaronson about something, I am absolutely confident that he will agree with me that the effort to pretend that there's no big difference between classical and quantum computers because the latter may be "emulated" is utterly stupid.

    3. I will read it, I know the book, but I am always short of time. By the way, check this out:

    4. Wow, this is a pretty professional, likeable website - thank God, so far with no visitors - given the value of the "director's" science. It must be funded by someone, right? Who's that?

    5. Don't know. From the staff and affiliates page I know only Joy and Fred. I don't know who Jay R. Yablon or the other people are.

    6. Given that this is headed by Joy Christian maybe it is best not to read this. He has very muddled ideas about Clifford algebras and the locality of QM.


    7. Lawrence,

      "Muddled" is the polite description.