quantum-computing

Topologically driven no-superposing theorem with a tight error bound

Zuzana Gavorová

12 min read

0 likes

⚡ Quantum Brief

Zuzana Gavorová proves that superposing two unknown quantum states is fundamentally impossible, even with unlimited copies. The topological proof shows the required operation violates continuity principles inherent in quantum mechanics. The study establishes the first tight error bound for approximate superposition, revealing a fundamental tradeoff: any algorithm either fails completely or incurs unavoidable errors proportional to sample complexity. A trivial single-copy algorithm exists but produces large errors, while the theorem proves no protocol can reduce this error regardless of sample size. This closes a long-standing gap in quantum no-go theorems. State tomography’s utility for superposition is severely limited—it only works in models allowing randomness in outputs. The optimal randomness-tolerant protocol remains an open challenge for quantum algorithm designers. The work extends topological methods in quantum computation, linking algebraic topology to practical limits in state manipulation and reinforcing parallels with no-cloning and no-deleting theorems.

AI Audio Summary

0:00 / 0:00

Click to play

Unsplash · Validated Fallback

Understand this faster with AI

Ask ChatGPT

Research with Perplexity

Explain with Claude

Discuss on Grok

AbstractTo better understand quantum computation we can search for its limits or no-gos, especially if analogous limits do not appear in classical computation. Classical computation easily implements and extensively employs the addition of two bit strings, so here we study 'quantum addition': the superposition of two quantum states. We prove the impossibility of superposing two unknown states, no matter how many samples of each state are available. The proof uses topology; a quantum algorithm of any sample complexity corresponds to a continuous function, but the function required by the superposition task cannot be continuous by topological arguments. Our result for the first time quantifies the approximation error and the sample complexity $N$ of the superposition task, and it is tight. We present a trivial algorithm with a large approximation error and $N=1$, and the matching impossibility of any smaller approximation error for any $N$. Consequently, our results limit state tomography as a useful subroutine for the superposition. State tomography is useful only in a model that tolerates randomness in the superposed state. The optimal protocol in this random model remains open.Featured image: We use the topology of spheres to prove the no-superposing error bound.Popular summaryCreating an exact superposition of two unknown states is known to be impossible. What about an approximate superposition when multiple copies of either input are available? We show simple superposing protocols with a large error and an impossibility of any smaller error. The problem is the discontinuous nature of the superposing task. We show how to circumvent the impossibility by introducing measurements, i.e. randomness, into the task and the quantum circuit that solves it.► BibTeX data@article{Gavorova2025topologicallydriven, doi = {10.22331/q-2025-11-20-1916}, url = {https://doi.org/10.22331/q-2025-11-20-1916}, title = {Topologically driven no-superposing theorem with a tight error bound}, author = {Gavorov{\'{a}}, Zuzana}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {9}, pages = {1916}, month = nov, year = {2025} }► References [1] W. K. Wootters and W. H. Zurek. ``A single quantum cannot be cloned''. Nature 299, 802–803 (1982). https://doi.org/10.1038/299802a0 [2] Charles H. Bennett and Gilles Brassard. ``Quantum cryptography: Public key distribution and coin tossing''.

Theoretical Computer Science 560, 7–11 (2014). https://doi.org/10.1016/j.tcs.2014.05.025 [3] Valerio Scarani, Sofyan Iblisdir, Nicolas Gisin, and Antonio Acín. ``Quantum cloning''. Reviews of Modern Physics 77, 1225–1256 (2005). https://doi.org/10.1103/revmodphys.77.1225 [4] Giulio Chiribella, Giacomo Mauro D’Ariano, and Paolo Perinotti. ``Probabilistic theories with purification''. Physical Review A 81 (2010). https://doi.org/10.1103/physreva.81.062348 [5] Bob Coecke and Ross Duncan. ``Interacting quantum observables: categorical algebra and diagrammatics''. New Journal of Physics 13, 043016 (2011). https://doi.org/10.1088/1367-2630/13/4/043016 [6] Adrian Kent. ``Quantum tasks in Minkowski space''. Classical and Quantum Gravity 29, 224013 (2012). https://doi.org/10.1088/0264-9381/29/22/224013 [7] Wojciech Hubert Zurek. ``Quantum Darwinism''. Nature Physics 5, 181–188 (2009). https://doi.org/10.1038/nphys1202 [8] Paul M.B. Vitányi. ``Quantum Kolmogorov complexity based on classical descriptions''. IEEE Transactions on Information Theory 47, 2464–2479 (2001). https://doi.org/10.1109/18.945258 [9] M. A. Nielsen and Isaac L. Chuang. ``Programmable quantum gate arrays''.

Physical Review Letters 79, 321–324 (1997). https://doi.org/10.1103/physrevlett.79.321 [10] V. Bužek, M. Hillery, and R. F. Werner. ``Optimal manipulations with qubits: Universal-NOT gate''. Physical Review A 60, R2626–R2629 (1999). https://doi.org/10.1103/physreva.60.r2626 [11] Arun Kumar Pati and Samuel L. Braunstein. ``Impossibility of deleting an unknown quantum state''. Nature 404, 164–165 (2000). https://doi.org/10.1038/404130b0 [12] Scott Aaronson. ``Multilinear formulas and skepticism of quantum computing''. In Proceedings of the thirty-sixth annual ACM symposium on Theory of computing. STOC04. ACM (2004). https://doi.org/10.1145/1007352.1007378 [13] Yu Cai, Huy Nguyen Le, and Valerio Scarani. ``State complexity and quantum computation''. Annalen der Physik 527, 684–700 (2015). https://doi.org/10.1002/andp.201400199 [14] Mina Doosti, Farzad Kianvash, and Vahid Karimipour. ``Universal superposition of orthogonal states''. Physical Review A 96 (2017). https://doi.org/10.1103/physreva.96.052318 [15] Michał Oszmaniec, Andrzej Grudka, Michał Horodecki, and Antoni Wójcik. ``Creating a superposition of unknown quantum states''.

Physical Review Letters 116 (2016). https://doi.org/10.1103/physrevlett.116.110403 [16] U. Alvarez-Rodriguez, M. Sanz, L. Lamata, and E. Solano. ``The forbidden quantum adder''. Scientific Reports 5 (2015). https://doi.org/10.1038/srep11983 [17] Rui Li, Unai Alvarez-Rodriguez, Lucas Lamata, and Enrique Solano. ``Approximate quantum adders with genetic algorithms: An IBM quantum experience''. Quantum Measurements and Quantum Metrology 4, 1–7 (2017). https://doi.org/10.1515/qmetro-2017-0001 [18] Xiao-Min Hu, Meng-Jun Hu, Jiang-Shan Chen, Bi-Heng Liu, Yun-Feng Huang, Chuan-Feng Li, Guang-Can Guo, and Yong-Sheng Zhang. ``Experimental creation of superposition of unknown photonic quantum states''. Physical Review A 94 (2016). https://doi.org/10.1103/physreva.94.033844 [19] Keren Li, Guofei Long, Hemant Katiyar, Tao Xin, Guanru Feng, Dawei Lu, and Raymond Laflamme. ``Experimentally superposing two pure states with partial prior knowledge''. Physical Review A 95 (2017). https://doi.org/10.1103/physreva.95.022334 [20] Zuzana Gavorová, Matan Seidel, and Yonathan Touati. ``Topological obstructions to quantum computation with unitary oracles''. Physical Review A 109 (2024). https://doi.org/10.1103/physreva.109.032625 [21] Takanori Sugiyama, Peter S. Turner, and Mio Murao. ``Precision-guaranteed quantum tomography''.

Physical Review Letters 111 (2013). https://doi.org/10.1103/physrevlett.111.160406 [22] Matthias Christandl and Renato Renner. ``Reliable quantum state tomography''.

Physical Review Letters 109 (2012). https://doi.org/10.1103/physrevlett.109.120403 [23] Scott Aaronson. ``Quantum computing, postselection, and probabilistic polynomial-time''. Proceedings of The Royal Society of London. Series A. Mathematical, Physical and Engineering Sciences 461, 3473–3482 (2005). https://doi.org/10.1098/rspa.2005.1546 [24] Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf. ``Quantum lower bounds by polynomials''. Journal of the ACM 48, 778–797 (2001). https://doi.org/10.1145/502090.502097 [25] Ran Raz. ``Tensor-rank and lower bounds for arithmetic formulas''. Journal of the ACM 60, 1–15 (2013). https://doi.org/10.1145/2535928 [26] Howard Barnum, Carlton M. Caves, Christopher A. Fuchs, Richard Jozsa, and Benjamin Schumacher. ``Noncommuting mixed states cannot be broadcast''.

Physical Review Letters 76, 2818–2821 (1996). https://doi.org/10.1103/physrevlett.76.2818 [27] Sandy Irani, Anand Natarajan, Chinmay Nirkhe, Sujit Rao, and Henry Yuen. ``Quantum search-to-decision reductions and the state synthesis problem''. In 37th Computational Complexity Conference. Volume 234 of LIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 5, 19. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern (2022). https://doi.org/10.4230/lipics.ccc.2022.5 [28] Zhengfeng Ji, Yi-Kai Liu, and Fang Song. ``Pseudorandom quantum states''. Pages 126–152.

Springer International Publishing. (2018). https://doi.org/10.1007/978-3-319-96878-0_5 [29] William Kretschmer. ``Quantum pseudorandomness and classical complexity''. In 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021). Pages 2:1–2:20. (2021). https://doi.org/10.4230/LIPIcs.TQC.2021.2 [30] Jonas Haferkamp, Philippe Faist, Naga B. T. Kothakonda, Jens Eisert, and Nicole Yunger Halpern. ``Linear growth of quantum circuit complexity''. Nature Physics 18, 528–532 (2022). https://doi.org/10.1038/s41567-022-01539-6 [31] Leonard Susskind. ``Black holes and complexity classes''. Preprint (2018) arXiv:1802.02175. arXiv:1802.02175 [32] Adam Bouland, Bill Fefferman, and Umesh Vazirani. ``Computational pseudorandomness, the wormhole growth paradox, and constraints on the AdS/CFT duality''. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Pages 63:1–63:2. (2020). https://doi.org/10.4230/LIPIcs.ITCS.2020.63 [33] Allen Hatcher. ``Algebraic topology''.

Cambridge University Press, Cambridge. (2002). [34] Mark M Wilde. ``From classical to quantum Shannon theory''. Preprint (2011) arXiv:1106.1445. https://doi.org/10.1017/9781316809976.001 arXiv:1106.1445Cited byCould not fetch Crossref cited-by data during last attempt 2025-11-20 15:15:23: Could not fetch cited-by data for 10.22331/q-2025-11-20-1916 from Crossref. This is normal if the DOI was registered recently. Could not fetch ADS cited-by data during last attempt 2025-11-20 15:15:24: No response from ADS or unable to decode the received json data when getting the list of citing works.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. AbstractTo better understand quantum computation we can search for its limits or no-gos, especially if analogous limits do not appear in classical computation. Classical computation easily implements and extensively employs the addition of two bit strings, so here we study 'quantum addition': the superposition of two quantum states. We prove the impossibility of superposing two unknown states, no matter how many samples of each state are available. The proof uses topology; a quantum algorithm of any sample complexity corresponds to a continuous function, but the function required by the superposition task cannot be continuous by topological arguments. Our result for the first time quantifies the approximation error and the sample complexity $N$ of the superposition task, and it is tight. We present a trivial algorithm with a large approximation error and $N=1$, and the matching impossibility of any smaller approximation error for any $N$. Consequently, our results limit state tomography as a useful subroutine for the superposition. State tomography is useful only in a model that tolerates randomness in the superposed state. The optimal protocol in this random model remains open.Featured image: We use the topology of spheres to prove the no-superposing error bound.Popular summaryCreating an exact superposition of two unknown states is known to be impossible. What about an approximate superposition when multiple copies of either input are available? We show simple superposing protocols with a large error and an impossibility of any smaller error. The problem is the discontinuous nature of the superposing task. We show how to circumvent the impossibility by introducing measurements, i.e. randomness, into the task and the quantum circuit that solves it.► BibTeX data@article{Gavorova2025topologicallydriven, doi = {10.22331/q-2025-11-20-1916}, url = {https://doi.org/10.22331/q-2025-11-20-1916}, title = {Topologically driven no-superposing theorem with a tight error bound}, author = {Gavorov{\'{a}}, Zuzana}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {9}, pages = {1916}, month = nov, year = {2025} }► References [1] W. K. Wootters and W. H. Zurek. ``A single quantum cannot be cloned''. Nature 299, 802–803 (1982). https://doi.org/10.1038/299802a0 [2] Charles H. Bennett and Gilles Brassard. ``Quantum cryptography: Public key distribution and coin tossing''.

Physical Review Letters 111 (2013). https://doi.org/10.1103/physrevlett.111.160406 [22] Matthias Christandl and Renato Renner. ``Reliable quantum state tomography''.

Read Original

Source Information

Source: Quantum Science and Technology (arXiv overlay)

Website: https://quantum-journal.org/feed

Discussion

0 professional contributions

Be the first to add a constructive contribution.

Topologically driven no-superposing theorem with a tight error bound

Tags

Source Information