Cover Image

Fine-Grained Complexity for Quantum Problems from Size-Preserving Circuit-to-Hamiltonian Constructions

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Chia, Nai-Hui, Hasegawa, Atsuya, Gall, François Le, Shen, Yu-Ching
Format:	Preprint
Published:	2026
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

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 and Hardness of Spectral Sum Estimation
by: Edenhofer, Roman, et al.
Published: (2025)

Classical Algorithms for Constant Approximation of the Ground State Energy of Local Hamiltonians
by: Gall, François Le
Published: (2024)

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

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

The Fine-Grained Complexity of Episode Matching
by: Bille, Philip, et al.
Published: (2021)

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

Fine-Grained Equivalence for Problems Related to Integer Linear Programming
by: Rohwedder, Lars, et al.
Published: (2024)

An Invitation to "Fine-grained Complexity of NP-Complete Problems"
by: Nederlof, Jesper
Published: (2026)

A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT
by: Buhrman, Harry, et al.
Published: (2025)

Fine-Grained Complexity of Continuous Euclidean k-Center
by: Blank, Lotte, et al.
Published: (2026)

A Note on Fine-Grained Quantum Reductions for Linear Algebraic Problems
by: Doney, Kyle, et al.
Published: (2025)

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

Fine-Grained Classification Of Detecting Dominating Patterns
by: Dransfeld, Jonathan, et al.
Published: (2025)

Space Complexity Dichotomies for Subgraph Finding Problems in the Streaming Model
by: Shih, Yu-Sheng, et al.
Published: (2026)

Connectivity-Preserving Important Separators: A Framework for Cut-Uncut Problems
by: Kenig, Batya
Published: (2025)

Complexity of Local Search for Euclidean Clustering Problems
by: Manthey, Bodo, et al.
Published: (2023)

On the Complexity of Fundamental Problems for DAG-Compressed Graphs
by: Chudigiewitsch, Florian, et al.
Published: (2026)

Multicut Problems in Embedded Graphs: The Dependency of Complexity on the Demand Pattern
by: Focke, Jacob, et al.
Published: (2023)

A Complexity Analysis of the c-Closed Vertex Deletion Problem
by: Lehner, Lisa, et al.
Published: (2025)

End Cover for Initial Value Problem: Complete Validated Algorithms with Complexity Analysis
by: Zhang, Bingwei, et al.
Published: (2026)

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

Kernelization Complexity of Solution Discovery Problems
by: Grobler, Mario, et al.
Published: (2024)

Size Minimization For Multi-Output AND-Functions
by: Armbruster, Susanne
Published: (2024)

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

Towards Deterministic Algorithms for Constant-Depth Factors of Constant-Depth Circuits
by: Kumar, Mrinal, et al.
Published: (2024)

Constructing self-referential instances for the clique problem
by: Li, Jiaqi, et al.
Published: (2026)

Scheduling Problems with Constrained Rejections
by: Davies, Sami, et al.
Published: (2025)

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

Neighborhood-Aware Graph Labeling Problem
by: Shahverdikondori, Mohammad, et al.
Published: (2026)

String Consensus Problems with Swaps and Substitutions
by: Gabory, Estéban, et al.
Published: (2025)

Equivalent Instances for Scheduling and Packing Problems
by: Jansen, Klaus, et al.
Published: (2025)

Pseudodeterministic Algorithms for Minimum Cut Problems
by: Agarwala, Aryan, et al.
Published: (2025)

Parameterized Complexity of Vehicle Routing
by: Döring, Michelle, et al.
Published: (2025)

The Complexity of Finding and Counting Subtournaments
by: Döring, Simon, et al.
Published: (2025)

On the Parameterized Complexity of Odd Coloring
by: Bhyravarapu, Sriram, et al.
Published: (2025)

On the Complexity of Signed Roman Domination
by: Reddy, Sangam Balchandar
Published: (2025)

On the Space Complexity of Online Convolution
by: Andersson, Joel Daniel, et al.
Published: (2025)

Computational Complexity in Property Testing
by: Pinto Jr., Renato Ferreira, et al.
Published: (2025)

The Fine-Grained Complexity of Gradient Computation for Training Large Language Models
by: Alman, Josh, et al.
Published: (2024)