Buchumschlag

On the (Classical and Quantum) Fine-Grained Complexity of Approximate CVP and Max-Cut

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Huang, Jeremy Ahrens, Ko, Young Kun, Wang, Chunhao
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Computational Complexity Data Structures and Algorithms Quantum Physics
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)

Unifying the Landscape of Super-Logarithmic Dynamic Cell-Probe Lower Bounds
von: Ko, Young Kun
Veröffentlicht: (2025)

Multi-Pass Streaming Lower Bounds for Approximating Max-Cut
von: Fei, Yumou, et al.
Veröffentlicht: (2025)

The Fine-Grained Complexity of Episode Matching
von: Bille, Philip, et al.
Veröffentlicht: (2021)

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

Quantum Algorithm for Lexicographically Minimal String Rotation
von: Wang, Qisheng, et al.
Veröffentlicht: (2020)

Superpolynomial smoothed complexity of 3-FLIP in Local Max-Cut
von: Michel, Lukas, et al.
Veröffentlicht: (2023)

Strict Hierarchy for Quantum Channel Certification to Unitary
von: Chen, Kean, et al.
Veröffentlicht: (2026)

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

Quantum Algorithms on Edge Lists: Hiding, Shuffling, and Cycle Finding
von: Gilani, Amin Shiraz, et al.
Veröffentlicht: (2024)

Quantum Search with In-Place Queries
von: Holman, Blake, et al.
Veröffentlicht: (2025)

Quantum Mass Production Theorems
von: Kretschmer, William
Veröffentlicht: (2022)

Lower Bounds for Linear Operators
von: Ko, Young Kun
Veröffentlicht: (2025)

An $Ω( (\log n / \log \log n)^2 )$ Cell-Probe Lower Bound for Dynamic Boolean Data Structures
von: Ko, Young Kun
Veröffentlicht: (2026)

Dequantizing Short-Path Quantum Algorithms
von: Gall, François Le, et al.
Veröffentlicht: (2026)

Unstructured Adiabatic Quantum Optimization: Optimality with Limitations
von: Braida, Arthur, et al.
Veröffentlicht: (2024)

Quantum Channel Testing in Average-Case Distance
von: Rosenthal, Gregory, et al.
Veröffentlicht: (2024)

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

Quantum Property Testing for Bounded-Degree Directed Graphs
von: Peng, Pan, et al.
Veröffentlicht: (2026)

Quantum Property Testing Algorithm for the Concatenation of Two Palindromes Language
von: Khadiev, Kamil, et al.
Veröffentlicht: (2024)

Simulation of Non-Hermitian Hamiltonians with Bivariate Quantum Signal Processing
von: Courtney, Joshua M.
Veröffentlicht: (2026)

Quantum Worst-Case to Average-Case Reduction for Matrix-Vector Multiplication
von: Aggarwal, Divesh, et al.
Veröffentlicht: (2025)

Quantum Algorithm for Finding the Optimal Variable Ordering for Binary Decision Diagrams
von: Tani, Seiichiro
Veröffentlicht: (2019)

Optimal Bounds, Barriers, and Extensions for Non-Hermitian Bivariate Quantum Signal Processing
von: Courtney, Joshua M.
Veröffentlicht: (2026)

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

Average-Case Complexity of Quantum Stabilizer Decoding
von: Khesin, Andrey Boris, 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)

Max-Cut with $ε$-Accurate Predictions
von: Cohen-Addad, Vincent, et al.
Veröffentlicht: (2024)

On estimating the trace of quantum state powers
von: Liu, Yupan, et al.
Veröffentlicht: (2024)

On estimating the quantum $\ell_α$ distance
von: Liu, Yupan, et al.
Veröffentlicht: (2025)

Algorithmic Cluster Expansions for Quantum Problems
von: Mann, Ryan L., et al.
Veröffentlicht: (2023)

Fine-Grained Complexity of Continuous Euclidean k-Center
von: Blank, Lotte, et al.
Veröffentlicht: (2026)

Fine-Grained Classification Of Detecting Dominating Patterns
von: Dransfeld, Jonathan, et al.
Veröffentlicht: (2025)

Efficient Algorithms for Weakly-Interacting Quantum Spin Systems
von: Mann, Ryan L., et al.
Veröffentlicht: (2026)

Gibbs state preparation for commuting Hamiltonian: Mapping to classical Gibbs sampling
von: Hwang, Yeongwoo, et al.
Veröffentlicht: (2024)

Positive bias makes tensor-network contraction tractable
von: Jiang, Jiaqing, et al.
Veröffentlicht: (2024)

Locality Bounds for Sampling Hamming Slices
von: Kane, Daniel M., et al.
Veröffentlicht: (2024)

Single-copy stabilizer testing
von: Hinsche, Marcel, et al.
Veröffentlicht: (2024)

Testing and learning structured quantum Hamiltonians
von: Arunachalam, Srinivasan, et al.
Veröffentlicht: (2024)