Pseudorandom unitaries from ordinary random two-qubit circuits

Problem

Does a polynomial-length random walk generated by ordinary two-qubit gates form a pseudorandom-unitary ensemble?

For an ensemble \(\mathcal U_n\) of efficiently implementable \(n\)-qubit unitaries, require that every quantum polynomial-time distinguisher with forward oracle access satisfy

\begin{equation} \left|\Pr_{U\sim\mathcal U_n}[\mathcal D^U(1^n)=1] -\Pr_{V\sim\operatorname{Haar}(2^n)}[\mathcal D^V(1^n)=1]\right| \leq\operatorname{negl}(n). \tag{1} \end{equation}

Here \(\operatorname{negl}(n)<n^{-a}\) eventually for every constant \(a>0\). One hidden unitary is sampled and reused; inverse, transpose, conjugate, and controlled-unitary oracles are not supplied.

Fix a finite universal gate set \(\mathcal G\subset SU(4)\). At each step choose a qubit pair and a gate from \(\mathcal G\) independently and uniformly, and let \(U_{n,m}\) be the resulting circuit. Do constants \(c,C_{\mathcal G}>0\) exist such that

\begin{equation} \mathcal U_n=\{U_{n,m(n)}:m(n)=\lceil C_{\mathcal G}n^c\rceil\} \tag{2} \end{equation}

satisfies the pseudorandomness condition in Eq. (1)? Equation (2) fixes one polynomial-size ensemble against all polynomial-time distinguishers.

Source

The question is explicitly posed or retained as open in the cited primary literature [Ji18][Bostanci25][Raza26]. The statement is rewritten here to make its hypotheses and success criterion self-contained.

Progress

Status: source-explicit conjecture, with a September 2026 consistency check. The HPS paper states this conjecture rather than proving it. The introduction of the September 2026 distinctness paper still describes cryptographic pseudorandomness of random circuits as a belief, not an established general theorem. [Bostanci25][Raza26]
There are strong positive results for approximate designs and for specially constructed low-depth PRUs. Schuster, Haferkamp, and Huang obtain the latter by assembling patches drawn from existing PRU constructions. This does not identify their ensemble with the independent, uniformly sampled two-qubit-gate walk above. [Schuster25]
No subsequent proof or efficient attack resolving this exact random-walk conjecture was located in the literature check.

Comment

The mathematical bottleneck is the order of quantifiers. Proving that circuits of size \(m(n,t)\) emulate \(t\) Haar moments does not show that one fixed polynomial-size ensemble defeats every polynomial-time observer. For example, establishing a bound only through \(t=n^a\) leaves adversaries using \(n^{a+1}\) queries outside the theorem.

Similarly, hardness of classically sampling an output distribution would not by itself establish indistinguishability against a quantum algorithm allowed coherent, adaptive access to the operation.

The question asks whether generic random evolution has cryptographic security, rather than whether a specially engineered cryptographic circuit can imitate random evolution. It is distinct from structured phase–Hadamard pseudorandom-unitary constructions.

References

[Ji18]: Zhengfeng Ji, Yi-Kai Liu, and Fang Song, Pseudorandom Quantum States. Cryptology ePrint 2018/544, CRYPTO 2018. See §6.1 for the PRU definition and §6.2, especially printed p. 23, for the constant-round candidate with different keys.link
[Bostanci25]: Bostanci, Haferkamp, Hangleiter, and Poremba, Efficient Quantum Pseudorandomness from Hamiltonian Phase States. Conjecture 1.1.link
[Raza26]: Raza, Eisert, and Fefferman, Introduction.link
[Schuster25]: Thomas Schuster, Jonas Haferkamp, and Hsin-Yuan Huang, Random unitaries in extremely low depth. Science 389, 92 (2025). See the construction framework and Corollary 2 for the cryptographic assumptions and the use of local PRU ingredients.link

Pseudorandom unitaries from ordinary random two-qubit circuits

Problem

Source

Progress

Comment

References

Cite this problem

BibTeX

Plain text

Problem

Source

Progress

Comment

References

Related problems