Fast pseudorandom quantum state generators via inflationary quantum gates

Abstract

Abstract We propose a mechanism for reaching pseudorandom quantum states, computationally indistinguishable from Haar random, with shallow log-n depth quantum circuits, where n is the number of qudits. We argue that $$\log n$$ log n depth 2-qubit-gate-based generic random quantum circuits that are claimed to provide a lower bound on the speed of information scrambling, cannot produce computationally pseudorandom quantum states. This conclusion is connected with the presence of polynomial (in n) tails in the stay probability of short Pauli strings that survive evolution through such shallow circuits. We show, however, that stay-probability-tails can be eliminated and pseudorandom quantum states can be accomplished with shallow $$\log n$$ log n depth circuits built from a special universal family of “inflationary” quantum (IQ) gates. We prove that IQ-gates cannot be implemented with 2-qubit gates, but can be realized either as a subset of 2-qudit-gates in U(d 2) with d ≥ 3 and d prime, or as special 3-qubit gates.