On Limits on the Provable Consequences of Quantum Pseudorandomness

• URL: http://arxiv.org/abs/2510.05393v2
• Date: Tue, 14 Oct 2025 17:09:05 GMT
• Title: On Limits on the Provable Consequences of Quantum Pseudorandomness
• Authors: Samuel Bouaziz--Ermann, Minki Hhan, Garazi Muguruza, Quoc-Huy Vu,
• Abstract summary: We show some evidence suggesting that some quantum pseudorandomness is unlikely to be constructed from the others.<n>We study new oracle worlds where one quantum pseudorandomness exists but another pseudorandomness does not.
• Score: 2.683233968306505
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: There are various notions of quantum pseudorandomness, such as pseudorandom unitaries (PRUs), pseudorandom state generators (PRSGs) and pseudorandom function-like state generators (PRSFGs). Unlike the different notions of classical pseudorandomness, which are known to be existentially equivalent to each other, the relation between quantum pseudorandomness has yet to be fully established. We present some evidence suggesting that some quantum pseudorandomness is unlikely to be constructed from the others, or at least is hard to construct unless some conjectures are false. This indicates that quantum pseudorandomness could behave quite differently from classical pseudorandomness. We study new oracle worlds where one quantum pseudorandomness exists but another pseudorandomness does not under some assumptions or constraints, and provide potential directions to achieve the full black-box separation. More precisely: - We give a unitary oracle relative to which PRFSGs exist but PRUs without using ancilla do not. This can be extended to the general PRUs if we can prove a structural property of the PRU algorithm. - Assuming an isoperimetric inequality-style conjecture, we show a unitary oracle world where log-length output PRFSGs exist but proving the existence of quantum-computable pseudorandom generators (QPRGs) with negligible correctness error is as hard as proving that ${\sf BQP}\neq {\sf QCMA}$. This result suggests that the inverse-polynomial error in the state of the art construction of QPRGs from log-length PRSGs is inherent. - Assuming the same conjecture, we prove that some natural way of constructing super-log-length output PRSGs from log-length output PRFSGs is impossible. This partly complements the known hardness of shrinking the PRSG output lengths. Along the way, we also discuss other potential approaches to extend the PRSG output lengths.

Related papers

• Average-Case Complexity of Quantum Stabilizer Decoding [42.770940323689445]
  We prove that decoding a random stabilizer code with even a single logical qubit is at least as hard as decoding a random classical code at constant rate.<n>This result suggests that the easiest random quantum decoding problem is at least as hard as the hardest random classical decoding problem.
  arXiv  Detail & Related papers  (2025-09-25T03:04:40Z)
• Scalable, quantum-accessible, and adaptive pseudorandom quantum state and pseudorandom function-like quantum state generators [7.921901082060529]
  Pseudorandom quantum states (PRSs) and pseudorandom function-like quantum state (PRFS) generators are quantum analogues of pseudorandom generators and pseudorandom functions.<n>We present a new method for scalable PRS that introduces no entanglement or correlations with the environment.<n>This naturally gives the first construction for scalable, quantum-accessible, and adaptive PRFS assuming quantum-secure one-way functions.
  arXiv  Detail & Related papers  (2025-07-30T10:02:45Z)
• Efficient Quantum Pseudorandomness from Hamiltonian Phase States [41.94295877935867]
  We introduce a quantum hardness assumption called the Hamiltonian Phase State (HPS) problem.<n>We show that our assumption is plausibly fully quantum; meaning, it cannot be used to construct one-way functions.<n>We show that our assumption and its variants allow us to efficiently construct many pseudorandom quantum primitives.
  arXiv  Detail & Related papers  (2024-10-10T16:10:10Z)
• Existential Unforgeability in Quantum Authentication From Quantum Physical Unclonable Functions Based on Random von Neumann Measurement [45.386403865847235]
  Physical Unclonable Functions (PUFs) leverage inherent, non-clonable physical randomness to generate unique input-output pairs.<n>Quantum PUFs (QPUFs) extend this concept by using quantum states as input-output pairs.<n>We show that random unitary QPUFs cannot achieve existential unforgeability against Quantum Polynomial Time adversaries.<n>We introduce a second model where the QPUF functions as a nonunitary quantum channel, which guarantees existential unforgeability.
  arXiv  Detail & Related papers  (2024-04-17T12:16:41Z)
• 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)
• A Quantum "Lifting Theorem" for Constructions of Pseudorandom Generators from Random Oracles [7.454028086083526]
  We study the (quantum) security of pseudorandom generators (PRGs) constructed from random oracles.<n>We prove a "lifting theorem" showing, roughly, that if such a PRG is unconditionally secure against classical adversaries making unboundedly many queries to the random oracle, then it is also (unconditionally) secure against quantum adversaries in the same sense.
  arXiv  Detail & Related papers  (2024-01-25T17:13:51Z)
• Pseudorandom Strings from Pseudorandom Quantum States [6.79244006793321]
  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.
  arXiv  Detail & Related papers  (2023-06-09T01:16:58Z)
• 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)
• 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)
• 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)
• Gaussian conversion protocols for cubic phase state generation [104.23865519192793]
  Universal quantum computing with continuous variables requires non-Gaussian resources. The cubic phase state is a non-Gaussian state whose experimental implementation has so far remained elusive. We introduce two protocols that allow for the conversion of a non-Gaussian state to a cubic phase state.
  arXiv  Detail & Related papers  (2020-07-07T09:19:49Z)

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.