Reproduce “Quartic quantum speedups for planted inference” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Alexander Schmidhuber, Ryan O'Donnell, Robin Kothari, Ryan Babbush
A quantum algorithm is presented that achieves a nearly quartic speedup for the Planted Noisy kXOR problem and a broader class of planted inference problems. This method reduces computational time to ~O(n^(l/4) * poly(n)) and requires only ~O(log n) qubits, significantly improving upon classical ~O(n^l) time and space complexities.
Key insights
- Super-quadratic polynomial speedups, such as the nearly quartic speedup demonstrated, are identified as more practical for achieving quantum advantage on fault-tolerant machines than quadratic speedups alone.
- The research establishes that even polynomially increased overlap of a guiding state is sufficient to yield substantial polynomial quantum speedups within the Guided Sparse Hamiltonian problem context.
- The methodology provides a general framework to 'quantize' classical algorithms based on the Kikuchi method, allowing for broader application to various planted inference problems.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.