Imagen de Portada

Quantum Advantage from Sampling Shallow Circuits: Beyond Hardness of Marginals

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Grier, Daniel, Kane, Daniel M., Morris, Jackson, Ostuni, Anthony, Wu, Kewen
Formato:	Preprint
Publicado:	2025
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

Symmetric Distributions from Shallow Circuits
por: Kane, Daniel M., et al.
Publicado: (2025)

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

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

Hard-to-Sample Distributions from Robust Extractors
por: Byramji, Farzan, et al.
Publicado: (2026)

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

On the Advantage of Adaptivity for Sampling with Cell Probes
por: Byramji, Farzan, et al.
Publicado: (2026)

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

Locally Sampleable Uniform Symmetric Distributions
por: Kane, Daniel M., et al.
Publicado: (2024)

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

Classical Simulability of Quantum Circuits with Shallow Magic Depth
por: Zhang, Yifan, et al.
Publicado: (2024)

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

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

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

Sampling Frequency Thresholds for Quantum Advantage of Quantum Approximate Optimization Algorithm
por: Lykov, Danylo, et al.
Publicado: (2022)

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

Quantum-Classical Separations in Shallow-Circuit-Based Learning with and without Noises
por: Zhang, Zhihan, et al.
Publicado: (2024)

Formal Framework for Quantum Advantage
por: Buhrman, Harry, et al.
Publicado: (2025)

Quantum Communication Advantage in TFNP
por: Göös, Mika, et al.
Publicado: (2024)

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

Quantum Advantage in Decision Trees: A Weighted Graph and $L_1$ Norm Approach
por: Grillo, Sebastian Alberto, et al.
Publicado: (2026)

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

Quantum Advantage from One-Way Functions
por: Morimae, Tomoyuki, et al.
Publicado: (2023)

Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture
por: Gharibian, Sevag, et al.
Publicado: (2021)

Thermodynamic Signature of Logical Depth in Quantum Circuits
por: Ibnouhsein, Issam
Publicado: (2025)

Verifiable Quantum Advantage without Structure
por: Yamakawa, Takashi, et al.
Publicado: (2022)

Exact Quantum Circuit Optimization is co-NQP-hard
por: Kjelstrøm, Adam Husted, et al.
Publicado: (2025)

Learning and Generating Mixed States Prepared by Shallow Channel Circuits
por: Hu, Fangjun, et al.
Publicado: (2026)

Classically Sampling Noisy Quantum Circuits in Quasi-Polynomial Time under Approximate Markovianity
por: Zhang, Yifan F., et al.
Publicado: (2025)

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

Anti-Concentration for the Unitary Haar Measure and Applications to Random Quantum Circuits
por: Fefferman, Bill, et al.
Publicado: (2024)

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

Distributed Quantum Advantage for Local Problems
por: Balliu, Alkida, et al.
Publicado: (2024)

Forrelation is Extremally Hard
por: Girish, Uma, et al.
Publicado: (2025)

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

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

On the Computational Hardness of Quantum One-Wayness
por: Cavalar, Bruno, et al.
Publicado: (2023)

Limitations of Linear Cross-Entropy as a Measure for Quantum Advantage
por: Gao, Xun, et al.
Publicado: (2021)

Quantum Advantages in (n,d)->1 Random Access Codes
por: Ambainis, Andris, et al.
Publicado: (2015)

Random Circuit Sampling: Fourier Expansion and Statistics
por: Kalai, Gil, et al.
Publicado: (2024)

Polynomial-Time Classical Simulation of Noisy Quantum Circuits with Naturally Fault-Tolerant Gates
por: Nelson, Jon, et al.
Publicado: (2024)