Pseudorandom Strings from Pseudorandom Quantum States
- URL: http://arxiv.org/abs/2306.05613v2
- Date: Wed, 13 Sep 2023 23:16:11 GMT
- Title: Pseudorandom Strings from Pseudorandom Quantum States
- Authors: Prabhanjan Ananth, Yao-Ting Lin, Henry Yuen
- Abstract summary: We study the relationship between notions of pseudorandomness in the quantum and classical worlds.
We show that a natural variant of pseudorandom generators called quantum pseudorandom generators (QPRGs) can be based on the existence of logarithmic output length PRSGs.
We also study the relationship between other notions, namely, pseudorandom function-like state generators and pseudorandom functions.
- Score: 6.79244006793321
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the relationship between notions of pseudorandomness in the quantum
and classical worlds. Pseudorandom quantum state generator (PRSG), a
pseudorandomness notion in the quantum world, is an efficient circuit that
produces states that are computationally indistinguishable from Haar random
states. PRSGs have found applications in quantum gravity, quantum machine
learning, quantum complexity theory, and quantum cryptography. Pseudorandom
generators, on the other hand, a pseudorandomness notion in the classical
world, is ubiquitous to theoretical computer science. While some separation
results were known between PRSGs, for some parameter regimes, and PRGs, their
relationship has not been completely understood.
In this work, we show that a natural variant of pseudorandom generators
called quantum pseudorandom generators (QPRGs) can be based on the existence of
logarithmic output length PRSGs. Our result along with the previous separations
gives a better picture regarding the relationship between the two notions. We
also study the relationship between other notions, namely, pseudorandom
function-like state generators and pseudorandom functions. We provide evidence
that QPRGs can be as useful as PRGs by providing cryptographic applications of
QPRGs such as commitments and encryption schemes.
Our primary technical contribution is a method for pseudodeterministically
extracting uniformly random strings from Haar-random states.
Related papers
- Characterizing randomness in parameterized quantum circuits through expressibility and average entanglement [39.58317527488534]
Quantum Circuits (PQCs) are still not fully understood outside the scope of their principal application.
We analyse the generation of random states in PQCs under restrictions on the qubits connectivities.
We place a connection between how steep is the increase on the uniformity of the distribution of the generated states and the generation of entanglement.
arXiv Detail & Related papers (2024-05-03T17:32:55Z) - Pseudorandom unitaries with non-adaptive security [43.15464425520681]
We present a PRU construction that is a concatenation of a random Clifford unitary, a pseudorandom binary phase operator, and a pseudorandom permutation operator.
We prove that this PRU construction is secure against non-adaptive distinguishers assuming the existence of quantum-secure one-way functions.
arXiv Detail & Related papers (2024-02-22T18:56:37Z) - Non Deterministic Pseudorandom Generator for Quantum Key Distribution [0.0]
Quantum Key Distribution thrives to achieve perfect secrecy of One time Pad (OTP) through quantum processes.
One of the crucial components of QKD are Quantum Random Number Generators(QRNG) for generation of keys.
This paper proposes a pseudorandom generator based on post quantum primitives.
arXiv Detail & Related papers (2023-11-06T11:03:03Z) - Indistinguishability between quantum randomness and pseudo-randomness
under efficiently calculable randomness measures [6.201566048090889]
We present a no-go theorem for the distinguishability between quantum random numbers (i.e., random numbers generated quantum mechanically) and pseudo-random numbers (i.e., random numbers generated algorithmically)
The theorem states that one cannot distinguish these two types of random numbers if the quantum random numbers are efficiently classically simulatable and the randomness measure used for the distinction is efficiently computable.
arXiv Detail & Related papers (2023-09-20T07:50:30Z) - Quantum Conformal Prediction for Reliable Uncertainty Quantification in
Quantum Machine Learning [47.991114317813555]
Quantum models implement implicit probabilistic predictors that produce multiple random decisions for each input through measurement shots.
This paper proposes to leverage such randomness to define prediction sets for both classification and regression that provably capture the uncertainty of the model.
arXiv Detail & Related papers (2023-04-06T22:05:21Z) - Pseudorandom (Function-Like) Quantum State Generators: New Definitions
and Applications [7.2051162210119495]
We explore new definitions, new properties and applications of pseudorandom states.
Pseudorandom quantum states (PRS) are efficiently constructible states that are computationally indistinguishable from being Haar-random.
We show that PRS generators with logarithmic output length imply commitment and encryption schemes with classical communication.
arXiv Detail & Related papers (2022-11-02T19:24:55Z) - Cryptography from Pseudorandom Quantum States [6.164147034988822]
One-way functions imply the existence of pseudorandom states, but Kretschmer (TQC'20) recently constructed an oracle relative to which there are no one-way functions but pseudorandom states still exist.
We study the intriguing possibility of basing interesting cryptographic tasks on pseudorandom states.
A consequence of (a) is that pseudorandom states are sufficient to construct maliciously secure multiparty protocols in the dishonest majority setting.
arXiv Detail & Related papers (2021-12-18T22:53:16Z) - Quantum Pseudorandomness and Classical Complexity [0.08158530638728499]
We show that cryptographic pseudorandom quantum states and pseudorandom unitary transformations exist.
We discuss implications of these results for cryptography, complexity theory, and quantum tomography.
arXiv Detail & Related papers (2021-03-16T20:54:12Z) - Preparing random states and benchmarking with many-body quantum chaos [48.044162981804526]
We show how to predict and experimentally observe the emergence of random state ensembles naturally under time-independent Hamiltonian dynamics.
The observed random ensembles emerge from projective measurements and are intimately linked to universal correlations built up between subsystems of a larger quantum system.
Our work has implications for understanding randomness in quantum dynamics, and enables applications of this concept in a wider context.
arXiv Detail & Related papers (2021-03-05T08:32:43Z) - Single photon randomness originating from the symmetry of dipole
emission and the unpredictability of spontaneous emission [55.41644538483948]
Quantum random number generation is a key ingredient for quantum cryptography and fundamental quantum optics.
We experimentally demonstrate quantum random number generation based on the spontaneous emission process.
The scheme can be extended to random number generation by coherent single photons with potential applications in solid-state based quantum communication at room temperature.
arXiv Detail & Related papers (2021-02-18T14:07:20Z) - Quantum Random Number Generation using a Solid-State Single-Photon
Source [89.24951036534168]
Quantum random number generation (QRNG) harnesses the intrinsic randomness of quantum mechanical phenomena.
We demonstrate QRNG with a quantum emitter in hexagonal boron nitride.
Our results open a new avenue to the fabrication of on-chip deterministic random number generators.
arXiv Detail & Related papers (2020-01-28T22:47:43Z)
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.