6 ms·
A new quantum algorithm for classical mechanics with an exponential speedup
- inasio 3y agoThis 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.
- marktangotango 3y agoVery 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.
- vimax 3y agoThe 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.
- chermi 3y agoJust 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.
- eigenket 3y agoThey have exponentially many classical oscillators, but then they simulate them with their quantum algorithm with exponential speed up. The two exponential factors cancel and you end up with a quantum algorithm for a BQP complete problem which runs in polynomial time.
- abdullahkhalids 3y agoOne 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.
- noduerme 3y agoWould a 3-or-more body gravitational problem be one of these that could use a speed up?
- dchftcs 3y agoFor that, accuracy seems to be a stronger limiting factor than speed.
- noduerme 3y agoMy 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.
- deleted 3y ago[deleted]
- cvoss 3y agoThe 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.
- T-A 3y agohttps://quantum.lassp.cornell.edu/lecture/coupled_harmonic_oscillators https://quantum.lassp.cornell.edu/lecture/coupled_harmonic_o...
- latenightcoding 3y agoI'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.
- moab 3y agoIt would be a good idea to read the blog post before making comments. 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.
- affgrff2 3y agoAnyone have an interesting link to some quantum neural network bs? Sounds interesting...
- ko27 3y agoStop basing your opinions on titles alone. Most of their blog posts on AI and quantum are exceptionally well written and researched, even the one you referenced: "Making a Dual of a Traversable Wormhole with a Quantum Computer" [1] 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-wormhole-with.html https://blog.research.google/2022/11/making-traversable-worm... https://en.wikipedia.org/wiki/Quantum_teleportation https://en.wikipedia.org/wiki/Quantum_teleportation
- tucnak 3y agoTouche
- deleted 3y ago[deleted]
- eigenket 3y ago
- deleted 3y ago[deleted]
- fgoesbrrr 3y ago> 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. Is this a new result, giving that quantum field theory is described in terms of quantum harmonic oscillators?
- eigenket 3y agoIts a network of exponentially many coupled classical oscillators, not quantum harmonic oscillators. This is a new result.
- IIAOPSW 3y agoI'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. [0] https://www.zyvex.com/nanotech/mechano.html https://www.zyvex.com/nanotech/mechano.html
- jksk61 3y agoIf you need an exponential number of coupled oscillators to construct a general purpose computer, then you don't have the exponential speedup.
- eigenket 3y agoThe logic gates described in that link are more complicated than just coupled harmonic oscillators. They have things like ratchets, or they block each other, or there is buckling. The quantum algorithm couldn't simulate these things.
- naasking 3y agoYou would need an exponential number of coupled oscillators to achieve that exponential speedup. Doesn't seem too good to be true to me.
- somat 3y agoI am probably misunderstanding something fundamental. But isn't that exactly what a qubit is. A coupled harmonic oscillator.
- xinayder 3y agoIs this similar to Ed Gerck's "finding" of a QC algorithm that can break RSA-2048?
- swiftlyTyped 3y agoUsually these types of articles are total nonsense, but this is legit. 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).
- 11101010001100 3y agoNeed 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?
- shollos 3y agoI suspect an analog computer would work just as well for modeling coupled harmonic oscillators.
- eigenket 3y agoThat would be very surprising. They show in this work that their problem is complete for the complexity class BQP. That means that if you can solve it on a classical computer (analog or not) in polynomial time you get (for free) classical polynomial-time algorithms for solving a bunch of problems we don't currently have classical poly-time algorithms for. Most surpisingly this would include the hidden subgroup problem and hence give you a classical poly-time algorithm for integer factorization.