5 ms·

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 preve

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.

deleted 12y ago
[deleted]
ballstothewalls 12y ago
How can you say that no classical computer will ever be able to handle a simulation that big? Where is the bottleneck?
- Xcelerate 12y ago
  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.
  - ScottBurson 12y ago
    Are you sure it shouldn't be 2^(3 + 3 + 3*12) = 2^42 ? That would still be a pretty big number, but not yet astronomical.
  - ballstothewalls 12y ago
    I understand that is massive, but aren't computers today doing things that seemed utterly impossible forty years ago?
- Dn_Ab 12y ago
  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.
- zackmorris 12y ago
  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 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.
balsam 12y ago
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 [1] http://arxiv.org/pdf/cond-mat/0408370.pdf http://arxiv.org/pdf/cond-mat/0408370.pdf [2] http://www.scottaaronson.com/papers/bqpph.pdf http://www.scottaaronson.com/papers/bqpph.pdf [3] http://arxiv.org/abs/cond-mat/0012334 http://arxiv.org/abs/cond-mat/0012334
- Xcelerate 12y ago
  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.
- Dn_Ab 12y ago
  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.
mantrax5 12y ago
"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.
- ibrahima 12y ago
  Besides, quantum algorithms courses are offered, but like you said, I don't really see the point.
- krastanov 12y 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.
- dagw 12y ago
  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.)
  - arethuza 12y ago
    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: http://en.wikipedia.org/wiki/Rekursiv http://en.wikipedia.org/wiki/Rekursiv Now functional programming is pretty mainstream.

deleted 12y ago

[deleted]

ballstothewalls 12y ago

How can you say that no classical computer will ever be able to handle a simulation that big? Where is the bottleneck?

Xcelerate 12y ago
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.
- ScottBurson 12y ago
  Are you sure it shouldn't be 2^(3 + 3 + 3*12) = 2^42 ? That would still be a pretty big number, but not yet astronomical.
- ballstothewalls 12y ago
  I understand that is massive, but aren't computers today doing things that seemed utterly impossible forty years ago?
Dn_Ab 12y ago
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.
zackmorris 12y ago
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 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.

balsam 12y ago

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 [1] http://arxiv.org/pdf/cond-mat/0408370.pdf http://arxiv.org/pdf/cond-mat/0408370.pdf [2] http://www.scottaaronson.com/papers/bqpph.pdf http://www.scottaaronson.com/papers/bqpph.pdf [3] http://arxiv.org/abs/cond-mat/0012334 http://arxiv.org/abs/cond-mat/0012334

Xcelerate 12y ago
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.
Dn_Ab 12y ago
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.

mantrax5 12y ago

"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.

ibrahima 12y ago
Besides, quantum algorithms courses are offered, but like you said, I don't really see the point.
krastanov 12y 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.
dagw 12y ago
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.)
- arethuza 12y ago
  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: http://en.wikipedia.org/wiki/Rekursiv http://en.wikipedia.org/wiki/Rekursiv Now functional programming is pretty mainstream.