pith. sign in

arxiv: 1906.10611 · v2 · pith:WU4E5S3Rnew · submitted 2019-06-25 · 🪐 quant-ph · cs.CR

(Pseudo) Random Quantum States with Binary Phase

Zvika Brakerski , Omri Shmueli This is my paper

Pith reviewed 2026-05-25 16:25 UTC · model grok-4.3

classification 🪐 quant-ph cs.CR
keywords pseudorandom quantum statesHaar random statesquantum state designsbinary phasetrace distancepost-quantum cryptographyToffoli gates
0
0 comments X

The pith

A uniform superposition with independent random binary phases is statistically indistinguishable from a Haar-random state for any polynomial number of copies.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that preparing a uniform superposition over the computational basis and multiplying each amplitude by an independent random sign of plus or minus one produces a state whose polynomial copies are exponentially close in trace distance to the same number of copies of a truly Haar-random state. This resolves a conjecture from CRYPTO 2018 and immediately supplies an elementary way to build pseudorandom quantum states from any post-quantum pseudorandom function. The same technique yields explicit constructions of quantum state t-designs for every t by swapping the pseudorandom function for a (2t)-wise independent function; the resulting circuits use only Hadamard and Toffoli gates and have polylogarithmic depth. The states moreover have strictly real amplitudes, a property not previously achieved by comparable constructions.

Core claim

The uniform superposition state with independent random binary phases ±1 is statistically indistinguishable from a Haar-random state: for any polynomial number of copies the trace distance is at most exponentially small in the number of qubits. This fact is used to construct pseudorandom quantum states from post-quantum pseudorandom functions and to obtain explicit quantum state t-designs from (2t)-wise independent functions whose circuit complexity (size and depth) is bounded by that of the underlying function.

What carries the argument

Uniform superposition with independent random binary phases (±1) applied to each computational basis state.

If this is right

  • Pseudorandom quantum states can be built directly from any post-quantum pseudorandom function.
  • Quantum state t-designs exist for every t via (2t)-wise independent functions.
  • The circuit depth needed for any t-design is at most polylogarithmic rather than linear.
  • All constructed states have only real amplitudes and are generated by one layer of Hadamards followed by Toffoli gates.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The restricted gate set may simplify fault-tolerant implementations on hardware that implements Toffoli natively.
  • The same phase-randomization idea could be tested on small qubit numbers to check whether the exponential closeness already appears at modest sizes.
  • Replacing the uniform distribution over phases by other concentrated distributions might preserve the indistinguishability if similar concentration bounds hold.

Load-bearing premise

The phases are chosen uniformly and independently at random for every basis state.

What would settle it

An efficient algorithm that, on input polynomially many copies of the binary-phase state, distinguishes it from Haar-random states with non-negligible advantage for sufficiently large dimension.

read the original abstract

We prove a quantum information-theoretic conjecture due to Ji, Liu and Song (CRYPTO 2018) which suggested that a uniform superposition with random \emph{binary} phase is statistically indistinguishable from a Haar random state. That is, any polynomial number of copies of the aforementioned state is within exponentially small trace distance from the same number of copies of a Haar random state. As a consequence, we get a provable elementary construction of \emph{pseudorandom} quantum states from post-quantum pseudorandom functions. Generating pseduorandom quantum states is desirable for physical applications as well as for computational tasks such as quantum money. We observe that replacing the pseudorandom function with a $(2t)$-wise independent function (either in our construction or in previous work), results in an explicit construction for \emph{quantum state $t$-designs} for all $t$. In fact, we show that the circuit complexity (in terms of both circuit size and depth) of constructing $t$-designs is bounded by that of $(2t)$-wise independent functions. Explicitly, while in prior literature $t$-designs required linear depth (for $t > 2$), this observation shows that polylogarithmic depth suffices for all $t$. We note that our constructions yield pseudorandom states and state designs with only real-valued amplitudes, which was not previously known. Furthermore, generating these states require quantum circuit of restricted form: applying one layer of Hadamard gates, followed by a sequence of Toffoli gates. This structure may be useful for efficiency and simplicity of implementation.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 1 minor

Summary. The paper proves the Ji-Liu-Song (CRYPTO 2018) conjecture that a uniform superposition over computational basis states with independent random binary phases is exponentially close in trace distance to a Haar-random state when polynomially many copies are considered. As a consequence it yields pseudorandom quantum states from post-quantum PRFs; it further observes that substituting a (2t)-wise independent function produces exact quantum state t-designs whose circuit size and depth are bounded by those of the (2t)-wise independent function, improving prior linear-depth constructions and yielding states with real amplitudes via a Hadamard-plus-Toffoli circuit.

Significance. If the main indistinguishability result holds, the work supplies the first elementary, provably secure construction of pseudorandom quantum states and an explicit polylog-depth route to t-designs; both are directly relevant to quantum money and to efficient state preparation. The real-amplitude and restricted-gate-form properties are additional concrete strengths.

major comments (1)
  1. [Abstract] Abstract (and the paragraph beginning “We observe that replacing…”): the claim that a (2t)-wise independent function yields an exact quantum t-design is load-bearing for the circuit-complexity improvement. The matrix elements of E[|ψ⟩⟨ψ|⊗t] vanish under Haar precisely when, for every basis index, the total ket multiplicity equals the total bra multiplicity. Binary phases (or any function of them) only guarantee that the total multiplicity across all 2t positions is even; configurations with even but unbalanced multiplicities (e.g., multiplicity 2 on ket legs and 0 on bra legs) survive and differ from the Haar integral. This mismatch is present for any t≥2 and is not resolved by (2t)-wise independence.
minor comments (1)
  1. The abstract states that the main result is a “proof” of the conjecture, yet the provided text gives no section or equation numbers for the key steps; the reader cannot locate the precise place where the trace-distance bound is derived.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading and constructive feedback. We address the major comment point by point below.

read point-by-point responses

  1. Referee: [Abstract] Abstract (and the paragraph beginning “We observe that replacing…”): the claim that a (2t)-wise independent function yields an exact quantum t-design is load-bearing for the circuit-complexity improvement. The matrix elements of E[|ψ⟩⟨ψ|⊗t] vanish under Haar precisely when, for every basis index, the total ket multiplicity equals the total bra multiplicity. Binary phases (or any function of them) only guarantee that the total multiplicity across all 2t positions is even; configurations with even but unbalanced multiplicities (e.g., multiplicity 2 on ket legs and 0 on bra legs) survive and differ from the Haar integral. This mismatch is present for any t≥2 and is not resolved by (2t)-wise independence.

    Authors: We thank the referee for identifying this subtlety. Upon re-examination of the moment calculation, we agree that (2t)-wise independence of the phase function only enforces even total multiplicity for each basis index across all 2t positions (ket and bra combined), whereas the Haar t-design requires separate equality of ket and bra multiplicities for each index. Consequently, the ensemble average differs from the Haar integral for t ≥ 2, and the claim that (2t)-wise independent functions produce exact t-designs is incorrect. We will revise the abstract and the relevant discussion to remove this claim. The primary result on exponential indistinguishability from Haar for polynomially many copies of the random-phase states remains valid and is unaffected. revision: yes

Circularity Check

0 steps flagged

No circularity: external conjecture proof with independent observation

full rationale

The paper's central result is an explicit proof of a conjecture stated by Ji, Liu and Song (CRYPTO 2018), an external reference. The t-design observation is derived by substituting a (2t)-wise independent function into the same construction and applying the same analysis technique; it references prior literature for the function class but does not reduce the main indistinguishability claim to a self-definition, fitted parameter, or self-citation chain. No equations or steps in the provided text exhibit the enumerated circularity patterns. The derivation is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

Based on abstract only; no free parameters or invented entities are apparent from the provided text. The result relies on standard quantum information assumptions and external cryptographic primitives.

axioms (2)
  • domain assumption Post-quantum security of pseudorandom functions
    Used for the construction of pseudorandom states from the indistinguishability result.
  • standard math Standard definitions of Haar measure, trace distance, and quantum state t-designs
    Basis for the indistinguishability claim and t-design constructions.

pith-pipeline@v0.9.0 · 5822 in / 1326 out tokens · 68226 ms · 2026-05-25T16:25:23.573157+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

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

  1. Sample- and Hardware-Efficient Fidelity Estimation by Stripping Phase-Dominated Magic

    quant-ph 2026-02 unverdicted novelty 6.0

    Phase stripping reduces target-state magic to enable O(poly(n)) or O(1) sample fidelity estimation for phase-dominated states using a single fan-out gate plus nonlinear Pauli post-processing.

Reference graph

Works this paper leans on

14 extracted references · 14 canonical work pages · cited by 1 Pith paper · 2 internal anchors

  1. [1]

    Candidate weak pseudorandom functions in ac0 mod2

    Adi Akavia, Andrej Bogdanov, Siyao Guo, Akshay Kamath, and Alon Rosen. Candidate weak pseudorandom functions in ac0 mod2. In Electronic Colloquium on Computational Complexity (ECCC) , volume 21, page 33, 2014

    work page 2014

  2. [2]

    Quantum t-designs: t-wise independence in the quantum world

    Andris Ambainis and Joseph Emerson. Quantum t-designs: t-wise independence in the quantum world. In Twenty-Second Annual IEEE Conference on Computational Complexity (CCC'07) , pages 129--140. IEEE, 2007

    work page 2007

  3. [3]

    Exact and approximate unitary 2-designs and their application to fidelity estimation

    Christoph Dankert, Richard Cleve, Joseph Emerson, and Etera Livine. Exact and approximate unitary 2-designs and their application to fidelity estimation. Physical Review A , 80(1):012304, 2009

    work page 2009

  4. [4]

    Random quantum circuits are approximate 2-designs

    Aram W Harrow and Richard A Low. Random quantum circuits are approximate 2-designs. Communications in Mathematical Physics , 291(1):257--302, 2009

    work page 2009

  5. [5]

    Pseudorandom quantum states

    Zhengfeng Ji, Yi - Kai Liu, and Fang Song. Pseudorandom quantum states. In Hovav Shacham and Alexandra Boldyreva, editors, Advances in Cryptology - CRYPTO 2018 - 38th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2018, Proceedings, Part III , volume 10993 of Lecture Notes in Computer Science , pages 126--152. Springer, 2018

    work page 2018

  6. [6]

    Qubit stabilizer states are complex projective 3-designs

    Richard Kueng and David Gross. Qubit stabilizer states are complex projective 3-designs. arXiv preprint arXiv:1510.02767 , 2015

    work page internal anchor Pith review Pith/arXiv arXiv 2015

  7. [7]

    Capacity of the noisy quantum channel

    Seth Lloyd. Capacity of the noisy quantum channel. Physical Review A , 55(3):1613, 1997

    work page 1997

  8. [8]

    Classical simulation of quantum computation, the Gottesman-Knill theorem, and slightly beyond

    M Nest. Classical simulation of quantum computation, the gottesman-knill theorem, and slightly beyond. arXiv preprint arXiv:0811.0898 , 2008

    work page internal anchor Pith review Pith/arXiv arXiv 2008

  9. [9]

    Generating a state t-design by diagonal quantum circuits

    Yoshifumi Nakata, Masato Koashi, and Mio Murao. Generating a state t-design by diagonal quantum circuits. New Journal of Physics , 16(5):053043, 2014

    work page 2014

  10. [10]

    Diagonal-unitary 2-design and their implementations by quantum circuits

    Yoshifumi Nakata and Mio Murao. Diagonal-unitary 2-design and their implementations by quantum circuits. International Journal of Quantum Information , 11(07):1350062, 2013

    work page 2013

  11. [11]

    Synthesizers and their application to the parallel construction of pseudo-random functions

    Moni Naor and Omer Reingold. Synthesizers and their application to the parallel construction of pseudo-random functions. Journal of Computer and System Sciences , 58(2):336--375, 1999

    work page 1999

  12. [12]

    Entanglement and the foundations of statistical mechanics

    Sandu Popescu, Anthony J Short, and Andreas Winter. Entanglement and the foundations of statistical mechanics. Nature Physics , 2(11):754, 2006

    work page 2006

  13. [13]

    Symmetric informationally complete quantum measurements

    Joseph M Renes, Robin Blume-Kohout, Andrew J Scott, and Carlton M Caves. Symmetric informationally complete quantum measurements. Journal of Mathematical Physics , 45(6):2171--2180, 2004

    work page 2004

  14. [14]

    How to construct quantum random functions

    Mark Zhandry. How to construct quantum random functions. In 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science , pages 679--687. IEEE, 2012

    work page 2012