Tight Query Lower Bounds for Quantum Sampling, with an Application to Certified Randomness
quant-ph, cs.CR
Submitted: 2026-10-05
Updated: 2026-10-05
Sources
- The Computational Complexity of Linear Optics
- Supplementary information for "Quantum supremacy using a programmable superconducting processor"
- Complexity-Theoretic Foundations of Quantum Supremacy Experiments
- A polynomial-time classical algorithm for noisy random circuit sampling
- Certified Randomness from Quantum Supremacy
- Quantum Attacks on Classical Proof Systems - The Hardness of Quantum Rewinding
- Quantum Lower Bounds by Polynomials
- On Certified Randomness from Fourier Sampling or Random Circuit Sampling
- Spoofing Linear Cross-Entropy Benchmarking in Shallow Quantum Circuits
- A Cryptographic Test of Quantumness and Certifiable Randomness from a Single Quantum Device
- Quantum Supremacy and the Complexity of Random Circuit Sampling
- Quantum Amplitude Amplification and Estimation
- Quantum Algorithm for the Collision Problem
- Characterizing Quantum Supremacy in Near-Term Devices
- Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
- Average-case complexity versus approximate simulation of commuting quantum computations
- Unconditional Certified Randomness without Structure
- Quantum And Relativistic Protocols For Secure Multi-Party Computation
- Limitations of Linear Cross-Entropy as a Measure for Quantum Advantage
- On nonlinear transformations in quantum computation
Related papers
- Reconquering Bell sampling on qudits: stabilizer learning and testing, quantum pseudorandomness bounds, and more
- Encrypted clones can leak: Classification of informative subsets in Quantum Encrypted Cloning
- Polynomial-time classical and quantum simulation of quantum impurity models
- A quasiparticle-protected superconducting qubit
- Theory of quantum-enhanced interferometry with general Markovian light sources
- A convergent hierarchy of spectral gap certificates for qubit Hamiltonians