Pith. sign in

REVIEW 3 cited by

Pseudorandom and Pseudoentangled States from Subset States

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2312.15285 v2 pith:V4TNZZQV submitted 2023-12-23 quant-ph cs.CCcs.CR

Fernando Granha Jeronimo , Nir Magrafta , Pei Wu This is my paper · ORCID
classification quant-phcs.CCcs.CR
keywords subsetstatesstatemathrmomegapolypseudorandomrandom
verification ladder T0 review T1 audit T2 compute T3 formal

Signed reviews

No signed human review yet.

0 comments
abstract

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 \[ \frac{1}{\sqrt{|S|}}\sum_{i\in S} |i\rangle. \] As a technical centerpiece, we show that for any fixed subset size $|S|=s$ such that $s = 2^n/\omega(\mathrm{poly}(n))$ and $s=\omega(\mathrm{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.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 3 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Unconditional Pseudorandomness against Shallow Quantum Circuits

    quant-ph 2025-07 conditional novelty 8.0 of 10

    Any approximate quantum state 2-design is unconditionally pseudorandom against QNC0 and AC0 after QNC0 adversaries, with analogous pseudoentanglement and parallel-query unitary-design results.

  2. Parallel Kac's Walk Generates PRU

    quant-ph 2025-04 conditional novelty 7.0 of 10

    A linear number of parallel Kac's walk steps forms an adaptively secure pseudorandom unitary, and adding inverse queries costs no extra asymptotic steps.

  3. State-Based Classical Shadows

    quant-ph 2025-07 conditional novelty 6.0 of 10

    Replacing random unitaries with random auxiliary states in a Bell-basis measurement gives classical shadows whose guarantees hold for approximate state designs and even for pseudorandom state families.

Pith tools