Buchumschlag

Improved Lower Bounds for QAC0

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Joshi, Malvika Raj, Tal, Avishay, Vasconcelos, Francisca, Wright, John
Format:	Preprint
Veröffentlicht:	2025
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

Parity $\notin$ QAC0 $\iff$ QAC0 is Fourier-Concentrated
von: Gretta, Lucas, et al.
Veröffentlicht: (2026)

Constant-Depth Unitary Preparation of Dicke States
von: Joshi, Malvika Raj, et al.
Veröffentlicht: (2026)

On the Pauli Spectrum of QAC0
von: Nadimpalli, Shivam, et al.
Veröffentlicht: (2023)

Low-degree approximation of QAC$^0$ circuits
von: Montanaro, Ashley, et al.
Veröffentlicht: (2024)

$\mathsf{QAC}^0$ Contains $\mathsf{TC}^0$ (with Many Copies of the Input)
von: Grier, Daniel, et al.
Veröffentlicht: (2026)

Learning junta distributions, quantum junta states, and QAC$^0$ circuits
von: Bao, Jinge, et al.
Veröffentlicht: (2024)

A Relativizing MIP for BQP
von: Aaronson, Scott, et al.
Veröffentlicht: (2026)

Quantum-Computable One-Way Functions without One-Way Functions
von: Kretschmer, William, et al.
Veröffentlicht: (2024)

Shrinkage under Random Projections, and Cubic Formula Lower Bounds for $\mathsf{AC}^0$
von: Filmus, Yuval, et al.
Veröffentlicht: (2020)

Quantum Cryptography in Algorithmica
von: Kretschmer, William, et al.
Veröffentlicht: (2022)

Improved Circuit Lower Bounds and Quantum-Classical Separations
von: Grewal, Sabee, et al.
Veröffentlicht: (2024)

Lower Bounds for Unitary Property Testing with Proofs and Advice
von: Weggemans, Jordi
Veröffentlicht: (2024)

Random Unitaries in Constant (Quantum) Time
von: Foxman, Ben, et al.
Veröffentlicht: (2025)

Lower Bounds on Relative Error Quantum Compression and Classical Shadows
von: Sankar, Kaushik
Veröffentlicht: (2025)

Quantum Query-Space Lower Bounds Using Branching Programs
von: Bera, Debajyoti, et al.
Veröffentlicht: (2024)

Tight Quantum Depth Lower Bound for Solving Systems of Linear Equations
von: Wang, Qisheng, et al.
Veröffentlicht: (2024)

Tight bounds on depth-2 QAC-circuits computing parity
von: Fenner, Stephen, et al.
Veröffentlicht: (2025)

Improved Quantum Query Upper Bounds Based on Classical Decision Trees
von: Cornelissen, Arjan, et al.
Veröffentlicht: (2022)

On Bounded Advice Classes
von: Marshall, Simon, et al.
Veröffentlicht: (2024)

New Lower-bounds for Quantum Computation with Non-Collapsing Measurements
von: Miloschewsky, David, et al.
Veröffentlicht: (2024)

Lower bounds for quantum-inspired classical algorithms via communication complexity
von: Mande, Nikhil S., et al.
Veröffentlicht: (2024)

Quadratic Lower bounds on the Approximate Stabilizer Rank: A Probabilistic Approach
von: Mehraban, Saeed, et al.
Veröffentlicht: (2023)

Bounding the computational power of bosonic systems
von: Upreti, Varun, et al.
Veröffentlicht: (2025)

Lower Bounds for Learning Quantum States with Single-Copy Measurements
von: Lowe, Angus, et al.
Veröffentlicht: (2022)

Bounds on Eventually Universal Quantum Gate Sets
von: Karamchedu, Chaitanya, et al.
Veröffentlicht: (2025)

Certificate Games and Consequences for the Classical Adversary Bound
von: Chakraborty, Sourav, et al.
Veröffentlicht: (2022)

Entanglement-Dependent Error Bounds for Hamiltonian Simulation
von: Kulkarni, Prateek P.
Veröffentlicht: (2026)

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

Quantum Lovász Local Lemma: Shearer's Bound is Tight
von: He, Kun, et al.
Veröffentlicht: (2018)

Amplitude amplification and estimation require inverses
von: Tang, Ewin, et al.
Veröffentlicht: (2025)

Are controlled unitaries helpful?
von: Tang, Ewin, et al.
Veröffentlicht: (2025)

Query and Depth Upper Bounds for Quantum Unitaries via Grover Search
von: Rosenthal, Gregory
Veröffentlicht: (2021)

Improved quantum data analysis
von: Bădescu, Costin, et al.
Veröffentlicht: (2020)

Lower Bounds against the Ideal Proof System in Finite Fields
von: Elbaz, Tal, et al.
Veröffentlicht: (2025)

Optimal lower bounds for quantum state tomography
von: Scharnhorst, Thilo, et al.
Veröffentlicht: (2025)

Conjugate queries can help
von: Tang, Ewin, et al.
Veröffentlicht: (2025)

Improved Hardness Results for the Guided Local Hamiltonian Problem
von: Cade, Chris, et al.
Veröffentlicht: (2022)

Improved separation between quantum and classical computers for sampling and functional tasks
von: Marshall, Simon C., et al.
Veröffentlicht: (2024)

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

Beating full state tomography for unentangled spectrum estimation
von: Pelecanos, Angelos, et al.
Veröffentlicht: (2025)