One 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<p>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.<p>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).<p>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.<p>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.
Very interesting indeed:<p>> discovery of a new quantum algorithm that offers an exponential advantage for simulating coupled classical harmonic oscillators.<p>> 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 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.
The 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.
I'm skeptical. If you have an exponential speedup for simulations of coupled oscillators, you can rig a system of coupled oscillators into a general purpose computer [0] and therefore have an exponential speedup for any computation. That seems too good to be true.<p>[0] <a href="https://www.zyvex.com/nanotech/mechano.html" rel="nofollow noreferrer">https://www.zyvex.com/nanotech/mechano.html</a>
This could be pretty exciting. For all the talk about quantum advantage, the number of quantum algorithms that have exponential speedup is super small; as the blog mentions it's essentially Shor's prime factoring and quantum simulations.
> Further, we use this mapping to prove that any problem efficiently solvable by a quantum algorithm can be recast as a problem involving a network of coupled oscillators, albeit exponentially many of them.<p>Is this a new result, giving that quantum field theory is described in terms of quantum harmonic oscillators?
Need to take a closer look at the paper, but a classical approach to this problems is to map it to an eigenvalue problem, so could we say that they have found a quantum speed up for solving eigenvalue problems?
Usually these types of articles are total nonsense, but this is legit.<p>A very cool result!<p>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).
I'll read it when I'm home. But I want to say that the fact that this is from google "quantum AI" makes me doubt the legitimacy. They are really ruining their reputation with all the absurd quantum stuff they have been publishing, e.g: their wormhole stuff and a lot of quantum neural networks bs.