New quantum algorithms finally crack nonlinear equations(quantamagazine.org)
quantamagazine.org
New quantum algorithms finally crack nonlinear equations
https://www.quantamagazine.org/new-quantum-algorithms-finally-crack-nonlinear-equations-20210105/
34 comments
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".
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.
Yes, they even state that the "quantity R is qualitatively similar to the Reynolds number", which supports this intuition.
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
[0] https://news.ycombinator.com/item?id=24167691
This is true. My favorite such article is https://michaelberryphysics.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 Schrödinger 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.
In classical mechanics, small initial perturbations can have an ever widening effect with exponential growth in consequences without bound.
In quantum mechanics, the Schrödinger 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.
Time-dependent Schrödinger equation for the time evolution of a quantum system is a linear equation.
Essentially: d/dt Ψ = H Ψ
There is no second, or higher, powers of Ψ. 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 Schrödinger 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.
Essentially: d/dt Ψ = H Ψ
There is no second, or higher, powers of Ψ. 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 Schrödinger 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.
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.
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.
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.
Edit: removed an accusation because I misread the original comment.
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.
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.
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 Schrödinger 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.
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 Schrödinger 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.
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.)
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.)
H can depend on Ψ, which is why Bose-Einstein condensates referred in the new article are nonlinear.
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-Müller 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.
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-Müller 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.
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.
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.
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.
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.
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.
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.
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?
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?
> 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.
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.
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.
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 poincaré 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
And ... as I believe poincaré 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
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.
> 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.
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.
What is the mesmerizing image at the top of the article ?
Olena Shmahalo
https://twitter.com/natureintheory?lang=en
https://twitter.com/natureintheory?lang=en
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
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.
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.
To be fair, we're using a linear model (Schrödinger'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.
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.
The typical paradox that leads to consideration of trace class matrices is usually to consider the trace of the commutator of putatively traceless operators.
The inner space of our reality is linear.
That's an extraordinary (and unsupported, here) claim.
>"So the trick is finding a way to mathematically
convert a nonlinear system into a linear one.
“We want to have some linear system because that’s what our toolbox has in it,” Childs said. The groups did this in two different ways.
Childs’ team used
Carleman linearization
, an out-of-fashion mathematical technique from the 1930s, to transform nonlinear problems into an array of linear equations."
[...]
"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
(PDS: You mean like a WAVE ??? <g>)
,
each particle’s behavior influences the rest
(PDS: You mean like a WAVE ??? <g>)
, feeding back to that particle in a loop characteristic of nonlinearity."
[...]
>“Give me your favorite nonlinear differential equation, then I’ll build you a Bose-Einstein condensate that will simulate it,” said Tobias Osborne"
If you can get a Bose-Einstein condensate for a given nonlinear differential equation -- perhaps the reverse is true as well -- perhaps, for a given Bose-Einstein condensate, you can get back a nonlinear differential equation...
If that's true, and if it's also true that the nonlinear differential equation can be turned back into a linear differential equation (via Carleman linearization), and if so, then you can possess a linear differential equation representing your Bose-Einstein condensate, er, wave, er, fluid equation, er, linear differential equation, er, Bose-Einstein condensate... <g>
Perhaps all of these things -- are just different ways of viewing, different VIEWS -- of the same underlying physical phenomena...
To quote a famous Musician(!):
"We always didn't feel the same, we just saw it from a different point of VIEW..."
-Bob Dylan, "Tangled Up In Blue"
convert a nonlinear system into a linear one.
“We want to have some linear system because that’s what our toolbox has in it,” Childs said. The groups did this in two different ways.
Childs’ team used
Carleman linearization
, an out-of-fashion mathematical technique from the 1930s, to transform nonlinear problems into an array of linear equations."
[...]
"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
(PDS: You mean like a WAVE ??? <g>)
,
each particle’s behavior influences the rest
(PDS: You mean like a WAVE ??? <g>)
, feeding back to that particle in a loop characteristic of nonlinearity."
[...]
>“Give me your favorite nonlinear differential equation, then I’ll build you a Bose-Einstein condensate that will simulate it,” said Tobias Osborne"
If you can get a Bose-Einstein condensate for a given nonlinear differential equation -- perhaps the reverse is true as well -- perhaps, for a given Bose-Einstein condensate, you can get back a nonlinear differential equation...
If that's true, and if it's also true that the nonlinear differential equation can be turned back into a linear differential equation (via Carleman linearization), and if so, then you can possess a linear differential equation representing your Bose-Einstein condensate, er, wave, er, fluid equation, er, linear differential equation, er, Bose-Einstein condensate... <g>
Perhaps all of these things -- are just different ways of viewing, different VIEWS -- of the same underlying physical phenomena...
To quote a famous Musician(!):
"We always didn't feel the same, we just saw it from a different point of VIEW..."
-Bob Dylan, "Tangled Up In Blue"
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.