A Caltech Library Service

Quantum Algorithm for Petz Recovery Channels and Pretty Good Measurements

Gilyén, András and Lloyd, Seth and Marvian, Iman and Quek, Yihui and Wilde, Mark M. (2022) Quantum Algorithm for Petz Recovery Channels and Pretty Good Measurements. Physical Review Letters, 128 (22). Art. No. 220502. ISSN 0031-9007. doi:10.1103/physrevlett.128.220502.

[img] PDF - Published Version
See Usage Policy.

[img] PDF - Accepted Version
See Usage Policy.

[img] PDF (details of a modification of the algorithm presented in the main text. The main concept behind the algorithm is already presented in the main text, and the modified version is not necessary in order to understand what is presented in the main text) - Supplemental Material
See Usage Policy.


Use this Persistent URL to link to this item:


The Petz recovery channel plays an important role in quantum information science as an operation that approximately reverses the effect of a quantum channel. The pretty good measurement is a special case of the Petz recovery channel, and it allows for near-optimal state discrimination. A hurdle to the experimental realization of these vaunted theoretical tools is the lack of a systematic and efficient method to implement them. This Letter sets out to rectify this lack: Using the recently developed tools of quantum singular value transformation and oblivious amplitude amplification, we provide a quantum algorithm to implement the Petz recovery channel when given the ability to perform the channel that one wishes to reverse. Moreover, we prove that, in some sense, our quantum algorithm’s usage of the channel implementation cannot be improved by more than a quadratic factor. Our quantum algorithm also provides a procedure to perform pretty good measurements when given multiple copies of the states that one is trying to distinguish.

Item Type:Article
Related URLs:
URLURL TypeDescription Paper Information
Gilyén, András0000-0001-5992-5743
Lloyd, Seth0000-0003-0353-4529
Marvian, Iman0000-0001-6719-061X
Quek, Yihui0000-0002-1227-0804
Wilde, Mark M.0000-0002-3916-4462
Additional Information:© 2022 American Physical Society. (Received 21 July 2020; revised 14 March 2022; accepted 7 April 2022; published 1 June 2022) We gratefully acknowledge the Simons Institute for the Theory of Computing, where part of this work was conducted. A. G. acknowledges funding provided by Samsung Electronics Co., Ltd., for the project “The Computational Power of Sampling on Quantum Computers.” Additional support was provided by the Institute for Quantum Information and Matter, an NSF Physics Frontiers Center (National Science Foundation Grant No. PHY-1733907). S. L. was funded by ARO, AFOSR, and IARPA. I. M. acknowledges support from the U.S. National Science Foundation under Grant No. 1910571. Y. Q. acknowledges support from a Stanford QFARM fellowship and from an NUS Overseas Graduate Scholarship. M. M. W. acknowledges support from the U.S. National Science Foundation under Grant No. 1714215, from Stanford QFARM, and from AFOSR under Grant No. FA9550-19-1-0369.
Group:Institute for Quantum Information and Matter
Funding AgencyGrant Number
Army Research Office (ARO)UNSPECIFIED
Air Force Office of Scientific Research (AFOSR)FA9550-19-1-0369
Intelligence Advanced Research Projects Activity (IARPA)UNSPECIFIED
Stanford UniversityUNSPECIFIED
National University of SingaporeUNSPECIFIED
Issue or Number:22
Record Number:CaltechAUTHORS:20220608-849402000
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:115082
Deposited By: George Porter
Deposited On:14 Jun 2022 16:09
Last Modified:25 Jul 2022 23:14

Repository Staff Only: item control page