APPROXIMATE UNITARY k-DESIGNS FROM SHALLOW, LOW-COMMUNICATION CIRCUITS

APPROXIMATE UNITARY k-DESIGNS FROM SHALLOW, LOW-COMMUNICATION CIRCUITS

11 Jul 2024 | NICHOLAS LARACUENTE AND FELIX LEDITZKY
The paper "Approximate Unitary $k$-Designs from Shallow, Low-Communication Circuits" by Nicholas Laracuente and Felix Leditzky addresses the challenge of generating random unitaries in quantum information and related fields, which are difficult to produce with limited resources. The authors focus on approximate unitary $k$-designs, which are ensembles of unitaries that are close to a Haar (uniformly random) ensemble up to the first $k$ moments. They construct multiplicative-error approximate unitary $k$-design ensembles with communication between subsystems that is $O(1)$ in the system size. This is achieved using the alternating projection method to analyze overlapping Haar twirls, providing a bound on the convergence speed to the full twirl with respect to the 2-norm. By using von Neumann subalgebra indices to replace system dimension, the 2-norm distance is converted to relative error without introducing additional dimension dependence. The authors then construct a scheme that yields relative error designs in $O((k \log k + \log m + \log (1/\epsilon)) k \text{polylog}(k))$ depth, where $m$ is the number of qubits and $\epsilon$ is the approximation error. This sublinear depth construction answers a variant of an open problem posed by Harrow and Mehraban in 2023. Additionally, the entanglement generated by the sublinear depth scheme follows an area law on spatial lattices, up to corrections logarithmic in the full system size. The paper includes detailed proofs and technical results, including bounds on the subspace angle and convergence rates, and discusses the implications and potential applications of these findings.The paper "Approximate Unitary $k$-Designs from Shallow, Low-Communication Circuits" by Nicholas Laracuente and Felix Leditzky addresses the challenge of generating random unitaries in quantum information and related fields, which are difficult to produce with limited resources. The authors focus on approximate unitary $k$-designs, which are ensembles of unitaries that are close to a Haar (uniformly random) ensemble up to the first $k$ moments. They construct multiplicative-error approximate unitary $k$-design ensembles with communication between subsystems that is $O(1)$ in the system size. This is achieved using the alternating projection method to analyze overlapping Haar twirls, providing a bound on the convergence speed to the full twirl with respect to the 2-norm. By using von Neumann subalgebra indices to replace system dimension, the 2-norm distance is converted to relative error without introducing additional dimension dependence. The authors then construct a scheme that yields relative error designs in $O((k \log k + \log m + \log (1/\epsilon)) k \text{polylog}(k))$ depth, where $m$ is the number of qubits and $\epsilon$ is the approximation error. This sublinear depth construction answers a variant of an open problem posed by Harrow and Mehraban in 2023. Additionally, the entanglement generated by the sublinear depth scheme follows an area law on spatial lattices, up to corrections logarithmic in the full system size. The paper includes detailed proofs and technical results, including bounds on the subspace angle and convergence rates, and discusses the implications and potential applications of these findings.
Reach us at info@study.space
[slides and audio] Approximate Unitary %24k%24-Designs from Shallow%2C Low-Communication Circuits