On the Limits of Stretching Quantum Pseudorandomness

• URL: http://arxiv.org/abs/2606.24736v1
• Date: Tue, 23 Jun 2026 16:00:17 GMT
• Title: On the Limits of Stretching Quantum Pseudorandomness
• Abstract summary: Pseudorandom states are quantum analogues of classical pseudorandom generators.<n>We prove the first black-box separation between single-copy secure pseudorandom states with different output lengths.
• Score: 7.528006499174231
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Pseudorandom states, introduced by Ji, Liu, and Song (CRYPTO '18), are quantum analogues of classical pseudorandom generators. A fundamental property of classical pseudorandom generators is that their output can be stretched to arbitrary polynomial length. Whether an analogous stretching property holds for quantum pseudorandom states remains unclear. In this work, we prove the first black-box separation between single-copy secure pseudorandom states ($\mathsf{1PRS}$) with different output lengths. Specifically, we construct a quantum oracle relative to which $\mathsf{1PRS}$ with output length $m(n)=1.1n$ exist, but $\mathsf{1PRS}$ with output length $m(n)=Ω(n^{2+ε})$ do not, for any $ε>0$. Our proof leverages the Common Haar Random State (CHRS) model introduced by Chen, Coladangelo, and Sattath (EUROCRYPT '25), and introduces a technique to bound the effective number of resource CHRS states utilized by any $\mathsf{1PRS}$ generator in this model.

Related papers

• Generic Number-of-Copies Amplification for Pseudorandom States [3.5551093158690037]
  We show that any quantum pseudorandom state that is secure against single-copy distinguishers, i.e. a $1$-PRS, can be amplified to $t$-copy security.<n>We show that by carefully accounting for the randomness that is used in the construction, and using quantum extractors, it is possible to eliminate an ancilla register of any length and obtain a meaningful $t$-PRS outcome.
  arXiv  Detail & Related papers  (2026-06-28T10:36:34Z)
• Unitary designs in nearly optimal depth [40.28216388589026]
  We construct unitary designs on qubits in circuit depth $O(log k log log n k / varepsilon)$.<n>The depth is exponentially improved over all known results in all three parameters $n$, $k$, $varepsilon$.<n>We also develop a new analytical framework for bounding errors in quantum experiments involving many queries to random unitaries.
  arXiv  Detail & Related papers  (2025-07-08T17:48:33Z)
• Coherence in Property Testing: Quantum-Classical Collapses and Separations [42.44394412033434]
  We show that no tester can distinguish subset states of size $2n/8$ from $2n/4$ with probability better than $2-Theta(n)$.<n>We also show connections to disentangler and quantum-to-quantum transformation lower bounds.
  arXiv  Detail & Related papers  (2024-11-06T19:52:15Z)
• Rényi divergence-based uniformity guarantees for $k$-universal hash functions [53.80737717363129]
  Universal hash functions map the output of a source to random strings over a finite alphabet.<n>We show that it is possible to distill random bits that are nearly uniform, as measured by min-entropy.
  arXiv  Detail & Related papers  (2024-10-21T19:37:35Z)
• Efficient unitary designs and pseudorandom unitaries from permutations [35.66857288673615]
  We show that products exponentiated sums of $S(N)$ permutations with random phases match the first $2Omega(n)$ moments of the Haar measure. The heart of our proof is a conceptual connection between the large dimension (large-$N$) expansion in random matrix theory and the method.
  arXiv  Detail & Related papers  (2024-04-25T17:08:34Z)
• Simple constructions of linear-depth t-designs and pseudorandom unitaries [40.72668922727092]
  Uniformly random unitaries, i.e. unitaries drawn from the Haar measure, have many useful properties, but cannot be implemented efficiently. Two different notions of derandomisation have emerged: $t-designs are random unitaries that reproduce the first $t moments of the Haar measure, and pseudorandom unitaries (PRUs) are random unitaries that are computationally indistinguishable from Haar random.
  arXiv  Detail & Related papers  (2024-04-19T06:13:02Z)
• 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)
• On the Computational Hardness of Quantum One-Wayness [3.3315839189695167]
  Pseudorandom states compressing $n$ bits to $log n + 1$ qubits can be used to build one-way state generators.<n>One-way state generators can be broken by a quantum algorithm with classical access to a $rmPP$ oracle.<n>An interesting implication of our results is that a $t(n)$-copy one-way state generator exists unconditionally, for every $t(n) = o(n/log n)$.
  arXiv  Detail & Related papers  (2023-12-13T18:56:03Z)
• Quantum Cryptography in Algorithmica [0.7524721345903025]
  We show that in a black-box setting, quantum cryptography based on pseudorandom states is possible even if one-way functions do not exist. We also introduce a conjecture that would generalize our results to multi-copy secure pseudorandom states.
  arXiv  Detail & Related papers  (2022-12-01T21:33:38Z)
• 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)
• Random matrices in service of ML footprint: ternary random features with no performance loss [55.30329197651178]
  We show that the eigenspectrum of $bf K$ is independent of the distribution of the i.i.d. entries of $bf w$. We propose a novel random technique, called Ternary Random Feature (TRF) The computation of the proposed random features requires no multiplication and a factor of $b$ less bits for storage compared to classical random features.
  arXiv  Detail & Related papers  (2021-10-05T09:33:49Z)
• Scalable Pseudorandom Quantum States [14.048989759890476]
  In existing constructions of PRS generators, security scales with the number of qubits in the states, i.e. the (statistical) security parameter for an $n$-qubit PRS is roughly $n$. We show that any quantum-secure one-way function implies scalable PRS. We follow the paradigm of first showing a emphstatistically secure construction when given oracle access to a random function, and then replacing the random function with a quantum-secure (classical) pseudorandom function to achieve computational security.
  arXiv  Detail & Related papers  (2020-04-04T17:15:03Z)

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.