当前位置：
X-MOL 学术
›
Phys. Rev. X
›
论文详情
Our official English website, www.x-mol.net, welcomes your
feedback! (Note: you will need to create a separate account there.)
Quartic Quantum Speedups for Planted Inference
Physical Review X ( IF 11.6 ) Pub Date : 2025-06-02 , DOI: 10.1103/physrevx.15.021077
Alexander Schmidhuber, Ryan O’Donnell, Robin Kothari, Ryan Babbush
Physical Review X ( IF 11.6 ) Pub Date : 2025-06-02 , DOI: 10.1103/physrevx.15.021077
Alexander Schmidhuber, Ryan O’Donnell, Robin Kothari, Ryan Babbush
We describe a quantum algorithm for the Planted Noisy kXOR Problem (also known as Sparse Learning Parity with Noise) that achieves a nearly (fourth-power) speedup over the best known classical algorithm while using exponentially less space. Our work generalizes and simplifies prior work of Hastings [], 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 k XOR Published by the American Physical Society 2025
更新日期：2025-06-02
京公网安备 11010802027423号