Quartic Quantum Speedups for Planted Inference
We describe a quantum algorithm for the Planted Noisy kXOR Problem (also known as Sparse Learning Parity with Noise) that achieves a nearly quartic (fourth-power) speedup over the best known classical algorithm while using exponentially less space. Our work generalizes and simplifies prior work of H...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
American Physical Society
2025-06-01
|
| Series: | Physical Review X |
| Online Access: | http://doi.org/10.1103/PhysRevX.15.021077 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850248608154124288 |
|---|---|
| author | Alexander Schmidhuber Ryan O’Donnell Robin Kothari Ryan Babbush |
| author_facet | Alexander Schmidhuber Ryan O’Donnell Robin Kothari Ryan Babbush |
| author_sort | Alexander Schmidhuber |
| collection | DOAJ |
| description | We describe a quantum algorithm for the Planted Noisy kXOR Problem (also known as Sparse Learning Parity with Noise) that achieves a nearly quartic (fourth-power) speedup over the best known classical algorithm while using exponentially less space. Our work generalizes and simplifies prior work of Hastings [Quantum 4, 237 (2020)2521-327X10.22331/q-2020-02-27-237], by building on his quantum algorithm for the tensor principal component analysis (PCA) problem. We achieve our quantum speedup using a general framework based on the Kikuchi method (recovering the quartic speedup for Tensor PCA), and we anticipate it will yield similar speedups for further planted inference problems. These speedups rely on the fact that planted inference problems naturally instantiate the guided sparse Hamiltonian problem. Since the Planted Noisy kXOR Problem has been used as a component of certain cryptographic constructions, our work suggests that some of these are susceptible to superquadratic quantum attacks. |
| format | Article |
| id | doaj-art-de0cd23638ae4a728dbb6308a9d0a1e6 |
| institution | OA Journals |
| issn | 2160-3308 |
| language | English |
| publishDate | 2025-06-01 |
| publisher | American Physical Society |
| record_format | Article |
| series | Physical Review X |
| spelling | doaj-art-de0cd23638ae4a728dbb6308a9d0a1e62025-08-20T01:58:41ZengAmerican Physical SocietyPhysical Review X2160-33082025-06-0115202107710.1103/PhysRevX.15.021077Quartic Quantum Speedups for Planted InferenceAlexander SchmidhuberRyan O’DonnellRobin KothariRyan BabbushWe describe a quantum algorithm for the Planted Noisy kXOR Problem (also known as Sparse Learning Parity with Noise) that achieves a nearly quartic (fourth-power) speedup over the best known classical algorithm while using exponentially less space. Our work generalizes and simplifies prior work of Hastings [Quantum 4, 237 (2020)2521-327X10.22331/q-2020-02-27-237], by building on his quantum algorithm for the tensor principal component analysis (PCA) problem. We achieve our quantum speedup using a general framework based on the Kikuchi method (recovering the quartic speedup for Tensor PCA), and we anticipate it will yield similar speedups for further planted inference problems. These speedups rely on the fact that planted inference problems naturally instantiate the guided sparse Hamiltonian problem. Since the Planted Noisy kXOR Problem has been used as a component of certain cryptographic constructions, our work suggests that some of these are susceptible to superquadratic quantum attacks.http://doi.org/10.1103/PhysRevX.15.021077 |
| spellingShingle | Alexander Schmidhuber Ryan O’Donnell Robin Kothari Ryan Babbush Quartic Quantum Speedups for Planted Inference Physical Review X |
| title | Quartic Quantum Speedups for Planted Inference |
| title_full | Quartic Quantum Speedups for Planted Inference |
| title_fullStr | Quartic Quantum Speedups for Planted Inference |
| title_full_unstemmed | Quartic Quantum Speedups for Planted Inference |
| title_short | Quartic Quantum Speedups for Planted Inference |
| title_sort | quartic quantum speedups for planted inference |
| url | http://doi.org/10.1103/PhysRevX.15.021077 |
| work_keys_str_mv | AT alexanderschmidhuber quarticquantumspeedupsforplantedinference AT ryanodonnell quarticquantumspeedupsforplantedinference AT robinkothari quarticquantumspeedupsforplantedinference AT ryanbabbush quarticquantumspeedupsforplantedinference |