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?
$\begingroup$
$\endgroup$
1
-
3$\begingroup$ 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. $\endgroup$– John SidlesAug 3, 2011 at 13:37
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
14
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).
answered Jul 30, 2011 at 3:55
-
8$\begingroup$ 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. $\endgroup$ Jul 30, 2011 at 22:33
-
1$\begingroup$ 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. $\endgroup$ Aug 2, 2011 at 18:14
-
1$\begingroup$ @Neil: Post-selection isn't defined for all states, so I'm not sure how it should be classified. $\endgroup$ Aug 2, 2011 at 19:06
-
1$\begingroup$ @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. $\endgroup$ Aug 3, 2011 at 18:13
-
$\begingroup$ @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$. $\endgroup$ Aug 3, 2011 at 22:44
$\begingroup$
$\endgroup$
Updated For further discussion and references, see this answer to Scott Aaronson's Physics.StackExchange question "Reversing gravitational decoherence."
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.
answered Aug 2, 2011 at 17:46
$\begingroup$
$\endgroup$
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".
