arXiv:2112.14284 · IEEE Transactions on Information Theory

Exploring Quantum Average-Case Distances: Proofs, Properties, and Examples

Filip B. Maciejewski, Zbigniew Puchała, Michał Oszmaniec

Published Mar 9, 2023• 8 citations

Abstract

In this work, we present an in-depth study of average-case quantum distances introduced in Maciejewski et al. (2022). The average-case distances approximate, up to the relative error, the average Total-Variation (TV) distance between measurement outputs of two quantum processes, in which quantum objects of interest (states, measurements, or channels) are intertwined with random quantum circuits. Contrary to conventional distances, such as trace distance or diamond norm, they quantifyaverage-casestatistical distinguishability via random quantum circuits. We prove that once a family of random circuits forms an$\delta $-approximate 4-design, with$\delta =o(d^{-8})$, then the average-case distances can be approximated by simple explicit functions that can be expressed via simple degree two polynomials in objects of interest. For systems of moderate dimension, they can be easily explicitly computed – no optimization is needed as opposed to diamond norm distance between channels or operational distance between measurements. We prove that those functions, which we call quantum average-case distances, have a plethora of desirable properties, such as subadditivity w.r.t. tensor products, joint convexity, and (restricted) data-processing inequalities. Notably, all distances utilize the Hilbert-Schmidt (HS) norm, which provides this norm with a new operational interpretation. We also provide upper bounds on the maximal ratio between worst-case and average-case distances, and for each of them, we provide an example that saturates the bound. Specifically, we show that for each dimension$d$this ratio is at most$d^{\frac {1}{2}}, d, d^{\frac {3}{2}}$for states, measurements, and channels, respectively. To support the practical usefulness of our findings, we study multiple examples in which average-case quantum distances can be calculated analytically.

DOI: 10.1109/tit.2023.3250100

Related papers

Operational Quantum Average-Case Distances

Filip B. Maciejewski, Zbigniew Puchała, Michał Oszmaniec

arXiv:2112.14283QuantumSep 11, 20238 citations

Quantum Channel Testing in Average-Case Distance

Rosenthal, Gregory, Hugo Aaronson, Sathyawageeswar Subramanian +2 more

arXiv:2409.12566Sep 19, 20242 citations

Quantum de Finetti theorems for states and channels in any distance measure

Liuhang Ye, Bjarne Bergh, Nilanjana Datta

quant-pharXiv:2609.40343Oct 1, 20260 citations

Average Contraction Coefficients of Quantum Channels

Rubén Ibarrondo, Daniel Stilck França

arXiv:2508.08214Aug 11, 20250 citations

Tightening Continuity Bounds for Entropies and Bounds on Quantum Capacities

Michael G. Jabbour, Nilanjana Datta

arXiv:2310.17329IEEE Journal on Selected Areas in Information TheoryJan 1, 20243 citations

Epsilon-Nets, Unitary Designs, and Random Quantum Circuits

Michał Oszmaniec, Adam Sawicki, Michał Horodecki

arXiv:2007.10885IEEE Transactions on Information TheoryNov 13, 202127 citations

arXiv:2112.14284 · IEEE Transactions on Information Theory

Exploring Quantum Average-Case Distances: Proofs, Properties, and Examples

Filip B. Maciejewski, Zbigniew Puchała, Michał Oszmaniec

Published Mar 9, 2023• 8 citations

arXiv HTML PDF

Abstract

\delta

-approximate 4-design, with

\delta =o(d^{-8})

, then the average-case distances can be approximated by simple explicit functions that can be expressed via simple degree two polynomials in objects of interest. For systems of moderate dimension, they can be easily explicitly computed – no optimization is needed as opposed to diamond norm distance between channels or operational distance between measurements. We prove that those functions, which we call quantum average-case distances, have a plethora of desirable properties, such as subadditivity w.r.t. tensor products, joint convexity, and (restricted) data-processing inequalities. Notably, all distances utilize the Hilbert-Schmidt (HS) norm, which provides this norm with a new operational interpretation. We also provide upper bounds on the maximal ratio between worst-case and average-case distances, and for each of them, we provide an example that saturates the bound. Specifically, we show that for each dimension

d

this ratio is at most

d^{\frac {1}{2}}, d, d^{\frac {3}{2}}

for states, measurements, and channels, respectively. To support the practical usefulness of our findings, we study multiple examples in which average-case quantum distances can be calculated analytically.

DOI: 10.1109/tit.2023.3250100

Related papers

Operational Quantum Average-Case Distances

Filip B. Maciejewski, Zbigniew Puchała, Michał Oszmaniec

We introduce distance measures between quantum states, measurements, and channels based on their statistical distinguishability in generic experiments. Specifically, we analyze the average Total Variation Distance (TVD) between output statistics of protocols in which quantum objects are intertwined with random circuits and measured in standard basis. We show that for circuits forming approximate 4-designs, the average TVDs can be approximated by simple explicit functions of the underlying objects – the average-case distances (ACDs). We apply them to analyze the effects of noise in quantum advantage experiments and for efficient discrimination of high-dimensional states and channels without quantum memory. We argue that ACDs are better suited for assessing the quality of NISQ devices than common distance measures such as trace distance or the diamond norm.We introduce distance measures between quantum states, measurements, and channels based on their statistical distinguishability in generic experiments. Specifically, we analyze the average Total Variation Distance (TVD) between output statistics of protocols in which quantum objects are intertwined with random circuits and measured in standard basis. We show that for circuits forming approximate 4-designs, the average TVDs can be approximated by simple explicit functions of the underlying objects – the average-case distances (ACDs). We apply them to analyze the effects of noise in quantum advantage experiments and for efficient discrimination of high-dimensional states and channels without quantum memory. We argue that ACDs are better suited for assessing the quality of NISQ devices than common distance measures such as trace distance or the diamond norm.

arXiv:2112.14283QuantumSep 11, 20238 citations

Quantum Channel Testing in Average-Case Distance

Rosenthal, Gregory, Hugo Aaronson, Sathyawageeswar Subramanian +2 more

We study the complexity of testing properties of quantum channels. First, we show that testing identity to any channel $\mathcal N: \mathbb C^{d_{\mathrm{in}} \times d_{\mathrm{in}}} \to \mathbb C^{d_{\mathrm{out}} \times d_{\mathrm{out}}}$ in diamond norm distance requires $Ω(\sqrt{d_{\mathrm{in}}} / \varepsilon)$ queries, even in the strongest algorithmic model that admits ancillae, coherence, and adaptivity. This is due to the worst-case nature of the distance induced by the diamond norm. Motivated by this limitation and other theoretical and practical applications, we introduce an average-case analogue of the diamond norm, which we call the average-case imitation diamond (ACID) norm. In the weakest algorithmic model without ancillae, coherence, or adaptivity, we prove that testing identity to certain types of channels in ACID distance can be done with complexity independent of the dimensions of the channel, while for other types of channels the complexity depends on both the input and output dimensions. Building on previous work, we also show that identity to any fixed channel can be tested with $\tilde O(d_{\mathrm{in}} d_{\mathrm{out}}^{3/2} / \varepsilon^2)$ queries in ACID distance and $\tilde O(d_{\mathrm{in}}^2 d_{\mathrm{out}}^{3/2} / \varepsilon^2)$ queries in diamond distance in this model. Finally, we prove tight bounds on the complexity of channel tomography in ACID distance.We study the complexity of testing properties of quantum channels. First, we show that testing identity to any channel $\mathcal N: \mathbb C^{d_{\mathrm{in}} \times d_{\mathrm{in}}} \to \mathbb C^{d_{\mathrm{out}} \times d_{\mathrm{out}}}$ in diamond norm distance requires $Ω(\sqrt{d_{\mathrm{in}}} / \varepsilon)$ queries, even in the strongest algorithmic model that admits ancillae, coherence, and adaptivity. This is due to the worst-case nature of the distance induced by the diamond norm. Motivated by this limitation and other theoretical and practical applications, we introduce an average-case analogue of the diamond norm, which we call the average-case imitation diamond (ACID) norm. In the weakest algorithmic model without ancillae, coherence, or adaptivity, we prove that testing identity to certain types of channels in ACID distance can be done with complexity independent of the dimensions of the channel, while for other types of channels the complexity depends on both the input and output dimensions. Building on previous work, we also show that identity to any fixed channel can be tested with $\tilde O(d_{\mathrm{in}} d_{\mathrm{out}}^{3/2} / \varepsilon^2)$ queries in ACID distance and $\tilde O(d_{\mathrm{in}}^2 d_{\mathrm{out}}^{3/2} / \varepsilon^2)$ queries in diamond distance in this model. Finally, we prove tight bounds on the complexity of channel tomography in ACID distance.

arXiv:2409.12566Sep 19, 20242 citations

Quantum de Finetti theorems for states and channels in any distance measure

Liuhang Ye, Bjarne Bergh, Nilanjana Datta

Standard finite quantum de Finetti theorems approximate the $k$ -system marginals of permutation-invariant states of $n$ -systems by mixtures of independent and identically distributed (iid) states, usually in trace distance. We prove both standard and Renner's exponential de Finetti theorems in the stronger form of operator inequalities, implying bounds in every Schatten norm and for every quantum Rényi divergence satisfying data processing. In the standard case, for fixed local dimension, our $k/n$ error bound in max-relative entropy improves on the previously best known $k^2/n$ scaling, even in the classical setting. The operator-inequality approach is particularly suited to study channel de Finetti representations because operator order between Choi states is equivalent to completely positive (CP) order between the underlying channels. For permutation-covariant channels $N^{(n)}:A^{\otimes n}\to B^{\otimes n}$ , where $d_A=\dim A$ , we prove that the $k$ -system reduced channel is CP-dominated by a mixture of tensor-power channels with error $O(k/\sqrt{n})$ and polynomial dependence on the local dimensions, addressing a question raised by Berta et al. [Math. Program. 194, 781-829 (2022)]. Under the no-signalling condition, we also prove an exponential channel de Finetti theorem where the approximating mixture consists of Choi-almost-iid channels, whose normalized Choi states are almost-iid in the sense of Mazzola-Sutter-Renner. In the case of $r$ defects, the representation error is at most $\mathrm{poly}(n)\bigl(2d_A^4k^3/(nr^2)\bigr)^{(r+1)/2}$ and decays exponentially in $n$ for a suitable choice of parameters $r$ and $k$ .Standard finite quantum de Finetti theorems approximate the $k$-system marginals of permutation-invariant states of $n$-systems by mixtures of independent and identically distributed (iid) states, usually in trace distance. We prove both standard and Renner's exponential de Finetti theorems in the stronger form of operator inequalities, implying bounds in every Schatten norm and for every quantum Rényi divergence satisfying data processing. In the standard case, for fixed local dimension, our $k/n$ error bound in max-relative entropy improves on the previously best known $k^2/n$ scaling, even in the classical setting. The operator-inequality approach is particularly suited to study channel de Finetti representations because operator order between Choi states is equivalent to completely positive (CP) order between the underlying channels. For permutation-covariant channels $N^{(n)}:A^{\otimes n}\to B^{\otimes n}$, where $d_A=\dim A$, we prove that the $k$-system reduced channel is CP-dominated by a mixture of tensor-power channels with error $O(k/\sqrt{n})$ and polynomial dependence on the local dimensions, addressing a question raised by Berta et al. [Math. Program. 194, 781-829 (2022)]. Under the no-signalling condition, we also prove an exponential channel de Finetti theorem where the approximating mixture consists of Choi-almost-iid channels, whose normalized Choi states are almost-iid in the sense of Mazzola-Sutter-Renner. In the case of $r$ defects, the representation error is at most $\mathrm{poly}(n)\bigl(2d_A^4k^3/(nr^2)\bigr)^{(r+1)/2}$ and decays exponentially in $n$ for a suitable choice of parameters $r$ and $k$.

quant-pharXiv:2609.40343Oct 1, 20260 citations

Average Contraction Coefficients of Quantum Channels

Rubén Ibarrondo, Daniel Stilck França

The data-processing inequality ensures quantum channels reduce state distinguishability, with contraction coefficients quantifying optimal bounds. However, these can be overly optimistic and not representative of the usual behavior. We study how noise contracts distinguishability of `typical' states, beyond the worst-case. To that end, we introduce and study a family of moments of contraction for quantum divergences, which interpolate between the worst-case contraction coefficient of a channel and its average behavior under a chosen ensemble of input states. We establish general properties of these moments, relate moments for different divergences, and derive bounds in terms of channel parameters like the entropy or purity of its Choi state. Focusing on the trace distance, we obtain upper and lower bounds on its average contraction under tensor-product noise channels, and prove that, depending on the local noise strength, there is a phase transition in the limit of many channel uses: below a critical error rate the average contraction remains near unity, whereas above it decays exponentially with system size. We extend these phase-transition phenomena to random quantum circuits with unital noise, showing that constant-depth noisy circuits do not shrink the trace distance on average, even when given highly entangled states as input. In contrast, even at $\log\log n$ depth, the average trace distance can become superpolynomially small. Finally, we explore moments of contraction for f-divergences and discuss applications to local differential privacy, demonstrating that noise regimes ensuring privacy can render outputs essentially indistinguishable on average. Thus, our results provide a fine-grained framework to quantify typical channel noise in quantum information and computation and unveil new phenomena in contraction coefficients, such as phase transitions for average contraction.The data-processing inequality ensures quantum channels reduce state distinguishability, with contraction coefficients quantifying optimal bounds. However, these can be overly optimistic and not representative of the usual behavior. We study how noise contracts distinguishability of `typical' states, beyond the worst-case. To that end, we introduce and study a family of moments of contraction for quantum divergences, which interpolate between the worst-case contraction coefficient of a channel and its average behavior under a chosen ensemble of input states. We establish general properties of these moments, relate moments for different divergences, and derive bounds in terms of channel parameters like the entropy or purity of its Choi state. Focusing on the trace distance, we obtain upper and lower bounds on its average contraction under tensor-product noise channels, and prove that, depending on the local noise strength, there is a phase transition in the limit of many channel uses: below a critical error rate the average contraction remains near unity, whereas above it decays exponentially with system size. We extend these phase-transition phenomena to random quantum circuits with unital noise, showing that constant-depth noisy circuits do not shrink the trace distance on average, even when given highly entangled states as input. In contrast, even at $\log\log n$ depth, the average trace distance can become superpolynomially small. Finally, we explore moments of contraction for f-divergences and discuss applications to local differential privacy, demonstrating that noise regimes ensuring privacy can render outputs essentially indistinguishable on average. Thus, our results provide a fine-grained framework to quantify typical channel noise in quantum information and computation and unveil new phenomena in contraction coefficients, such as phase transitions for average contraction.

arXiv:2508.08214Aug 11, 20250 citations

Tightening Continuity Bounds for Entropies and Bounds on Quantum Capacities

Michael G. Jabbour, Nilanjana Datta

Uniform continuity bounds on entropies are generally expressed in terms of a single distance measure between probability distributions or quantum states, typically, the total variation- or trace distance. However, if an additional distance measure is known, the continuity bounds can be significantly strengthened. Here, we prove a tight uniform continuity bound for the Shannon entropy in terms of both the local- and total variation distances, sharpening an inequality in (Sason, 2013). We also obtain a uniform continuity bound for the von Neumann entropy in terms of both the operator norm- and trace distances. We then apply our results to compute upper bounds on channel capacities. We first refine the concept of approximate degradable channels by introducing $(\varepsilon ,\nu)$ –degradable channels. These are$\varepsilon $–close in diamond norm and$ \nu $–close in completely bounded spectral norm to their complementary channel when composed with a degrading channel. This leads to improved upper bounds to the quantum- and private classical capacities of such channels. Moreover, these bounds can be further improved by considering certain unstabilized versions of the above norms. We show that upper bounds on the latter can be efficiently expressed as semidefinite programs. As an application, we obtain a new upper bound on the quantum capacity of the qubit depolarizing channel.Uniform continuity bounds on entropies are generally expressed in terms of a single distance measure between probability distributions or quantum states, typically, the total variation- or trace distance. However, if an additional distance measure is known, the continuity bounds can be significantly strengthened. Here, we prove a tight uniform continuity bound for the Shannon entropy in terms of both the local- and total variation distances, sharpening an inequality in (Sason, 2013). We also obtain a uniform continuity bound for the von Neumann entropy in terms of both the operator norm- and trace distances. We then apply our results to compute upper bounds on channel capacities. We first refine the concept of approximate degradable channels by introducing$(\varepsilon ,\nu)$–degradable channels. These are$\varepsilon $–close in diamond norm and$\nu $–close in completely bounded spectral norm to their complementary channel when composed with a degrading channel. This leads to improved upper bounds to the quantum- and private classical capacities of such channels. Moreover, these bounds can be further improved by considering certain unstabilized versions of the above norms. We show that upper bounds on the latter can be efficiently expressed as semidefinite programs. As an application, we obtain a new upper bound on the quantum capacity of the qubit depolarizing channel.

arXiv:2310.17329IEEE Journal on Selected Areas in Information TheoryJan 1, 20243 citations

Epsilon-Nets, Unitary Designs, and Random Quantum Circuits

Michał Oszmaniec, Adam Sawicki, Michał Horodecki

Epsilon-nets and approximate unitary $t$ -designs are natural notions that capture properties of unitary operations relevant for numerous applications in quantum information and quantum computing. In this work we study quantitative connections between these two notions. Specifically, we prove that, for $d$ dimensional Hilbert space, unitaries constituting$\delta $-approximate$ t $-expanders form$ \epsilon $-nets for$ t\simeq \frac {d^{5/2}}{ \epsilon } $and$ \delta \simeq \left ({\frac { \epsilon ^{3/2}}{d}}\right)^{d^{2}} $. We also show that for arbitrary$ t $,$ \epsilon $-nets can be used to construct$ \delta $-approximate unitary$ t $-designs for$ \delta \simeq \epsilon t $, where the notion of approximation is based on the diamond norm. Finally, we prove that the degree of an exact unitary$ t $design necessary to obtain an$ \epsilon $-net must grow at least as fast as$ \frac {1}{ \epsilon } $(for fixed dimension) and not slower than$ d^{2} $(for fixed$ \epsilon $). This shows near optimality of our result connecting$ t $-designs and$ \epsilon $-nets. We apply our findings in the context of quantum computing. First, we show that that approximate t-designs can be generated by shallow random circuits formed from a set of universal two-qudit gates in the parallel and sequential local architectures considered in (Brandão et al., 2016). Importantly, our gate sets need not to be symmetric (i.e., contains gates together with their inverses) or consist of gates with algebraic entries. Second, we consider compilation of quantum gates and prove a non-constructive Solovay-Kitaev theorem for general universal gate sets. Our main technical contribution is a new construction of efficient polynomial approximations to the Dirac delta in the space of quantum channels, which can be of independent interest.Epsilon-nets and approximate unitary$t$-designs are natural notions that capture properties of unitary operations relevant for numerous applications in quantum information and quantum computing. In this work we study quantitative connections between these two notions. Specifically, we prove that, for$d$dimensional Hilbert space, unitaries constituting$\delta $-approximate$t$-expanders form$\epsilon $-nets for$t\simeq \frac {d^{5/2}}{ \epsilon }$and$\delta \simeq \left ({\frac { \epsilon ^{3/2}}{d}}\right)^{d^{2}}$. We also show that for arbitrary$t$,$\epsilon $-nets can be used to construct$\delta $-approximate unitary$t$-designs for$\delta \simeq \epsilon t$, where the notion of approximation is based on the diamond norm. Finally, we prove that the degree of an exact unitary$t$design necessary to obtain an$\epsilon $-net must grow at least as fast as$\frac {1}{ \epsilon }$(for fixed dimension) and not slower than$d^{2}$(for fixed$\epsilon $). This shows near optimality of our result connecting$t$-designs and$\epsilon $-nets. We apply our findings in the context of quantum computing. First, we show that that approximate t-designs can be generated by shallow random circuits formed from a set of universal two-qudit gates in the parallel and sequential local architectures considered in (Brandão et al., 2016). Importantly, our gate sets need not to be symmetric (i.e., contains gates together with their inverses) or consist of gates with algebraic entries. Second, we consider compilation of quantum gates and prove a non-constructive Solovay-Kitaev theorem for general universal gate sets. Our main technical contribution is a new construction of efficient polynomial approximations to the Dirac delta in the space of quantum channels, which can be of independent interest.

arXiv:2007.10885IEEE Transactions on Information TheoryNov 13, 202127 citations

\delta

-approximate 4-design, with

\delta =o(d^{-8})

d

this ratio is at most

d^{\frac {1}{2}}, d, d^{\frac {3}{2}}

We study the complexity of testing properties of quantum channels. First, we show that testing identity to any channel

\mathcal N: \mathbb C^{d_{\mathrm{in}} \times d_{\mathrm{in}}} \to \mathbb C^{d_{\mathrm{out}} \times d_{\mathrm{out}}}

in diamond norm distance requires

Ω(\sqrt{d_{\mathrm{in}}} / \varepsilon)

queries, even in the strongest algorithmic model that admits ancillae, coherence, and adaptivity. This is due to the worst-case nature of the distance induced by the diamond norm. Motivated by this limitation and other theoretical and practical applications, we introduce an average-case analogue of the diamond norm, which we call the average-case imitation diamond (ACID) norm. In the weakest algorithmic model without ancillae, coherence, or adaptivity, we prove that testing identity to certain types of channels in ACID distance can be done with complexity independent of the dimensions of the channel, while for other types of channels the complexity depends on both the input and output dimensions. Building on previous work, we also show that identity to any fixed channel can be tested with

\tilde O(d_{\mathrm{in}} d_{\mathrm{out}}^{3/2} / \varepsilon^2)

queries in ACID distance and

\tilde O(d_{\mathrm{in}}^2 d_{\mathrm{out}}^{3/2} / \varepsilon^2)

queries in diamond distance in this model. Finally, we prove tight bounds on the complexity of channel tomography in ACID distance.

Standard finite quantum de Finetti theorems approximate the

k

-system marginals of permutation-invariant states of

n

-systems by mixtures of independent and identically distributed (iid) states, usually in trace distance. We prove both standard and Renner's exponential de Finetti theorems in the stronger form of operator inequalities, implying bounds in every Schatten norm and for every quantum Rényi divergence satisfying data processing. In the standard case, for fixed local dimension, our

k/n

error bound in max-relative entropy improves on the previously best known

k^2/n

scaling, even in the classical setting. The operator-inequality approach is particularly suited to study channel de Finetti representations because operator order between Choi states is equivalent to completely positive (CP) order between the underlying channels. For permutation-covariant channels

N^{(n)}:A^{\otimes n}\to B^{\otimes n}

, where

d_A=\dim A

, we prove that the

k

-system reduced channel is CP-dominated by a mixture of tensor-power channels with error

O(k/\sqrt{n})

and polynomial dependence on the local dimensions, addressing a question raised by Berta et al. [Math. Program. 194, 781-829 (2022)]. Under the no-signalling condition, we also prove an exponential channel de Finetti theorem where the approximating mixture consists of Choi-almost-iid channels, whose normalized Choi states are almost-iid in the sense of Mazzola-Sutter-Renner. In the case of

r

defects, the representation error is at most

\mathrm{poly}(n)\bigl(2d_A^4k^3/(nr^2)\bigr)^{(r+1)/2}

and decays exponentially in

n

for a suitable choice of parameters

r

and

k

\log\log n

depth, the average trace distance can become superpolynomially small. Finally, we explore moments of contraction for f-divergences and discuss applications to local differential privacy, demonstrating that noise regimes ensuring privacy can render outputs essentially indistinguishable on average. Thus, our results provide a fine-grained framework to quantify typical channel noise in quantum information and computation and unveil new phenomena in contraction coefficients, such as phase transitions for average contraction.

(\varepsilon ,\nu)

–degradable channels. These are$\varepsilon

–close in diamond norm and

\nu $–close in completely bounded spectral norm to their complementary channel when composed with a degrading channel. This leads to improved upper bounds to the quantum- and private classical capacities of such channels. Moreover, these bounds can be further improved by considering certain unstabilized versions of the above norms. We show that upper bounds on the latter can be efficiently expressed as semidefinite programs. As an application, we obtain a new upper bound on the quantum capacity of the qubit depolarizing channel.

Epsilon-nets and approximate unitary

t

-designs are natural notions that capture properties of unitary operations relevant for numerous applications in quantum information and quantum computing. In this work we study quantitative connections between these two notions. Specifically, we prove that, for

d

dimensional Hilbert space, unitaries constituting$\delta

-approximate

-expanders form

\epsilon

-nets for

t\simeq \frac {d^{5/2}}{ \epsilon }

and

\delta \simeq \left ({\frac { \epsilon ^{3/2}}{d}}\right)^{d^{2}}

. We also show that for arbitrary

,

\epsilon

-nets can be used to construct

\delta

-approximate unitary

-designs for

\delta \simeq \epsilon t

, where the notion of approximation is based on the diamond norm. Finally, we prove that the degree of an exact unitary

design necessary to obtain an

\epsilon

-net must grow at least as fast as

\frac {1}{ \epsilon }

(for fixed dimension) and not slower than

d^{2}

(for fixed

\epsilon

). This shows near optimality of our result connecting

-designs and

\epsilon $-nets. We apply our findings in the context of quantum computing. First, we show that that approximate t-designs can be generated by shallow random circuits formed from a set of universal two-qudit gates in the parallel and sequential local architectures considered in (Brandão et al., 2016). Importantly, our gate sets need not to be symmetric (i.e., contains gates together with their inverses) or consist of gates with algebraic entries. Second, we consider compilation of quantum gates and prove a non-constructive Solovay-Kitaev theorem for general universal gate sets. Our main technical contribution is a new construction of efficient polynomial approximations to the Dirac delta in the space of quantum channels, which can be of independent interest.