# Pseudorandom and Pseudoentangled States from Subset States

arXiv: https://arxiv.org/abs/2312.15285 · HTML: https://mlsanity.com/paper/2312.15285/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Dec 2023.

## Built on by (most cited first, 1 of 1)

- [Testing classical properties from quantum data](https://mlsanity.com/paper/2411.12730/) (2024)

## Abstract (arXiv)

Pseudorandom states (PRS) are an important primitive in quantum cryptography. In this paper, we show that subset states can be used to construct PRSs. A subset state with respect to S, a subset of the computational basis, is [ frac1√|S|sumi∈ S |irangle. ] As a technical centerpiece, we show that for any fixed subset size |S|=s such that s = 2n/ω(poly(n)) and s=ω(poly(n)), where n is the number of qubits, a random subset state is information-theoretically indistinguishable from a Haar random state even provided with polynomially many copies. This range of parameter is tight. Our work resolves a conjecture by Ji, Liu and Song. Since subset states of small size have small entanglement across all cuts, this construction also illustrates a pseudoentanglement phenomenon.