  Estimating the difference between quantum data is crucial in quantum
computing. In particular, trace distance and quantum fidelity are vital for
verifying various quantum information processing tasks. In this work, we
introduce hybrid quantum-classical algorithms for practical distance measure
estimation on near-term quantum devices. First, we introduce the Variational
Trace Distance Estimation (VTDE) algorithm. We in particular show that local
measurement results can extract the desired spectrum information of any
Hermitian matrix. We further exploit this fact to design a novel variational
algorithm for trace norm estimation that only involves one ancillary qubit.
Notably, the cost function in VTDE gathers information from a single-qubit
observable and thus could avoid the barren plateau issue with logarithmic depth
parameterized circuits. Second, we introduce the Variational Fidelity
Estimation (VFE) algorithm. We combine Uhlmann's theorem and the freedom in
purification to translate the estimation task into an optimization problem over
a unitary on an ancillary system with fixed purified inputs. We then introduce
a purification subroutine to complete the task. Numerical experiments for both
algorithms have been conducted to show the validity of our methods. The metrics
are estimated with high accuracy for randomly generated mixed states.
