Imagen de Portada

A Note on the Complexity of the Spectral Gap Problem

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autor principal:	Yirka, Justin
Formato:	Preprint
Publicado:	2025
Materias:	Quantum Physics Computational Complexity
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Even quantum advice is unlikely to solve PP
por: Yirka, Justin
Publicado: (2024)

Complexity Classification of Product State Problems for Local Hamiltonians
por: Kallaugher, John, et al.
Publicado: (2024)

The Entangled Quantum Polynomial Hierarchy Collapses
por: Grewal, Sabee, et al.
Publicado: (2024)

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

Complexity Theory for Quantum Promise Problems
por: Chia, Nai-Hui, et al.
Publicado: (2024)

On the Complexity of the Succinct State Local Hamiltonian Problem
por: Waite, Gabriel, et al.
Publicado: (2025)

A Cautionary Note on Quantum Oracles
por: Agarwal, Avantika, et al.
Publicado: (2025)

Complexity of the Guided Local Hamiltonian Problem: Improved Parameters and Extension to Excited States
por: Cade, Chris, et al.
Publicado: (2022)

Unitary Complexity and the Uhlmann Transformation Problem
por: Bostanci, John, et al.
Publicado: (2023)

Quantum Complexity vs Classical Complexity: A Survey
por: Vaezi, Arash, et al.
Publicado: (2023)

A Brief Introduction to Quantum Query Complexity
por: Hamoudi, Yassine
Publicado: (2025)

A Lifting Theorem for Hybrid Classical-Quantum Communication Complexity
por: Wu, Xudong, et al.
Publicado: (2025)

On the Complexity of Decoded Quantum Interferometry
por: Marwaha, Kunal, et al.
Publicado: (2025)

The Complexity of Stoquastic Sparse Hamiltonians
por: Grilo, Alex B., et al.
Publicado: (2026)

Bosonic Quantum Computational Complexity
por: Chabaud, Ulysse, et al.
Publicado: (2024)

A Note on Quantum-Secure PRPs
por: Zhandry, Mark
Publicado: (2016)

A Qubit, a Coin, and an Advice String Walk Into a Relational Problem
por: Aaronson, Scott, et al.
Publicado: (2023)

The Guided Local Hamiltonian Problem for Stoquastic Hamiltonians
por: Waite, Gabriel
Publicado: (2025)

Quantum k-SAT Related Hypergraph Problems
por: Kremer, Simon-Luca, et al.
Publicado: (2025)

Complexity and hardness of random peaked circuits
por: Zhang, Yuxuan
Publicado: (2025)

The Communication Complexity of Approximating Matrix Rank
por: Sherstov, Alexander A., et al.
Publicado: (2024)

Tight Bounds for Quantum Phase Estimation and Related Problems
por: Mande, Nikhil S., et al.
Publicado: (2023)

Improved Hardness Results for the Guided Local Hamiltonian Problem
por: Cade, Chris, et al.
Publicado: (2022)

The Complexity of Local Stoquastic Hamiltonians on 2D Lattices
por: Waite, Gabriel, et al.
Publicado: (2025)

Computational Complexity and Simulability of Non-Hermitian Quantum Dynamics
por: Barch, Brian, et al.
Publicado: (2025)

On the Pure Quantum Polynomial Hierarchy and Quantified Hamiltonian Complexity
por: Grewal, Sabee, et al.
Publicado: (2025)

Fine-Grained Complexity via Quantum Natural Proofs
por: Chen, Yanlin, et al.
Publicado: (2025)

Quantum and Classical Communication Complexity of Permutation-Invariant Functions
por: Guan, Ziyi, et al.
Publicado: (2023)

Why Philosophers Should Care About Computational Complexity
por: Aaronson, Scott
Publicado: (2011)

On the Complexity of Pure-State Consistency of Local Density Matrices
por: Kamminga, Jonas, et al.
Publicado: (2024)

Virtual Qudits for Simon's Problem: Dimension-Lifted Algorithms on Qubit Hardware
por: Semre, Abed, et al.
Publicado: (2025)

Maximum Separation of Quantum Communication Complexity With and Without Shared Entanglement
por: Hasegawa, Atsuya, et al.
Publicado: (2025)

Quantum SAT Problems with Finite Sets of Projectors are Complete for a Plethora of Classes
por: Cardoso, Ricardo Rivera, et al.
Publicado: (2025)

Complexity-theoretic foundations of BosonSampling with a linear number of modes
por: Bouland, Adam, et al.
Publicado: (2023)

Guidable Local Hamiltonian Problems with Implications to Heuristic Ansätze State Preparation and the Quantum PCP Conjecture
por: Weggemans, Jordi, et al.
Publicado: (2023)

Quantum State Synthesis: Relation with Decision Complexity Classes and Impossibility of Synthesis Error Reduction
por: Delavenne, Hugo, et al.
Publicado: (2024)

Complexity of Contextuality
por: Yianni, Theodoros, et al.
Publicado: (2025)

A Note on Output Length of One-Way State Generators and EFIs
por: Hhan, Minki, et al.
Publicado: (2023)

Complexity of Quadratic Bosonic Hamiltonian Simulation: $\mathsf{BQP}$-Completeness and $\mathsf{PostBQP}$-Hardness
por: Zschetzsche, Lilith, et al.
Publicado: (2026)

On the Computational Complexity of Schrödinger Operators
por: Zheng, Yufan, et al.
Publicado: (2024)