The power of a single Haar random state: constructing and separating quantum pseudorandomness
- URL: http://arxiv.org/abs/2404.03295v2
- Date: Mon, 6 May 2024 06:04:06 GMT
- Title: The power of a single Haar random state: constructing and separating quantum pseudorandomness
- Authors: Boyang Chen, Andrea Coladangelo, Or Sattath,
- Abstract summary: We show, perhaps surprisingly, that such an oracle is construct quantum pseudorandomness.
A weaker notion, called single-copy pseudorandom states (1PRS), satisfies this property with respect to a single copy.
- Score: 2.2748974006378937
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this work, we focus on the following question: what are the cryptographic implications of having access to an oracle that provides a single Haar random quantum state? We show, perhaps surprisingly, that such an oracle is sufficient to construct quantum pseudorandomness. Pseudorandom states (PRS) are a family of states for which it is hard to distinguish between polynomially many copies of either a state sampled uniformly from the family or a Haar random state. A weaker notion, called single-copy pseudorandom states (1PRS), satisfies this property with respect to a single copy. Our main result is that 1PRS (as well as bit-commitments) exist relative to an oracle that provides a single Haar random state. We build on this result to show the existence of an oracle relative to which 1PRS exist, but PRS do not. This provides one of the first black-box separations between different forms of quantum pseudorandomness.
Related papers
- Pseudorandom and Pseudoentangled States from Subset States [49.74460522523316]
A subset state with respect to $S$, a subset of the computational basis, is [ frac1sqrt|S|sum_iin S |irangle.
We show that for any fixed subset size $|S|=s$ such that $s = 2n/omega(mathrmpoly(n))$ and $s=omega(mathrmpoly(n))$, a random subset state is information-theoretically indistinguishable from a Haar random state even provided
arXiv Detail & Related papers (2023-12-23T15:52:46Z) - Quantum Pseudorandom Scramblers [5.187307904567701]
Quantum pseudorandom state generators (PRSGs) produce an output state that is computationally indistinguishable from a Haar random state.
Known PRSG constructions provably fail on some initial states.
We construct quantum Pseudorandom State Scramblers (PRSSs) which can produce a pseudorandom state on an arbitrary initial state.
arXiv Detail & Related papers (2023-09-16T10:17:46Z) - Sparse random Hamiltonians are quantumly easy [105.6788971265845]
A candidate application for quantum computers is to simulate the low-temperature properties of quantum systems.
This paper shows that, for most random Hamiltonians, the maximally mixed state is a sufficiently good trial state.
Phase estimation efficiently prepares states with energy arbitrarily close to the ground energy.
arXiv Detail & Related papers (2023-02-07T10:57:36Z) - 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) - Quantum Pseudoentanglement [4.3053817709507]
Entanglement is a quantum resource, in some ways analogous to randomness in classical computation.
We give a construction of pseudoentangled states with entanglement entropy arbitrarily close to $log n$ across every cut.
We discuss applications of this result to Matrix Product State testing, entanglement distillation, and the complexity of the AdS/CFT correspondence.
arXiv Detail & Related papers (2022-11-01T21:04:49Z) - The quantum commuting model (Ia): The CHSH game and other examples:
Uniqueness of optimal states [91.3755431537592]
We use the universal description of quantum commuting correlations as state space on the universal algebra for two player games.
We find that the CHSH game leaves a single optimal state on this common algebra.
arXiv Detail & Related papers (2022-10-07T17:38:31Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle.
We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm.
We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
arXiv Detail & Related papers (2022-05-26T20:32:36Z) - 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) - 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) - Using Randomness to decide among Locality, Realism and Ergodicity [91.3755431537592]
An experiment is proposed to find out, or at least to get an indication about, which one is false.
The results of such experiment would be important not only to the foundations of Quantum Mechanics.
arXiv Detail & Related papers (2020-01-06T19:26:32Z)
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.