Cover Image

Provable and Verifiable Quantum Advantage in Sample Complexity

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Benedetti, Marcello, Buhrman, Harry, Weggemans, Jordi
Format:	Preprint
Published:	2025
Subjects:	Quantum Physics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Quantum PCPs: on Adaptivity, Multiple Provers and Reductions to Local Hamiltonians
by: Buhrman, Harry, et al.
Published: (2024)

Unconditional and exponentially large violation of classicality
by: Benedetti, Marcello, et al.
Published: (2025)

Classical versus quantum queries in quantum PCPs with classical proofs
by: Buhrman, Harry, et al.
Published: (2024)

Permutation tests for quantum state identity
by: Buhrman, Harry, et al.
Published: (2024)

Formal Framework for Quantum Advantage
by: Buhrman, Harry, et al.
Published: (2025)

Finding quantum partial assignments by search-to-decision reductions
by: Weggemans, Jordi
Published: (2024)

Lower Bounds for Unitary Property Testing with Proofs and Advice
by: Weggemans, Jordi
Published: (2024)

On the Sample Complexity of Quantum Boltzmann Machine Learning
by: Coopmans, Luuk, et al.
Published: (2023)

Complexity of the Guided Local Hamiltonian Problem: Improved Parameters and Extension to Excited States
by: Cade, Chris, et al.
Published: (2022)

Guidable Local Hamiltonian Problems with Implications to Heuristic Ansätze State Preparation and the Quantum PCP Conjecture
by: Weggemans, Jordi, et al.
Published: (2023)

Assessing fault-tolerant quantum advantage for $k$-SAT with structure
by: Brehm, Martijn, et al.
Published: (2024)

Instantaneous Quantum Polynomial-Time Sampling and Verifiable Quantum Advantage: Stabilizer Scheme and Classical Security
by: Bremner, Michael J., et al.
Published: (2023)

An Exponential Sample-Complexity Advantage for Coherent Quantum Inference
by: Li, Zhaoyi, et al.
Published: (2026)

A Qubit, a Coin, and an Advice String Walk Into a Relational Problem
by: Aaronson, Scott, et al.
Published: (2023)

Sparsity-dependent Complexity Lower Bound of Quantum Linear System Solvers
by: Mori, Hitomi, et al.
Published: (2026)

Verifiable Quantum Advantage via Optimized DQI Circuits
by: Khattar, Tanuj, et al.
Published: (2025)

A Cryptographic Perspective on the Verifiability of Quantum Advantage
by: Chia, Nai-Hui, et al.
Published: (2023)

Verifiable Quantum Advantage without Structure
by: Yamakawa, Takashi, et al.
Published: (2022)

Provable Quantum Algorithm Advantage for Gaussian Process Quadrature
by: Galvis-Florez, Cristian A., et al.
Published: (2025)

Quantum Catalytic Space
by: Buhrman, Harry, et al.
Published: (2025)

Quantum Energetic Advantage before Computational Advantage in Boson Sampling
by: Soret, Ariane, et al.
Published: (2026)

Universal Quantum Electron Microscopy: A Small-Scale Quantum Computing Application with Provable Advantage
by: Okamoto, Hiroshi
Published: (2022)

State preparation by shallow circuits using feed forward
by: Buhrman, Harry, et al.
Published: (2023)

Protecting Expressive Circuits with a Quantum Error Detection Code
by: Self, Chris N., et al.
Published: (2022)

Relating non-local quantum computation to information theoretic cryptography
by: Allerstorfer, Rene, et al.
Published: (2023)

Making Existing Quantum Position Verification Protocols Secure Against Arbitrary Transmission Loss
by: Allerstorfer, Rene, et al.
Published: (2023)

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

Training Quantum Boltzmann Machines with the $β$-Variational Quantum Eigensolver
by: Huijgen, Onno, et al.
Published: (2023)

Less Quantum, More Advantage: An End-to-End Quantum Algorithm for the Jones Polynomial
by: Laakkonen, Tuomas, et al.
Published: (2025)

Probabilistic quantum algorithm for Lyapunov equations and matrix inversion
by: Benedetti, Marcello, et al.
Published: (2025)

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

Beating the natural Grover bound for low-energy estimation and state preparation
by: Buhrman, Harry, et al.
Published: (2024)

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

Exponential Quantum Advantage for Message Complexity in Distributed Algorithms
by: Gall, François Le, et al.
Published: (2025)

Towards Quantum Advantage in Chemistry
by: Genin, Scott N., et al.
Published: (2025)

A Framework for Quantum Advantage
by: Lanes, Olivia, et al.
Published: (2025)

Quantum Computational-Sensing Advantage
by: Khan, Saeed A., et al.
Published: (2025)

Quantum Advantage in Resource Estimation
by: Simon, William A., et al.
Published: (2025)

Nonlocal Advantages of Quantum Imaginarity
by: Wei, Zhi-Wei, et al.
Published: (2024)

Cryptographic Characterization of Quantum Advantage
by: Morimae, Tomoyuki, et al.
Published: (2024)