Variational Quantum Fidelity Estimation

We present an efficient, near-term algorithm for estimating the well-known fidelity, which quantifies the closeness of quantum states. Our algorithm is an important tool for verifying and characterizing states on a quantum computer. This work is timely given the industrial rise of quantum computing. Prior to our work, there was no efficient algorithm to estimate the fidelity that could be refined to arbitrary tightness. We solve this outstanding problem by introducing novel bounds on the fidelity that can be estimated with hybrid quantum-classical computation. We show that our approach can detect quantum phase transitions and cannot be classical simulated efficiently.