Cover Image

Unconditionally separating noisy $\mathsf{QNC}^0$ from bounded polynomial threshold circuits of constant depth

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Hsieh, Min-Hsiu, Mendes, Leandro, de Oliveira, Michael, Subramanian, Sathyawageeswar
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

Unconditional Pseudorandomness against Shallow Quantum Circuits
by: Ghosh, Soumik, et al.
Published: (2025)

Information-theoretic generalization bounds for learning from quantum data
by: Caro, Matthias, et al.
Published: (2023)

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

A polynomial-time classical algorithm for noisy quantum circuits
by: Schuster, Thomas, et al.
Published: (2024)

Quantum Channel Testing in Average-Case Distance
by: Rosenthal, Gregory, et al.
Published: (2024)

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

Learning depth-3 circuits via quantum agnostic boosting
by: Arunachalam, Srinivasan, et al.
Published: (2025)

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

When quantum resources backfire: Non-gaussianity and symplectic coherence in noisy bosonic circuits
by: Upreti, Varun, et al.
Published: (2025)

Oracle Separation between Noisy Quantum Polynomial Time and the Polynomial Hierarchy
by: Chia, Nai-Hui, et al.
Published: (2024)

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

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

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

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

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

How to Verify that a Small Device is Quantum, Unconditionally
by: Malavolta, Giulio, et al.
Published: (2025)

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

The Power of Shallow-depth Toffoli and Qudit Quantum Circuits
by: Grilo, Alex Bredariol, et al.
Published: (2024)

Learning quantum states prepared by shallow circuits in polynomial time
by: Landau, Zeph, et al.
Published: (2024)

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

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

Bell sampling from quantum circuits
by: Hangleiter, Dominik, et al.
Published: (2023)

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

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

The power of quantum circuits in sampling
by: Blanc, Guy, et al.
Published: (2025)

IQP circuits for 2-Forrelation
by: Buzet, Quentin, et al.
Published: (2026)

Complexity and hardness of random peaked circuits
by: Zhang, Yuxuan
Published: (2025)

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

Incompressibility and spectral gaps of random circuits
by: Chen, Chi-Fang, et al.
Published: (2024)

On estimating the entropy of shallow circuit outputs
by: Gheorghiu, Alexandru, et al.
Published: (2020)

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

A sharp interaction-degree threshold for simulating QAOA
by: Āboliņš, Ralfs, et al.
Published: (2026)

Constant-depth circuits for Boolean functions and quantum memory devices using multi-qubit gates
by: Allcock, Jonathan, et al.
Published: (2023)

Quantum Merlin-Arthur with an internally separable proof
by: Bassirian, Roozbeh, et al.
Published: (2024)

The membership problem for constant-sized quantum correlations is undecidable
by: Fu, Honghao, et al.
Published: (2021)

On classical advice, sampling advice and complexity assumptions for learning separations
by: Pérez-Guijarro, Jordi
Published: (2024)

Classical simulability of quantum circuits followed by sparse classical post-processing
by: Takahashi, Yasuhiro, et al.
Published: (2026)

Quantum precomputation: parallelizing cascade circuits and the Moore-Nilsson conjecture is false
by: Watts, Adam Bene, et al.
Published: (2025)

Unconditional proofs of quantumness between small-space machines
by: Say, A. C. Cem, et al.
Published: (2024)

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