Cover Image

Information-Computation Gaps in Quantum Learning via Low-Degree Likelihood

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Chen, Sitan, Gong, Weiyuan, Haferkamp, Jonas, Quek, Yihui
Format:	Preprint
Published:	2025
Subjects:	Quantum Physics Computational Complexity Data Structures and Algorithms Machine Learning
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Stabilizer bootstrapping: A recipe for efficient agnostic tomography and magic estimation
by: Chen, Sitan, et al.
Published: (2024)

On the sample complexity of purity and inner product estimation
by: Gong, Weiyuan, et al.
Published: (2024)

An Exponential Separation Between Quantum and Quantum-Inspired Classical Algorithms for Linear Systems
by: Grønlund, Allan, et al.
Published: (2024)

Quantum Property Testing for Bounded-Degree Directed Graphs
by: Peng, Pan, et al.
Published: (2026)

Computation-Utility-Privacy Tradeoffs in Bayesian Estimation
by: Chen, Sitan, et al.
Published: (2026)

Hardness of Maximum Likelihood Learning of DPPs
by: Grigorescu, Elena, et al.
Published: (2022)

Low-Degree Method Fails to Predict Robust Subspace Recovery
by: Jia, He, et al.
Published: (2026)

Testing classical properties from quantum data
by: Caro, Matthias C., et al.
Published: (2024)

Interactive proofs for verifying (quantum) learning and testing
by: Caro, Matthias C., et al.
Published: (2024)

Reconquering Bell sampling on qudits: stabilizer learning and testing, quantum pseudorandomness bounds, and more
by: Allcock, Jonathan, et al.
Published: (2025)

Complexity of Digital Quantum Simulation in the Low-Energy Subspace: Applications and a Lower Bound
by: Gong, Weiyuan, et al.
Published: (2023)

Instance-Optimal Matrix Multiplicative Weight Update and Its Quantum Applications
by: Gong, Weiyuan, et al.
Published: (2025)

Single-copy stabilizer testing
by: Hinsche, Marcel, et al.
Published: (2024)

Strict Hierarchy for Quantum Channel Certification to Unitary
by: Chen, Kean, et al.
Published: (2026)

Learning low-degree quantum objects
by: Arunachalam, Srinivasan, et al.
Published: (2024)

Optimal Quantum State Testing Even with Limited Entanglement
by: Wadhwa, Chirag, et al.
Published: (2026)

The Low-Degree Hardness of Finding Large Independent Sets in Sparse Random Hypergraphs
by: Dhawan, Abhishek, et al.
Published: (2024)

Quantum Search with In-Place Queries
by: Holman, Blake, et al.
Published: (2025)

Quantum Mass Production Theorems
by: Kretschmer, William
Published: (2022)

An optimal tradeoff between entanglement and copy complexity for state tomography
by: Chen, Sitan, et al.
Published: (2024)

Optimal high-precision shadow estimation
by: Chen, Sitan, et al.
Published: (2024)

Dequantizing Short-Path Quantum Algorithms
by: Gall, François Le, et al.
Published: (2026)

Clifford testing: algorithms and lower bounds
by: Hinsche, Marcel, et al.
Published: (2025)

Quantum Algorithm for Lexicographically Minimal String Rotation
by: Wang, Qisheng, et al.
Published: (2020)

Unstructured Adiabatic Quantum Optimization: Optimality with Limitations
by: Braida, Arthur, et al.
Published: (2024)

Quantum Channel Testing in Average-Case Distance
by: Rosenthal, Gregory, et al.
Published: (2024)

An Entropy-Governed Speedup for Quantum Algorithms on Local Hamiltonians
by: Mataraarachchi, Ranitha, et al.
Published: (2026)

Computational Lower Bounds for Graphon Estimation via Low-degree Polynomials
by: Luo, Yuetian, et al.
Published: (2023)

Simulation of Non-Hermitian Hamiltonians with Bivariate Quantum Signal Processing
by: Courtney, Joshua M.
Published: (2026)

Quantum Property Testing Algorithm for the Concatenation of Two Palindromes Language
by: Khadiev, Kamil, et al.
Published: (2024)

Quantum Algorithms on Edge Lists: Hiding, Shuffling, and Cycle Finding
by: Gilani, Amin Shiraz, et al.
Published: (2024)

Detecting Low-Degree Truncation
by: De, Anindya, et al.
Published: (2024)

Quantum Worst-Case to Average-Case Reduction for Matrix-Vector Multiplication
by: Aggarwal, Divesh, et al.
Published: (2025)

Quantum Algorithm for Finding the Optimal Variable Ordering for Binary Decision Diagrams
by: Tani, Seiichiro
Published: (2019)

On the (Classical and Quantum) Fine-Grained Complexity of Approximate CVP and Max-Cut
by: Huang, Jeremy Ahrens, et al.
Published: (2024)

Optimal Bounds, Barriers, and Extensions for Non-Hermitian Bivariate Quantum Signal Processing
by: Courtney, Joshua M.
Published: (2026)

Lasso with Latents: Efficient Estimation, Covariate Rescaling, and Computational-Statistical Gaps
by: Kelner, Jonathan, et al.
Published: (2024)

Fine-Grained Complexity for Quantum Problems from Size-Preserving Circuit-to-Hamiltonian Constructions
by: Chia, Nai-Hui, et al.
Published: (2026)

Computational-Statistical Tradeoffs from NP-hardness
by: Blanc, Guy, et al.
Published: (2025)

The Computational Complexity of Almost Stable Clustering with Penalties
by: Khodamoradi, Kamyar, et al.
Published: (2025)