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!
|