Certified Randomness from Quantum Supremacy
- URL: http://arxiv.org/abs/2303.01625v1
- Date: Thu, 2 Mar 2023 23:28:31 GMT
- Title: Certified Randomness from Quantum Supremacy
- Authors: Scott Aaronson, Shih-Han Hung
- Abstract summary: We propose an application for near-term quantum devices, namely, generating cryptographically certified random bits.
Our protocol repurposes the existing "quantum supremacy" experiments, based on random circuit sampling.
We show that our protocol's output is unpredictable even to a computationally unbounded adversary.
- Score: 5.313318620422295
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We propose an application for near-term quantum devices: namely, generating
cryptographically certified random bits, to use (for example) in proof-of-stake
cryptocurrencies. Our protocol repurposes the existing "quantum supremacy"
experiments, based on random circuit sampling, that Google and USTC have
successfully carried out starting in 2019. We show that, whenever the outputs
of these experiments pass the now-standard Linear Cross-Entropy Benchmark
(LXEB), under plausible hardness assumptions they necessarily contain
$\Omega(n)$ min-entropy, where $n$ is the number of qubits. To achieve a net
gain in randomness, we use a small random seed to produce pseudorandom
challenge circuits. In response to the challenge circuits, the quantum computer
generates output strings that, after verification, can then be fed into a
randomness extractor to produce certified nearly-uniform bits -- thereby
"bootstrapping" from pseudorandomness to genuine randomness. We prove our
protocol sound in two senses: (i) under a hardness assumption called Long List
Quantum Supremacy Verification, which we justify in the random oracle model,
and (ii) unconditionally in the random oracle model against an eavesdropper who
could share arbitrary entanglement with the device. (Note that our protocol's
output is unpredictable even to a computationally unbounded adversary who can
see the random oracle.) Currently, the central drawback of our protocol is the
exponential cost of verification, which in practice will limit its
implementation to at most $n\sim 60$ qubits, a regime where attacks are
expensive but not impossible. Modulo that drawback, our protocol appears to be
the only practical application of quantum computing that both requires a QC and
is physically realizable today.
Related papers
- How much secure randomness is in a quantum state? [0.0]
How much cryptographically-secure randomness can be extracted from a quantum state?
We consider a general adversarial model that allows for an adversary who has quantum side-information about both the source and the measurement device.
arXiv Detail & Related papers (2024-10-21T19:16:56Z) - Local contextuality-based self-tests are sufficient for randomness expansion secure against quantum adversaries [0.0]
We show that local contextuality-based self-tests are sufficient to construct a randomness expansion protocol that is secure against unbounded quantum adversaries.
Our protocol is based on self-testing from non-contextuality inequalities and we prove that our schemeally produces secure random numbers which are $mathcalO(mstepsilon)$-close to uniformly distributed and private.
arXiv Detail & Related papers (2024-09-30T08:31:46Z) - On verifiable quantum advantage with peaked circuit sampling [9.551919087634522]
We show that getting $1/textpoly(n)$ peakedness from such circuits requires $tau_p = Omega(tau_r/n)0.19)$ with overwhelming probability.
We also give numerical evidence that nontrivial peakedness is possible in this model.
arXiv Detail & Related papers (2024-04-22T18:00:06Z) - Improvements on Device Independent and Semi-Device Independent Protocols
of Randomness Expansion [0.0]
Device Independent (DI) and Semi-Device Independent (semi-DI) protocols of randomness expansion are discussed.
We introduce enhanced DI and semi-DI protocols that surpass existing ones in terms of output randomness rate, security, or in some instances, both.
A notable contribution is the introduction of randomness expansion protocols that recycle input randomness, significantly enhancing finite round randomness rates for DI protocols based on the CHSH inequality violation.
arXiv Detail & Related papers (2023-11-22T17:03:04Z) - Simple Tests of Quantumness Also Certify Qubits [69.96668065491183]
A test of quantumness is a protocol that allows a classical verifier to certify (only) that a prover is not classical.
We show that tests of quantumness that follow a certain template, which captures recent proposals such as (Kalai et al., 2022) can in fact do much more.
Namely, the same protocols can be used for certifying a qubit, a building-block that stands at the heart of applications such as certifiable randomness and classical delegation of quantum computation.
arXiv Detail & Related papers (2023-03-02T14:18:17Z) - Importance sampling for stochastic quantum simulations [68.8204255655161]
We introduce the qDrift protocol, which builds random product formulas by sampling from the Hamiltonian according to the coefficients.
We show that the simulation cost can be reduced while achieving the same accuracy, by considering the individual simulation cost during the sampling stage.
Results are confirmed by numerical simulations performed on a lattice nuclear effective field theory.
arXiv Detail & Related papers (2022-12-12T15:06:32Z) - Testing randomness of series generated in Bell's experiment [62.997667081978825]
We use a toy fiber optic based setup to generate binary series, and evaluate their level of randomness according to Ville principle.
Series are tested with a battery of standard statistical indicators, Hurst, Kolmogorov complexity, minimum entropy, Takensarity dimension of embedding, and Augmented Dickey Fuller and Kwiatkowski Phillips Schmidt Shin to check station exponent.
The level of randomness of series obtained by applying Toeplitz extractor to rejected series is found to be indistinguishable from the level of non-rejected raw ones.
arXiv Detail & Related papers (2022-08-31T17:39:29Z) - Efficient Certifiable Randomness from a Single Quantum Device [6.531546527140474]
We use the leakage resilience properties of the Learning With problem to address the rate of generation of randomness.
Our new protocol can certify $Omega(n)$ fresh bits of randomness in constant rounds.
arXiv Detail & Related papers (2022-04-24T20:32:17Z) - Efficient Bipartite Entanglement Detection Scheme with a Quantum
Adversarial Solver [89.80359585967642]
Proposal reformulates the bipartite entanglement detection as a two-player zero-sum game completed by parameterized quantum circuits.
We experimentally implement our protocol on a linear optical network and exhibit its effectiveness to accomplish the bipartite entanglement detection for 5-qubit quantum pure states and 2-qubit quantum mixed states.
arXiv Detail & Related papers (2022-03-15T09:46:45Z) - Quantum copy-protection of compute-and-compare programs in the quantum random oracle model [48.94443749859216]
We introduce a quantum copy-protection scheme for a class of evasive functions known as " compute-and-compare programs"
We prove that our scheme achieves non-trivial security against fully malicious adversaries in the quantum random oracle model (QROM)
As a complementary result, we show that the same scheme fulfils a weaker notion of software protection, called "secure software leasing"
arXiv Detail & Related papers (2020-09-29T08:41:53Z) - Boundaries of quantum supremacy via random circuit sampling [69.16452769334367]
Google's recent quantum supremacy experiment heralded a transition point where quantum computing performed a computational task, random circuit sampling.
We examine the constraints of the observed quantum runtime advantage in a larger number of qubits and gates.
arXiv Detail & Related papers (2020-05-05T20:11:53Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.