<p><strong>Updated</strong>&nbsp; For further discussion and references, see <a href="https://physics.stackexchange.com/a/35102/11637">this answer</a> to Scott Aaronson's <em>Physics.StackExchange</em> question "<a href="https://physics.stackexchange.com/q/34993/11637">Reversing gravitational decoherence</a>."</p>

<hr>

<p>As a supplement to Henry Yuen's comment, it's prudent to read the Abrams and Lloyd article <em>Nonlinear quantum mechanics implies polynomial-time solution for NP-complete and P problems</em> (1998) carefully and more than once.  First because it's a very well-written article, and second because the arguments it presents and the literature it references have subtleties that are not readily appreciated on first reading.</p>

<p>In particular, the Abrams and Lloyd analysis, and all the literature that it references, assume that the state-space of quantum mechanics is a linear vector space and the quantum dynamical equations are (possibly) nonlinear.  The converse possibility, that the state-space of quantum mechanics is nonlinear, and the quantum dynamical equations are (locally) linear, is not considered.   The latter possibility includes, as its simplest and most familiar example, the dynamical flow that is naturally associated the pullback of the symplectic structure and Hamiltonian potentials of Hilbert space onto an immersed spin-1/2 Segre variety ... in other words, the familiar Bloch equations.</p>

<p>As is well-known, Bloch dynamics exhibits precisely the linear response and arbitrarily sharp spectral lines that are cited by Abrams and Lloyd as "Experiments [that] confirm the linearity of quantum mechanics to a high degree of accuracy."  Therefore, with equal logical justification, Abrams and Lloyd might have asserted "Experiments confirm the symplecticity of Bloch dynamics to a high degree of accuracy."</p>

<p>Joseph Polchinksi's article <em>Weinberg's nonlinear quantum mechanics and the Einstein-Podolsky-Rosen Paradox</em> (1991) and Peres' article <em>Nonlinear variants of Schrodinger's equation violate the second law of thermodynamics</em> (1989) both are referenced by Abrams and Lloyd, and their articles too require careful reading.  For example, nowhere do Polchinksi or Peres mention that the Hamiltonian flow associated to the Bloch equation is Hamiltonian, and thus respects the symplectic measure associated to the second law.</p>

<p>Of the two Weinberg articles that all of the preceding authors reference, the later (longer) Weinberg article <em>Testing quantum mechanics</em> (1989) is really outstanding.  Weinberg's analysis can be read as a physics-oriented prequel to Ashtekar and Schilling's subsequent <em>Geometrical formulation of quantum mechanics</em> (1999), which expresses many of the same ideas as Weinberg's article, in a coordinate-free and structure-oriented mathematical idiom.</p>

<p>The bottom line (as I understand it) is that if we <em>assume</em> that the state-space of quantum mechanics is a large-dimension Hilbert space, upon which the projection postulate and the superposition principle hold, then both theoretical considerations and experimental measurements strongly affirm that that quantum dynamics is governed by Hamiltonian potentials that are bilinear in the quantum coordinate functions $\{\psi_i\}$ and $\{\bar\psi_i\}$, for all the experimental and theoretical reasons that the articles by Abrams and Lloyd, Polchinksi, Peres, and especially Weinberg (etc.) survey and summarize so nicely.  </p>

<p>On the other hand, if we drop the assumption of linear state-space geometry, yet are careful to respect symplecticity and local linearity (as is mathematically natural in the Ashtekar and Schilling geometric formulation of quantum mechanics) then the previous reasoning of Weinberg, Peres, Polchinksi, Abrams &amp; Lloyd (etc.) ceases to apply, and we see that the question of the "linearity of quantum mechanics" largely begs the question, what does "linearity of quantum mechanics" physically mean, when the geometry of the quantum dynamical state-space has no global vector structure?</p>

<p>For example, does this mean that the curvature of quantum dynamical state-space (or some other geometric property of it) might someday be experimentally measured, much as we we measure the curvature of Riemannian space?  That is a fine question, to which, most definitely, I do <em>not</em> know the answer.</p>

CC BY-SA 3.0
2011-08-02T17:46:29.323Z
2012-09-10T22:29:35.950Z
2017-04-13T12:40:17.207Z
John Sidles
<p>As the accepted answer implies, Quantum Mechanics is a linear theory. That means that unless there is a deeper theory that supersedes it (just as it &amp; Einstein's General Relativity jointly replaced Newtonian Mechanics), then you cannot have non-linear evolution of quantum systems.</p>

<p>BUT, there is a mighty big catch there: There almost certainly IS a deeper theory that supersedes it, a theory of "quantum gravity". Quantum physics has no model for gravity, and every attempt to add one has caused the whole thing to fall apart. Our best theory for that force, General Relativity, IS nonlinear and is has survived just as much experimental scrutiny as quantum physics.</p>

<p>The upshot is this: For a machine powered purely by known quantum physics, you won't be able to solve NP-complete problems in polynomial time. But that is a far weaker statement than asserting that the laws of physics definitely PRECLUDE solving NP-complete problems efficiently. Start running that quantum computer in a high gravity field and WE DON'T KNOW what will happen. And given that there are plenty of examples in mathematics of conjectures thought to be true for CENTURIES that were later dis-proven, failing to have found any polynomial-time algorithm for solving NP-complete problems (or nonlinear quantum operators) after less than 80 years of searching is more "par for the course" than "hard evidence none exists". </p>

CC BY-SA 3.0
2015-09-09T01:14:46.890Z
2015-09-09T01:14:46.890Z
Zack Yezek
<p>Short answer: if you believe quantum mechanics is an accurate description of nature, then since QM is a linear theory, it isn't possible to physically realize nonlinear operations.</p>

<p>As far as we know, the only nonlinear operation in quantum mechanics is that of measurement, but it's of a very restricted kind: measurement only happens at the end of your computation, and it doesn't allow you to amplify exponentially small amplitudes into non-trivial ones (except with negligible probability).</p>

<p>On the other hand, the kinds of nonlinearities discussed by the Abrams and Lloyd paper (as well as others) are generally those that allow you to take a quantum state with exponentially small amplitude, and amplify it to something nontrivial. We don't believe that it is possible to physically realize these nonlinear operations. Why? If it were possible, then you would be able to solve <strong>#P</strong> problems efficiently! From a complexity point of view, this consequence effectively chucks out the assumption. Being able to solve <strong>NP</strong>-complete problems efficiently is laughable; to handle <strong>#P</strong> with ease is a bad joke taken a little too far. The Abrams and Lloyd paper can be understood as an argument <em>against</em> the possibility of nonlinear quantum mechanics.</p>

<p>To try to answer the last part of your question: if there existed nonlinear quantum gates like described in the Abrams and Lloyd paper, then <strong>PostBQP</strong> could certainly be simulated by their nonlinear quantum computer (because <strong>PostBQP = PP</strong> by a result of Aaronson, and their nonlinear quantum computer can solve <strong>#P</strong>-complete problems efficiently).</p>

CC BY-SA 3.0
2011-07-30T22:33:29.347Z
Note also that if you describe quantum computation using CPTP maps on density operators, both unitary evolution and projective measurement are linear transformations, whereas e.g. postselection is not.
Niel de Beaudrap
CC BY-SA 3.0
2011-08-02T18:14:02.543Z
In answering this question, it's helpful to separate the (postulated) geometry of quantum state-space from the (postulated) dynamical flow on that state-space.  In undergraduate textbooks the geometry is postulated to be Hilbert (not Kahler) and the flow is postulated to be Hamiltonian (not some arbitrary vector field).   The quickest way to create computational extravagance, causal paradoxes, and thermodynamic violations is to drop the Hamiltonian postulate ... dropping the Hilbert postulate is comparatively benign.
John Sidles
CC BY-SA 3.0
2011-08-02T19:06:08.500Z
@Neil: Post-selection isn't defined for all states, so I'm not sure how it should be classified.
Joe Fitzsimons
CC BY-SA 3.0
2011-08-03T18:13:12.203Z
@Joe: It can be classified at least as a partial map (whereas linear transformations are total); and it isn't even linear where defined. So I think one can definitively say that postselection isn't a linear transformation on density operators.
Niel de Beaudrap
CC BY-SA 3.0
2011-08-03T22:44:05.870Z
@Neil: Surely if you disregard normalization, post-selection *is* a linear operator. It maps $\mid 1 \rangle \to \mid 1 \rangle$ and $\mid 0 \rangle \to 0$.
Joe Fitzsimons
CC BY-SA 3.0
2011-08-04T12:32:08.300Z
@Joe and Niel suppose that Alice operates a noisy quantum computer, with noise unravelled as a "jump" process (e.g., per Sec. 8.2 of Nielsen and Chuang).  Subsequently Alice post-selects quantum trajectories conditioned upon certain noise-jumps *not* having occurred.  So far, so good.  Now let Bob operate the *same* quantum computer, unravelling the noise as a continuous stochastic process.  How can Bob post-select his trajectories to obtain Alice's result?  The point is (AFAICT) post-selection breaks unravelling invariance, and in this sense is informatically unnatural.
John Sidles
CC BY-SA 3.0
2011-08-04T13:51:28.237Z
@Joe: if you disregard normalization, it doesn't make any sense to talk about linearity. Also: postselection (of the outcome 1 on a given qubit $j$) acting on density operators would be described by something like $\rho \mapsto \langle 1 |_j \rho | 1 \rangle_j / \mathrm{Tr}(|1\rangle\!\langle 1|_j \rho)$: performing this on a state where $j$ is in the state $|0\rangle\langle 0|$ gives division by zero.
Niel de Beaudrap
CC BY-SA 3.0
2011-08-04T14:19:55.500Z
@Neil: It still does make sense to talk about linearity. For example, post selection does not let you distinguish a mixed state of $\mid 0 \rangle$ and $\mid 1 \rangle$, from a mixed state of $\mid + \rangle$ and $\mid - \rangle$.
Joe Fitzsimons
CC BY-SA 3.0
2011-08-04T14:47:58.437Z
@Joe: linearity requires in particular that $f(tA) = t f(A)$, for scalars $t$. If you neglect real scalar factors, how do you begin to express this? What you described above is not postselection, but a single projection (as opposed e.g. to a projective measurement, which has more than just the one Kraus operator). This is linear, but does not conserve probability, and is therefore quite reasonably unphysical a priori (never mind the fact that it is not observed to be feasible in practice).
Niel de Beaudrap
CC BY-SA 3.0
2011-08-04T16:12:15.403Z
@Niel: You can simply use the relative amplitudes to define the probability rather than the normalising them. This approach is very useful for talking about non-unitary operators, since all quantum mechanical operators are linear in this sense. Indeed, this is the sense that is generally used when talking about the linearity in relationship to quantum mechanics.
Joe Fitzsimons
CC BY-SA 3.0
2011-08-04T16:20:48.597Z
@Joe: Talking about the "relative amplitudes" merely hides the normalization step, it doesn't really avoid it. (What are the relative amplitudes of the zero vector?)
Niel de Beaudrap
CC BY-SA 3.0
2011-08-04T16:32:06.947Z
@Neil: it is zero. However, it's pretty clear that this isn't going anywhere. I'm sticking to my guns though: I do not accept that post-selection is non-linear in the usual sense in which this term is applied to quantum mechanics.
Joe Fitzsimons
CC BY-SA 3.0
2011-08-04T16:37:10.517Z
@Joe: for *which result* is the relative amplitude zero, for the zero vector? I would be happier if you could show me a formula to compute the probability for subnormalized operators, and convince me that it was linear; but suit yourself.
Niel de Beaudrap
CC BY-SA 3.0
2011-08-04T16:57:40.530Z
@NieldeBeaudrap let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/995/discussion-between-joe-fitzsimons-and-niel-de-beaudrap)
Joe Fitzsimons
CC BY-SA 3.0
2011-07-30T03:55:14.993Z
2011-07-30T07:17:50.303Z
2011-07-30T07:17:50.303Z
Henry Yuen
<p>I have read in a paper where nonlinear operators for quantum computers implies the solving of problems in #P time. See <a href="http://arxiv.org/pdf/quant-ph/9801041" rel="noreferrer">http://arxiv.org/pdf/quant-ph/9801041</a> .
What would be the simplest realization of this? Could you limit its power to solve easy problems in #P Also is this equiavlent to $PostBQP$ or any other complexity class?</p>

CC BY-SA 3.0
2011-08-03T13:37:27.870Z
Joshua, may I commend Joseph Joseph Polchinksi's article (which Abrams and Lloyd reference) titled *Weinberg's nonlinear quantum mechanics and the Einstein-Podolsky-Rosen Paradox* (1991), whose point is that non-Hamiltonian dynamical equations on Hilbert space generically lead to computational extravagance, causal paradoxes, and thermodynamic violations.  The converse modification, namely Hamiltonian dynamics on non-Hilbert spaces, leads to trendy TCS topics like compressive sampling and efficient matrix multiplication. Thus both quantum modifications point to good TCS research topics.
John Sidles
<cc.complexity-theory><quantum-computing><physics>
Physical realization of nonlinear operators for quantum computers.
Joshua Herman
# Physical realization of nonlinear operators for quantum computers.

(Asked by: username_0 on 2011-07-30)

I have read in a paper where nonlinear operators for quantum computers implies the solving of problems in #P time. See <http://arxiv.org/pdf/quant-ph/9801041> .
What would be the simplest realization of this? Could you limit its power to solve easy problems in #P Also is this equiavlent to $PostBQP$ or any other complexity class?

**Tags:** cc.complexity-theory, quantum-computing, physics
> **Comments:**
> **username_1**: Joshua, may I commend Joseph Joseph Polchinksi's article (which Abrams and Lloyd reference) titled *Weinberg's nonlinear quantum mechanics and the Einstein-Podolsky-Rosen Paradox* (1991), whose point is that non-Hamiltonian dynamical equations on Hilbert space generically lead to computational extravagance, causal paradoxes, and thermodynamic violations.  The converse modification, namely Hamiltonian dynamics on non-Hilbert spaces, leads to trendy TCS topics like compressive sampling and efficient matrix multiplication. Thus both quantum modifications point to good TCS research topics.  

---

## 3 answers

### Answer by username_3 on 2011-07-30. Score: 18 | Accepted answer

Short answer: if you believe quantum mechanics is an accurate description of nature, then since QM is a linear theory, it isn't possible to physically realize nonlinear operations.

As far as we know, the only nonlinear operation in quantum mechanics is that of measurement, but it's of a very restricted kind: measurement only happens at the end of your computation, and it doesn't allow you to amplify exponentially small amplitudes into non-trivial ones (except with negligible probability).

On the other hand, the kinds of nonlinearities discussed by the Abrams and Lloyd paper (as well as others) are generally those that allow you to take a quantum state with exponentially small amplitude, and amplify it to something nontrivial. We don't believe that it is possible to physically realize these nonlinear operations. Why? If it were possible, then you would be able to solve **#P** problems efficiently! From a complexity point of view, this consequence effectively chucks out the assumption. Being able to solve **NP**-complete problems efficiently is laughable; to handle **#P** with ease is a bad joke taken a little too far. The Abrams and Lloyd paper can be understood as an argument *against* the possibility of nonlinear quantum mechanics.

To try to answer the last part of your question: if there existed nonlinear quantum gates like described in the Abrams and Lloyd paper, then **PostBQP** could certainly be simulated by their nonlinear quantum computer (because **PostBQP = PP** by a result of Aaronson, and their nonlinear quantum computer can solve **#P**-complete problems efficiently).

> **Comments:**
> **username_4**: Note also that if you describe quantum computation using CPTP maps on density operators, both unitary evolution and projective measurement are linear transformations, whereas e.g. postselection is not.  
> **username_1**: In answering this question, it's helpful to separate the (postulated) geometry of quantum state-space from the (postulated) dynamical flow on that state-space.  In undergraduate textbooks the geometry is postulated to be Hilbert (not Kahler) and the flow is postulated to be Hamiltonian (not some arbitrary vector field).   The quickest way to create computational extravagance, causal paradoxes, and thermodynamic violations is to drop the Hamiltonian postulate ... dropping the Hilbert postulate is comparatively benign.  
> **username_5**: @Neil: Post-selection isn't defined for all states, so I'm not sure how it should be classified.  
> **username_4**: @Joe: It can be classified at least as a partial map (whereas linear transformations are total); and it isn't even linear where defined. So I think one can definitively say that postselection isn't a linear transformation on density operators.  
> **username_5**: @Neil: Surely if you disregard normalization, post-selection *is* a linear operator. It maps $\mid 1 \rangle \to \mid 1 \rangle$ and $\mid 0 \rangle \to 0$.  
> **username_1**: @Joe and Niel suppose that Alice operates a noisy quantum computer, with noise unravelled as a "jump" process (e.g., per Sec. 8.2 of Nielsen and Chuang).  Subsequently Alice post-selects quantum trajectories conditioned upon certain noise-jumps *not* having occurred.  So far, so good.  Now let Bob operate the *same* quantum computer, unravelling the noise as a continuous stochastic process.  How can Bob post-select his trajectories to obtain Alice's result?  The point is (AFAICT) post-selection breaks unravelling invariance, and in this sense is informatically unnatural.  
> **username_4**: @Joe: if you disregard normalization, it doesn't make any sense to talk about linearity. Also: postselection (of the outcome 1 on a given qubit $j$) acting on density operators would be described by something like $\rho \mapsto \langle 1 |_j \rho | 1 \rangle_j / \mathrm{Tr}(|1\rangle\!\langle 1|_j \rho)$: performing this on a state where $j$ is in the state $|0\rangle\langle 0|$ gives division by zero.  
> **username_5**: @Neil: It still does make sense to talk about linearity. For example, post selection does not let you distinguish a mixed state of $\mid 0 \rangle$ and $\mid 1 \rangle$, from a mixed state of $\mid + \rangle$ and $\mid - \rangle$.  
> **username_4**: @Joe: linearity requires in particular that $f(tA) = t f(A)$, for scalars $t$. If you neglect real scalar factors, how do you begin to express this? What you described above is not postselection, but a single projection (as opposed e.g. to a projective measurement, which has more than just the one Kraus operator). This is linear, but does not conserve probability, and is therefore quite reasonably unphysical a priori (never mind the fact that it is not observed to be feasible in practice).  
> **username_5**: @Niel: You can simply use the relative amplitudes to define the probability rather than the normalising them. This approach is very useful for talking about non-unitary operators, since all quantum mechanical operators are linear in this sense. Indeed, this is the sense that is generally used when talking about the linearity in relationship to quantum mechanics.  
> **username_4**: @Joe: Talking about the "relative amplitudes" merely hides the normalization step, it doesn't really avoid it. (What are the relative amplitudes of the zero vector?)  
> **username_5**: @Neil: it is zero. However, it's pretty clear that this isn't going anywhere. I'm sticking to my guns though: I do not accept that post-selection is non-linear in the usual sense in which this term is applied to quantum mechanics.  
> **username_4**: @Joe: for *which result* is the relative amplitude zero, for the zero vector? I would be happier if you could show me a formula to compute the probability for subnormalized operators, and convince me that it was linear; but suit yourself.  
> **username_5**: @NieldeBeaudrap let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/995/discussion-between-joe-fitzsimons-and-niel-de-beaudrap)  

---

### Answer by username_1 on 2011-08-02. Score: 7

**Updated**  For further discussion and references, see [this answer](https://physics.stackexchange.com/a/35102/11637) to Scott Aaronson's *Physics.StackExchange* question "[Reversing gravitational decoherence](https://physics.stackexchange.com/q/34993/11637)."

---

As a supplement to Henry Yuen's comment, it's prudent to read the Abrams and Lloyd article *Nonlinear quantum mechanics implies polynomial-time solution for NP-complete and P problems* (1998) carefully and more than once. First because it's a very well-written article, and second because the arguments it presents and the literature it references have subtleties that are not readily appreciated on first reading.

In particular, the Abrams and Lloyd analysis, and all the literature that it references, assume that the state-space of quantum mechanics is a linear vector space and the quantum dynamical equations are (possibly) nonlinear. The converse possibility, that the state-space of quantum mechanics is nonlinear, and the quantum dynamical equations are (locally) linear, is not considered. The latter possibility includes, as its simplest and most familiar example, the dynamical flow that is naturally associated the pullback of the symplectic structure and Hamiltonian potentials of Hilbert space onto an immersed spin-1/2 Segre variety ... in other words, the familiar Bloch equations.

As is well-known, Bloch dynamics exhibits precisely the linear response and arbitrarily sharp spectral lines that are cited by Abrams and Lloyd as "Experiments [that] confirm the linearity of quantum mechanics to a high degree of accuracy." Therefore, with equal logical justification, Abrams and Lloyd might have asserted "Experiments confirm the symplecticity of Bloch dynamics to a high degree of accuracy."

Joseph Polchinksi's article *Weinberg's nonlinear quantum mechanics and the Einstein-Podolsky-Rosen Paradox* (1991) and Peres' article *Nonlinear variants of Schrodinger's equation violate the second law of thermodynamics* (1989) both are referenced by Abrams and Lloyd, and their articles too require careful reading. For example, nowhere do Polchinksi or Peres mention that the Hamiltonian flow associated to the Bloch equation is Hamiltonian, and thus respects the symplectic measure associated to the second law.

Of the two Weinberg articles that all of the preceding authors reference, the later (longer) Weinberg article *Testing quantum mechanics* (1989) is really outstanding. Weinberg's analysis can be read as a physics-oriented prequel to Ashtekar and Schilling's subsequent *Geometrical formulation of quantum mechanics* (1999), which expresses many of the same ideas as Weinberg's article, in a coordinate-free and structure-oriented mathematical idiom.

The bottom line (as I understand it) is that if we *assume* that the state-space of quantum mechanics is a large-dimension Hilbert space, upon which the projection postulate and the superposition principle hold, then both theoretical considerations and experimental measurements strongly affirm that that quantum dynamics is governed by Hamiltonian potentials that are bilinear in the quantum coordinate functions $\{\psi\_i\}$ and $\{\bar\psi\_i\}$, for all the experimental and theoretical reasons that the articles by Abrams and Lloyd, Polchinksi, Peres, and especially Weinberg (etc.) survey and summarize so nicely.

On the other hand, if we drop the assumption of linear state-space geometry, yet are careful to respect symplecticity and local linearity (as is mathematically natural in the Ashtekar and Schilling geometric formulation of quantum mechanics) then the previous reasoning of Weinberg, Peres, Polchinksi, Abrams & Lloyd (etc.) ceases to apply, and we see that the question of the "linearity of quantum mechanics" largely begs the question, what does "linearity of quantum mechanics" physically mean, when the geometry of the quantum dynamical state-space has no global vector structure?

For example, does this mean that the curvature of quantum dynamical state-space (or some other geometric property of it) might someday be experimentally measured, much as we we measure the curvature of Riemannian space? That is a fine question, to which, most definitely, I do *not* know the answer.


---

### Answer by username_2 on 2015-09-09. Score: -1

As the accepted answer implies, Quantum Mechanics is a linear theory. That means that unless there is a deeper theory that supersedes it (just as it & Einstein's General Relativity jointly replaced Newtonian Mechanics), then you cannot have non-linear evolution of quantum systems.

BUT, there is a mighty big catch there: There almost certainly IS a deeper theory that supersedes it, a theory of "quantum gravity". Quantum physics has no model for gravity, and every attempt to add one has caused the whole thing to fall apart. Our best theory for that force, General Relativity, IS nonlinear and is has survived just as much experimental scrutiny as quantum physics.

The upshot is this: For a machine powered purely by known quantum physics, you won't be able to solve NP-complete problems in polynomial time. But that is a far weaker statement than asserting that the laws of physics definitely PRECLUDE solving NP-complete problems efficiently. Start running that quantum computer in a high gravity field and WE DON'T KNOW what will happen. And given that there are plenty of examples in mathematics of conjectures thought to be true for CENTURIES that were later dis-proven, failing to have found any polynomial-time algorithm for solving NP-complete problems (or nonlinear quantum operators) after less than 80 years of searching is more "par for the course" than "hard evidence none exists".


---

