Scalable and (quantum-accessible) adaptive pseudorandom quantum states and pseudorandom function-like quantum state generators

• URL: http://arxiv.org/abs/2507.22535v2
• Date: Wed, 06 Aug 2025 07:40:55 GMT
• Title: Scalable and (quantum-accessible) adaptive pseudorandom quantum states and pseudorandom function-like quantum state generators
• Authors: Rishabh Batra, Zhili Chen, Rahul Jain, YaoNan Zhang,
• Abstract summary: 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 and (quantum-accessible) adaptive PRFS assuming quantum-secure one-way functions.
• Score: 8.173149714375322
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: Pseudorandom quantum states (PRSs) and pseudorandom function-like quantum state (PRFS) generators are quantum analogues of pseudorandom generators and pseudorandom functions. It is known that PRS (and PRFS) can exist even if BQP = QMA (relative to a quantum oracle) [Kre21] or if P = NP (relative to a classical oracle) [KQST23], which does not allow for the existence of one-way functions (relative to these oracles). Hence, these are potentially weaker objects than quantum-secure one-way functions, which can be used to do quantum cryptography. A desirable property of PRS and PRFS constructions is scalability, which ensures that the security parameter $\lambda$ (which determines indistinguishability from their Haar-random counterparts) can be much larger than $n$ (the number of qubits of the output states). This may be important in some applications where PRS and PRFS primitives are used. We present an isometric procedure to prepare quantum states that can be arbitrarily random (i.e., the trace distance from the Haar-random state can be arbitrarily small for the true random case, or the distinguishing advantage can be arbitrarily small for the pseudorandom case). Our procedure provides a new method for scalable PRS that introduces no entanglement or correlations with the environment. This naturally gives the first construction for scalable and (quantum-accessible) adaptive PRFS assuming quantum-secure one-way functions. Our PRFS construction implies various primitives, including long-input PRFS, short-input PRFS, short-output PRFS, non-adaptive PRFS, and classical-accessible adaptive PRFS [AQY22, AGQY22]. This new construction may be helpful in some simplification of the microcrypt zoo (https://sattath.github.io/microcrypt-zoo/).

Related papers

• Pseudorandom Function-like States from Common Haar Unitary [1.0067421338825544]
  We construct classically-accessible adaptive secure PRFSGs in the invertible quantum Haar random oracle (QHRO) model. Our PRFSG constructions resemble the classical EvenMansour encryption based on a single permutation, and are secure against any unbounded number of queries.
  arXiv  Detail & Related papers  (2024-11-05T15:48:27Z)
• 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)
• Quantum Pseudorandomness Cannot Be Shrunk In a Black-Box Way [0.0]
  Pseudorandom Quantum States (PRS) were introduced by Ji, Liu and Song as quantum analogous to Pseudorandom Generators. Short-PRSs, that is PRSs with logarithmic size output, have been introduced in literature along with cryptographic applications. Here we show that it is not possible to shrink the output of a PRS from 2021 to logarithmic qubit length while still preserving the pseudorandomness property.
  arXiv  Detail & Related papers  (2024-02-20T19:02:43Z)
• 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)
• Robust preparation of Wigner-negative states with optimized SNAP-displacement sequences [41.42601188771239]
  We create non-classical states of light in three-dimensional microwave cavities. These states are useful for quantum computation. We show that this way of creating non-classical states is robust to fluctuations of the system parameters.
  arXiv  Detail & Related papers  (2021-11-15T18:20:38Z)
• Learnability of the output distributions of local quantum circuits [53.17490581210575]
  We investigate, within two different oracle models, the learnability of quantum circuit Born machines. We first show a negative result, that the output distributions of super-logarithmic depth Clifford circuits are not sample-efficiently learnable. We show that in a more powerful oracle model, namely when directly given access to samples, the output distributions of local Clifford circuits are computationally efficiently PAC learnable.
  arXiv  Detail & Related papers  (2021-10-11T18:00:20Z)
• FLIP: A flexible initializer for arbitrarily-sized parametrized quantum circuits [105.54048699217668]
  We propose a FLexible Initializer for arbitrarily-sized Parametrized quantum circuits. FLIP can be applied to any family of PQCs, and instead of relying on a generic set of initial parameters, it is tailored to learn the structure of successful parameters. We illustrate the advantage of using FLIP in three scenarios: a family of problems with proven barren plateaus, PQC training to solve max-cut problem instances, and PQC training for finding the ground state energies of 1D Fermi-Hubbard models.
  arXiv  Detail & Related papers  (2021-03-15T17:38:33Z)
• 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.