Quantum solves learning with errors
Imagine a set of weather vanes that are all pointing in the same direction. Give each of them a measured shove, then let a gusty wind influence their direction. Regev wanted to determine, based on their final directions, where they all pointed initially. Problems like this came to be called “learning with errors,” because the shove and the wind act like a source of random error on the original direction. There is evidence that it is hard to solve for both classical and quantum algorithms.
Yamakawa and Zhandry tweaked the setup. They modified the strength of those starting shoves, making them more predictable. They also caused the wind to be determined by a random oracle so that it was even more random in certain cases but completely dormant in others.
With these modifications, the researchers discovered that a quantum algorithm could efficiently find the initial direction. They also proved that any classical algorithm must be slower by an exponential factor. Like Shor, they then adapted their algorithm to solve a real-world version of the problem, which replaces the oracle with an actual mathematical equation.
Link:: https://www.quantamagazine.org/quantum-algorithms-conquer-a-new-kind-of-problem-20220711/
Прорыв по применению [[квантовые вычисления]].