Random unitaries in extremely low depth
<|reference_start|>Random unitaries in extremely low depth: We prove that random quantum circuits on any geometry, including a 1D line, can form approximate unitary designs over $n$ qubits in $\log n$ depth. In a similar manner, we construct pseudorandom unitaries (PRUs) in 1D circuits in $\text{poly} \log n $ depth, and in all-to-all-connected circuits in $\text{poly} \log \log n $ depth. In all three cases, the $n$ dependence is optimal and improves exponentially over known results. These shallow quantum circuits have low complexity and create only short-range entanglement, yet are indistinguishable from unitaries with exponential complexity. Our construction glues local random unitaries on $\log n$-sized or $\text{poly} \log n$-sized patches of qubits to form a global random unitary on all $n$ qubits. In the case of designs, the local unitaries are drawn from existing constructions of approximate unitary $k$-designs, and hence also inherit an optimal scaling in $k$. In the case of PRUs, the local unitaries are drawn from existing unitary ensembles conjectured to form PRUs. Applications of our results include proving that classical shadows with 1D log-depth Clifford circuits are as powerful as those with deep circuits, demonstrating superpolynomial quantum advantage in learning low-complexity physical systems, and establishing quantum hardness for recognizing phases of matter with topological order.<|reference_end|>
@article{schuster2024random,
    title={Random unitaries in extremely low depth},
    author={Thomas Schuster, Jonas Haferkamp, Hsin-Yuan Huang},
    journal={arXiv preprint arXiv:2407.07754},
    year={2024},
    archivePrefix={arXiv},
    eprint={2407.07754},
    primaryClass={quant-ph cond-mat.str-el cs.CC cs.IT math.IT}
}