Simple quantum steps do not always mimic random quantum behavior
On the pseudorandomness of simple quantum processes
Cryptography and Security
Summary
Some processes can look very complex even if they are made by repeating simple steps. The authors studied this idea for quantum systems, which use tiny particles that follow special rules. They found that certain mathematical properties thought to mean a system looks random do not always prevent someone from spotting a pattern quickly. This means that even quantum systems that seem very scrambled can still have hidden structure detectable by efficient methods. Their work also suggests new ways to think about when quantum systems truly behave like random ones.
What this means in practice
- •For quantum hardware engineers: Identify limitations of existing randomization methods in quantum circuits to design more robust quantum processors.
- •For quantum software developers: Develop new algorithms that use careful circuit design to better achieve pseudorandom quantum states for cryptographic or simulation tasks.
A theory result. No direct application yet.
Authors
Jesko Dujmovic, Jonas Haferkamp, Alexander Poremba
Abstract
Can simple processes appear highly complex? Gowers (Comb. Prob. Comp. '96) conjectured that repeatedly composing local random reversible operations can yield global permutations that are indistinguishable from random. In this work, we study the unitary quantum analog of this question, in an attempt to make new progress on this longstanding conjecture. Our first result shows that statistical moment matching in the form of unitary designs does not generically lead to pseudorandomness---even for the simplest quantum processes: for every fixed $t$, we give an efficiently samplable family $\{ν_n\}_n$ of distributions on one- and two-qubit gates such that, after $T=O_t(n^2\log^2 n)$ independent steps, the resulting $n$-qubit ensemble is an approximate unitary $t$-design with negligible error $\exp(-Ω(\log^2 n))$, yet an efficient quantum algorithm distinguishes it from random using only $O_t(\log^2 n)$ queries. This refutes the unitary analog of the Hoory--Magen--Myers--Rackoff conjecture (ICALP '04) for permutations. Our second result is a stronger separation between unitary designs and pseudorandom unitaries at polynomially bounded moments; our counterexample, however, requires highly structured ensembles, in contrast with the simple local walks from before. This suggests caution when using unitary designs to model information scrambling in black-hole physics, as even maximally scrambled systems can exhibit structure which is accessible to efficient experiments. Motivated by these findings, we then propose new conjectures for how pseudorandomness can plausibly emerge within simple quantum processes, such as random quantum circuits.