Trading Locality for Time: Certifiable Randomness from Low-Depth Circuits
Explore this paper's citation graph
Summary
A protocol for exponential certified randomness expansion using a single quantum device and relies on the physical assumption that the adversarial device being tested implements a circuit of sub-logarithmic depth to be able to be easily verified in classical linear time.
- Type
- preprint
- Published
- 2018-10-09
- Cited by
- 38
- References
- 42
- Access
- Open access
- OpenAlex
- https://openalex.org/W2896981111
- Semantic Scholar
- https://api.semanticscholar.org/CorpusID:53588712
Keywords
Randomness, Computer science, Quantum circuit, Qubit, Logarithm
References
- Long-range quantum entanglement in noisy cluster states (6 pages)
- Trevisan's Extractor in the Presence of Quantum Side Information
- Loophole-free Bell inequality violation using electron spins separated by 1.3 kilometres
- Fully device independent quantum key distribution
- Simple unified form for the major no-hidden-variables theorems.
- Pseudorandomness for network algorithms
- Classical command of quantum systems
- Quantum cryptography based on Bell's theorem.
- A classical leash for a quantum system: command of quantum systems via rigidity of CHSH games
- Extreme quantum entanglement in a superposition of macroscopically distinct states.
- Quantum Information Processing with Finite Resources - Mathematical Foundations
- Significant-Loophole-Free Test of Bell's Theorem with Entangled Photons.
- Device-independent parallel self-testing of two singlets
- Quantum advantage with shallow circuits
- A strong loophole-free test of local realism
- Quantum computational supremacy
- Fast quantum logic gates with trapped-ion qubits
- Practical device-independent quantum cryptography via entropy accumulation
- 64-qubit quantum circuit simulation.
- Certifiable Randomness from a Single Quantum Device
Cited by
- Average-case quantum advantage with shallow circuits
- Stoquastic PCP vs. Randomness
- Quantum advantage with noisy shallow circuits
- Possibilistic simulation of quantum circuits by classical circuits
- Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits
- Simulating quantum circuits by classical circuits
- Quantum Advantage with Noisy Shallow Circuits in 3D
- Interactive shallow Clifford circuits: Quantum advantage against NC¹ and beyond
- How Quantum Information Can Improve Social Welfare
- Non-restrictive state reduction and analytical bounds in a multipartite device-independent scenario
- Analytical entropic bounds for multiparty device-independent cryptography
- Quantum Computational Advantage with String Order Parameters of One-Dimensional Symmetry-Protected Topological Order.
- Quantum advantage for computations with limited space
- Test of Quantumness with Small-Depth Quantum Circuits
- Depth-efficient proofs of quantumness
- Quantum computational advantage attested by nonlocal games with the cyclic cluster state
- On Certified Randomness from Fourier Sampling or Random Circuit Sampling
- Noisy decoding by shallow circuits with parities: classical and quantum
- Inflated graph states refuting communication-assisted local-hidden-variable models
- On the power of geometrically-local classical and quantum circuits
Related papers
- Device-independent randomness expansion with entangled photons
- Convex-Split and Hypothesis Testing Approach to One-Shot Quantum Measurement Compression and Randomness Extraction
- One-shot measurement compression with quantum side information using shared randomness
- The Computational Complexity of Randomness
- Randomness extractors for independent sources and applications
- Computing efficiently using weak random sources
- Extracting randomness from samplable distributions
- Applications of unconditional pseudorandomness in complexity theory