Computing quantum state fidelity will be important to verify and characterize
states prepared on a quantum computer. In this work, we propose novel lower and
upper bounds for the fidelity $F(\rho,\sigma)$ based on the "truncated
fidelity" $F(\rho_m, \sigma)$, which is evaluated for a state $\rho_m$ obtained
by projecting $\rho$ onto its $m$-largest eigenvalues. Our bounds can be
refined, i.e., they tighten monotonically with $m$. To compute our bounds, we
introduce a hybrid quantum-classical algorithm, called Variational Quantum
Fidelity Estimation, that involves three steps: (1) variationally diagonalize
$\rho$, (2) compute matrix elements of $\sigma$ in the eigenbasis of $\rho$,
and (3) combine these matrix elements to compute our bounds. Our algorithm is
aimed at the case where $\sigma$ is arbitrary and $\rho$ is low rank, which we
call low-rank fidelity estimation, and we prove that a classical algorithm
cannot efficiently solve this problem. Finally, we demonstrate that our bounds
can detect quantum phase transitions and are often tighter than previously
known computable bounds for realistic situations.

本文提出了一种基于截断保真度来计算量子状态保真度上下界的新方法，其可以用于低秩情况下的保真度估计，并证明了这是一个经典算法无法高效解决的问题，同时展示了该方法的应用能够检测到量子相变并且往往比以前已知的可计算边界更加紧密。