Buchumschlag

Complexity Theory for Quantum Promise Problems

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Chia, Nai-Hui, Chung, Kai-Min, Huang, Tzu-Hsiang, Shih, Jhih-Wei
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Quantum Physics Computational Complexity
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

On the Need for Large Quantum Depth
von: Chia, Nai-Hui, et al.
Veröffentlicht: (2019)

Oracle Separation between Noisy Quantum Polynomial Time and the Polynomial Hierarchy
von: Chia, Nai-Hui, et al.
Veröffentlicht: (2024)

Efficient Matrix Product State Learning in Logarithmic Depth
von: Lin, Chia-Ying, et al.
Veröffentlicht: (2025)

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

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)

Shadow Tomography Against Adversaries
von: Aliakbarpour, Maryam, et al.
Veröffentlicht: (2025)

Adversarially robust quantum state learning and testing
von: Aliakbarpour, Maryam, et al.
Veröffentlicht: (2025)

Quantum and Classical Communication Complexity of Permutation-Invariant Functions
von: Guan, Ziyi, et al.
Veröffentlicht: (2023)

On the Complexity of the Succinct State Local Hamiltonian Problem
von: Waite, Gabriel, et al.
Veröffentlicht: (2025)

A Note on the Complexity of the Spectral Gap Problem
von: Yirka, Justin
Veröffentlicht: (2025)

Quantum Complexity vs Classical Complexity: A Survey
von: Vaezi, Arash, et al.
Veröffentlicht: (2023)

Complexity Classification of Product State Problems for Local Hamiltonians
von: Kallaugher, John, et al.
Veröffentlicht: (2024)

Bosonic Quantum Computational Complexity
von: Chabaud, Ulysse, et al.
Veröffentlicht: (2024)

On the Complexity of Decoded Quantum Interferometry
von: Marwaha, Kunal, et al.
Veröffentlicht: (2025)

Quantum k-SAT Related Hypergraph Problems
von: Kremer, Simon-Luca, et al.
Veröffentlicht: (2025)

A Brief Introduction to Quantum Query Complexity
von: Hamoudi, Yassine
Veröffentlicht: (2025)

Tight Bounds for Quantum Phase Estimation and Related Problems
von: Mande, Nikhil S., et al.
Veröffentlicht: (2023)

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

Computational Complexity and Simulability of Non-Hermitian Quantum Dynamics
von: Barch, Brian, et al.
Veröffentlicht: (2025)

On the Pure Quantum Polynomial Hierarchy and Quantified Hamiltonian Complexity
von: Grewal, Sabee, et al.
Veröffentlicht: (2025)

Fine-Grained Complexity via Quantum Natural Proofs
von: Chen, Yanlin, et al.
Veröffentlicht: (2025)

Maximum Separation of Quantum Communication Complexity With and Without Shared Entanglement
von: Hasegawa, Atsuya, et al.
Veröffentlicht: (2025)

A Lifting Theorem for Hybrid Classical-Quantum Communication Complexity
von: Wu, Xudong, et al.
Veröffentlicht: (2025)

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

Unitary Complexity and the Uhlmann Transformation Problem
von: Bostanci, John, et al.
Veröffentlicht: (2023)

Quantum State Synthesis: Relation with Decision Complexity Classes and Impossibility of Synthesis Error Reduction
von: Delavenne, Hugo, et al.
Veröffentlicht: (2024)

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

The Subgraph Isomorphism Problem for Port Graphs and Quantum Circuits
von: Mondada, Luca, et al.
Veröffentlicht: (2023)

Separating Quantum and Classical Advice with Good Codes
von: Bostanci, John, et al.
Veröffentlicht: (2026)

Unconditional Pseudorandomness against Shallow Quantum Circuits
von: Ghosh, Soumik, et al.
Veröffentlicht: (2025)

Quantum Pseudorandomness and Classical Complexity
von: Kretschmer, William
Veröffentlicht: (2021)

Chemically Motivated Simulation Problems are Efficiently Solvable by a Quantum Computer
von: Schleich, Philipp, et al.
Veröffentlicht: (2024)

Anti-Concentration for the Unitary Haar Measure and Applications to Random Quantum Circuits
von: Fefferman, Bill, et al.
Veröffentlicht: (2024)

A Meta-Complexity Characterization of Quantum Cryptography
von: Cavalar, Bruno P., et al.
Veröffentlicht: (2024)

Accessible Quantum Correlations Under Complexity Constraints
von: Yángüez, Álvaro, et al.
Veröffentlicht: (2026)

New Approaches to Complexity via Quantum Graphs
von: Culf, Eric, et al.
Veröffentlicht: (2023)

Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom
von: Grewal, Sabee, et al.
Veröffentlicht: (2022)

The Complexity of Stoquastic Sparse Hamiltonians
von: Grilo, Alex B., et al.
Veröffentlicht: (2026)

Hardness of Quantum Distribution Learning and Quantum Cryptography
von: Hiroka, Taiga, et al.
Veröffentlicht: (2025)

The Guided Local Hamiltonian Problem for Stoquastic Hamiltonians
von: Waite, Gabriel
Veröffentlicht: (2025)