Jonas
Haferkamp
Saarland University
We prove that random quantum circuits on any geometry, including a one-dimensional line, can form approximate unitary designs over n qubits with logarithmic depth in n. In a similar spirit, we construct pseudorandom unitaries in one-dimensional circuits with polylogarithmic depth, and in all-to-all connected circuits with polyloglogarithmic depth. In all three settings, the dependence on n is optimal and yields an exponential improvement over previously known results.
These shallow quantum circuits have low complexity and generate only short-range entanglement, yet they are indistinguishable from unitaries of exponential complexity. Our construction proceeds by gluing together local random unitaries acting on patches of qubits of logarithmic or polylogarithmic size, thereby forming a global random unitary on all n qubits.
In the case of approximate unitary designs, the local unitaries are drawn from existing constructions of approximate unitary k-designs and therefore inherit optimal scaling in k. For pseudorandom unitaries, the local components are drawn from existing PRU constructions.
Applications of our results include showing that classical shadows generated by one-dimensional logarithmic-depth Clifford circuits are as powerful as those obtained from deep circuits, demonstrating a superpolynomial quantum advantage in learning low-complexity physical systems, and establishing quantum hardness for recognizing phases of matter with topological order.
