Cover Image

Oracle Separation between Noisy Quantum Polynomial Time and the Polynomial Hierarchy

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Chia, Nai-Hui, Hsieh, Min-Hsiu, Hung, Shih-Han, Kuo, En-Jui
Format:	Preprint
Published:	2024
Subjects:	Quantum Physics Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Oracle Separations for the Quantum-Classical Polynomial Hierarchy
by: Agarwal, Avantika, et al.
Published: (2024)

Efficient Matrix Product State Learning in Logarithmic Depth
by: Lin, Chia-Ying, et al.
Published: (2025)

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

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

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

Polynomial-Time Classical Simulation of Noisy Quantum Circuits with Naturally Fault-Tolerant Gates
by: Nelson, Jon, et al.
Published: (2024)

Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower bounds
by: Agarwal, Avantika, et al.
Published: (2024)

On the Need for Large Quantum Depth
by: Chia, Nai-Hui, et al.
Published: (2019)

Polynomial-Time Classical Simulation of Noisy IQP Circuits with Constant Depth
by: Rajakumar, Joel, et al.
Published: (2024)

Classically Sampling Noisy Quantum Circuits in Quasi-Polynomial Time under Approximate Markovianity
by: Zhang, Yifan F., et al.
Published: (2025)

Hardness of Quantum Distribution Learning and Quantum Cryptography
by: Hiroka, Taiga, et al.
Published: (2025)

A Schematic Definition of Quantum Polynomial Time Computability
by: Yamakami, Tomoyuki
Published: (2018)

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)

Unconditionally separating noisy $\mathsf{QNC}^0$ from bounded polynomial threshold circuits of constant depth
by: Hsieh, Min-Hsiu, et al.
Published: (2024)

Toward Separating QMA from QCMA with a Classical Oracle
by: Zhandry, Mark
Published: (2024)

Quantum Interactive Oracle Proofs
by: Sun, Baocheng, et al.
Published: (2026)

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

Cryptographic Conditions for Efficient Testing of Distributions and Quantum States
by: Cavalar, Bruno, et al.
Published: (2025)

En Route to a Standard QMA1 vs. QCMA Oracle Separation
by: Miloschewsky, David, et al.
Published: (2026)

Shadow Tomography Against Adversaries
by: Aliakbarpour, Maryam, et al.
Published: (2025)

Adversarially robust quantum state learning and testing
by: Aliakbarpour, Maryam, et al.
Published: (2025)

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

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

Fourier Spectrum of Noisy Quantum Algorithms
by: Girish, Uma
Published: (2025)

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

Reordering Method and Hierarchies for Quantum and Classical Ordered Binary Decision Diagrams
by: Khadiev, Kamil, et al.
Published: (2017)

Oracle separation of QMA and QCMA with bounded adaptivity
by: Ben-David, Shalev, et al.
Published: (2024)

Polynomial-time tolerant testing stabilizer states
by: Arunachalam, Srinivasan, et al.
Published: (2024)

Separating Quantum and Classical Advice with Good Codes
by: Bostanci, John, et al.
Published: (2026)

Reachability Constraints in Variational Quantum Circuits: Optimization within Polynomial Group Module
by: Oh, Yun-Tak, et al.
Published: (2026)

Improved Circuit Lower Bounds and Quantum-Classical Separations
by: Grewal, Sabee, et al.
Published: (2024)

Coherence in Property Testing: Quantum-Classical Collapses and Separations
by: Jeronimo, Fernando Granha, et al.
Published: (2024)

Exponential Separation Criteria for Quantum Iterative Power Algorithms
by: Czégel, András, et al.
Published: (2025)

Classical vs Quantum Advice and Proofs under Classically-Accessible Oracle
by: Li, Xingjian, et al.
Published: (2023)

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

Quantum versus Classical Separation in Simultaneous Number-on-Forehead Communication
by: Yang, Guangxu, et al.
Published: (2025)

Exponential Separation of Quantum and Classical One-Way Numbers-on-Forehead Communication
by: Yang, Guangxu, et al.
Published: (2026)

Polynomial time classical versus quantum algorithms for representation theoretic multiplicities
by: Panova, Greta
Published: (2025)

Strict Hierarchy for Quantum Channel Certification to Unitary
by: Chen, Kean, et al.
Published: (2026)

Elementary Quantum Recursion Schemes That Capture Quantum Polylogarithmic Time Computability of Quantum Functions
by: Yamakami, Tomoyuki
Published: (2023)