  Efficient measures to determine similarity of quantum states, such as the
fidelity metric, have been widely studied. In this paper, we address the
problem of defining a similarity measure for quantum operations that can be
\textit{efficiently estimated}. Given two quantum operations, $U_1$ and $U_2$,
represented in their circuit forms, we first develop a quantum sampling circuit
to estimate the normalized Schatten 2-norm of their difference ($\| U_1-U_2
\|_{S_2}$) with precision $\epsilon$, using only one clean qubit and one
classical random variable. We prove a Poly$(\frac{1}{\epsilon})$ upper bound on
the sample complexity, which is independent of the size of the quantum system.
We then show that such a similarity metric is directly related to a functional
definition of similarity of unitary operations using the conventional fidelity
metric of quantum states ($F$): If $\| U_1-U_2 \|_{S_2}$ is sufficiently small
(e.g. $ \leq \frac{\epsilon}{1+\sqrt{2(1/\delta - 1)}}$) then the fidelity of
states obtained by processing the same randomly and uniformly picked pure
state, $|\psi \rangle$, is as high as needed ($F({U}_1 |\psi \rangle, {U}_2
|\psi \rangle)\geq 1-\epsilon$) with probability exceeding $1-\delta$. We
provide example applications of this efficient similarity metric estimation
framework to quantum circuit learning tasks, such as finding the square root of
a given unitary operation.
