Google Project Lets You Program a Simulated Quantum Computer

Funny how those links are all gray already. I didn't mention it in my first post, but there does seem to be an additional problem in finding a way to efficiently formulate QM simulations for a QM computer. I'm not sure if much work has been done on this. I would also be interested in a blog post or two by Scott Aaronson on this topic though.

I think Xcelerate meant polynomial - which is an exponential improvement. It is not known but strongly believed that quantum computers cannot solve NP-complete problems. Be wary of anything that has "quantum computer" and "exponentially more powerful" in the same sentence.

It is not yet know whether Quantum computers can simulate all physical systems - though probably better than even odds for - perhaps some exotic physics might underlie some systems (on the other hand it is not known if quantum computing is even needed at all for physical systems, though only a handful have this doubt). But QCs should be able to simulate many kinds of systems, and even before full quantum computers we might get useful systems that simulate particular classes of Hamiltonians.

I don't know enough physics to grasp all the details but simulating a system involves preparing a state, evolving the Hamiltonian and reading out the result. Preparing the Hamiltonian can be done in time polynomial of the size of the system (I don't know anything more exact) and depending on the details of the system (local, sparse) and method in use, evolution can be as fast as linear in the size of the system (and though no general method allow sublinear calculation, particular hamiltonians could well admit such a speedup). And although, in general, non-sparse systems can't be simulated in polynomial time there should be methods that allow reductions/decomposition into simpler problems.

There also other caveats: reading out the result requires a lot of sampling and error correction is a thorn. All these are why quantum computers are not some magical device - they're much too finickity, and to be preferred mainly as a last resort. They'll be pivotal for chemistry and to biochemists, pharmacology, material science and solid state physics (so better classical computers) but it seems hard to find any utility in general computer science.

--

Even if the difficulty of general QC algorithms is from the failings of human intuition, that still suggests to me that methods like inductive or genetic or automatic programming will easily outperform humans.

Let's say you want to simulate three carbon atoms with near perfect accuracy (not considering constituent quarks, radiative effects, or relativistic effects). We'll remove the BO approximation though. So that's 2^(3 atoms * 3 coordinates * 3*12 particles) = 2^324. That's more than the number of particles in the universe. A classical computer that can handle that is simply not gonna happen. And that's just three atoms.

For what it's worth, I wrote a small iOS app for a client, to convert isometric 2D line drawings to 3D, and encountered similar complexity issues:

https://itunes.apple.com/us/app/dotpaper-3d/id662561642

My naive implementation ended up being something like O(n!) in the number of lines, due to combinations/permutations. That's because I created a 3D representation as large as the dimensions of the graph that was drawn, and tried arranging the blocks in every possible combination and seeing which one matched the hand drawn lines when projected to 2D.

If each cube in that 3D space represents a bit, then even a 4x4x4 space has 2^64 (18 quintillion) possibilities. So you could draw a few overlapping blocks, but add one more and the iPhone would freeze for several minutes. Add a few more and it wouldn't finish on a human timescale!

I ended up getting around it with a hill climbing algorithm that tried toggling blocks and keeping the result that most closely matched the projection, with a certain amount of fanout up to N entries. It was basically a primitive genetic algorithm. It actually worked great even on relatively large graphs, because humans tend to draw them as a sheet where all of the blocks are next to one another on a diagonal.

It's not perfect and really falls down if a line's out of place (think M.C. Escher) but it's worth playing around with. The client is a teacher, so if you purchase the app, the money will go to a good cause.

Simulating classical systems results in slow downs that are only polynomially with respect to system size while quantum systems slow exponentially. Consider that a quantum system of n qubits would require a classical system able to cope with 2^n bits. But you might be right since there is a (remote) possibility that classical systems can efficiently simulate quantum systems. However, it is generally believed that quantum computers are more powerful than classical but not strong enough to solve NP-complete problems.

There is a big difference between courses teaching computer languages (intro CS) and courses teaching algorithms (advanced CS and mathematics). Courses dealing with quantum computation are in the second category, they teach much more than "a programming model that has zero application today", and they are already present as math, CS or physics courses.

How are we going to get to tomorrow if everybody only learns about stuff that is applicable today? (Queue rant about how a CS degree shouldn't be a vocational training course for programmers etc.)

Besides, quantum algorithms courses are offered, but like you said, I don't really see the point.

Right, so the value of the simulation is somewhat questionable. Exponential slowdown is enough to kill all intuition about what works and what doesn't. You only get some correctness gurantee and that would be for very small problems / test cases.