<p>If quantum computers can simulate in polynomial time the Standard Model, which is a quite complicated quantum field theory, then probably the Standard Model does not provide any extra computational power beyond BQP. Simulating quantum field theories with a quantum computer is not an easy task, but a start has been made by <a href="http://arxiv.org/abs/1111.3633">this paper</a> by Jordan, Lee, and Preskill, which shows how to simulate in polynomial time a much simpler quantum field theory than the Standard Model. </p>

CC BY-SA 3.0
2015-06-01T13:18:22.647Z
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?
Chris Blake
CC BY-SA 3.0
2015-06-01T13:28:20.943Z
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).
Peter Shor 
CC BY-SA 3.0
2015-06-01T13:41:57.420Z
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?
Chris Blake
CC BY-SA 3.0
2015-06-01T16:58:36.320Z
@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*.
Peter Shor 
CC BY-SA 3.0
2015-06-01T19:32:23.993Z
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?
Chris Blake
CC BY-SA 3.0
2015-06-01T19:50:56.523Z
@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.
Peter Shor 
CC BY-SA 3.0
2015-06-01T19:58:19.757Z
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?
Chris Blake
CC BY-SA 3.0
2015-06-01T12:48:43.617Z
2015-06-01T13:29:21.533Z
2015-06-01T13:29:21.533Z
Peter Shor 
<p>The Standard Model of physics (the mathematical model which predicts the Higg's boson) is, as far as I understand, our most complete model of the universe. That is to say, it is the best description of the mathematical game to be played to make predictions on the outcome of  experiments performed in our Universe.</p>

<p>As I understand it, quantum physics, used to create models of quantum computation (as used, for example, in the construction of Shor's algorithm) is a mathematical game contained within the Standard Model. Thus, in this sense the Standard Model is a generalization of quantum physics.</p>

<p>Is it at all conceivable that the Standard Model can allow for the construction of more general Standard Model computers? Or is there an obvious reason why quantum physics extracts all the benefit modern physics brings over classical models of computation and thus computer scientists should only reason according to quantum physics? Has any fundamental work been done on this? Is my question even well posed? Supposing that a Standard Model of physics computer could be a well-posed mathematical object more general than quantum computers, is there any reason at all to think that there could be any use to reasoning about that? Has there been any work done related to this question?</p>

<p>More informally, you might think of this question as something of the form "could we make a 'Higg's Boson' computer?" a rather natural justification for research in particle physics. Note that I know very little of the Standard Model (but a good deal about quantum physics) so this question might be ill posed, and if so, knowing that would be a clarification of my understanding.</p>

<cc.complexity-theory><quantum-computing><physics>
Is it conceivable at all that the standard model of physics can outperform a quantum computer in any sense?
Chris Blake
# Is it conceivable at all that the standard model of physics can outperform a quantum computer in any sense?

(Asked by: username_0 on 2015-06-01)

The Standard Model of physics (the mathematical model which predicts the Higg's boson) is, as far as I understand, our most complete model of the universe. That is to say, it is the best description of the mathematical game to be played to make predictions on the outcome of experiments performed in our Universe.

As I understand it, quantum physics, used to create models of quantum computation (as used, for example, in the construction of Shor's algorithm) is a mathematical game contained within the Standard Model. Thus, in this sense the Standard Model is a generalization of quantum physics.

Is it at all conceivable that the Standard Model can allow for the construction of more general Standard Model computers? Or is there an obvious reason why quantum physics extracts all the benefit modern physics brings over classical models of computation and thus computer scientists should only reason according to quantum physics? Has any fundamental work been done on this? Is my question even well posed? Supposing that a Standard Model of physics computer could be a well-posed mathematical object more general than quantum computers, is there any reason at all to think that there could be any use to reasoning about that? Has there been any work done related to this question?

More informally, you might think of this question as something of the form "could we make a 'Higg's Boson' computer?" a rather natural justification for research in particle physics. Note that I know very little of the Standard Model (but a good deal about quantum physics) so this question might be ill posed, and if so, knowing that would be a clarification of my understanding.

**Tags:** cc.complexity-theory, quantum-computing, physics


---

## 1 answers

### Answer by username_1 on 2015-06-01. Score: 10

If quantum computers can simulate in polynomial time the Standard Model, which is a quite complicated quantum field theory, then probably the Standard Model does not provide any extra computational power beyond BQP. Simulating quantum field theories with a quantum computer is not an easy task, but a start has been made by [this paper](http://arxiv.org/abs/1111.3633) by Jordan, Lee, and Preskill, which shows how to simulate in polynomial time a much simpler quantum field theory than the Standard Model.

> **Comments:**
> **username_0**: 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?  
> **username_1**: 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).  
> **username_0**: 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?  
> **username_1**: @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*.  
> **username_0**: 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?  
> **username_1**: @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.  
> **username_0**: 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?  

---

