3 ms·

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 p

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

by balsam 12y ago

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.