Cover Image

On Bounded Advice Classes

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Marshall, Simon, Gyurik, Casper, Dunjko, Vedran
Format:	Preprint
Published:	2024
Subjects:	Computational Complexity Quantum Physics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Computational complexity of the homology problem with orientable filtration: MA-completeness
by: Hayakawa, Ryu, et al.
Published: (2025)

Quantum computing and persistence in topological data analysis
by: Gyurik, Casper, et al.
Published: (2024)

Improved separation between quantum and classical computers for sampling and functional tasks
by: Marshall, Simon C., et al.
Published: (2024)

Exponential separations between classical and quantum learners
by: Gyurik, Casper, et al.
Published: (2023)

Exponential quantum advantages in learning quantum observables from classical data
by: Molteni, Riccardo, et al.
Published: (2024)

Testing the presence of balanced and bipartite components in a sparse graph is QMA1-hard
by: Incudini, Massimiliano, et al.
Published: (2024)

Shadows of quantum machine learning
by: Jerbi, Sofiene, et al.
Published: (2023)

Lower Bounds for Unitary Property Testing with Proofs and Advice
by: Weggemans, Jordi
Published: (2024)

Uncloneable Quantum Advice
by: Broadbent, Anne, et al.
Published: (2023)

On the relation between trainability and dequantization of variational quantum learning models
by: Gil-Fuster, Elies, et al.
Published: (2024)

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

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

PDQMA = DQMA = NEXP: QMA With Hidden Variables and Non-collapsing Measurements
by: Aaronson, Scott, et al.
Published: (2024)

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

Quantum machine learning advantages beyond hardness of evaluation
by: Molteni, Riccardo, et al.
Published: (2025)

Improved Lower Bounds for QAC0
by: Joshi, Malvika Raj, et al.
Published: (2025)

Bounding the computational power of bosonic systems
by: Upreti, Varun, et al.
Published: (2025)

Bounds on Eventually Universal Quantum Gate Sets
by: Karamchedu, Chaitanya, et al.
Published: (2025)

Certificate Games and Consequences for the Classical Adversary Bound
by: Chakraborty, Sourav, et al.
Published: (2022)

Entanglement-Dependent Error Bounds for Hamiltonian Simulation
by: Kulkarni, Prateek P.
Published: (2026)

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

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

Quantum Lovász Local Lemma: Shearer's Bound is Tight
by: He, Kun, et al.
Published: (2018)

Quantum Query-Space Lower Bounds Using Branching Programs
by: Bera, Debajyoti, et al.
Published: (2024)

Lower Bounds on Relative Error Quantum Compression and Classical Shadows
by: Sankar, Kaushik
Published: (2025)

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

Tight Quantum Depth Lower Bound for Solving Systems of Linear Equations
by: Wang, Qisheng, et al.
Published: (2024)

Query and Depth Upper Bounds for Quantum Unitaries via Grover Search
by: Rosenthal, Gregory
Published: (2021)

Improved Quantum Query Upper Bounds Based on Classical Decision Trees
by: Cornelissen, Arjan, et al.
Published: (2022)

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

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

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

The Round Complexity of Proofs in the Bounded Quantum Storage Model
by: Grilo, Alex B., et al.
Published: (2024)

Generalization Error Bound for Quantum Machine Learning in NISQ Era -- A Survey
by: Khanal, Bikram, et al.
Published: (2024)

A List of Complexity Bounds for Property Testing by Quantum Sample-to-Query Lifting
by: Chen, Kean, et al.
Published: (2025)

Locality Bounds for Sampling Hamming Slices
by: Kane, Daniel M., et al.
Published: (2024)

Quantum Property Testing for Bounded-Degree Directed Graphs
by: Peng, Pan, et al.
Published: (2026)

Optimal Bounds, Barriers, and Extensions for Non-Hermitian Bivariate Quantum Signal Processing
by: Courtney, Joshua M.
Published: (2026)

Commuting Local Hamiltonians Beyond 2D
by: Bostanci, John, et al.
Published: (2024)

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