Distinctness threshold for pseudorandom unitaries

• URL: http://arxiv.org/abs/2609.03065v1
• Date: Wed, 02 Sep 2026 18:38:01 GMT
• Title: Distinctness threshold for pseudorandom unitaries
• Abstract summary: We show that statistical pseudorandomness is not necessary for computationally pseudorandom unitaries.<n>We do this by replacing the unitary $2$-design layer in the existing constructions with ensembles that are not even state $1$-designs.<n>This yields new non-adaptively secure PRU ensembles whose computational pseudorandomness is obtained without an underlying statistically pseudorandom quantum ensemble.
• Score: 0.3670422696827525
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Pseudorandomness is increasingly recognized as a key property of ensembles in quantum information theory, statistical mechanics, and quantum many-body physics. Yet it appears in two conceptually different forms: statistical pseudorandomness, embodied by unitary designs, and computational pseudorandomness captured by pseudorandom unitaries (PRUs). The relationship between these two forms of pseudorandomness remains surprisingly poorly understood. Existing PRU constructions reveal this interplay where a statistically randomizing ingredient, a unitary design, is combined with classical cryptographic primitives to produce computational pseudorandomness. We show that statistical pseudorandomness is not necessary for computationally pseudorandom unitaries. We do this by replacing the unitary $2$-design layer in the existing constructions with ensembles that are not even state $1$-designs, yet are sufficiently {\em distinct}, a property we identify to be necessary for any PRU. This yields new non-adaptively secure PRU ensembles whose computational pseudorandomness is obtained without an underlying statistically pseudorandom quantum ensemble, such as a $2$-design. We characterize distinctness via an entangled analogue of anticoncentration and use it to show that distinctness already captures constraints on coherence and imaginarity of PRUs, while identifying broad classes of inputs for which the latter obstruction disappears, enabling real-valued PRUs even for certain (maximally) entangled states. As an application, we use lack of distinctness to constrain the conjectured pseudorandomness of the random phase-Hadamard ensemble to form a PRU.

Related papers

• Derivatives of Quantum Randomness: Separating Pseudorandom Unitaries from Pseudorandom (Function-like) States [3.891921282474929]
  We show a full unitary oracle separation between PRFSGs and PRUs.<n>This reveals a fundamental distinction between pseudorandomness for quantum states and for quantum unitaries.
  arXiv  Detail & Related papers  (2026-09-13T15:54:16Z)
• How to Verify Consistency of Probabilistic Claims [49.47758039235095]
  We construct an interactive PCP to prove a predictive model's consistency.<n>We show how a small additive-soundness gap removes dependence on B.<n>We view our interactive PCP as a first step toward predictive models to prove their own consistency.
  arXiv  Detail & Related papers  (2026-08-11T17:41:39Z)
• 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)
• Real-Valued Somewhat-Pseudorandom Unitaries [5.294604210205507]
  We show that even though real-valued unitaries cannot be completely pseudorandom, we can still obtain some pseudorandom properties without giving up on a real-valued unitary. Our analysis shows that an even simpler construction: applying a random (binary) phase followed by a random computational-basis permutation, would suffice.
  arXiv  Detail & Related papers  (2024-03-25T12:37:50Z)
• 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)
• Pseudorandom unitaries are neither real nor sparse nor noise-robust [0.0]
  Pseudorandom quantum states (PRSs) and pseudorandom unitaries (PRUs) possess the dual nature of being efficiently constructible while appearing completely random to any efficient quantum algorithm.<n>We show that PRSs and PRUs exist only when the probability that an error occurs is negligible, ruling out their generation on noisy intermediate-scale and early fault-tolerant quantum computers.
  arXiv  Detail & Related papers  (2023-06-20T16:54:27Z)
• 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)
• Simplex Random Features [53.97976744884616]
  We present Simplex Random Features (SimRFs), a new random feature (RF) mechanism for unbiased approximation of the softmax and Gaussian kernels. We prove that SimRFs provide the smallest possible mean square error (MSE) on unbiased estimates of these kernels. We show consistent gains provided by SimRFs in settings including pointwise kernel estimation, nonparametric classification and scalable Transformers.
  arXiv  Detail & Related papers  (2023-01-31T18:53:39Z)
• 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)
• Probabilistic Conformal Prediction Using Conditional Random Samples [73.26753677005331]
  PCP is a predictive inference algorithm that estimates a target variable by a discontinuous predictive set. It is efficient and compatible with either explicit or implicit conditional generative models.
  arXiv  Detail & Related papers  (2022-06-14T03:58: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.