I've seen a lot of analyses on quantum circuit error bound based on the norm difference $\Vert U - V \Vert$.
On the other hand, I've also seen a lot of papers that use the gate fidelity $\frac{1}{2^n}\lvert \text{tr}(U^\dagger V) \rvert$.
Is there a precise relationship between the two, e.g. does one upper bound the other?
The gate fidelity can be expressed with the Frobenius norm as follows: \begin{align*} \min_{\varphi\in\mathbb R}\frac1{2^n}\|U-e^{i\varphi}V\|_2^2&=\min_{\varphi\in\mathbb R} \frac1{2^n}{\rm tr}((U-e^{i\varphi}V)^\dagger (U-e^{i\varphi}V)) \\ &=\min_{\varphi\in\mathbb R}\frac1{2^n}{\rm tr}(U^\dagger U-e^{i\varphi}U^\dagger V-e^{-i\varphi}V^\dagger U+V^\dagger V)\\ &=\min_{\varphi\in\mathbb R}\frac2{2^n}{\rm tr}({\bf1}_{2^n})-\frac1{2^n}{\rm tr}(e^{i\varphi}U^\dagger V+e^{-i\varphi}V^\dagger U)\\ &=2\Big(1-\frac1{2^n}\max_{\varphi\in\mathbb R}{\rm Re}(e^{i\varphi}{\rm tr}(U^\dagger V))\Big)=2\Big(1-\frac1{2^n}|{\rm tr}(U^\dagger V)|\Big)\,. \end{align*} Using the upper bound $\|X\|_2\leq\sqrt m\|X\|_\infty$ which is valid for all $X\in\mathbb C^{m\times m}$ the above identity can be related to the operator norm distance via $$ \frac1{2^n}|{\rm tr}(U^\dagger V)|=1-\frac1{2^{n+1}}\min_{\varphi\in\mathbb R}\|U-e^{i\varphi}V\|_2^2\geq 1-\frac{(\sqrt{2^n})^2}{2^{n+1}}\min_{\varphi\in\mathbb R}\|U-e^{i\varphi}V\|_\infty^2 $$ which altogether yields the following relation: $$ \boxed{\frac{|{\rm tr}(U^\dagger V)|}{2^n}\geq 1-\frac12\min_{\varphi\in\mathbb R}\|U-e^{i\varphi}V\|_\infty^2} $$