This is great! I think quantum computers are inevitable at some point as soon as we figure out how to effectively isolate them from their environment (to prevent decoherence).
In this case, the theory is way ahead of the practice, and it would seem wise to go ahead and begin offering CS courses now in quantum programming and quantum algorithms so by the time these computers are built, we're all ready to hit the ground running. Websites like this one Google has made are a good start.
Quantum computing will revolution a lot of fields. In my field (molecular dynamics and quantum chemistry), there's an issue known as the fermion sign problem, which essentially puts a hard limit on what we can accomplish through classical simulation. It basically says that the most accurate methods of performing quantum simulation scale with 2^(3N) number of particles. There is no classical computer that can handle this for any molecular system of interest, and there will never be one either. However, a quantum computer can solve this problem in non-exponential time (can't remember the exact complexity off-hand). What does this mean? Quantum simulation will lead to huge advances in materials science. Maybe we could even find a room-temperature superconductor with this kind of approach.
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.
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.
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.
Maybe you mean subexponential time? Which is not much of an improvement. This is a question which I would like someone like Scott Aaronson to answer. The sign problem is NP-hard[1].
So it's not currently believed that quantum computers can actually help with the sign problem [2]. On the other hand, we have papers that seem to say they could [3].
"today it seems extremely unlikely that quantum computers
can solve NP-complete problems in polynomial time" -- Scott Aaronson
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.
"In this case, the theory is way ahead of the practice, and it would seem wise to go ahead and begin offering CS courses now in quantum programming and quantum algorithms so by the time these computers are built, we're all ready to hit the ground running."
Aren't you a little bit too excited about quantum computing. I'm quite sure that when it becomes practical we'll be able to catch up quickly in terms of programming it.
Doing a CS course in a programming model that has zero application today is not different in terms of sanity that teaching a programming model that stopped being useful years ago.
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.)
Exactly - when I did a CS degree in the 1980s we did a fair amount of functional programming (from Lambda Calculus and combinators up to "real" programming) which had almost no real world application at the time (I did apply to a specialized CPU manufacturer who wanted people who knew about functional programming, but they changed their mind about that approach while sitting on my application form).
NB The hardware manufacturer in question was Linn Products - the high end audio/AV manufacturer who had a notion to turn their eccentric hand to CPU design in the shape of the Recursiv:
Though I don't think the point of academia vs. vocational training is to teach things that are used in future vs. things that are currently applicable. Isn't it more of learn to think analytically and to become better suited to grasp new things that might need theoretical understanding, and apply those in new contexts. But it's rational to emphasize real world solutions, or fundamental paradigms.
This is a naive question, but how can we simulate a quantum computer on a classical computer? Isn't the whole point of developing quantum computers that they enable computations that are totally outside the capabilities of a classical computer? I'm sure I'm missing something simple here.
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.
I see the value: you get to debug real, working algorithms based on a quantum computer so that once they're available, you already know many of the fundamentals and pitfalls of programming it.
I was thinking myself about the problem of 'slowdown' of this type of approach -- I think it would be interesting if the simulated quantum computer could also give you performance metrics that say, 'If this were run on a real quantum computer, it could have been done in 100 cycles as opposed to 2000.'
So you could make an algorithm in normal computing, and one on a simulated quantum computer, and compare the running time of the normal computation with the projected running time of the simulated quantum algorithm (obviously the actual running time of the simulation would be incomparable to the projected running time). I think that would be quite useful.
Quantum computers aren't magic. Their computing primitives - qubits - just have some special properties that can be used to make algorithms that are much faster than classical computers for certain problems. A qubit is basically a bit with a certain probability that it will "reduce" to 0 or 1 when read. While this is non-deterministic, it can easily be modelled, with a slowdown.
Here is a talk which may explain it better https://www.youtube.com/watch?v=8bLXHvH9s1A (The stuff about qubits and quantum computers starts at 30 minutes, but you may find the lead-up interesting/informative).
Google also released a video[1] describing their joint investment in a D-Wave "quantum computer" (given the debates I've left it in quotes) with NASA. It talks about some cool potential applications and attempts to break down the very basics.
What I'm wondering is if the investments into quantum computing by Google is merely them sinking left over R&D cash or if they believe that powerful quantum computers can be achieved relatively soon?
Unfortunately, the examples in the documentation aren't as well known as Shor's or Grover's algorithm. For Shor's, I think this is due to the difficulty of encoding the modular exponentiation within the framework.
It's not the new 60s, because we already have existing computers to back us up in terms of automation, simulation and so on of whatever is to come. Case in point, the article.
It'll be the "60s" maybe for a few months, at the most.
Development is accelerating, and it'll never slow down.
Apology for the naive question, am I supposed to be able to see the difference between a quantum computer and a standard computer from the simulator?
I ran some basic examples, and while it seems a neat scripting language to play with the computer, I couldn't see anything unusual.
My vague knowledge about quantum computers is that they don't deal with binary bits (that can be only 0 or 1), but their "bits" (qubits?) can be anything from 0 to 1, which should accelerate massively some calculations.
> but their "bits" (qubits?) can be anything from 0 to 1
This is not the interesting part, because there are models of computation that allow for this, but are believed to be equivalent to classical computation. What makes quantum computing different is that 1. the basic data are unit vectors in a 2^n dimensional vector space (when you have n qubits) and 2. you don't have direct access to the qubits during a computation, and "reading" a qubit destroys all the information in any related qubits!
So imagine a classical computer program where reading a variable destroyed the content of your other variables! That's closer to the quantum model. So it's more of a semantic difference than a syntactic one.
This is a cool demo, but I'm afraid this is the wrong pedagogical approach to understanding quantum computing.
The representation of the quantum state as a bar chart is difficult to interpret and provides little intuition. The fact is, visualizing vectors in high-dimensional spaces is hard, much less vectors in high-dimensional complex spaces. Bra-ket notation is pretty much the best thing we have right now.
But more generally, "Quantum programming" will almost certainly look nothing like this. This is like programming a classical computer by describing a boolean circuit. It's an extremely useful model for researchers working with actual hardware, but there's a reason we currently program with lambda calculi, not NAND gates. Understanding how to capture the possibilities of quantum circuits in a higher-level language is an open problem. Many interesting attempts have been made at solving it, but none convincingly in my opinion.
Damian Conway's Perl Quantum::Superpositions module (http://search.cpan.org/~lembark/Quantum-Superpositions/lib/Q...) dates back to 2000 and lets you play around with datatypes that act like they are in multiple superposed states at once; Damian's presentation of the module was an entertaining journey into language hacking as well as quantum physics - well worth looking up on youtube.
Bear in mind that the resulting module is not real "Quantum Computing", but an implementation of the conventional misunderstanding of quantum computing. Damian Conway understands real QC just fine (at least well enough to know this). It's a choice he made to implement this library for fun, as is his wont [1]. However, be aware that playing with that module will do nothing whatsoever to prepare you for real quantum computing.
Perhaps also germane to the discussion is the University of Bristol's "Quantum in the Cloud" project, which similarly offers access to a simulator - but, once you've refined your project, you can then submit it to a real quantum computer:
It is a lower level than the Google project and only suitable for 3 qbits circuits, but I found it very useful for building up an intuition about the basic logic gates.
45 comments
[ 3.4 ms ] story [ 102 ms ] threadIn this case, the theory is way ahead of the practice, and it would seem wise to go ahead and begin offering CS courses now in quantum programming and quantum algorithms so by the time these computers are built, we're all ready to hit the ground running. Websites like this one Google has made are a good start.
Quantum computing will revolution a lot of fields. In my field (molecular dynamics and quantum chemistry), there's an issue known as the fermion sign problem, which essentially puts a hard limit on what we can accomplish through classical simulation. It basically says that the most accurate methods of performing quantum simulation scale with 2^(3N) number of particles. There is no classical computer that can handle this for any molecular system of interest, and there will never be one either. However, a quantum computer can solve this problem in non-exponential time (can't remember the exact complexity off-hand). What does this mean? Quantum simulation will lead to huge advances in materials science. Maybe we could even find a room-temperature superconductor with this kind of approach.
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.
"today it seems extremely unlikely that quantum computers can solve NP-complete problems in polynomial time" -- Scott Aaronson
[1] http://arxiv.org/pdf/cond-mat/0408370.pdf
[2] http://www.scottaaronson.com/papers/bqpph.pdf
[3] http://arxiv.org/abs/cond-mat/0012334
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.
Aren't you a little bit too excited about quantum computing. I'm quite sure that when it becomes practical we'll be able to catch up quickly in terms of programming it.
Doing a CS course in a programming model that has zero application today is not different in terms of sanity that teaching a programming model that stopped being useful years ago.
NB The hardware manufacturer in question was Linn Products - the high end audio/AV manufacturer who had a notion to turn their eccentric hand to CPU design in the shape of the Recursiv:
http://en.wikipedia.org/wiki/Rekursiv
Now functional programming is pretty mainstream.
I was thinking myself about the problem of 'slowdown' of this type of approach -- I think it would be interesting if the simulated quantum computer could also give you performance metrics that say, 'If this were run on a real quantum computer, it could have been done in 100 cycles as opposed to 2000.'
So you could make an algorithm in normal computing, and one on a simulated quantum computer, and compare the running time of the normal computation with the projected running time of the simulated quantum algorithm (obviously the actual running time of the simulation would be incomparable to the projected running time). I think that would be quite useful.
Here is a talk which may explain it better https://www.youtube.com/watch?v=8bLXHvH9s1A (The stuff about qubits and quantum computers starts at 30 minutes, but you may find the lead-up interesting/informative).
What I'm wondering is if the investments into quantum computing by Google is merely them sinking left over R&D cash or if they believe that powerful quantum computers can be achieved relatively soon?
1 - https://www.youtube.com/watch?v=CMdHDHEuOUE
http://www.mathstat.dal.ca/~selinger/quipper/
Unfortunately, the examples in the documentation aren't as well known as Shor's or Grover's algorithm. For Shor's, I think this is due to the difficulty of encoding the modular exponentiation within the framework.
https://github.com/qutip/qutip/
It'll be the "60s" maybe for a few months, at the most.
Development is accelerating, and it'll never slow down.
I ran some basic examples, and while it seems a neat scripting language to play with the computer, I couldn't see anything unusual.
My vague knowledge about quantum computers is that they don't deal with binary bits (that can be only 0 or 1), but their "bits" (qubits?) can be anything from 0 to 1, which should accelerate massively some calculations.
This is not the interesting part, because there are models of computation that allow for this, but are believed to be equivalent to classical computation. What makes quantum computing different is that 1. the basic data are unit vectors in a 2^n dimensional vector space (when you have n qubits) and 2. you don't have direct access to the qubits during a computation, and "reading" a qubit destroys all the information in any related qubits!
So imagine a classical computer program where reading a variable destroyed the content of your other variables! That's closer to the quantum model. So it's more of a semantic difference than a syntactic one.
The representation of the quantum state as a bar chart is difficult to interpret and provides little intuition. The fact is, visualizing vectors in high-dimensional spaces is hard, much less vectors in high-dimensional complex spaces. Bra-ket notation is pretty much the best thing we have right now.
But more generally, "Quantum programming" will almost certainly look nothing like this. This is like programming a classical computer by describing a boolean circuit. It's an extremely useful model for researchers working with actual hardware, but there's a reason we currently program with lambda calculi, not NAND gates. Understanding how to capture the possibilities of quantum circuits in a higher-level language is an open problem. Many interesting attempts have been made at solving it, but none convincingly in my opinion.
[1] http://research.microsoft.com/apps/video/default.aspx?id=194...
[1]: http://www.csse.monash.edu.au/~damian/papers/HTML/Perligata....
http://www.bristol.ac.uk/physics/research/quantum/qcloud
http://strilanc.com/quantum/2014/03/07/Building-your-own-Qua...
It is a lower level than the Google project and only suitable for 3 qbits circuits, but I found it very useful for building up an intuition about the basic logic gates.