New quantum algorithms finally crack nonlinear equations

https://www.quantamagazine.org/new-quantum-algorithms-finally-crack-nonlinear-equations-20210105/

by theastrowolfe • 6 years ago

148 33 6 years ago

ur-whale3• 6 years ago

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• 6 years ago

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• 6 years ago

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-whale3• 6 years ago

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

marius_k• 6 years ago

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• 6 years ago

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.

btilly2• 6 years ago

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.

CyberRabbi• 6 years ago

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.

prof-dr-ir4• 6 years ago

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.

conformist2• 6 years ago

Yes, they even state that the "quantity R is qualitatively similar to the Reynolds number", which supports this intuition.

tagrun3• 6 years ago

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.

prof-dr-ir4• 6 years ago

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.

gnulinux• 6 years ago

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.

conformist2• 6 years ago

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".

fchu• 6 years ago

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-whale3• 6 years ago

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.

selimthegrim• 6 years ago

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• 6 years ago

The inner space of our reality is linear.

ci5er• 6 years ago

That's an extraordinary (and unsupported, here) claim.

dls2016• 6 years ago

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.

GistNoesis2• 6 years ago

What is the mesmerizing image at the top of the article ?

mankyd• 6 years ago

Olena Shmahalo

https://twitter.com/natureintheory?lang=en

GistNoesis2• 6 years ago

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

r34• 6 years ago

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.

peter_d_sherman• 6 years ago

"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"

New quantum algorithms finally crack nonlinear equations

Related Stories