Imagen de Portada

$\mathsf{QAC}^0$ Contains $\mathsf{TC}^0$ (with Many Copies of the Input)

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Grier, Daniel, Morris, Jackson, Wu, Kewen
Formato:	Preprint
Publicado:	2026
Materias:	Computational Complexity Quantum Physics
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

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

Quantum Advantage from Sampling Shallow Circuits: Beyond Hardness of Marginals
por: Grier, Daniel, et al.
Publicado: (2025)

Quantum Threshold is Powerful
por: Grier, Daniel, et al.
Publicado: (2024)

On the Pauli Spectrum of QAC0
por: Nadimpalli, Shivam, et al.
Publicado: (2023)

Complexity of Quadratic Bosonic Hamiltonian Simulation: $\mathsf{BQP}$-Completeness and $\mathsf{PostBQP}$-Hardness
por: Zschetzsche, Lilith, et al.
Publicado: (2026)

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

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

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

Towards a universal gateset for $\mathsf{QMA}_1$
por: Rudolph, Dorian
Publicado: (2024)

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

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

Perfect diffusion is $\mathsf{TC}^0$ -- Bad diffusion is Turing-complete
por: Liu, Yuxi
Publicado: (2025)

Quantum 2-SAT on low dimensional systems is $\mathsf{QMA}_1$-complete: Direct embeddings and black-box simulation
por: Rudolph, Dorian, et al.
Publicado: (2024)

Search versus Decision for $\mathsf{S}_2^\mathsf{P}$
por: Fortnow, Lance
Publicado: (2025)

From Worst-Case Hardness of $\mathsf{NP}$ to Quantum Cryptography via Quantum Indistinguishability Obfuscation
por: Morimae, Tomoyuki, et al.
Publicado: (2025)

On Condensation of Block Sensitivity, Certificate Complexity and the $\mathsf{AND}$ (and $\mathsf{OR}$) Decision Tree Complexity
por: Nalli, Sai Soumya, et al.
Publicado: (2026)

The $\mathsf{AC}^0$-Complexity Of Visibly Pushdown Languages
por: Göller, Stefan, et al.
Publicado: (2023)

Total Search Problems in $\mathsf{ZPP}$
por: Fleming, Noah, et al.
Publicado: (2025)

Fast simulation of planar Clifford circuits
por: Gosset, David, et al.
Publicado: (2020)

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

Complexity-theoretic foundations of BosonSampling with a linear number of modes
por: Bouland, Adam, et al.
Publicado: (2023)

Total Variation Distance for Product Distributions is $\#\mathsf{P}$-Complete
por: Bhattacharyya, Arnab, et al.
Publicado: (2024)

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

(Sub)Exponential Quantum Speedup for Optimization
por: Leng, Jiaqi, et al.
Publicado: (2025)

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

On the Unprovability of Circuit Size Bounds in Intuitionistic $\mathsf{S}^1_2$
por: Chen, Lijie, et al.
Publicado: (2024)

Extensively Not P-Bi-Immune promiseBQP-Complete Languages
por: Jackson, Andrew
Publicado: (2024)

No exponential quantum speedup for $\mathrm{SIS}^\infty$ anymore
por: Kothari, Robin, et al.
Publicado: (2025)

Lower Bounds for Learning Quantum States with Single-Copy Measurements
por: Lowe, Angus, et al.
Publicado: (2022)

Theoretical Constraints on the Expressive Power of $\mathsf{RoPE}$-based Tensor Attention Transformers
por: Li, Xiaoyu, et al.
Publicado: (2024)

Local Quantum Search Algorithm for Random $k$-SAT with $Ω(n^{1+ε})$ Clauses
por: Wu, Mingyou
Publicado: (2024)

Modern Hopfield Networks Require Chain-of-Thought to Solve $\mathsf{NC}^1$-Hard Problems
por: Cao, Yang, et al.
Publicado: (2024)

Computational complexity of isometric tensor network states
por: Malz, Daniel, et al.
Publicado: (2024)

Computational Complexity and Simulability of Non-Hermitian Quantum Dynamics
por: Barch, Brian, et al.
Publicado: (2025)

The rotation-invariant Hamiltonian problem is QMA$_{\rm EXP}$-complete
por: Nelson, Jon, et al.
Publicado: (2025)

Unentangled stoquastic Merlin-Arthur proof systems: the power of unentanglement without destructive interference
por: Liu, Yupan, et al.
Publicado: (2026)

The Power of Lorentz Quantum Computer
por: Zhang, Qi, et al.
Publicado: (2024)

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

A Criterion for Post-Selected Quantum Advantage
por: Karamchedu, Chaitanya, et al.
Publicado: (2024)

Dimension Independent Disentanglers from Unentanglement and Applications
por: Jeronimo, Fernando G., et al.
Publicado: (2024)