# Variational Quantum Fidelity Estimation

1Theoretical Division, Los Alamos National Laboratory, Los Alamos, NM, USA
2Center for Nonlinear Studies, Los Alamos National Laboratory, Los Alamos, NM, USA
3Computing and Mathematical Sciences, California Institute of Technology, Pasadena, CA, USA.

### Abstract

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 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.

In the past few years, there has been tremendous progress towards the development of near-term quantum devices. Today's quantum computers have limited number of qubits to work with, and are prone to noise-induced error. Nevertheless, despite those limitations, it has been recently shown that they can outperform our current supercomputers, being able to prepare quantum states that cannot be classically simulated. Hence, a very important question becomes: How do we verify and characterize these states prepared on a quantum computer?

Estimating a state's fidelity to a target state provides a $mean$ to verify and characterize the state. However, estimating the fidelity is known to $\textit{be a computationally}$ difficult task for a classical or even a quantum computer. Specifically, no classical or quantum algorithm exists to efficiently compute such quantities. In this work we introduce a hybrid quantum-classical algorithm to estimate the fidelity for the practically important case when one of the two states is low rank. Specifically, we introduce new lower and upper bounds for the fidelity which can be refined to arbitrary tightness, and we show that these bounds can outperform other known computable state-of-the-art bounds for the fidelity. Second, we introduce a near-term algorithm for computing our bounds.

### ► References

[1] A. Peruzzo, J. McClean, P. Shadbolt, M.-H. Yung, X.-Q. Zhou, P. J. Love, A. Aspuru-Guzik, and J. L. O'Brien. A variational eigenvalue solver on a photonic quantum processor. Nature Communications, 5: 4213, 2014. https:/​/​doi.org/​10.1038/​ncomms5213.
https:/​/​doi.org/​https:/​/​doi.org/​10.1038/​ncomms5213

[2] Katherine L Brown, William J Munro, and Vivien M Kendon. Using quantum computers for quantum simulation. Entropy, 12 (11): 2268–2307, 2010. https:/​/​doi.org/​10.3390/​e12112268.
https:/​/​doi.org/​https:/​/​doi.org/​10.3390/​e12112268

[3] Aram W Harrow, Avinatan Hassidim, and Seth Lloyd. Quantum algorithm for linear systems of equations. Physical review letters, 103 (15): 150502, 2009. https:/​/​doi.org/​10.1103/​PhysRevLett.103.150502.
https:/​/​doi.org/​https:/​/​doi.org/​10.1103/​PhysRevLett.103.150502

[4] Armin Uhlmann. The "transition probability" in the state space of a$\star$-algebra. Reports on Mathematical Physics, 9 (2): 273–279, 1976. https:/​/​doi.org/​10.1016/​0034-4877(76)90060-4.
https:/​/​doi.org/​https:/​/​doi.org/​10.1016/​0034-4877(76)90060-4

[5] Richard Jozsa. Fidelity for mixed quantum states. Journal of modern optics, 41 (12): 2315–2323, 1994. https:/​/​doi.org/​10.1080/​09500349414552171.
https:/​/​doi.org/​https:/​/​doi.org/​10.1080/​09500349414552171

[6] M. A. Nielsen and I. L. Chuang. Quantum Computation and Quantum Information. December 2010. https:/​/​doi.org/​10.1017/​CBO9780511976667.
https:/​/​doi.org/​https:/​/​doi.org/​10.1017/​CBO9780511976667

[7] M. M. Wilde. Quantum Information Theory. Cambridge University Press, 2 edition, 2017. https:/​/​doi.org/​10.1017/​9781316809976.
https:/​/​doi.org/​https:/​/​doi.org/​10.1017/​9781316809976

[8] Yeong-Cherng Liang, Yu-Hao Yeh, Paulo E M F Mendonça, Run Yan Teh, Margaret D Reid, and Peter D Drummond. Quantum fidelity measures for mixed states. Reports on Progress in Physics, 82 (7): 076001, jun 2019. https:/​/​doi.org/​10.1088/​1361-6633/​ab1ca4.
https:/​/​doi.org/​https:/​/​doi.org/​10.1088/​1361-6633/​ab1ca4

[9] Markus Hauru and Guifre Vidal. Uhlmann fidelities from tensor networks. Physical Review A, 98 (4): 042316, 2018. https:/​/​doi.org/​10.1103/​PhysRevA.98.042316.
https:/​/​doi.org/​https:/​/​doi.org/​10.1103/​PhysRevA.98.042316

[10] John Watrous. Quantum statistical zero-knowledge. arXiv:quant-ph/​0202111, 2002. URL https:/​/​arxiv.org/​abs/​quant-ph/​0202111.
arXiv:quant-ph/0202111

[11] Hui Li and F. D. M. Haldane. Entanglement spectrum as a generalization of entanglement entropy: Identification of topological order in non-abelian fractional quantum hall effect states. Phys. Rev. Lett., 101: 010504, Jul 2008. https:/​/​doi.org/​10.1103/​PhysRevLett.101.010504.
https:/​/​doi.org/​https:/​/​doi.org/​10.1103/​PhysRevLett.101.010504

[12] Christopher M Bishop. Pattern recognition and machine learning. Springer, 2006. URL https:/​/​www.springer.com/​gp/​book/​9780387310732.
https:/​/​www.springer.com/​gp/​book/​9780387310732

[13] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate optimization algorithm. arXiv:1411.4028, 2014. URL https:/​/​arxiv.org/​abs/​1411.4028.
arXiv:1411.4028

[14] J. R. McClean, J. Romero, R. Babbush, and A. Aspuru-Guzik. The theory of variational hybrid quantum-classical algorithms. New Journal of Physics, 18 (2): 023023, 2016. https:/​/​doi.org/​10.1088/​1367-2630/​18/​2/​023023.
https:/​/​doi.org/​https:/​/​doi.org/​10.1088/​1367-2630/​18/​2/​023023

[15] J. Romero, J. P. Olson, and A. Aspuru-Guzik. Quantum autoencoders for efficient compression of quantum data. Quantum Science and Technology, 2: 045001, December 2017. https:/​/​doi.org/​10.1088/​2058-9565/​aa8072.
https:/​/​doi.org/​https:/​/​doi.org/​10.1088/​2058-9565/​aa8072

[16] Ying Li and Simon C Benjamin. Efficient variational quantum simulator incorporating active error minimization. Physical Review X, 7 (2): 021050, 2017. https:/​/​doi.org/​10.1103/​PhysRevX.7.021050.
https:/​/​doi.org/​https:/​/​doi.org/​10.1103/​PhysRevX.7.021050

[17] S. Khatri, R. LaRose, A. Poremba, L. Cincio, A. T. Sornborger, and P. J. Coles. Quantum-assisted quantum compiling. Quantum, 3: 140, May 2019. ISSN 2521-327X. https:/​/​doi.org/​10.22331/​q-2019-05-13-140.
https:/​/​doi.org/​https:/​/​doi.org/​10.22331/​q-2019-05-13-140

[18] Ryan LaRose, Arkin Tikku, Étude O'Neel-Judy, Lukasz Cincio, and Patrick J Coles. Variational quantum state diagonalization. npj Quantum Information, 5 (1): 8, 2019. https:/​/​doi.org/​10.1038/​s41534-019-0167-6.
https:/​/​doi.org/​https:/​/​doi.org/​10.1038/​s41534-019-0167-6

[19] A. Arrasmith, L. Cincio, A. T. Sornborger, W. H. Zurek, and P. J. Coles. Variational consistent histories as a hybrid algorithm for quantum foundations. Nature communications, 10 (1): 3438, 2019. https:/​/​doi.org/​10.1038/​s41467-019-11417-0.
https:/​/​doi.org/​https:/​/​doi.org/​10.1038/​s41467-019-11417-0

[20] Kunal Sharma, Sumeet Khatri, M Cerezo, and Patrick J Coles. Noise resilience of variational quantum compiling. New Journal of Physics, 2020. https:/​/​doi.org/​10.1088/​1367-2630/​ab784c.
https:/​/​doi.org/​https:/​/​doi.org/​10.1088/​1367-2630/​ab784c

[21] Cristina Cirstoiu, Zoe Holmes, Joseph Iosue, Lukasz Cincio, Patrick J Coles, and Andrew Sornborger. Variational fast forwarding for quantum simulation beyond the coherence time. arXiv:1910.04292, 2019. URL https:/​/​arxiv.org/​abs/​1910.04292.
arXiv:1910.04292

[22] Jaroslaw Adam Miszczak, Zbigniew Puchala, Pawel Horodecki, Armin Uhlmann, and Karol Zyczkowski. Sub- and super-fidelity as bounds for quantum fidelity. Quantum Information & Computation, 9 (1): 103–130, 2009. https:/​/​doi.org/​10.26421/​QIC9.1-2.
https:/​/​doi.org/​https:/​/​doi.org/​10.26421/​QIC9.1-2

[23] Jing-Ling Chen, Libin Fu, Abraham A Ungar, and Xian-Geng Zhao. Alternative fidelity measure between two states of an n-state quantum system. Physical Review A, 65 (5): 054304, 2002. https:/​/​doi.org/​10.1103/​PhysRevA.65.054304.
https:/​/​doi.org/​https:/​/​doi.org/​10.1103/​PhysRevA.65.054304

[24] Paulo EMF Mendonça, Reginaldo d J Napolitano, Marcelo A Marchiolli, Christopher J Foster, and Yeong-Cherng Liang. Alternative fidelity measure between quantum states. Physical Review A, 78 (5): 052330, 2008. https:/​/​doi.org/​10.1103/​PhysRevA.78.052330.
https:/​/​doi.org/​https:/​/​doi.org/​10.1103/​PhysRevA.78.052330

[25] Zbigniew Puchała and Jarosław Adam Miszczak. Bound on trace distance based on superfidelity. Phys. Rev. A, 79: 024302, Feb 2009. https:/​/​doi.org/​10.1103/​PhysRevA.79.024302.
https:/​/​doi.org/​https:/​/​doi.org/​10.1103/​PhysRevA.79.024302

[26] Todd A Brun. Measuring polynomial functions of states. Quantum Information & Computation, 4 (5): 401–408, 2004. URL https:/​/​arxiv.org/​abs/​quant-ph/​0401067.
arXiv:quant-ph/0401067

[27] Karol Bartkiewicz, Karel Lemr, and Adam Miranowicz. Direct method for measuring of purity, superfidelity, and subfidelity of photonic two-qubit mixed states. Phys. Rev. A, 88: 052104, Nov 2013. https:/​/​doi.org/​10.1103/​PhysRevA.88.052104.
https:/​/​doi.org/​https:/​/​doi.org/​10.1103/​PhysRevA.88.052104

[28] L. Cincio, Y. Subaşi, A. T. Sornborger, and P. J. Coles. Learning the quantum algorithm for state overlap. New J. Phys., 20: 113022, Nov 2018. https:/​/​doi.org/​10.1088/​1367-2630/​aae94a.
https:/​/​doi.org/​https:/​/​doi.org/​10.1088/​1367-2630/​aae94a

[29] J. C. Garcia-Escartin and P. Chamorro-Posada. Swap test and Hong-Ou-Mandel effect are equivalent. Phys. Rev. A, 87: 052330, May 2013. https:/​/​doi.org/​10.1103/​PhysRevA.87.052330.
https:/​/​doi.org/​https:/​/​doi.org/​10.1103/​PhysRevA.87.052330

[30] Marco Tomamichel, Roger Colbeck, and Renato Renner. Duality between smooth min-and max-entropies. IEEE Transactions on Information Theory, 56 (9): 4674–4681, 2010. https:/​/​doi.org/​10.1109/​TIT.2010.2054130.
https:/​/​doi.org/​https:/​/​doi.org/​10.1109/​TIT.2010.2054130

[31] Marco Tomamichel. Quantum Information Processing with Finite Resources: Mathematical Foundations, volume 5. Springer, 2015. https:/​/​doi.org/​10.1007/​978-3-319-21891-5.
https:/​/​doi.org/​https:/​/​doi.org/​10.1007/​978-3-319-21891-5

[32] John A. Smolin, Jay M. Gambetta, and Graeme Smith. Efficient method for computing the maximum-likelihood quantum state from measurements with additive gaussian noise. Phys. Rev. Lett., 108: 070502, Feb 2012. https:/​/​doi.org/​10.1103/​PhysRevLett.108.070502.
https:/​/​doi.org/​https:/​/​doi.org/​10.1103/​PhysRevLett.108.070502

[33] Alexei Gilchrist, Nathan K. Langford, and Michael A. Nielsen. Distance measures to compare real and ideal quantum processes. Phys. Rev. A, 71: 062310, Jun 2005. https:/​/​doi.org/​10.1103/​PhysRevA.71.062310.
https:/​/​doi.org/​https:/​/​doi.org/​10.1103/​PhysRevA.71.062310

[34] Alexey E Rastegin. Sine distance for quantum states. quant-ph/​0602112, 2006. URL https:/​/​arxiv.org/​abs/​quant-ph/​0602112.
arXiv:quant-ph/0602112

[35] M J. D. Powell. The bobyqa algorithm for bound constrained optimization without derivatives. Technical Report, Department of Applied Mathematics and Theoretical Physics, 01 2009. URL http:/​/​www.damtp.cam.ac.uk/​user/​na/​NA_papers/​NA2009_06.pdf.
http:/​/​www.damtp.cam.ac.uk/​user/​na/​NA_papers/​NA2009_06.pdf

[36] Jonas M Kübler, Andrew Arrasmith, Lukasz Cincio, and Patrick J Coles. An adaptive optimizer for measurement-frugal variational algorithms. arXiv preprint arXiv:1909.09083, 2019. URL https:/​/​arxiv.org/​abs/​1909.09083.
arXiv:1909.09083

[37] Paolo Zanardi, H. T. Quan, Xiaoguang Wang, and C. P. Sun. Mixed-state fidelity and quantum criticality at finite temperature. Phys. Rev. A, 75: 032109, Mar 2007a. https:/​/​doi.org/​10.1103/​PhysRevA.75.032109.
https:/​/​doi.org/​https:/​/​doi.org/​10.1103/​PhysRevA.75.032109

[38] Paolo Zanardi, Paolo Giorda, and Marco Cozzini. Information-theoretic differential geometry of quantum phase transitions. Phys. Rev. Lett., 99: 100603, Sep 2007b. https:/​/​doi.org/​10.1103/​PhysRevLett.99.100603.
https:/​/​doi.org/​https:/​/​doi.org/​10.1103/​PhysRevLett.99.100603

[39] H. T. Quan and F. M. Cucchietti. Quantum fidelity and thermal phase transitions. Phys. Rev. E, 79: 031101, Mar 2009. https:/​/​doi.org/​10.1103/​PhysRevE.79.031101.
https:/​/​doi.org/​https:/​/​doi.org/​10.1103/​PhysRevE.79.031101

[40] Frank Verstraete, J Ignacio Cirac, and José I Latorre. Quantum circuits for strongly correlated quantum systems. Physical Review A, 79 (3): 032316, 2009. https:/​/​doi.org/​10.1103/​PhysRevA.79.032316.
https:/​/​doi.org/​https:/​/​doi.org/​10.1103/​PhysRevA.79.032316

[41] Alba Cervera-Lierta. Exact Ising model simulation on a quantum computer. Quantum, 2: 114, December 2018. ISSN 2521-327X. https:/​/​doi.org/​10.22331/​q-2018-12-21-114.
https:/​/​doi.org/​https:/​/​doi.org/​10.22331/​q-2018-12-21-114

[42] Ewin Tang. A quantum-inspired classical algorithm for recommendation systems. pages 217–228, 2019. https:/​/​doi.org/​10.1145/​3313276.3316310.
https:/​/​doi.org/​https:/​/​doi.org/​10.1145/​3313276.3316310

[43] András Gilyén, Seth Lloyd, and Ewin Tang. Quantum-inspired low-rank stochastic regression with logarithmic dependence on the dimension. arXiv preprint arXiv:1811.04909, 2018. URL https:/​/​arxiv.org/​abs/​1811.04909.
arXiv:1811.04909

[44] E. Knill and R. Laflamme. Power of one bit of quantum information. Physical Review Letters, 81: 5672–5675, 1998. https:/​/​doi.org/​10.1103/​PhysRevLett.81.5672.
https:/​/​doi.org/​https:/​/​doi.org/​10.1103/​PhysRevLett.81.5672

[45] K. Fujii, H. Kobayashi, T. Morimae, H. Nishimura, S. Tamate, and S. Tani. Impossibility of Classically Simulating One-Clean-Qubit Model with Multiplicative Error. Physical Review Letters, 120: 200502, May 2018. https:/​/​doi.org/​10.1103/​PhysRevLett.120.200502.
https:/​/​doi.org/​https:/​/​doi.org/​10.1103/​PhysRevLett.120.200502

[46] Tomoyuki Morimae. Hardness of classically sampling one clean qubit model with constant total variation distance error. 2017. https:/​/​doi.org/​10.1103/​PhysRevA.96.040302.
https:/​/​doi.org/​https:/​/​doi.org/​10.1103/​PhysRevA.96.040302

[47] Christian Schwemmer, Lukas Knips, Daniel Richart, Harald Weinfurter, Tobias Moroder, Matthias Kleinmann, and Otfried Gühne. Systematic errors in current quantum state tomography tools. Physical review letters, 114 (8): 080403, 2015. https:/​/​doi.org/​10.1103/​PhysRevLett.114.080403.
https:/​/​doi.org/​https:/​/​doi.org/​10.1103/​PhysRevLett.114.080403

[48] Gael Sentís, Johannes N Greiner, Jiangwei Shang, Jens Siewert, and Matthias Kleinmann. Bound entangled states fit for robust experimental verification. Quantum, 2: 113, 2018. https:/​/​doi.org/​10.22331/​q-2018-12-18-113.
https:/​/​doi.org/​https:/​/​doi.org/​10.22331/​q-2018-12-18-113

[49] Zbigniew Puchała, Jarosław Adam Miszczak, Piotr Gawron, and Bartłomiej Gardas. Experimentally feasible measures of distance between quantum operations. Quantum Information Processing, 10 (1): 1–12, 2011. https:/​/​doi.org/​10.1007/​s11128-010-0166-1.
https:/​/​doi.org/​https:/​/​doi.org/​10.1007/​s11128-010-0166-1

[50] Martin Müller-Lennert, Frédéric Dupuis, Oleg Szehr, Serge Fehr, and Marco Tomamichel. On quantum rényi entropies: A new generalization and some properties. Journal of Mathematical Physics, 54 (12): 122203, 2013. https:/​/​doi.org/​10.1063/​1.4838856.
https:/​/​doi.org/​https:/​/​doi.org/​10.1063/​1.4838856

[51] Mark M Wilde, Andreas Winter, and Dong Yang. Strong converse for the classical capacity of entanglement-breaking and hadamard channels via a sandwiched rényi relative entropy. Communications in Mathematical Physics, 331 (2): 593–622, 2014. https:/​/​doi.org/​10.1007/​s00220-014-2122-x.
https:/​/​doi.org/​https:/​/​doi.org/​10.1007/​s00220-014-2122-x

[52] Patrick J. Coles, M. Cerezo, and Lukasz Cincio. Strong bound between trace distance and hilbert-schmidt distance for low-rank states. Phys. Rev. A, 100: 022103, Aug 2019. https:/​/​doi.org/​10.1103/​PhysRevA.100.022103.
https:/​/​doi.org/​https:/​/​doi.org/​10.1103/​PhysRevA.100.022103

[53] Bernhard Baumgartner. An inequality for the trace of matrix products, using absolute values. arXiv:1106.6189, 2011. URL https:/​/​arxiv.org/​abs/​1106.6189.
arXiv:1106.6189

[54] R. A. Horn and C. R. Johnson. Matrix Analysis. Cambridge University Press, 1990. https:/​/​doi.org/​10.1017/​CBO9780511810817.
https:/​/​doi.org/​https:/​/​doi.org/​10.1017/​CBO9780511810817

[55] H. Weyl. Das asymptotische verteilungsgesetz der eigenwerte linearer partieller differentialgleichungen (mit einer anwendung auf die theorie der hohlraumstrahlung). Mathematische Annalen, 71 (4): 441–479, 1912. https:/​/​doi.org/​10.1007/​BF01456804.
https:/​/​doi.org/​https:/​/​doi.org/​10.1007/​BF01456804

[56] A. S. Kholevo. On quasiequivalence of locally normal states. Theoretical and Mathematical Physics, 13 (2): 1071–1082, Nov 1972. ISSN 1573-9333. https:/​/​doi.org/​10.1007/​BF01035528.
https:/​/​doi.org/​https:/​/​doi.org/​10.1007/​BF01035528

[57] Koenraad M. R. Audenaert. Comparisons between quantum state distinguishability measures. Quantum Info. Comput., 14 (1–2): 31–38, January 2014. ISSN 1533-7146. https:/​/​doi.org/​10.26421/​QIC14.1-2.
https:/​/​doi.org/​https:/​/​doi.org/​10.26421/​QIC14.1-2

### Cited by

[1] Santosh Kumar, "Wishart and random density matrices: Analytical results for the mean-square Hilbert-Schmidt distance", Physical Review A 102 1, 012405 (2020).

[2] Jonas M. Kübler, Andrew Arrasmith, Lukasz Cincio, and Patrick J. Coles, "An Adaptive Optimizer for Measurement-Frugal Variational Algorithms", Quantum 4, 263 (2020).

[3] Patrick J. Coles, M. Cerezo, and Lukasz Cincio, "Strong bound between trace distance and Hilbert-Schmidt distance for low-rank states", Physical Review A 100 2, 022103 (2019).

[4] M. Cerezo, Akira Sone, Tyler Volkoff, Lukasz Cincio, and Patrick J. Coles, "Cost-Function-Dependent Barren Plateaus in Shallow Quantum Neural Networks", arXiv:2001.00550.

[5] Andrew Arrasmith, Lukasz Cincio, Rolando D. Somma, and Patrick J. Coles, "Operator Sampling for Shot-frugal Optimization in Variational Algorithms", arXiv:2004.06252.

[6] Kunal Sharma, Sumeet Khatri, M. Cerezo, and Patrick J. Coles, "Noise resilience of variational quantum compiling", New Journal of Physics 22 4, 043006 (2020).

[7] Xin Wang, Zhixin Song, and Youle Wang, "Variational Quantum Singular Value Decomposition", arXiv:2006.02336.

The above citations are from Crossref's cited-by service (last updated successfully 2020-09-22 20:43:54) and SAO/NASA ADS (last updated successfully 2020-09-22 20:43:54). The list may be incomplete as not all publishers provide suitable and complete citation data.