Assume to have query access to the values $p(x)$, and $q(x)$ of two probability distributions over n elements $x \in X$, $|X|=n$. That is, for a given $x\in X$ we pay constant time $O(1)$ to perform a query to $p$ or $q$.
What is the fastest randomized algorithm for estimating the trace distance between $p$ and $q$? Formally, I would like to know the fastest algorithm in literature to estimate $\widetilde{T}$ such that $|T-\widetilde{T}|<\epsilon$ with probability $1-\delta$ where $T$ is:
$$T = \frac{1}{2}\sum_{x \in X} |p(x) -q(x)| $$
I am looking for all the type of cases: average time, worst time.. I would ready any paper that is relevat to this question, so to understand when it's important to estimate trace distances.