A new quantum algorithm for classical mechanics with an exponential speedup
blog.research.google
A new quantum algorithm for classical mechanics with an exponential speedup
1–10 of 67 posts
Re: A new quantum algorithm for classical mechanics with an exponential speedup
#2Very interesting indeed:
> 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.
Re: A new quantum algorithm for classical mechanics with an exponential speedup
#3The thing that stands out to me is the described proof of BQP-completeness where they say they prove any quantum system can be similarities as balls and springs, but later they say you may need an exponential number of springs for a classical simulation. That sounds like the BQP reduction would be exponential, guess I'll have to read the paper to see what I'm missing.
Re: A new quantum algorithm for classical mechanics with an exponential speedup
#4One of the most important insights you take away from a physics undergrad is that you can model much of physical phenomena as a harmonic oscillator. The reason for this is quite simple
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.
Re: A new quantum algorithm for classical mechanics with an exponential speedup
#5The thing that stands out to me is the described proof of BQP-completeness where they say they prove any quantum system can be similarities as balls and springs, but later they say you may need an exponential number of springs for a classical simulation. That sounds like the BQP reduction would be exponential, guess I'll have to read the paper to see what I'm missing.
Just a gut feeling but it could be related to the ability to map so much stuff to path integrals with harmonic fields. I too need to read it better.
Re: A new quantum algorithm for classical mechanics with an exponential speedup
#6One of the most important insights you take away from a physics undergrad is that you can model much of physical phenomena as a harmonic oscillator. The reason for this is quite simple 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 til…
Would a 3-or-more body gravitational problem be one of these that could use a speed up?
Re: A new quantum algorithm for classical mechanics with an exponential speedup
#7One of the most important insights you take away from a physics undergrad is that you can model much of physical phenomena as a harmonic oscillator. The reason for this is quite simple 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 til…
Would a 3-or-more body gravitational problem be one of these that could use a speed up?
For that, accuracy seems to be a stronger limiting factor than speed.
Re: A new quantum algorithm for classical mechanics with an exponential speedup
#8The approach maps the classical mechanics of coupled harmonic oscillators to a particular quantum system. I'm curious if there is some (unrelated) classical system whose quantization is that same quantum system. In other words, does this quantum system have a natural interpretation as the quantum mechanical version of some classical system? If so, it's presumably very different from (e.g., a lot smaller than?) the oscillator system which motivated the study of the quantum system.
Re: A new quantum algorithm for classical mechanics with an exponential speedup
#9Earlier quoted context omitted.
Would a 3-or-more body gravitational problem be one of these that could use a speed up?
For that, accuracy seems to be a stronger limiting factor than speed.
My lay understanding of the problem with classical algorithms is basically that a lack of resolution means you need to monte carlo the thing millions of times... which is why it's slow. If you could model it as a set of quantum states of similar inaccuracy, wouldn't that by definition be just as (in)accurate but faster?
[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.
Re: A new quantum algorithm for classical mechanics with an exponential speedup
#10Earlier quoted context omitted.
For that, accuracy seems to be a stronger limiting factor than speed.
My lay understanding of the problem with classical algorithms is basically that a lack of resolution means you need to monte carlo the thing millions of times... which is why it's slow. If you could model it as a set of quantum states of similar inaccuracy, wouldn't that by definition be just as (in)accurate but faster? [edit] this reminds me of something I read about how NASA doesn't predict solar eclipses by trying…
[deleted]