Timeline for Is it conceivable at all that the standard model of physics can outperform a quantum computer in any sense?

Current License: CC BY-SA 3.0

9 events

when toggle format	what		by	license	comment
Jun 1, 2015 at 19:58	comment	added	Chris Blake		It's just an arbitrary polynomial term to demonstrate the point that two polynomial algorithms of different complexity can have hugely different speeds for sufficiently large n, even though they are both polynomials. We could extract the complexity from the linked paper if we want to be exact about what kinds of gains could be possible in a more general model. My main question still remains unanswered: is there any intuitive reason why this type of gain may not be possible for any type of actual problem compared to classical quantum computer models?
Jun 1, 2015 at 19:50	comment	added	Peter Shor		@Chris: Where did you get $O(n^{1000})$ from in your last comment? There's going to be some polynomial penalty for simulating quantum field theory, but I very much doubt it is $O(n^{1000})$. And *nothing* is proved for the Standard Model; just for much simpler quantum field theories.
Jun 1, 2015 at 19:32	comment	added	Chris Blake		In your reply, you say that "architecture B can factor slightly faster than architecture A." But surely an O(n^2) algorithm is not just "slightly faster" than an O(n^1000) one. The authors state: "Such an algorithm would establish that, except for quantum-gravity effects,the standard quantum circuit model suffices to capture completely the computational power of our universe." Is it fair to say that this statement is actually unproven, as clearly a polynomial time-savings is an unproven but at least possible computational power not considered in the standard quantum circuit model?
Jun 1, 2015 at 16:58	comment	added	Peter Shor		@Chris: all quantum computers are really physics experiments (or at least, can be viewed as ones), and so if your quantum computer has architecture A, and your physics experiment is really a quantum computer with architecture B, and architecture B can factor slightly faster than architecture A, then yes.
Jun 1, 2015 at 13:41	comment	added	Chris Blake		It seems like a more general computer can likely simulate its own physics faster than a more restricted computer, if only by a polynomial factor. Of course, as we know by Shor's algorithm, sometimes a generalization of a computer allows for the creation of a more efficient algorithm for a problem unrelated to the simulation problem. Could there conceivably be a physics experiment whose outcome, when measured, allows us, for example, to factor an integer more efficiently than a corresponding quantum algorithm, even if only by say, a loglog n factor?
Jun 1, 2015 at 13:29	history	edited	Peter Shor	CC BY-SA 3.0	added 11 characters in body
Jun 1, 2015 at 13:28	comment	added	Peter Shor		There is probably going to be a polynomial factor involved. If the problem the computer is solving is; what happens when I do this physics experiment? then the computer is going to require some overhead to simulate it, while the universe does not. But even different architectures for quantum computers require polynomial factors when simulating each other (and different architectures for classical computers require at least logarithmic factors when simulating each other).
Jun 1, 2015 at 13:18	comment	added	Chris Blake		Is your statement "probably the Standard Model does not provide any extra computational power" really implied by a quantum polynomial time algorithm to simulate the Standard Model? Certainly the distinction between "exponential time" and "polynomial time" is a significant one. That does not imply, however, that there can be no gain at all from a more general computation, it just means that the gain could at most be a polynomial factor. Is there any intuitive reason at all to assume more general computers cannot provide any such gain over a quantum computer?
Jun 1, 2015 at 12:48	history	answered	Peter Shor	CC BY-SA 3.0