Cover Image

Unconditional Pseudorandomness against Shallow Quantum Circuits

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Ghosh, Soumik, Subramanian, Sathyawageeswar, Zhan, Wei
Format:	Preprint
Published:	2025
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 Quantum Advantage for Sampling with Shallow Circuits
by: Watts, Adam Bene, et al.
Published: (2023)

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

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

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

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

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

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

Quantum Pseudorandom Scramblers
by: Lu, Chuhan, et al.
Published: (2023)

Quantum Pseudorandomness and Classical Complexity
by: Kretschmer, William
Published: (2021)

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

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

Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom
by: Grewal, Sabee, et al.
Published: (2022)

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

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

Random regular graph states are complex at almost any depth
by: Ghosh, Soumik, et al.
Published: (2024)

Pseudorandom quantum authentication
by: Haug, Tobias, et al.
Published: (2025)

Pseudorandom density matrices
by: Bansal, Nikhil, et al.
Published: (2024)

Peaked quantum advantage using error correction
by: Deshpande, Abhinav, et al.
Published: (2025)

Pseudorandomness in the (Inverseless) Haar Random Oracle Model
by: Ananth, Prabhanjan, et al.
Published: (2024)

Pseudorandom and Pseudoentangled States from Subset States
by: Jeronimo, Fernando Granha, et al.
Published: (2023)

Thermodynamic Signature of Logical Depth in Quantum Circuits
by: Ibnouhsein, Issam
Published: (2025)

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

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

Pseudorandom unitaries are neither real nor sparse nor noise-robust
by: Haug, Tobias, et al.
Published: (2023)

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

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

The Jacobi Factoring Circuit: Quantum Factoring with Near-Linear Gates and Sublinear Space and Depth
by: Kahanamoku-Meyer, Gregory D., et al.
Published: (2024)

The Subgraph Isomorphism Problem for Port Graphs and Quantum Circuits
by: Mondada, Luca, et al.
Published: (2023)

Quantum Circuit Optimization by Graph Coloring
by: Lee, Hochang, et al.
Published: (2025)

Fast computational deep thermalization
by: Chakraborty, Shantanav, et al.
Published: (2025)

Quantum Multiplier Based on Exponent Adder
by: Zhan, Junpeng
Published: (2023)

Quantum Feasibility Labeling for NP-complete Vertex Coloring Problem
by: Zhan, Junpeng
Published: (2023)

Circuit-to-Hamiltonian from tensor networks and fault tolerance
by: Anshu, Anurag, et al.
Published: (2023)

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

Polynomial-Time Classical Simulation of Noisy IQP Circuits with Constant Depth
by: Rajakumar, Joel, et al.
Published: (2024)

Wasserstein Complexity of Quantum Circuits
by: Li, Lu, et al.
Published: (2022)

Complexity Theory for Quantum Promise Problems
by: Chia, Nai-Hui, et al.
Published: (2024)

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

Taming Barren Plateaus in Arbitrary Parameterized Quantum Circuits without Sacrificing Expressibility
by: Chen, Zhenyu, et al.
Published: (2025)

Elementary Quantum Recursion Schemes That Capture Quantum Polylogarithmic Time Computability of Quantum Functions
by: Yamakami, Tomoyuki
Published: (2023)