Cover Image

Nearly optimal algorithms to learn sparse quantum Hamiltonians in physically motivated distances

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Abbas, Amira, Cerrato, Nunzia, Gutiérrez, Francisco Escudero, Grinko, Dmitry, Mele, Francesco Anna, Sinha, Pulkit
Format:	Preprint
Published:	2025
Subjects:	Quantum Physics Computational Complexity Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Optimal learning of quantum channels in diamond distance
by: Mele, Antonio Anna, et al.
Published: (2025)

Testing and learning structured quantum Hamiltonians
by: Arunachalam, Srinivasan, et al.
Published: (2024)

Simple algorithms to test and learn local Hamiltonians
by: Gutiérrez, Francisco Escudero
Published: (2024)

Certifying and learning quantum Ising Hamiltonians
by: Bluhm, Andreas, et al.
Published: (2025)

Certifying and learning local quantum Hamiltonians
by: Bluhm, Andreas, et al.
Published: (2026)

Nearly optimal independence oracle algorithms for edge estimation in hypergraphs
by: Dell, Holger, et al.
Published: (2022)

On estimating the quantum $\ell_α$ distance
by: Liu, Yupan, et al.
Published: (2025)

Conditional lower bounds for sparse parameterized 2-CSP: A streamlined proof
by: S., Karthik C., et al.
Published: (2023)

Fast quantum algorithm for differential equations
by: Bagherimehrab, Mohsen, et al.
Published: (2023)

Simple approximation algorithms for Polyamorous Scheduling
by: Biktairov, Yuriy, et al.
Published: (2024)

Self-referential instances of the dominating set problem are irreducible
by: Zhou, Guangyan
Published: (2026)

Near-Optimal Averaging Samplers and Matrix Samplers
by: Xun, Zhiyang, et al.
Published: (2024)

Near Optimal Alphabet-Soundness Tradeoff PCPs
by: Minzer, Dor, et al.
Published: (2024)

Towards universally optimal sorting algorithms
by: Sen, Sandeep
Published: (2025)

Faster Algorithms for Sparse ILP and Hypergraph Multi-Packing/Multi-Cover Problems
by: Gribanov, Dmitry, et al.
Published: (2022)

Near-Optimality for Single-Source Personalized PageRank
by: Jiang, Xinpeng, et al.
Published: (2025)

Near-Optimal Space Lower Bounds for Streaming CSPs
by: Fei, Yumou, et al.
Published: (2026)

Kronecker scaling of tensors with applications to arithmetic circuits and algorithms
by: Björklund, Andreas, et al.
Published: (2025)

On optimal distinguishers for Planted Clique
by: Nagda, Ansh, et al.
Published: (2025)

Subset Sum in Near-Linear Pseudopolynomial Time and Polynomial Space
by: Sajith, Thejas Radhika
Published: (2025)

Additive approximation algorithm for geodesic centers in $δ$-hyperbolic graphs
by: Chakraborty, Dibyayan, et al.
Published: (2024)

Nine lower bound conjectures on streaming approximation algorithms for CSPs
by: Singer, Noah G.
Published: (2025)

An extension of Dembo-Hammer's reduction algorithm for the 0-1 knapsack problem
by: Yang, Yang
Published: (2025)

Rate-optimal community detection near the KS threshold via node-robust algorithms
by: Ding, Jingqiu, et al.
Published: (2025)

Near Optimal Algorithms for Noisy $k$-XOR under Low-Degree Heuristic
by: Mao, Songtao
Published: (2026)

A constant time complexity algorithm for the unbounded knapsack problem with bounded coefficients
by: Yang, Yang
Published: (2024)

The complexity of finding and enumerating optimal subgraphs to represent spatial correlation
by: Enright, Jessica, et al.
Published: (2020)

Sampling Permutations with Cell Probes is Hard
by: Alekseev, Yaroslav, et al.
Published: (2025)

A sublinear query quantum algorithm for s-t minimum cut on dense simple graphs
by: Apers, Simon, et al.
Published: (2021)

Parameterised distance to local irregularity
by: Fioravantes, Foivos, et al.
Published: (2023)

3-Local Hamiltonian Problem and Constant Relative Error Quantum Partition Function Approximation: $O(2^{\frac{n}{2}})$ Algorithm Is Nearly Optimal under QSETH
by: Chia, Nai-Hui, et al.
Published: (2025)

Dequantization Barriers for Guided Stoquastic Hamiltonians
by: Hamoudi, Yassine, et al.
Published: (2026)

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

Hamiltonian Locality Testing via Trotterized Postselection
by: Kallaugher, John, et al.
Published: (2025)

Beyond Bell sampling: stabilizer state learning and quantum pseudorandomness lower bounds on qudits
by: Allcock, Jonathan, et al.
Published: (2024)

BBK: a simpler, faster algorithm for enumerating maximal bicliques in large sparse bipartite graphs
by: Baudin, Alexis, et al.
Published: (2024)

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

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

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

Gibbs state preparation for commuting Hamiltonian: Mapping to classical Gibbs sampling
by: Hwang, Yeongwoo, et al.
Published: (2024)