Buchumschlag

3-Local Hamiltonian Problem and Constant Relative Error Quantum Partition Function Approximation: $O(2^{\frac{n}{2}})$ Algorithm Is Nearly Optimal under QSETH

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Chia, Nai-Hui, Shen, Yu-Ching
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Quantum Physics Computational Complexity Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

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

Classical Algorithms for Constant Approximation of the Ground State Energy of Local Hamiltonians
von: Gall, François Le
Veröffentlicht: (2024)

Near Optimal Algorithms for Noisy $k$-XOR under Low-Degree Heuristic
von: Mao, Songtao
Veröffentlicht: (2026)

Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search
von: Esmer, Barış Can, et al.
Veröffentlicht: (2022)

Towards Deterministic Algorithms for Constant-Depth Factors of Constant-Depth Circuits
von: Kumar, Mrinal, et al.
Veröffentlicht: (2024)

On the Constant-Factor Approximability of Minimum Cost Constraint Satisfaction Problems
von: DeHaan, Ian, et al.
Veröffentlicht: (2025)

Fantastic Flips and Where to Find Them: A General Framework for Parameterized Local Search on Partitioning Problems
von: Grüttemeier, Niels, et al.
Veröffentlicht: (2025)

An Entropy-Governed Speedup for Quantum Algorithms on Local Hamiltonians
von: Mataraarachchi, Ranitha, et al.
Veröffentlicht: (2026)

Near-Optimal Averaging Samplers and Matrix Samplers
von: Xun, Zhiyang, et al.
Veröffentlicht: (2024)

Near Optimal Alphabet-Soundness Tradeoff PCPs
von: Minzer, Dor, et al.
Veröffentlicht: (2024)

Maximization of Approximately Submodular Functions
von: Horel, Thibaut, et al.
Veröffentlicht: (2024)

On the (In)Approximability of the Monitoring Edge Geodetic Set Problem
von: Bilò, Davide, et al.
Veröffentlicht: (2025)

Near-Optimality for Single-Source Personalized PageRank
von: Jiang, Xinpeng, et al.
Veröffentlicht: (2025)

Near-Optimal Space Lower Bounds for Streaming CSPs
von: Fei, Yumou, et al.
Veröffentlicht: (2026)

Capacitated Fair-Range Clustering: Hardness and Approximation Algorithms
von: Gadekar, Ameet, et al.
Veröffentlicht: (2025)

TSP Escapes the $O(2^n n^2)$ Curse
von: Stoian, Mihail
Veröffentlicht: (2024)

Gray Codes With Constant Delay and Constant Auxiliary Space
von: Amarilli, Antoine, et al.
Veröffentlicht: (2026)

Pseudodeterministic Algorithms for Minimum Cut Problems
von: Agarwala, Aryan, et al.
Veröffentlicht: (2025)

Optimal Single-Pass Streaming Lower Bounds for Approximating CSPs
von: Singer, Noah G., et al.
Veröffentlicht: (2026)

On the Approximability of Train Routing and the Min-Max Disjoint Paths Problem
von: Bhaskar, Umang, et al.
Veröffentlicht: (2025)

Improved Hardness and Approximations for Cardinality-Based Minimum $s$-$t$ Cuts Problems in Hypergraphs
von: Adriaens, Florian, et al.
Veröffentlicht: (2024)

A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT
von: Buhrman, Harry, et al.
Veröffentlicht: (2025)

Complexity of Local Search for Euclidean Clustering Problems
von: Manthey, Bodo, et al.
Veröffentlicht: (2023)

Optimal Parallel Basis Finding in Graphic and Related Matroids
von: Khanna, Sanjeev, et al.
Veröffentlicht: (2025)

Complexity of Paired Domination Problems on Circle and $k$-Polygon Graphs
von: Mu, Ta-Yu, et al.
Veröffentlicht: (2024)

Fine-Grained Equivalence for Problems Related to Integer Linear Programming
von: Rohwedder, Lars, et al.
Veröffentlicht: (2024)

PCF Learned Sort: a Learning Augmented Sort Algorithm with $O(n \log\log n)$ Expected Complexity
von: Sato, Atsuki, et al.
Veröffentlicht: (2024)

Asymmetric Number Partitioning with Splitting and Interval Targets
von: Bismuth, Samuel, et al.
Veröffentlicht: (2022)

An $\widetilde{O} (n^{3/7})$ Round Parallel Algorithm for Matroid Bases
von: Khanna, Sanjeev, et al.
Veröffentlicht: (2026)

Fast Approximation Algorithm for Non-Monotone DR-submodular Maximization under Size Constraint
von: Tran, Tan D., et al.
Veröffentlicht: (2025)

End Cover for Initial Value Problem: Complete Validated Algorithms with Complexity Analysis
von: Zhang, Bingwei, et al.
Veröffentlicht: (2026)

On the Complexity of Minimizing Energy Consumption of Partitioning DAG Tasks
von: Liu, Wei, et al.
Veröffentlicht: (2024)

Counting Stars is Constant-Degree Optimal For Detecting Any Planted Subgraph
von: Yu, Xifan, et al.
Veröffentlicht: (2024)

Hamiltonian Locality Testing via Trotterized Postselection
von: Kallaugher, John, et al.
Veröffentlicht: (2025)

Nearly optimal algorithms to learn sparse quantum Hamiltonians in physically motivated distances
von: Abbas, Amira, et al.
Veröffentlicht: (2025)

Exact and Approximate Algorithms for Polytree Learning
von: Harviainen, Juha, et al.
Veröffentlicht: (2026)

Constant Time with Minimal Preprocessing, a Robust and Extensive Complexity Class
von: Grandjean, Étienne, et al.
Veröffentlicht: (2025)

Geodetic Set on Graphs of Constant Pathwidth and Feedback Vertex Set Number
von: Tale, Prafullkumar
Veröffentlicht: (2025)

Testing Juntas and Junta Subclasses with Relative Error
von: Chen, Xi, et al.
Veröffentlicht: (2025)

On the Hardness of Approximation of the Fair k-Center Problem
von: Thejaswi, Suhas
Veröffentlicht: (2026)