Depth-efficient proofs of quantumness
arXiv:2107.02163 · doi:10.22331/q-2022-09-19-807
Abstract
A proof of quantumness is a type of challenge-response protocol in which a classical verifier can efficiently certify the quantum advantage of an untrusted prover. That is, a quantum prover can correctly answer the verifier's challenges and be accepted, while any polynomial-time classical prover will be rejected with high probability, based on plausible computational assumptions. To answer the verifier's challenges, existing proofs of quantumness typically require the quantum prover to perform a combination of polynomial-size quantum circuits and measurements. In this paper, we give two proof of quantumness constructions in which the prover need only perform constant-depth quantum circuits (and measurements) together with log-depth classical computation. Our first construction is a generic compiler that allows us to translate all existing proofs of quantumness into constant quantum depth versions. Our second construction is based around the learning with rounding problem, and yields circuits with shorter depth and requiring fewer qubits than the generic construction. In addition, the second construction also has some robustness against noise.
arXiv comment49 pages, 8 figures. Published in Quantum
References in corpus (24)
- Quantum Computing in the NISQ era and beyond
- Supplementary information for "Quantum supremacy using a programmable superconducting processor"
- Surface codes: Towards practical large-scale quantum computation
- Quantum computational advantage using photons
- Trapped-Ion Quantum Computing: Progress and Challenges
- Characterizing Quantum Supremacy in Near-Term Devices
- Strong quantum computational advantage using a superconducting quantum processor
- Quantum information processing with superconducting circuits: a review
- Quantum Computational Supremacy
- How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits
- Benchmarking an 11-qubit quantum computer
- Quantum Supremacy and the Complexity of Random Circuit Sampling
- Instantaneous Quantum Computation
- Quantum Circuits with Unbounded Fan-out
- Classical Simulation of Quantum Supremacy Circuits
- Classically-Verifiable Quantum Advantage from a Computational Bell Test
- Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits
- Quantum Encryption with Certified Deletion, Revisited: Public Key, Attribute-Based, and Classical Communication
- QFactory: classically-instructed remote secret qubits preparation
- Secure Software Leasing from Standard Assumptions
- Forging quantum data: classically defeating an IQP-based quantum test
- On estimating the entropy of shallow circuit outputs
- Device-independent quantum key distribution from computational assumptions
- Test of Quantumness with Small-Depth Quantum Circuits
Cited by in corpus (10)
- Computational advantage of quantum random sampling
- Hierarchy of topological order from finite-depth unitaries, measurement and feedforward
- Multivariate trace estimation in constant quantum depth
- Interactive Protocols for Classically-Verifiable Quantum Advantage
- Measurement-based infused circuits for variational quantum eigensolvers
- On Certified Randomness from Fourier Sampling or Random Circuit Sampling
- On estimating the entropy of shallow circuit outputs
- Experimental Implementation of an Efficient Test of Quantumness
- Lattice-Based Quantum Advantage from Rotated Measurements
- Entropy Accumulation under Post-Quantum Cryptographic Assumptions