Streaming quantum state purification

Andrew M. Childs; Honghao Fu; Debbie Leung; Zhi Li; Maris Ozols; Vedang Vyas

doi:10.22331/q-2025-01-21-1603

Streaming quantum state purification

Andrew M. Childs^1,2, Honghao Fu^1,2,3,6, Debbie Leung^1,4, Zhi Li⁴, Maris Ozols⁵, and Vedang Vyas¹

¹Institute for Quantum Computing, University of Waterloo, Waterloo, ON, N2L 3G1, Canada
²Department of Computer Science, Institute for Advanced Computer Studies, and Joint Center for Quantum Information and Computer Science, University of Maryland, College Park, MD 20742, USA
³Massachusetts Institute of Technology, 77 Massachusetts Ave., Cambridge, MA 02139, USA
⁴Perimeter Institute for Theoretical Physics, 31 Caroline St. N., Waterloo, ON N2L 2Y5, Canada
⁵QuSoft and University of Amsterdam, Science Park 123, 1098 XG, Amsterdam, the Netherlands
⁶Concordia Institute of Information Systems Engineering, Concordia University, 1455 Blvd. De Maisonneuve Ouest, Montreal, QC H3G 1M8, Canada

Published:	2025-01-21, volume 9, page 1603
Editor:	Pei Zeng
Eprint:	arXiv:2309.16387v4
Doi:	https://doi.org/10.22331/q-2025-01-21-1603
Citation:	Quantum 9, 1603 (2025).

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

Quantum state purification is the task of recovering a nearly pure copy of an unknown pure quantum state using multiple noisy copies of the state. This basic task has applications to quantum communication over noisy channels and quantum computation with imperfect devices, but has only been studied previously for the case of qubits. We derive an efficient purification procedure based on the swap test for qudits of any dimension, starting with any initial error parameter. Treating the initial error parameter and the dimension as constants, we show that our procedure has sample complexity asymptotically optimal in the final error parameter. Our protocol has a simple recursive structure that can be applied when the states are provided one at a time in a streaming fashion, requiring only a small quantum memory to implement.

► BibTeX data

@article{Childs2025streamingquantum,
  doi = {10.22331/q-2025-01-21-1603},
  url = {https://doi.org/10.22331/q-2025-01-21-1603},
  title = {Streaming quantum state purification},
  author = {Childs, Andrew M. and Fu, Honghao and Leung, Debbie and Li, Zhi and Ozols, Maris and Vyas, Vedang},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {9},
  pages = {1603},
  month = jan,
  year = {2025}
}

► References

[1] Charles H. Bennett, Gilles Brassard, Sandu Popescu, Benjamin Schumacher, John A. Smolin, and William K. Wootters. Purification of noisy entanglement and faithful teleportation via noisy channels. Physical Review Letters, 76(5):722, 1996. arXiv:quant-ph/9511027. doi:10.1103/PhysRevLett.76.722.
https://doi.org/10.1103/PhysRevLett.76.722
arXiv:quant-ph/9511027

[2] Dave Bacon, Isaac L. Chuang, and Aram W. Harrow. Efficient quantum circuits for Schur and Clebsch-Gordan transforms. Phys. Rev. Lett., 97(17):170502, Oct 2006. arXiv:quant-ph/0407082. doi:10.1103/PhysRevLett.97.170502.
https://doi.org/10.1103/PhysRevLett.97.170502
arXiv:quant-ph/0407082

[3] Harry Buhrman, Richard Cleve, John Watrous, and Ronald De Wolf. Quantum fingerprinting. Physical Review Letters, 87(16):167902, 2001. arXiv:quant-ph/0102001. doi:10.1103/PhysRevLett.87.167902.
https://doi.org/10.1103/PhysRevLett.87.167902
arXiv:quant-ph/0102001

[4] Harry Buhrman, Noah Linden, Laura Mančinska, Ashley Montanaro, and Maris Ozols. Quantum majority vote, 2022. arXiv:2211.11729. doi:10.48550/arXiv.2211.11729.
https://doi.org/10.48550/arXiv.2211.11729
arXiv:2211.11729

[5] J.I. Cirac, A.K. Ekert, and C. Macchiavello. Optimal purification of single qubits. Physical Review Letters, 82(21):4344, 1999. arXiv:quant-ph/9812075. doi:10.1103/PhysRevLett.82.4344.
https://doi.org/10.1103/PhysRevLett.82.4344
arXiv:quant-ph/9812075

[6] Jaromír Fiurášek. Optimal probabilistic cloning and purification of quantum states. Phys. Rev. A, 70:032308, Sep 2004. arXiv:quant-ph/0403165. doi:10.1103/PhysRevA.70.032308.
https://doi.org/10.1103/PhysRevA.70.032308
arXiv:quant-ph/0403165

[7] Honghao Fu. Quantum state purification. Master's thesis, University of Waterloo, 2016. URL: http://hdl.handle.net/10012/10706.
http://hdl.handle.net/10012/10706

[8] Dmitry Grinko and Maris Ozols. Linear programming with unitary-equivariant constraints, 2022. arXiv:2207.05713. doi:10.48550/arXiv.2207.05713.
https://doi.org/10.48550/arXiv.2207.05713
arXiv:2207.05713

[9] Daniel Grier, Hakop Pashayan, and Luke Schaeffer. Principal eigenstate classical shadows, 2024. arXiv:2405.13939. doi:10.48550/arXiv.2405.13939.
https://doi.org/10.48550/arXiv.2405.13939
arXiv:2405.13939

[10] Lov K. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the 28th Annual ACM Symposium on Theory of Computing, pages 212–219. ACM, 1996. arXiv:quant-ph/9605043. doi/10.1145/237814.237866.
https://doi.org/10.1145/237814.237866
arXiv:quant-ph/9605043

[11] Aram W. Harrow. Applications of coherent classical communication and the Schur transform to quantum information theory. PhD thesis, MIT, 2005. arXiv:quant-ph/0512255. doi/10.48550/arXiv.quant-ph/0512255.
https://doi.org/10.48550/arXiv.quant-ph/0512255
arXiv:quant-ph/0512255

[12] Jeongwan Haah, Aram W. Harrow, Zhengfeng Ji, Xiaodi Wu, and Nengkun Yu. Sample-optimal tomography of quantum states. IEEE Transactions on Information Theory, 63(9):5628–5641, 2017. arXiv:1508.01797. doi:10.1109/TIT.2017.2719044.
https://doi.org/10.1109/TIT.2017.2719044
arXiv:1508.01797

[13] M. Keyl and R.F. Werner. The rate of optimal purification procedures. Annales Henri Poincare, 2(1):1–26, 2001. arXiv:quant-ph/9910124. doi/10.1007/PL00001027.
https://doi.org/10.1007/PL00001027
arXiv:quant-ph/9910124

[14] Zhaoyi Li, Honghao Fu, Takuya Isogawa, and Isaac Chuang. Optimal quantum purity amplification. arXiv:2409.18167. doi/10.48550/arXiv.2409.18167.
https://doi.org/10.48550/arXiv.2409.18167
arXiv:2409.18167

[15] Qing Liu, Zihao Li, Xiao Yuan, Huangjun Zhu, and You Zhou. Auxiliary-free replica shadow estimation. arXiv:2407.20865. doi/10.48550/arXiv.2407.20865.
https://doi.org/10.48550/arXiv.2407.20865
arXiv:2407.20865

[16] Ashley Montanaro and Ronald de Wolf. A Survey of Quantum Property Testing. Number 7 in Graduate Surveys. Theory of Computing Library, 2016. arXiv:1310.2035, doi:10.4086/toc.gs.2016.007.
https://doi.org/10.4086/toc.gs.2016.007
arXiv:1310.2035

[17] Ryan O'Donnell and John Wright. Efficient quantum tomography, In Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, STOC '16, page 899-912, New York, NY, USA, 2016. Association for Computing Machinery. arXiv:1508.01907. doi:10.1145/2897518.2897544.
https://doi.org/10.1145/2897518.2897544
arXiv:1508.01907

[18] Ryan O'Donnell and John Wright. Quantum spectrum testing. In Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing, STOC '15, page 529–538, New York, NY, USA, 2015. Association for Computing Machinery. arXiv:1501.05028, doi:10.1145/2746539.2746582.
https://doi.org/10.1145/2746539.2746582
arXiv:1501.05028

[19] Oded Regev. The learning with errors problem (Invited Survey). 2010 IEEE 25th Annual Conference on Computational Complexity, Cambridge, MA, USA, 2010, pp. 191-204. doi:10.1109/CCC.2010.26.
https://doi.org/10.1109/CCC.2010.26

[20] Oded Regev and Liron Schiff. Impossibility of a quantum speed-up with a faulty oracle. In Automata, Languages and Programming, ICALP 2008, LNCS, 5125, Springer, Berlin, Heidelberg., arXiv:1202.1027. doi:10.1007/978-3-540-70575-8_63.
https://doi.org/10.1007/978-3-540-70575-8_63
arXiv:1202.1027

[21] Daniel R. Simon. On the power of quantum computation. SIAM Journal on Computing, 26(5):1474–1483, 1997. doi:10.1137/S0097539796298637.
https://doi.org/10.1137/S0097539796298637

[22] Stevo Stević. Asymptotic behaviour of a sequence defined by iteration. Matematički Vesnik, 48(3-4):99–105, 1996. Asymptotic behavior of a sequence defined by iteration with applications. Colloquium Mathematicum 93 (2002), 267-276. doi:10.4064/cm93-2-6.
https://doi.org/10.4064/cm93-2-6
https://www.impan.pl/pl/wydawnictwa/czasopisma-i-serie-wydawnicze/colloquium-mathematicum/all/93/2/86975/asymptotic-behavior-of-a-sequence-defined-by-iteration-with-applications

[23] John Wright. How to learn a quantum state. PhD thesis, Carnegie Mellon University, 2016. URL: https://csd.cmu.edu/academics/doctoral/degrees-conferred/john-wright.
https://csd.cmu.edu/academics/doctoral/degrees-conferred/john-wright

[24] Hongshun Yao, Yu-Ao Chen, Erdong Huang, Kaichu Chen, Honghao Fu, and Xin Wang. Protocols and trade-offs of quantum state purification, 2024. arXiv:2404.01138. doi/10.48550/arXiv.2404.01138.
https://doi.org/10.48550/arXiv.2404.01138
arXiv:2404.01138

[25] Bo Yang, Elham Kashefi, Dominik Leichtle, and Harold Ollivier. Quantum error suppression with subgroup stabilisation projectors. arXiv:2404.09973. doi/10.48550/arXiv.2404.09973.
https://doi.org/10.48550/arXiv.2404.09973
arXiv:2404.09973

[26] Christof Zalka. Grover's quantum searching algorithm is optimal. Physical Review A, 60:2746–2751, 1999. arXiv:quant-ph/9711070. doi/10.1103/PhysRevA.60.2746.
https://doi.org/10.1103/PhysRevA.60.2746
arXiv:quant-ph/9711070

[27] You Zhou and Zhenhuan Liu. A hybrid framework for estimating nonlinear functions of quantum states, 2022. arXiv:2208.08416. doi/10.48550/arXiv.2208.08416.
https://doi.org/10.48550/arXiv.2208.08416
arXiv:2208.08416

Cited by

[1] Sitan Chen and Weiyuan Gong, "Efficient Pauli Channel Estimation with Logarithmic Quantum Memory", PRX Quantum 6 2, 020323 (2025).

[2] Keming He, Chengkai Zhu, Hongshun Yao, Jinguo Liu, Yinan Li, and Xin Wang, "No-Go Theorems for Universal Quantum State Purification via Classically Simulable Operations", Physical Review Letters 136 9, 090204 (2026).

[3] Hongshun Yao, Yu-Ao Chen, Erdong Huang, Kaichu Chen, Honghao Fu, and Xin Wang, "Protocols and trade-offs of quantum state purification", Quantum Science and Technology 10 3, 035020 (2025).

[4] Zhenhuan Liu, Xingjian Zhang, Yue-Yang Fei, and Zhenyu Cai, "Virtual Channel Purification", PRX Quantum 6 2, 020325 (2025).

[5] Vikram Singh Thakur, Rai Shrijal Anjanir, Mayank Yadav, Atul Kumar, Maurizio Magarini, and Kapal Dev, 2025 IEEE Globecom Workshops (GC Wkshps) 2258 (2025) ISBN:979-8-3315-6741-5.

[6] J Knörzer, X Liu, B F Schiffer, and J Tura, "Distributed quantum information processing: a review of recent progress", Reports on Progress in Physics 89 7, 074401 (2026).

[7] Jeongrak Son, Marek Gluza, Ryuji Takagi, and Nelly H. Y. Ng, "Quantum Dynamic Programming", Physical Review Letters 134 18, 180602 (2025).

[8] Benchi Zhao, Yu-Ao Chen, Xuanqiang Zhao, Chengkai Zhu, Giulio Chiribella, and Xin Wang, "Power and Limitations of Distributed Quantum State Purification", Physical Review Letters 136 9, 090203 (2026).

[9] Hongfeng Liu, Zizhao Han, Xinfang Nie, Zhenhuan Liu, and Dawei Lu, "Experimental Demonstration of Calibration-Free Non-Markovian Noise Suppression", Physical Review Letters 137 3, 030601 (2026).

[10] Zhiping Liu, Kun Wang, and Xin Wang, "Quantum fidelity estimation in the resource theory of nonstabilizerness", Physical Review A 112 5, 052444 (2025).

[11] Jiaqi Tang and Mu-Jiang-Shan Wang, "Information-Theoretic Framework for Quantum State Purification and Error Correction via Symmetric Subspace Projection", Entropy 28 7, 726 (2026).

[12] Ye-Chao Liu and Jiangwei Shang, "Beating the optimal verification of entangled states via collective strategies", Physical Review A 112 6, L060401 (2025).

[13] Sitan Chen and Weiyuan Gong, "Efficient Pauli channel estimation with logarithmic quantum memory", arXiv:2309.14326, (2023).

[14] Zhaoyi Li, Honghao Fu, Takuya Isogawa, Caio Silva, and Isaac Chuang, "Optimal Quantum Purity Amplification", arXiv:2409.18167, (2024).

[15] Daniel Grier, Hakop Pashayan, and Luke Schaeffer, "Principal eigenstate classical shadows", arXiv:2405.13939, (2024).

[16] Alexander M. Dalzell, András Gilyén, Connor T. Hann, Sam McArdle, Grant Salton, Quynh T. Nguyen, Aleksander Kubica, and Fernando G. S. L. Brandão, "A distillation-teleportation protocol for fault-tolerant QRAM", arXiv:2505.20265, (2025).

[17] Daniel Grier, Debbie Leung, Zhi Li, Hakop Pashayan, and Luke Schaeffer, "Streaming quantum state purification for general mixed states", arXiv:2503.22644, (2025).

[18] Dmitry Grinko and Satoshi Yoshida, "Quantum Simulation of Random Unitaries from Clebsch-Gordan Transforms", arXiv:2509.26623, (2025).

[19] David Rasmussen Lolck, Laura Mančinska, and Manaswi Paraashar, "Quantum Advantage with Faulty Oracle", arXiv:2411.04931, (2024).

[20] Connor Casey, Albert Williams, Catherine McCaffrey, Eugene Rotherham, and Nathan Darby, "Multi-Mode Quantum Memories for High-Throughput Satellite Entanglement Distribution", arXiv:2512.00282, (2025).

The above citations are from Crossref's cited-by service (last updated successfully 2026-08-09 06:48:26) and SAO/NASA ADS (last updated successfully 2026-08-08 17:24:01). The list may be incomplete as not all publishers provide suitable and complete citation data.

Could not fetch ADS cited-by data during last attempt 2026-08-09 06:48:26: Cannot retrieve data from ADS due to rate limitations.

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.