6 ms·

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 initia

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

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