Approximate Unitary $k$-Designs from Shallow, Low-Communication Circuits

Abstract

Random unitaries are useful in quantum information and related fields, but hard to generate with limited resources. An approximate unitary $k$-design is an ensemble of unitaries with an underlying measure over which the average is close to a Haar random ensemble up to the first $k$ moments. A particularly strong notion of approximation bounds the distance from Haar randomness in relative error. Such relative-error approximate designs are secure against queries by an adaptive adversary trying to distinguish it from a Haar ensemble. We construct relative-error approximate unitary $k$-design ensembles for which communication between subsystems is $O(1)$ in the system size. These constructions use the alternating projection method to analyze overlapping Haar averages, giving a bound on the convergence speed to the full averaging with respect to the $2$-norm. Using von Neumann subalgebra indices to replace system dimension, the 2-norm distance converts to relative error without introducing any additional dimension dependence. We use these constructions as the building blocks of a two-step protocol that achieves a relative-error design in $O((\log m+\log (1/\epsilon )+k\log k)k\text{polylog}(k))$ depth, where $m$ is the number of qudits in the complete system and $\epsilon$ the approximation error. This sublinear depth construction answers a variant of [Harrow and Mehraban 2023, Section 1.5, Open Questions 1 and 7]. Moreover, entanglement generated by the sublinear depth scheme follows area laws on spatial lattices up to corrections logarithmic in the full system size.

47 pages, 2 figures. v3: Numerous improvements to presentation and streamlined proof of main result. Identical to published version

References in corpus (21)

• Area laws for the entanglement entropy - a review
• Random Quantum Circuits are Approximate 2-designs
• Local random quantum circuits are approximate polynomial-designs
• Barren Plateaus in Variational Quantum Computing
• A decoupling approach to the quantum capacity
• Introduction to Haar Measure Tools in Quantum Information: A Beginner's Tutorial
• Approximate unitary $t$-designs by short random quantum circuits using nearest-neighbor and long-range gates
• Models of quantum complexity growth
• Decoupling with random quantum circuits
• Efficient unitary designs with nearly time-independent Hamiltonian dynamics
• A Random Unitary Circuit Model for Black Hole Evaporation
• Large Deviation Bounds for k-designs
• Tight bounds on the convergence of noisy random circuits to the uniform distribution
• Complete entropic inequalities for quantum Markov chains
• Improved spectral gaps for random quantum circuits: large local dimensions and all-to-all interactions
• Thrifty shadow estimation: re-using quantum circuits and bounding tails
• Relative entropy for von Neumann subalgebras
• Efficient unitary designs and pseudorandom unitaries from permutations
• Efficient Unitary T-designs from Random Sums
• Approximate orthogonality of permutation operators, with application to quantum information
• Quasi-factorization and Multiplicative Comparison of Subalgebra-Relative Entropy

Cited by in corpus (6)

• Designs from magic-augmented Clifford circuits
• Non-Clifford Cost of Random Unitaries
• Realizing Unitary $k$-designs with a Single Quench
• Fermionic Averaged Circuit Eigenvalue Sampling
• Short remarks on shallow unitary circuits
• More global randomness from less-random local gates