7 ms·

New quantum algorithms finally crack nonlinear equations

148 points by theastrowolfe 6y ago

ur-whale 6y 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.
- cosmiccatnap 6y ago
  No big deal, all they gotta do is solve p=np first!
- meroes 6y 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 6y 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-whale 6y 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-Body_Problem https://en.wikipedia.org/wiki/Poincar%C3%A9_and_the_Three-Bo... http://www.bourbaphy.fr/chenciner.pdf http://www.bourbaphy.fr/chenciner.pdf
- marius_k 6y 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 https://news.ycombinator.com/item?id=24167691
  - sampo 6y 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-dependent_equation 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.
    - prof-dr-ir 6y ago
      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 6y ago
      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.
- prof-dr-ir 6y 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.
  - conformist 6y ago
    Yes, they even state that the "quantity R is qualitatively similar to the Reynolds number", which supports this intuition.
- CyberRabbi 6y 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.
- tagrun 6y 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-ir 6y 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.
    - tagrun 6y ago
      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 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?
- conformist 6y 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 6y 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-whale 6y 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 6y 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 6y ago
  The inner space of our reality is linear.
  - ci5er 6y ago
    That's an extraordinary (and unsupported, here) claim.
dls2016 6y 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.
GistNoesis 6y ago
What is the mesmerizing image at the top of the article ?
- r34 6y 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.
- mankyd 6y ago
  Olena Shmahalo https://twitter.com/natureintheory?lang=en https://twitter.com/natureintheory?lang=en
  - GistNoesis 6y 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 https://natureintheory.artstation.com/albums/762329
peter_d_sherman 6y 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"

148 points by theastrowolfe 6y 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.

cosmiccatnap 6y ago
No big deal, all they gotta do is solve p=np first!
meroes 6y 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 6y 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-whale 6y 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-Body_Problem https://en.wikipedia.org/wiki/Poincar%C3%A9_and_the_Three-Bo... http://www.bourbaphy.fr/chenciner.pdf http://www.bourbaphy.fr/chenciner.pdf
marius_k 6y 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 https://news.ycombinator.com/item?id=24167691
- sampo 6y 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-dependent_equation 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.
  - prof-dr-ir 6y ago
    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 6y ago
    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.
prof-dr-ir 6y 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.
- conformist 6y ago
  Yes, they even state that the "quantity R is qualitatively similar to the Reynolds number", which supports this intuition.
CyberRabbi 6y 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.
tagrun 6y 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-ir 6y 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.
  - tagrun 6y ago
    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 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?
conformist 6y 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 6y 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-whale 6y 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 6y 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 6y ago
The inner space of our reality is linear.
- ci5er 6y ago
  That's an extraordinary (and unsupported, here) claim.

dls2016 6y 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.

GistNoesis 6y ago

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

r34 6y 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.
mankyd 6y ago
Olena Shmahalo https://twitter.com/natureintheory?lang=en https://twitter.com/natureintheory?lang=en
- GistNoesis 6y 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 https://natureintheory.artstation.com/albums/762329

peter_d_sherman 6y 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"