Fundamental solutions of heat equation on unitary groups establish an improved relation between $\epsilon$-nets and approximate unitary $t$-designs

Abstract

The concepts of $\epsilon$-nets and unitary ($\delta$-approximate) $t$-designs are important and ubiquitous across quantum computation and information. Both notions are closely related and the quantitative relations between $t$, $\delta$ and $\epsilon$ find applications in areas such as (non-constructive) inverse-free Solovay-Kitaev like theorems and random quantum circuits. In recent work, quantitative relations have revealed the close connection between the two constructions, with $\epsilon$-nets functioning as unitary $\delta$-approximate $t$-designs and vice-versa, for appropriate choice of parameters. In this work we improve these results, significantly increasing the bound on the $\delta$ required for a $\delta$-approximate $t$-design to form an $\epsilon$-net from $\delta \simeq {\left({\epsilon }^{3/2}/d\right)}^{d^2}$ to $\delta \simeq {\left(\epsilon /d^{1/2}\right)}^{d^2}$. We achieve this by constructing polynomial approximations to the Dirac delta using heat kernels on the projective unitary group $\mathrm{PU}(d)\cong \mathbf{U}(d)$, whose properties we studied and which may be applicable more broadly. We also outline the possible applications of our results in quantum circuit overheads, quantum complexity and black hole physics.

arXiv comment35 pages, 1 figure

References in corpus (29)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Characterizing Quantum Supremacy in Near-Term Devices
• Predicting Many Properties of a Quantum System from Very Few Measurements
• Heat kernel expansion: user's manual
• Quantum Computational Supremacy
• Exact and Approximate Unitary 2-Designs: Constructions and Applications
• Chaos and complexity by design
• Local random quantum circuits are approximate polynomial-designs
• The mother of all protocols: Restructuring quantum information's family tree
• Randomized Benchmarking with Confidence
• Investigating the limits of randomized benchmarking protocols
• Optimizing quantum process tomography with unitary 2-designs
• Efficient Discrete Approximations of Quantum Gates
• Models of quantum complexity growth
• On the Distributions of the Lengths of the Longest Monotone Subsequences in Random Words
• Bounds on the Lambert function and their application to the outage analysis of user cooperation
• Unitary designs and codes
• A Partial Derandomization of PhaseLift using Spherical Designs
• Random bosonic states for robust quantum metrology
• Efficient unitary designs with nearly time-independent Hamiltonian dynamics
• The complexity of energy eigenstates as a mechanism for equilibration
• Decoupling with unitary approximate two-designs
• Anticoncentration theorems for schemes showing a quantum speedup
• Linking Entanglement Detection and State Tomography via Quantum 2-Designs
• Quantum advantage of unitary Clifford circuits with magic state inputs
• Thrifty shadow estimation: re-using quantum circuits and bounding tails
• Iso-entangled mutually unbiased bases, symmetric quantum measurements and mixed-state designs
• Calculable lower bounds on the efficiency of universal sets of quantum gates
• Saturation and recurrence of quantum complexity in random local quantum dynamics