[HN Gopher] New quantum algorithms finally crack nonlinear equat...
___________________________________________________________________
New quantum algorithms finally crack nonlinear equations
Author : theastrowolfe
Score : 97 points
Date : 2021-01-06 14:59 UTC (8 hours ago)
(HTM) web link (www.quantamagazine.org)
(TXT) w3m dump (www.quantamagazine.org)
| dls2016 wrote:
| > The new approaches disguise that nonlinearity as a more
| digestible set of linear approximations, though their exact
| methods vary considerably.
|
| The idea of reducing a nonlinear problem to a sequence of linear
| problems is the bread and butter of nonlinear PDE, both
| theoretical and numerical. The trick is always in the reduction
| and I guess here you want the reduction to have a nice "quantum"
| solution.
|
| I'm not qualified to say what either of these papers have to do
| with "chaos". You'll notice that this word only appears in one of
| the papers and then only once in the intro.
| ur-whale wrote:
| The article seem to imply that quantum computers are a solution
| to the problem that non-linear differential equations are chaotic
| (as in: tiny changes in initial conditions lead to vastly
| different solutions).
|
| My impression of quantum computers are they will allow us to get
| to solutions to algorithmic problems _faster_.
|
| I fail to see how they could possibly work around the chaos
| inherent to some diffeqs (e.g. N-body problems).
|
| [edit]:and after reading the article more carefully, I'm still
| not sure how QC has _any_ effect on the chaotic nature of non-
| linear diffeqs . All I see in here is that they 're trying to map
| non-linear diffeqs to linear systems via approximations so they
| can run it on a QC.
| meroes wrote:
| If you can map non-linear eq's to linear, i.e. Schrodinger eq,
| doesn't that dramatically reduce computation required? Non-
| linearity is necessary for chaos. This seems like a big deal to
| an layman like me. I don't know _how_ it 's done, but isn't the
| fact that nonrelativistic QM and classical mechanics are nearly
| identical at certain scales enough to say a mapping can be
| done.
| rowanG077 wrote:
| Did you read the article? It's possible to write a non-linear
| equation as an infinite set of lineair ones. They use this
| fact in one of their solutions.
| ur-whale wrote:
| The mapping is not 1-to-1, it's done via approximation, which
| means that what gets solved is not the original equation.
|
| And ... as I believe poincare found out when he tried to
| apply series expansion to the 3 body problem, the devil
| (chaotic behavior) is in the long tail of the series
| coefficients
|
| [edit]:
|
| https://en.wikipedia.org/wiki/Poincar%C3%A9_and_the_Three-
| Bo...
|
| http://www.bourbaphy.fr/chenciner.pdf
| prof-dr-ir wrote:
| I believe you are right, and that the Childs paper actually
| beautifully quantifies your suspicion: they appear to show that
| the speedup of the quantum algorithm disappears if 'R >
| sqrt(2)', which intuitively means that the problem is 'too'
| non-linear. (I would expect that truly chaotic systems fall
| into this category.) This negative result does not seem to be
| mentioned in the quanta article.
| conformist wrote:
| Yes, they even state that the "quantity R is qualitatively
| similar to the Reynolds number", which supports this
| intuition.
| marius_k wrote:
| I am not sure if this is related but during the past year I
| noticed few articles describing about how quantum systems are
| immune to butterfly effect [0]. I can't tell more details as
| those articles are still on my backlog.
|
| [0] https://news.ycombinator.com/item?id=24167691
| sampo wrote:
| Time-dependent Schrodinger equation for the time evolution of
| a quantum system is a linear equation.
|
| Essentially: d/dt Ps = H Ps
|
| There is no second, or higher, powers of Ps. There is even no
| constant term. It's linear.
|
| https://en.wikipedia.org/wiki/Schr%C3%B6dinger_equation#Time.
| ..
|
| Now, how does nonlinear macroscopic world appear, if the
| fundamental time evolution at quantum scale is linear? So
| obviously Schrodinger equation alone is not enough to
| describe the time evolution of the universe. One way is to
| introduce wavefunction collapse, which is a nonlinear
| process. But there is no physical theory (well, there are
| propositions) of how and when collapse happens. It just
| happens somehow, sometime. This problem is at the core of why
| quantum mechanics is an incomplete theory.
| btilly wrote:
| Your comment presupposes that the Everett interpretation
| cannot be true. But it offers an explanation of the
| appearance of collapse without having a collapse.
|
| Namely if a quantum mechanical observer observes a quantum
| mechanical system in a superposition of states, we get a
| superposition of quantum mechanical observers who can no
| longer meaningfully interact, each of which observed a
| different state of the quantum mechanical system. This is
| exactly what the Schrodinger equation predicts MUST happen.
|
| As a side note, this is the most popular interpretation of
| quantum mechanics among cosmologists. It turns out that if
| you're using quantum mechanics to explain things like the
| birth of galaxies, taking seriously what quantum mechanics
| says for human sized quantum mechanical systems becomes
| very easy.
| tagrun wrote:
| H can depend on Ps, which is why Bose-Einstein condensates
| referred in the new article are nonlinear.
| pontus wrote:
| While the Schrodinger equation is linear, that doesn't mean
| that the time evolution of various derived quantities are
| also linear. For example, the expectation value of position
| follows a nonlinear equation of motion even though the
| schrodinger equation is linear.
|
| This is known as Ehrenfest's theorem:
| https://en.m.wikipedia.org/wiki/Ehrenfest_theorem
|
| In other words, nonlinear time evolution is natural in
| quantum mechanics for quantities other than the wave
| function and does not require collapse.
| prof-dr-ir wrote:
| As your link shows, the time evolution of the expectation
| value of position does in fact _not_ generally obey a
| closed-form non-linear differential equation; instead one
| needs the expectation value of V '(x) which is a
| different quantity altogether. But the easiest way to
| compute that quantity is of course to solve the
| Schrodinger equation...
|
| Edit: removed an accusation because I misread the
| original comment.
| pontus wrote:
| Yes, that's right: you need <V'(x)> rather than V'(<x>).
| It's still the case that <x> does not follow a linear DE.
|
| My point was that while the SE is linear, that does not
| mean that everything derived from it is also linear. The
| original comment was asking where all the nonlinearities
| in the world could come from since the SE is linear. It
| was suggested that either QM is incomplete because it is
| linear or that we need wave function collapse to
| introduce nonlinearities. I think my counterexample shows
| that both of those suggestions are incorrect.
| Lichtso wrote:
| I am quite sure chaos can be an emergent property.
|
| E.g. think of Conways game of life: One could build a
| contraption which amplifies a very small event into a
| gigantic one (like a Geiger-Muller tube) and spawn a few
| gliders (as particles). Now, a very small change in the
| initial configuration changes the outcome drastically, even
| though all the rules of the simulation are still perfectly
| deterministic and linear.
| prof-dr-ir wrote:
| I do not think that you need to introduce wave-function
| collapse here, because there is no need for the universe to
| be fundamentally non-linear - it suffices for the Poincare
| recurrence time to be extremely large.
|
| Like phase transitions in statistical mechanics, could it
| no be that chaos is just an emergent effect that arises
| from the quantum dynamics of infinitely many particles?
| (The appearance of non-linearities in that limit happens to
| also be discussed in the MIT paper of the quanta article.)
| btilly wrote:
| This is true. My favorite such article is https://michaelberr
| yphysics.files.wordpress.com/2013/07/berr....
|
| In classical mechanics, small initial perturbations can have
| an ever widening effect with exponential growth in
| consequences without bound.
|
| In quantum mechanics, the Schrodinger equation is linear.
| There cannot be any exponential growth lasting forever -
| there is a linear bound!
|
| The field of quantum chaos is devoted to resolving this
| apparent paradox.
|
| The answer for a closed system is that the quantum mechanical
| system can approximate the classical system very well for a
| limited time. After that the quantum mechanical system will
| start repeating itself and show some decidedly non-classical
| behavior. This time is sometimes called the "quantum break
| time".
|
| The answer for an open system is that every interaction with
| the outside environment can change the state of the quantum
| mechanical system, and the appearance of chaos can then be
| maintained for unlimited times.
| conformist wrote:
| Yes, essentially that's right (regarding Child's paper), as far
| as I can tell. Child's article seems to be about a smart way to
| approximate sufficiently dissipative, non-linear, n-dimensional
| ODEs (or spatially discretised PDEs for that matter), such that
| you can apply good old forward Euler. They do that in such a
| manner that you end up solving a linear system for time-
| stepping for which a log(n) quantum algo is known. This is
| pretty cool, because they basically use standard numerical
| analysis tools and manage to plug in the quantum computing part
| to show that, e.g., as you increase the spatial "resolution"
| with which you solve a PDE, the cost only increases
| logarithmically. This feels useful from a computational fluid
| dynamics perspective, say, if you're not interested in super
| turbulent flows. So this is more about "how do we make solving
| hard PDEs faster" than "finally cracking non-linear PDEs".
| CyberRabbi wrote:
| Right, even if they have implemented an accurate solver for
| non-linear problems, that doesn't fundamentally get around the
| chaos problem for a lot of real world applications.
|
| For instance, even if you could 100% accurately model the most
| complex turbulent flow models, your predictions are still
| limited in their applicability because any small inaccuracy in
| your initial data will cause the long term results to look
| completely different from what may really happen.
| tagrun wrote:
| Physicists here. I'm having a hard time believing that you read
| it carefully, because that's the Childs preprint, which is only
| mentioned "in passing", and the true focus of this new article
| is the Palmer (MIT) preprint, which is about mapping nonlinear
| differential equations to nonlinear Bose-Einstein condensates.
| BECs are modeled by the Gross-Pitaevskii equation, which
| contains a potential term that is proportional to particle
| density (basically a potential that depends on the
| wavefunction), causing nonlinearity.
|
| From the news article:
|
| > The MIT-led paper took a different approach. It modeled any
| nonlinear problem as a Bose-Einstein condensate. This is a
| state of matter where interactions within an ultracold group of
| particles cause each individual particle to behave identically.
| Since the particles are all interconnected, each particle's
| behavior influences the rest, feeding back to that particle in
| a loop characteristic of nonlinearity.
| gnulinux wrote:
| > I'm having a hard time believing that you read it carefully
|
| Excuse me, but I find this uncalled for. Not everyone has a
| formal physics education. People who last studied physics in
| high school 10 years ago will make mistakes even if they read
| things carefully.
| prof-dr-ir wrote:
| There are two paragraphs dedicated to the Childs preprint and
| then two to the Palmer preprint. As far as I can see, the
| rest of the article consistently refers to 'both papers'. So
| I do not think it reasonable to claim that the Childs
| preprint 'is only mentioned in passing'.
|
| Second, you missed a key quote: "So by imagining a pseudo
| Bose-Einstein condensate tailor made for each nonlinear
| problem, this algorithm deduces a useful linear
| approximation." From this I conclude that the MIT paper does
| reduce the computation to a linear system after all, as OP
| suggested.
|
| Third, let me offer some unsolicited feedback on the tone of
| your comment: the phrase "I'm having a hard time believing
| that you read it carefully" came across as needlessly off-
| putting to me.
| tagrun wrote:
| I'll give you that it's a rather long passing, but title
| and the overall news article is actually about Palmer's
| work, and Childs paper is "in passing" in the sense that
| it's a relevant recent work that parallels Palmer's work
| ---I don't believe Childs preprint would be newsworthy on
| its own.
|
| Regarding the editorial "key qoute", if you read the
| preprint https://arxiv.org/pdf/2011.06571.pdf you can see
| this conflates two things: the mapping of nonlinear
| differential equations onto BECs, and the emulation of a
| BEC on a typical quantum computer (which introduces
| additional limitations). Note that the latter step isn't
| truly necessary, because one can use a BEC directly to do
| it.
|
| Third, I'm sorry about how you feel about it, but I stand
| by my dissent that this can be a coherent statement:
|
| > and after reading the article more carefully, I'm still
| not sure how QC has any effect on the chaotic nature of
| non-linear diffeqs . All I see in here is that they're
| trying to map non-linear diffeqs to linear systems via
| approximations so they can run it on a QC.
|
| which mischaracterizes Palmer's work at best. I don't
| believe anyone would be happy to have their work (be it
| physics or software development) disparaged like this,
| would you?
| cosmiccatnap wrote:
| No big deal, all they gotta do is solve p=np first!
| fchu wrote:
| I find it fascinating that we're using an overall linear model
| (Quantum Physics) of our non-linear reality, particularly the
| bits that are less linear (Bose Einstein condensates) to
| approximate linear solutions to non-linear models (flow dynamics,
| etc) of said non-linear reality.
| ur-whale wrote:
| To be fair, we're using a linear model (Schrodinger's Equation)
| but in an _infinite dimensional_ vector space and linear
| operators on these infinite dimensional vector spaces.
|
| These aren't your grandfather matrices and there are things in
| infinite dimension that are rather weird, specifically when it
| comes to eigenvalues, which QM makes extensive use of.
|
| The spectrum of an operator, for example can be a weird mix of
| discrete values, discrete sets of intervals and/or the entire
| real line.
| selimthegrim wrote:
| The typical paradox that leads to consideration of trace
| class matrices is usually to consider the trace of the
| commutator of putatively traceless operators.
| adamnemecek wrote:
| The inner space of our reality is linear.
| GistNoesis wrote:
| What is the mesmerizing image at the top of the article ?
| r34 wrote:
| I was just about to write a comment stating that Quanta (and
| Nautilus as well) have amazing art in almost every article. One
| of the best visualisations I encounter.
| mankyd wrote:
| Olena Shmahalo
|
| https://twitter.com/natureintheory?lang=en
| GistNoesis wrote:
| Following your link I found the place where, in a few days,
| the author will presumably post the description of what
| Quanta requested a depiction of :
| https://natureintheory.artstation.com/albums/762329
___________________________________________________________________
(page generated 2021-01-06 23:01 UTC)