Quantum Pseudorandomness Cannot Be Shrunk In a Black-Box Way

• URL: http://arxiv.org/abs/2402.13324v1
• Date: Tue, 20 Feb 2024 19:02:43 GMT
• Title: Quantum Pseudorandomness Cannot Be Shrunk In a Black-Box Way
• Authors: Samuel Bouaziz--Ermann and Garazi Muguruza
• Abstract summary: 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.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Pseudorandom Quantum States (PRS) were introduced by Ji, Liu and Song as quantum analogous to Pseudorandom Generators. They are an ensemble of states efficiently computable but computationally indistinguishable from Haar random states. Subsequent works have shown that some cryptographic primitives can be constructed from PRSs. Moreover, recent classical and quantum oracle separations of PRS from One-Way Functions strengthen the interest in a purely quantum alternative building block for quantum cryptography, potentially weaker than OWFs. However, our lack of knowledge of extending or shrinking the number of qubits of the PRS output still makes it difficult to reproduce some of the classical proof techniques and results. Short-PRSs, that is PRSs with logarithmic size output, have been introduced in the literature along with cryptographic applications, but we still do not know how they relate to PRSs. Here we answer half of the question, by showing that it is not possible to shrink the output of a PRS from polynomial to logarithmic qubit length while still preserving the pseudorandomness property, in a relativized way. More precisely, we show that relative to Kretschmer's quantum oracle (TQC 2021) short-PRSs cannot exist (while PRSs exist, as shown by Kretschmer's work).

Related papers

• PRS Length Expansion [4.31241676251521]
  Pseudo-random quantum states (PRS) are a key primitive in quantum cryptography. This work conjectures that some PRS generators can be expanded, and provides a proof for such expansion for some specific examples.
  arXiv  Detail & Related papers  (2024-11-05T16:06:59Z)
• Efficient Quantum Pseudorandomness from Hamiltonian Phase States [41.94295877935867]
  We introduce a quantum hardness assumption called the Hamiltonian Phase State (HPS) problem. We show that our assumption is plausibly fully quantum; meaning, it cannot be used to construct one-way functions. 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. Quantum PUFs (QPUFs) extend this concept by using quantum states as input-output pairs. We show that random unitary QPUFs cannot achieve existential unforgeability against Quantum Polynomial Time adversaries. 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 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. 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)
• Quantum process tomography of continuous-variable gates using coherent states [49.299443295581064]
  We demonstrate the use of coherent-state quantum process tomography (csQPT) for a bosonic-mode superconducting circuit. We show results for this method by characterizing a logical quantum gate constructed using displacement and SNAP operations on an encoded qubit.
  arXiv  Detail & Related papers  (2023-03-02T18:08:08Z)
• Simple Tests of Quantumness Also Certify Qubits [69.96668065491183]
  A test of quantumness is a protocol that allows a classical verifier to certify (only) that a prover is not classical. We show that tests of quantumness that follow a certain template, which captures recent proposals such as (Kalai et al., 2022) can in fact do much more. Namely, the same protocols can be used for certifying a qubit, a building-block that stands at the heart of applications such as certifiable randomness and classical delegation of quantum computation.
  arXiv  Detail & Related papers  (2023-03-02T14:18:17Z)
• 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)
• Depth-efficient proofs of quantumness [77.34726150561087]
  A proof of quantumness is a type of challenge-response protocol in which a classical verifier can efficiently certify quantum advantage of an untrusted prover. In this paper, we give two proof of quantumness constructions in which the prover need only perform constant-depth quantum circuits.
  arXiv  Detail & Related papers  (2021-07-05T17:45:41Z)
• Secure Two-Party Quantum Computation Over Classical Channels [63.97763079214294]
  We consider the setting where the two parties (a classical Alice and a quantum Bob) can communicate only via a classical channel. We show that it is in general impossible to realize a two-party quantum functionality with black-box simulation in the case of malicious quantum adversaries. We provide a compiler that takes as input a classical proof of quantum knowledge (PoQK) protocol for a QMA relation R and outputs a zero-knowledge PoQK for R that can be verified by classical parties.
  arXiv  Detail & Related papers  (2020-10-15T17:55:31Z)
• 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.