A new quantum algorithm for classical mechanics with an exponential speedup
blog.research.google
blog.research.google
1. Every closed system has a fixed total energy, so many systems just settle into an oscillating state, where kinetic energy converts into potential and back.
2. Most real world systems are approximately closed, so they leak energy till they have low total energy (this also follows from the second law).
3. An oscillating system with low total energy can have its potential energy accurately approximated with a quadratic function. Or in other words a harmonic oscillator.
So, while I can't say if there are many interesting/useful coupled classical oscillator systems that need an exponential speedup for us to study, it is nevertheless exciting to hear that such systems do admit a quantum speedup.
[edit] this reminds me of something I read about how NASA doesn't predict solar eclipses by trying to keep an exact model of the solar system, but rather uses pattern matching algorithms.
We struggle to predict the exact path of asteroids because of measurement errors, not because computing is slow. Minuscule changes to the initial condition manifest as massive differences in the outcome.
>> In summary, it is clear ancient people could predict timings for lunar eclipses and partial solar eclipses, but there is no convincing evidence of people predicting the times and locations of total solar eclipses.
>> Today, we don’t rely on calculating the orbits of the whole Solar System to predict eclipses. For example, NASA uses a highly advanced form of an ancient technique – pattern recognition. Using some 38,000 repeating mathematical terms, NASA can predict both solar and lunar eclipses for 1,000 years into the future. Beyond that, the Moon’s wobble and Earth’s changing rotation make eclipse prediction less accurate.
[0] https://www.astronomy.com/observing/humans-have-been-predict...
And mostly this fails. You cant really analyse the world using simple closed-form formula -- all the stuff that this worked for is studied and reported in books.
Explicitly, WLOG the potential is `V(x) = V_0 + V_1 (x-x_0) + V_2 (x-x_0)^2 + ...`. But the first derivative is 0 near a minimum, so V_1 = 0. The constant V_0 term doesn't affect dynamics, so choose it to be 0. Then the higher order terms go to 0 as x->x_0, so you have `V(x) = V_2 x^2` near any stable point.
And it's pretty obvious that lots of real-world phenomena 1. do have stable states and 2. do oscillate around them before settling, so the model is pretty good for lots of real-world systems (with the error being that the system is generally not conservative, so eventually it settles into the equilibrium because friction is stealing the energy).
And it makes sense that stable points exist. That means there's a well somewhere in the potential (and the stable point is at the bottom of the well). It seems reasonable that if you didn't know anything about the potential of a system, you might suppose it has at least one squiggle somewhere, and in that squiggle you'll find your equilibrium.
Edit: I guess actually it's not so obvious in the higher dimensional case since you can have saddles. I'd have to go back and look at my nonlinear diffeq book to see, but there might be some topological result (similar to the hairy ball theorem) that explains it, at least for compact configuration spaces.
> Look around you. Is the building you're in falling down?
You can say it’s stable, or that the building is in the act of slowly falling down without human input (maintenance). It’s a bit misleading to sneak in time scale.
> Are the things on your desk bouncing about, or are they just sitting there?
At a small enough scale bits of the desk are bouncing around due to thermal energy. Also same as the house, your desk will eventually decay into dust due to that bouncing.
> Are the atoms in your body fissioning, or are you still there?
This one is actually stable.
The other two systems are better characterized as metastable - they appear stable at certain time and length scales. In fact metastability can be pretty tricky to explain, and sometimes requires a detour into thermodynamics or other fields (e.g. biology if you’re asking why a person’s body seems rather stable).
The point is wells exist and are common in day-to-day life, including ones that are deep enough that things don't randomly thermodynamically pop out of them. If something is sitting on your desk when you go to bed, you can be pretty certain it'll be there in the morning too. The scale of the well is orders of magnitude larger than the thermal fluctuations, even if eventually a fluctuation could excite your computer monitor to suddenly vaporize. The atoms in your body and all matter will eventually decay to nothing too, but it's not useful to think about that.
And even if it's metastable, as long as the system stays inside the well, the potential is locally quadratic. So you see oscillations around the equilibrium in the meantime.
You're weighting parts of reality by their relevance to a us at a particular place and time -- without such prejudice you find that very little admits of this sort of cute mathematical description.
And that which does is now pretty exhausted as far as research goes. Describing beds is not a pressing theoretical quesiton
Describing organic systems, say is -- chaotic organic development across trillions of cells. There are no SHOs there
As soon as you have three of anythign physics, as applied math, breaks down
Is it part of the essential nature of a building to collapse? Sure, I suppose, as with all things. But I'm only going to be in this this coffee shop for another hour: to me, for my purposes, it's stable. If instead I were buying the building I'd want a much more detailed model that considered termites and the risk of earthquakes and all sorts of things, but I still wouldn't care about the date of the next ice age that will scour the landscape clean.
One thing to keep in mind is that our mathematical methods might as well be approximate, because we our measurements always will be. Precise calculations on fuzzy data are a waste of time. Not that there's anything wrong with philosophy! But it's not super relevant to understanding where harmonic oscillators are a useful model.
It models first order perturbations over a stable equilibrium. For sufficiently small perturbations around a stable equilibrium everything is an harmonic oscillator.
It's basically taking the first order perturbation of a Taylor expansion around a local minima.
I'm not sure that's less complicated, at least for my level understanding.
You know Taylor expansions ? So every complicated function of x can be written as soe expansion of infinite powers of x, a0 +a1 ( x )+a2 ( x^2 ) ... And so on Every complicated force can then be written as a function of displacement x like this , now if x is small ignore the sqaure and higher order terms what you get is the linear part , which looks something like F = a1x + a0 , the a0 part only shifts the default position (you can rewrite x as x-c so that a0 goes to zero,) lo and behold you have F=Kx everything is like your familiar hooks law spring as long as x is small enough.
Here's the presentation I've seen. Usually we like to work in potentials, not forces, because potentials are nice scalar functions, while force is an ugly vector function. So say you have a potential V which is at a local minimum at position x.
Expand the potential at x around a small displacement dx: V(x + dx). This gives us the Taylor series V(x+dx) = V(x) + a1 V'(x) dx + a2 V''(x) dx^2 + a3 V'''(x) dx^3...
We can neglect V(x) since it's just a constant, and adding a constant to the potential does not affect the physics. And (the crux) we can neglect V'(x) because the potential is at a minimum, so the derivative is zero.
That leaves the quadratic and higher-order terms. Neglecting the higher order terms on the basis that dx is small, we get the harmonic potential, or Hooke's Law in the language of forces.
i suppose it’s because most interesting forces are conservative, i.e. if motion doesn’t dissipate energy (like friction, unlike electromagnetism) then energy is conserved so perturbations must bounce. OP contains the key insight- dissipating systems dissipate proportional to total energy, so low energies are approximately stable, IIUC.
That's the same reason, why we linearize nonlinear systems around the equilibria to apply linear control theory, right?
While in control, this makes sense to me, since the goal is often to stabilize the system, how does this help with modeling the whole system in general (far away from any equilibrium point)?
Outside of equilibrium things get more complicated. In principle, you can still do a first order expansion to understand the dynamics in a vicinity of that regime, the problem is that outside equilibrium you are not going to stay near the point of the solution space you started at. You will keep drifting, at least until you reach another stable equilibrium if there is one.
Systems outside equilibrium are much harder to study because we cannot linearize. Basically.
Also, just a reminder that it is the second-order term in the Taylor expansion that is relevant for harmonic oscillators. Zeroth-order term (constant) does not determine the dynamics. The first-order term (linear) is zero only for low energies, as any potential well at sufficiently low energies will be symmetric. The second-order term (quadratic) is what provides the restoring force towards the equilibrium.
The first relevant term is quadratic in the potential around a stable equilibrium but linear in the force. That's why they are called linear harmonic oscillators, I thought that was obvious in my description.
If they are purely linear - it is simple; just write a matrix of their spring coefficients and diagonalize it. If there are non-linear terms, well, then it isn't. This is the case in one of the Quantum Field Theory (and its instance, the Standard Model), the most fundamental theory describing particles. One of the takes on Feynman diagrams is that it is a series approximation of non-linear interactions in the QFT.
> discovery of a new quantum algorithm that offers an exponential advantage for simulating coupled classical harmonic oscillators.
> To enable the simulation of a large number of coupled harmonic oscillators, we came up with a mapping that encodes the positions and velocities of all masses and springs into the quantum wavefunction of a system of qubits. Since the number of parameters describing the wavefunction of a system of qubits grows exponentially with the number of qubits, we can encode the information of N balls into a quantum mechanical system of only about log(N) qubits.
The quantum algorithm couldn't simulate these things.
Is this a new result, giving that quantum field theory is described in terms of quantum harmonic oscillators?
Most surpisingly this would include the hidden subgroup problem and hence give you a classical poly-time algorithm for integer factorization.
A very cool result!
It'd be interesting to see how many other systems can be approximated by the system they've solved for (without incurring an exponential penalty in the translation).
The result looks very interesting, and the blog post is well written (e.g., I did not know about the prior work re. Grover's algorithm and pendulum systems).
The blog post is also based on a recent FOCS paper, and the authors are reputable people in CS theory, if that convinces anyone to take a closer look.
It's like saying quantum teleportation [2] is BS, just because you don't like the SF sounding word "teleportation".
https://blog.research.google/2022/11/making-traversable-worm...
The "wormhole" thing was scientifically interesting as a quantum simulation of a non-trivial gravitational thing. A lot of the media stuff was garbage, but the actual science they did was quite cool.