Variational Quantum Fidelity Estimation

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 Vari ational 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 no classical algorithm can efficiently solve this problem under reasonable assumptions. Finally, we demonstrate that our bounds can detect quantum phase transitions and are often tighter than previously known computable bounds for realistic situations.