Assessing the feasibility of quantum learning algorithms for noisy linear problems
Minkyu Kim, Panjin Kim · 2024
Read Assessing the feasibility of quantum learning algorithms for noisy linear problems by Minkyu Kim, Panjin Kim (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/pmc-11589620.txt.
Description
Minkyu Kim and Panjin Kim present a 2024 paper testing whether quantum algorithms for noisy learning problems truly beat classical ones. The problems, with names like ring learning with errors, rest on adding noise to linear equations. An earlier team had built a fast quantum method using quantum samples. The pair re-examine that work under the same assumptions.
On one side, they widen the quantum method's reach, settling an open case about its Fourier step. On the other side, they show that if the same quantum samples are handed to a classical computer, efficient classical algorithms also exist for two related problems. The upshot is a fairer map of where quantum advantage may lie. The paper speaks to the cryptography built on these noisy problems, whose safety depends on such comparisons.
Catalog record
| CREATOR | Minkyu Kim, Panjin Kim |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 152 KB |
| VERSION | 1.0 |
| LICENSE | CC BY 4.0 |
| RIGHTS | CC BY |
| SOURCE | Europe PMC |