{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,17]],"date-time":"2026-07-17T00:38:16Z","timestamp":1784248696502,"version":"3.55.0"},"reference-count":27,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2025,1,21]],"date-time":"2025-01-21T00:00:00Z","timestamp":1737417600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.22331\/q-2025-01-21-1603","type":"journal-article","created":{"date-parts":[[2025,1,21]],"date-time":"2025-01-21T17:01:11Z","timestamp":1737478871000},"page":"1603","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":12,"title":["Streaming quantum state purification"],"prefix":"10.22331","volume":"9","author":[{"given":"Andrew M.","family":"Childs","sequence":"first","affiliation":[{"name":"Institute for Quantum Computing, University of Waterloo, Waterloo, ON, N2L 3G1, Canada"},{"name":"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"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Honghao","family":"Fu","sequence":"additional","affiliation":[{"name":"Institute for Quantum Computing, University of Waterloo, Waterloo, ON, N2L 3G1, Canada"},{"name":"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"},{"name":"Massachusetts Institute of Technology, 77 Massachusetts Ave., Cambridge, MA 02139, USA"},{"name":"Concordia Institute of Information Systems Engineering, Concordia University, 1455 Blvd. De Maisonneuve Ouest, Montreal, QC H3G 1M8, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Debbie","family":"Leung","sequence":"additional","affiliation":[{"name":"Institute for Quantum Computing, University of Waterloo, Waterloo, ON, N2L 3G1, Canada"},{"name":"Perimeter Institute for Theoretical Physics, 31 Caroline St. N., Waterloo, ON N2L 2Y5, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zhi","family":"Li","sequence":"additional","affiliation":[{"name":"Perimeter Institute for Theoretical Physics, 31 Caroline St. N., Waterloo, ON N2L 2Y5, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Maris","family":"Ozols","sequence":"additional","affiliation":[{"name":"QuSoft and University of Amsterdam, Science Park 123, 1098 XG, Amsterdam, the Netherlands"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Vedang","family":"Vyas","sequence":"additional","affiliation":[{"name":"Institute for Quantum Computing, University of Waterloo, Waterloo, ON, N2L 3G1, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"9598","published-online":{"date-parts":[[2025,1,21]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/PhysRevLett.76.722"},{"key":"1","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/PhysRevLett.97.170502"},{"key":"2","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/PhysRevLett.87.167902"},{"key":"3","doi-asserted-by":"publisher","unstructured":"Harry Buhrman, Noah Linden, Laura Man\u010dinska, Ashley Montanaro, and Maris Ozols. Quantum majority vote, 2022. arXiv:2211.11729. doi:10.48550\/arXiv.2211.11729.","DOI":"10.48550\/arXiv.2211.11729"},{"key":"4","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/PhysRevLett.82.4344"},{"key":"5","doi-asserted-by":"publisher","unstructured":"Jarom\u00edr Fiur\u00e1\u0161ek. 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.","DOI":"10.1103\/PhysRevA.70.032308"},{"key":"6","unstructured":"Honghao Fu. Quantum state purification. Master&apos;s thesis, University of Waterloo, 2016. URL: http:\/\/hdl.handle.net\/10012\/10706."},{"key":"7","doi-asserted-by":"publisher","unstructured":"Dmitry Grinko and Maris Ozols. Linear programming with unitary-equivariant constraints, 2022. arXiv:2207.05713. doi:10.48550\/arXiv.2207.05713.","DOI":"10.48550\/arXiv.2207.05713"},{"key":"8","doi-asserted-by":"publisher","unstructured":"Daniel Grier, Hakop Pashayan, and Luke Schaeffer. Principal eigenstate classical shadows, 2024. arXiv:2405.13939. doi:10.48550\/arXiv.2405.13939.","DOI":"10.48550\/arXiv.2405.13939"},{"key":"9","doi-asserted-by":"publisher","unstructured":"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\u2013219. ACM, 1996. arXiv:quant-ph\/9605043. doi\/10.1145\/237814.237866.","DOI":"10.1145\/237814.237866"},{"key":"10","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.48550\/arXiv.quant-ph\/0512255"},{"key":"11","doi-asserted-by":"publisher","unstructured":"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\u20135641, 2017. arXiv:1508.01797. doi:10.1109\/TIT.2017.2719044.","DOI":"10.1109\/TIT.2017.2719044"},{"key":"12","doi-asserted-by":"publisher","unstructured":"M. Keyl and R.F. Werner. The rate of optimal purification procedures. Annales Henri Poincare, 2(1):1\u201326, 2001. arXiv:quant-ph\/9910124. doi\/10.1007\/PL00001027.","DOI":"10.1007\/PL00001027"},{"key":"13","doi-asserted-by":"publisher","unstructured":"Zhaoyi Li, Honghao Fu, Takuya Isogawa, and Isaac Chuang. Optimal quantum purity amplification. arXiv:2409.18167. doi\/10.48550\/arXiv.2409.18167.","DOI":"10.48550\/arXiv.2409.18167"},{"key":"14","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.48550\/arXiv.2407.20865"},{"key":"15","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.4086\/toc.gs.2016.007"},{"key":"16","doi-asserted-by":"publisher","unstructured":"Ryan O&apos;Donnell and John Wright. Efficient quantum tomography, In Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, STOC &apos;16, page 899-912, New York, NY, USA, 2016. Association for Computing Machinery. arXiv:1508.01907. doi:10.1145\/2897518.2897544.","DOI":"10.1145\/2897518.2897544"},{"key":"17","doi-asserted-by":"publisher","unstructured":"Ryan O&apos;Donnell and John Wright. Quantum spectrum testing. In Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing, STOC &apos;15, page 529\u2013538, New York, NY, USA, 2015. Association for Computing Machinery. arXiv:1501.05028, doi:10.1145\/2746539.2746582.","DOI":"10.1145\/2746539.2746582"},{"key":"18","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1109\/CCC.2010.26"},{"key":"19","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1007\/978-3-540-70575-8_63"},{"key":"20","doi-asserted-by":"publisher","unstructured":"Daniel R. Simon. On the power of quantum computation. SIAM Journal on Computing, 26(5):1474\u20131483, 1997. doi:10.1137\/S0097539796298637.","DOI":"10.1137\/S0097539796298637"},{"key":"21","doi-asserted-by":"publisher","unstructured":"Stevo Stevi\u0107. Asymptotic behaviour of a sequence defined by iteration. Matemati\u010dki Vesnik, 48(3-4):99\u2013105, 1996. Asymptotic behavior of a sequence defined by iteration with applications. Colloquium Mathematicum 93 (2002), 267-276. doi:10.4064\/cm93-2-6.","DOI":"10.4064\/cm93-2-6"},{"key":"22","unstructured":"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."},{"key":"23","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.48550\/arXiv.2404.01138"},{"key":"24","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.48550\/arXiv.2404.09973"},{"key":"25","doi-asserted-by":"publisher","unstructured":"Christof Zalka. Grover&apos;s quantum searching algorithm is optimal. Physical Review A, 60:2746\u20132751, 1999. arXiv:quant-ph\/9711070. doi\/10.1103\/PhysRevA.60.2746.","DOI":"10.1103\/PhysRevA.60.2746"},{"key":"26","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.48550\/arXiv.2208.08416"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2025-01-21-1603\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2025,1,21]],"date-time":"2025-01-21T17:01:16Z","timestamp":1737478876000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2025-01-21-1603\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,21]]},"references-count":27,"URL":"https:\/\/doi.org\/10.22331\/q-2025-01-21-1603","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,1,21]]},"article-number":"1603"}}