Image de couverture de livre

Oracle Separation between Noisy Quantum Polynomial Time and the Polynomial Hierarchy

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Chia, Nai-Hui, Hsieh, Min-Hsiu, Hung, Shih-Han, Kuo, En-Jui
Format:	Preprint
Publié:	2024
Sujets:	Quantum Physics Computational Complexity
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Oracle Separations for the Quantum-Classical Polynomial Hierarchy
par: Agarwal, Avantika, et autres
Publié: (2024)

Efficient Matrix Product State Learning in Logarithmic Depth
par: Lin, Chia-Ying, et autres
Publié: (2025)

The Entangled Quantum Polynomial Hierarchy Collapses
par: Grewal, Sabee, et autres
Publié: (2024)

On the Pure Quantum Polynomial Hierarchy and Quantified Hamiltonian Complexity
par: Grewal, Sabee, et autres
Publié: (2025)

Complexity Theory for Quantum Promise Problems
par: Chia, Nai-Hui, et autres
Publié: (2024)

Polynomial-Time Classical Simulation of Noisy Quantum Circuits with Naturally Fault-Tolerant Gates
par: Nelson, Jon, et autres
Publié: (2024)

Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower bounds
par: Agarwal, Avantika, et autres
Publié: (2024)

On the Need for Large Quantum Depth
par: Chia, Nai-Hui, et autres
Publié: (2019)

Polynomial-Time Classical Simulation of Noisy IQP Circuits with Constant Depth
par: Rajakumar, Joel, et autres
Publié: (2024)

Classically Sampling Noisy Quantum Circuits in Quasi-Polynomial Time under Approximate Markovianity
par: Zhang, Yifan F., et autres
Publié: (2025)

Hardness of Quantum Distribution Learning and Quantum Cryptography
par: Hiroka, Taiga, et autres
Publié: (2025)

A Schematic Definition of Quantum Polynomial Time Computability
par: Yamakami, Tomoyuki
Publié: (2018)

3-Local Hamiltonian Problem and Constant Relative Error Quantum Partition Function Approximation: $O(2^{\frac{n}{2}})$ Algorithm Is Nearly Optimal under QSETH
par: Chia, Nai-Hui, et autres
Publié: (2025)

Unconditionally separating noisy $\mathsf{QNC}^0$ from bounded polynomial threshold circuits of constant depth
par: Hsieh, Min-Hsiu, et autres
Publié: (2024)

Toward Separating QMA from QCMA with a Classical Oracle
par: Zhandry, Mark
Publié: (2024)

Quantum Interactive Oracle Proofs
par: Sun, Baocheng, et autres
Publié: (2026)

A Cautionary Note on Quantum Oracles
par: Agarwal, Avantika, et autres
Publié: (2025)

Cryptographic Conditions for Efficient Testing of Distributions and Quantum States
par: Cavalar, Bruno, et autres
Publié: (2025)

En Route to a Standard QMA1 vs. QCMA Oracle Separation
par: Miloschewsky, David, et autres
Publié: (2026)

Shadow Tomography Against Adversaries
par: Aliakbarpour, Maryam, et autres
Publié: (2025)

Adversarially robust quantum state learning and testing
par: Aliakbarpour, Maryam, et autres
Publié: (2025)

Fine-Grained Complexity for Quantum Problems from Size-Preserving Circuit-to-Hamiltonian Constructions
par: Chia, Nai-Hui, et autres
Publié: (2026)

Nonuniform Families of Polynomial-Size Quantum Finite Automata and Quantum Logarithmic-Space Computation with Polynomial-Size Advice
par: Yamakami, Tomoyuki
Publié: (2019)

Fourier Spectrum of Noisy Quantum Algorithms
par: Girish, Uma
Publié: (2025)

Quantum Algorithms for Gowers Norm Estimation, Polynomial Testing, and Arithmetic Progression Counting over Finite Abelian Groups
par: Kuo, En-Jui
Publié: (2025)

Reordering Method and Hierarchies for Quantum and Classical Ordered Binary Decision Diagrams
par: Khadiev, Kamil, et autres
Publié: (2017)

Oracle separation of QMA and QCMA with bounded adaptivity
par: Ben-David, Shalev, et autres
Publié: (2024)

Polynomial-time tolerant testing stabilizer states
par: Arunachalam, Srinivasan, et autres
Publié: (2024)

Separating Quantum and Classical Advice with Good Codes
par: Bostanci, John, et autres
Publié: (2026)

Reachability Constraints in Variational Quantum Circuits: Optimization within Polynomial Group Module
par: Oh, Yun-Tak, et autres
Publié: (2026)

Improved Circuit Lower Bounds and Quantum-Classical Separations
par: Grewal, Sabee, et autres
Publié: (2024)

Coherence in Property Testing: Quantum-Classical Collapses and Separations
par: Jeronimo, Fernando Granha, et autres
Publié: (2024)

Exponential Separation Criteria for Quantum Iterative Power Algorithms
par: Czégel, András, et autres
Publié: (2025)

Classical vs Quantum Advice and Proofs under Classically-Accessible Oracle
par: Li, Xingjian, et autres
Publié: (2023)

Maximum Separation of Quantum Communication Complexity With and Without Shared Entanglement
par: Hasegawa, Atsuya, et autres
Publié: (2025)

Quantum versus Classical Separation in Simultaneous Number-on-Forehead Communication
par: Yang, Guangxu, et autres
Publié: (2025)

Exponential Separation of Quantum and Classical One-Way Numbers-on-Forehead Communication
par: Yang, Guangxu, et autres
Publié: (2026)

Polynomial time classical versus quantum algorithms for representation theoretic multiplicities
par: Panova, Greta
Publié: (2025)

Strict Hierarchy for Quantum Channel Certification to Unitary
par: Chen, Kean, et autres
Publié: (2026)

Elementary Quantum Recursion Schemes That Capture Quantum Polylogarithmic Time Computability of Quantum Functions
par: Yamakami, Tomoyuki
Publié: (2023)