Scott Aaronson wrote a 2005 paper pdf:
NP-complete Problems and Physical RealityIn particular, he cited the Abrams-Lloyd work on quantum-mechanical nonlinearities.Can NP-complete problems be solved efficiently in the physical universe? I survey proposals including soap bubbles, protein folding, quantum computing, quantum advice, quantum adiabatic algorithms, quantum-mechanical nonlinearities, hidden variables, relativistic time dilation, analog computing, Malament-Hogarth spacetimes, quantum gravity, closed timelike curves, and "anthropic computing." The section on soap bubbles even includes some "experimental" results. While I do not believe that any of the proposals will let us solve NP-complete problems efficiently, I argue that by studying them, we can learn something not only about computation but also about physics.
Quantum mechanics is linear, and quantum computer designs depend crucially on this linearity holding to far greater precision than has ever been measured. How reasonable is that?
In the natural world, all phenomena are nonlinear, with successful models being approximately linear. I cannot think of any exceptions. Just quantum mechanics.
If quantum computers are possible, and if quantum mechanics is a linear approximation to a deeper theory, then it destroys most of what we think we know about complexity theory. We could solve NP-complete problems efficiently, and Aaronson and almost everyone else firmly believes that is impossible.
Logic says that if the conclusion is false, then at least one of the premises must be false. My guess is that most physicists will say that QM is exactly linear, and most complexity theorists will say that NP-completely problems are impossibly hard. Maybe so, but I see this as a reason to see quantum computers as impossible.
I do not think that we should accept perfect linearity in QM. Nothing else is perfectly linear.
Update: See also Why I Left Quantum Computing Research, for arguments that quantum computers will not help chemistry much.
If we think of QFT as a probabilistic data analysis and signal analysis formalism, then I think we have to ask why applied modulations always result in nonlinear measurement responses.
ReplyDeleteIf we analyze that carefully, we notice that real-space renormalization and the renormalization group are both nonlinear processes. I present that analysis in the second part of a recent talk in Yale Physics, "A Dataset&Signal Analysis Unification of Classical&Quantum Physics", https://youtu.be/t25Htj3TK1o (PDF of the slides: https://www.dropbox.com/scl/fi/ubouk5ee24wnqwjghhcce/Yale2025AsGivenV.pdf?rlkey=0rp9sow1bmgpdn96zndhqxdvq&dl=0 )
One response to that is to modify the Wightman axioms, and I have a few more things to say towards the end of that talk.
The below comments follow the same sequence as of your post, even if, for the most part, I don't specifically cite the passages in question.
ReplyDelete1. Yes, QM *is* nonlinear, but not in the direction in which Weinberg's imagination went.
2. Yes, the MSQM *is* an approximation to the deeper iqWaves theory.
3. The QC might become slightly less probable to achieve when you factor in the correct nonlinearity. But it isn't expected to be a show-stopper.
4. About the Abrams-Lloyd idea:
4.1. The part of the maths that deals with the strength of the interactions is (now) the same in the iqWaves theory as it was in the Hartree theory. (Even otherwise, except for a small correction, it was more or less the same as the Hatree theory, as explicitly indicated in the first iqWaves paper itself.) The Hartree theory (modified by Fock et al.) has predicted correct results. The entire field of computational chemistry began with it (and even today makes use of it --- at least conceptually).
4.2. Abrams and Lloyd rest their imaginations and results on the supposition that a Weinberg type of nonlinearity holds in QM.
4.3. It would be easy to show that the Weinberg kind of a nonlinearity would contradict the Hartree (or iqWaves) kind of theory. [No, I am not going to get in touch with them. I already know what their [real] response is going to be like.]
4.4. The preceding does not rule out a [very] slim possibility [I still need to check] that a QC-like hardware could still emulate (in hardware) the Weinberg kind of a nonlinearity. In which case, efficient solutions of NP-complete problems might still be possible. At least, theoretically. [No, I am not going to write a paper on that. I already know what the American and other Western researchers' [real] response is going to be like.]
5. Comments on your text:
> ``My guess is that most physicists will say that QM is exactly linear, and most complexity theorists will say that NP-completely problems are impossibly hard.''
Above, I pointed out that the first part is nonphysical. As to the second part, it does seem to be uncalled for.
> ``Maybe so, but I see this as a reason to see quantum computers as impossible.''
No, that's not the reason scalable QCs that solve real problems (for instance, the factoring problem) are going to be impossible. One clue for the sheer hardness of the task is already supplied as soon as you say: nonlinearity. (Recall: Dynamical systems theory, SDIC, regimes, deterministic chaos, etc.) Why, they themselves acknowledge so, by quoting ``decoherence.'' They must do that; otherwise, they can't explain why they repeatedly failed to achieve their next promised major milestone for so many years (20+).
> ``I do not think that we should accept perfect linearity in QM. Nothing else is perfectly linear.''
Show me a single paper published in Science, PRL, or Nature, which says so --- equally confidently. Or, a quote by any member of their editorial boards --- past or present (or a potential future member, for the predictable future).
6. Looks like you're a sort of a guy who still might feel proud about the 4th of July (which you people call July the Fourth), and still allows comments by me. In view of both, happy the 4th of July!
--Ajit
I suspect that the whole "quantum computers cannot solve NP-complete problems" is a politically enforced narrative (for whatever reason). There is no computational justufication for it, that is if you accept the fiction that is quantum computing. We are told QC can solve the NP-indeterminate problem of integer factorization (as well as other hidden subgroup problems) by no other mechanism than handwaiving away an exponential number of operations through the magic of quantum phenomenon in the QC. Well, there's no real reason to limit that magic woo to just an NP-indeterminate problem. Why not similarly perform an exponential reduction on NP-complete problems too?
ReplyDelete