Cover Image

On the Pauli Spectrum of QAC0

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Nadimpalli, Shivam, Parham, Natalie, Vasconcelos, Francisca, Yuen, Henry
Format:	Preprint
Published:	2023
Subjects:	Quantum Physics Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Random Unitaries in Constant (Quantum) Time
by: Foxman, Ben, et al.
Published: (2025)

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

Parity $\notin$ QAC0 $\iff$ QAC0 is Fourier-Concentrated
by: Gretta, Lucas, et al.
Published: (2026)

Magic and communication complexity
by: Girish, Uma, et al.
Published: (2025)

Low-degree approximation of QAC$^0$ circuits
by: Montanaro, Ashley, et al.
Published: (2024)

Quantum circuit lower bounds in the magic hierarchy
by: Parham, Natalie
Published: (2025)

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

Learning junta distributions, quantum junta states, and QAC$^0$ circuits
by: Bao, Jinge, et al.
Published: (2024)

Unconditional Quantum Advantage for Sampling with Shallow Circuits
by: Watts, Adam Bene, et al.
Published: (2023)

Constant-Depth Unitary Preparation of Dicke States
by: Joshi, Malvika Raj, et al.
Published: (2026)

QMA vs. QCMA and Pseudorandomness
by: Liu, Jiahui, et al.
Published: (2024)

Hardness results for decoding the surface code with Pauli noise
by: Fischer, Alex, et al.
Published: (2023)

Pauli Measurements Are Near-Optimal for Single-Qubit Tomography
by: Acharya, Jayadev, et al.
Published: (2025)

Efficient approximate unitary designs from random Pauli rotations
by: Haah, Jeongwan, et al.
Published: (2024)

Tight bounds on depth-2 QAC-circuits computing parity
by: Fenner, Stephen, et al.
Published: (2025)

An efficient quantum parallel repetition theorem and applications
by: Bostanci, John, et al.
Published: (2023)

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

Efficient simulation of parametrized quantum circuits under non-unital noise through Pauli backpropagation
by: Martinez, Victor, et al.
Published: (2025)

Unitary Complexity and the Uhlmann Transformation Problem
by: Bostanci, John, et al.
Published: (2023)

Two bases suffice for QMA1-completeness
by: Ma, Henry, et al.
Published: (2025)

No Price Tags? No Problem: Query Strategies for Unpriced Information
by: Nadimpalli, Shivam, 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)

Efficient Pauli channel estimation with logarithmic quantum memory
by: Chen, Sitan, et al.
Published: (2023)

Detecting Low-Degree Truncation
by: De, Anindya, et al.
Published: (2024)

Testing Convex Truncation
by: De, Anindya, et al.
Published: (2023)

Quantum Automating $\mathbf{TC}^0$-Frege Is LWE-Hard
by: Arteche, Noel, et al.
Published: (2024)

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

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

Some Implications of the Independence Postulate for Physics
by: Epstein, Samuel
Published: (2023)

Quantum and Classical Communication Complexity of Permutation-Invariant Functions
by: Guan, Ziyi, et al.
Published: (2023)

Hamiltonians whose low-energy states require $Ω(n)$ T gates
by: Coble, Nolan J., et al.
Published: (2023)

On the exact quantum query complexity of $\text{MOD}_m^n$ and $\text{EXACT}_{k,l}^n$
by: Yao, Penghui, et al.
Published: (2023)

Quantum Merlin-Arthur proof systems for synthesizing quantum states
by: Delavenne, Hugo, et al.
Published: (2023)

The Computational Advantage of MIP* Vanishes in the Presence of Noise
by: Dong, Yangjing, et al.
Published: (2023)

An Efficient Quantum Factoring Algorithm
by: Regev, Oded
Published: (2023)

Trade-offs between Entanglement and Communication
by: Arunachalam, Srinivasan, et al.
Published: (2023)

Optimising quantum circuits is generally hard
by: van de Wetering, John, et al.
Published: (2023)

Quantum and classical query complexities of functions of matrices
by: Montanaro, Ashley, et al.
Published: (2023)

Free Fermion Distributions Are Hard to Learn
by: Nietner, Alexander
Published: (2023)

On the Rational Degree of Boolean Functions and Applications
by: Iyer, Vishnu, et al.
Published: (2023)