{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T19:34:51Z","timestamp":1773516891788,"version":"3.50.1"},"reference-count":53,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2025,1,17]],"date-time":"2025-01-17T00:00:00Z","timestamp":1737072000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,1,17]],"date-time":"2025-01-17T00:00:00Z","timestamp":1737072000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"JST, ACT-X","award":["JPMJAX210O"],"award-info":[{"award-number":["JPMJAX210O"]}]},{"name":"the MEXT Quantum Leap Flagship Program","award":["JPMXS0118067394"],"award-info":[{"award-number":["JPMXS0118067394"]}]},{"name":"JST [Moonshot R&D -- MILLENNIA Program]","award":["JPMJMS2061"],"award-info":[{"award-number":["JPMJMS2061"]}]},{"name":"JST [Moonshot R&D -- MILLENNIA Program]","award":["JPMJMS2061"],"award-info":[{"award-number":["JPMJMS2061"]}]},{"name":"the Grant-in-Aid for Transformative Research Areas, JSPS","award":["JP20H05966"],"award-info":[{"award-number":["JP20H05966"]}]},{"name":"the Grant-in-Aid for Scientific Research (A), JSPS","award":["JP22H00522"],"award-info":[{"award-number":["JP22H00522"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2025,3]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>We define rewinding operators that invert quantum measurements. Then, we define complexity classes <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\textsf{RwBQP}$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>RwBQP<\/mml:mi>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>, <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\textsf{CBQP}$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>CBQP<\/mml:mi>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>, and <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\textsf{AdPostBQP}$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>AdPostBQP<\/mml:mi>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> as sets of decision problems solvable by polynomial-size quantum circuits with a polynomial number of rewinding operators, cloning operators, and adaptive postselections, respectively. Our main result is that <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\textsf{BPP}^\\textsf{PP}\\subseteq \\textsf{RwBQP}=\\textsf{CBQP}=\\textsf{AdPostBQP}\\subseteq \\textsf{PSPACE}$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:msup>\n                      <mml:mi>BPP<\/mml:mi>\n                      <mml:mi>PP<\/mml:mi>\n                    <\/mml:msup>\n                    <mml:mo>\u2286<\/mml:mo>\n                    <mml:mi>RwBQP<\/mml:mi>\n                    <mml:mo>=<\/mml:mo>\n                    <mml:mi>CBQP<\/mml:mi>\n                    <mml:mo>=<\/mml:mo>\n                    <mml:mi>AdPostBQP<\/mml:mi>\n                    <mml:mo>\u2286<\/mml:mo>\n                    <mml:mi>PSPACE<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>. As a byproduct of this result, we show that any problem in <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\textsf{PostBQP}$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>PostBQP<\/mml:mi>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> can be solved with only postselections of events that occur with probabilities polynomially close to one. Under the strongly believed assumption that <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\textsf{BQP}\\nsupseteq \\textsf{SZK}$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>BQP<\/mml:mi>\n                    <mml:mo>\u2289<\/mml:mo>\n                    <mml:mi>SZK<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>, or the shortest independent vectors problem cannot be efficiently solved with quantum computers, we also show that a single rewinding operator is sufficient to achieve tasks that are intractable for quantum computation. Finally, we show that rewindable Clifford circuits remain classically simulatable, but rewindable instantaneous quantum polynomial time circuits can solve any problem in <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\textsf{PP}$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>PP<\/mml:mi>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>.<\/jats:p>","DOI":"10.1007\/s00224-024-10208-5","type":"journal-article","created":{"date-parts":[[2025,1,17]],"date-time":"2025-01-17T07:46:16Z","timestamp":1737099976000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Rewindable Quantum Computation and Its Equivalence to Cloning and Adaptive Postselection"],"prefix":"10.1007","volume":"69","author":[{"given":"Ryo","family":"Hiromasa","sequence":"first","affiliation":[]},{"given":"Akihiro","family":"Mizutani","sequence":"additional","affiliation":[]},{"given":"Yuki","family":"Takeuchi","sequence":"additional","affiliation":[]},{"given":"Seiichiro","family":"Tani","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,1,17]]},"reference":[{"key":"10208_CR1","unstructured":"Hiromasa, R., Mizutani, A., Takeuchi, Y., Tani, S.: Rewindable quantum computation and its equivalence to cloning and adaptive postselection. In: Proceedings of the 18th Conference on the Theory of Quantum Computation, Communication and Cryptography, p. 9:1. LIPIcs, Aveiro (2023)"},{"key":"10208_CR2","doi-asserted-by":"publisher","first-page":"1484","DOI":"10.1137\/S0097539795293172","volume":"26","author":"PW Shor","year":"1997","unstructured":"Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26, 1484 (1997)","journal-title":"SIAM J. Comput."},{"key":"10208_CR3","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1038\/nature23458","volume":"549","author":"AW Harrow","year":"2017","unstructured":"Harrow, A.W., Montanaro, A.: Quantum computational supremacy. Nature (London) 549, 203 (2017)","journal-title":"Nature (London)"},{"key":"10208_CR4","doi-asserted-by":"publisher","first-page":"459","DOI":"10.1098\/rspa.2010.0301","volume":"467","author":"MJ Bremner","year":"2011","unstructured":"Bremner, M.J., Jozsa, R., Shepherd, D.J.: Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy. Proc. R. Soc. A 467, 459 (2011)","journal-title":"Proc. R. Soc. A"},{"key":"10208_CR5","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.120.200502","volume":"120","author":"K Fujii","year":"2018","unstructured":"Fujii, K., Kobayashi, H., Morimae, T., Nishimura, H., Tamate, S., Tani, S.: Impossibility of classically simulating one-clean-qubit model with multiplicative error. Phys. Rev. Lett. 120, 200502 (2018)","journal-title":"Phys. Rev. Lett."},{"key":"10208_CR6","doi-asserted-by":"publisher","first-page":"106","DOI":"10.22331\/q-2018-11-15-106","volume":"2","author":"T Morimae","year":"2018","unstructured":"Morimae, T., Takeuchi, Y., Nishimura, H.: Merlin-Arthur with efficient quantum Merlin and quantum supremacy for the second level of the Fourier hierarchy. Quantum 2, 106 (2018)","journal-title":"Quantum"},{"key":"10208_CR7","doi-asserted-by":"crossref","unstructured":"Aaronson, S., Arkhipov, A.: The computational complexity of linear optics. In: Proceedings of the 43rd Symposium on Theory of Computing, p. 333. ACM Press, San Jose (2011)","DOI":"10.1145\/1993636.1993682"},{"key":"10208_CR8","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.112.130502","volume":"112","author":"T Morimae","year":"2014","unstructured":"Morimae, T., Fujii, K., Fitzsimons, J.F.: Hardness of classically simulating the one-clean-qubit model. Phys. Rev. Lett. 112, 130502 (2014)","journal-title":"Phys. Rev. Lett."},{"key":"10208_CR9","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.113.100502","volume":"113","author":"AP Lund","year":"2014","unstructured":"Lund, A.P., Laing, A., Rahimi-Keshari, S., Rudolph, T., O\u2019Brien, J.L., Ralph, T.C.: Boson Sampling from a Gaussian state. Phys. Rev. Lett. 113, 100502 (2014)","journal-title":"Phys. Rev. Lett."},{"key":"10208_CR10","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.117.080501","volume":"117","author":"MJ Bremner","year":"2016","unstructured":"Bremner, M.J., Montanaro, A., Shepherd, D.J.: Average-case complexity versus approximate simulation of commuting quantum computations. Phys. Rev. Lett. 117, 080501 (2016)","journal-title":"Phys. Rev. Lett."},{"key":"10208_CR11","first-page":"251","volume":"16","author":"Y Takahashi","year":"2016","unstructured":"Takahashi, Y., Tani, S., Yamazaki, T., Tanaka, K.: Commuting quantum circuits with few outputs are unlikely to be classically simulatable. Quantum Inf. Comput. 16, 251 (2016)","journal-title":"Quantum Inf. Comput."},{"key":"10208_CR12","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.94.062336","volume":"94","author":"Y Takeuchi","year":"2016","unstructured":"Takeuchi, Y., Takahashi, Y.: Ancilla-driven instantaneous quantum polynomial time circuit for quantum supremacy. Phys. Rev. A 94, 062336 (2016)","journal-title":"Phys. Rev. A"},{"key":"10208_CR13","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.118.040502","volume":"118","author":"X Gao","year":"2017","unstructured":"Gao, X., Wang, S.-T., Duan, L.-M.: Quantum supremacy for simulating a translation-invariant ising spin model. Phys. Rev. Lett. 118, 040502 (2017)","journal-title":"Phys. Rev. Lett."},{"key":"10208_CR14","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.119.170501","volume":"119","author":"CS Hamilton","year":"2017","unstructured":"Hamilton, C.S., Kruse, R., Sansoni, L., Barkhofen, S., Silberhorn, C., Jex, I.: Gaussian boson sampling. Phys. Rev. Lett. 119, 170501 (2017)","journal-title":"Phys. Rev. Lett."},{"key":"10208_CR15","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.96.062320","volume":"96","author":"J Miller","year":"2017","unstructured":"Miller, J., Sanders, S., Miyake, A.: Quantum supremacy in constant-time measurement-based computation: A unified architecture for sampling and verification. Phys. Rev. A 96, 062320 (2017)","journal-title":"Phys. Rev. A"},{"key":"10208_CR16","doi-asserted-by":"publisher","first-page":"595","DOI":"10.1038\/s41567-018-0124-x","volume":"14","author":"S Boixo","year":"2018","unstructured":"Boixo, S., Isakov, S.V., Smelyanskiy, V.N., Babbush, R., Ding, N., Jiang, Z., Bremner, M.J., Martinis, J.M., Neven, H.: Characterizing quantum supremacy in near-term devices. Nat. Phys. 14, 595 (2018)","journal-title":"Nat. Phys."},{"key":"10208_CR17","doi-asserted-by":"publisher","first-page":"65","DOI":"10.22331\/q-2018-05-22-65","volume":"2","author":"D Hangleiter","year":"2018","unstructured":"Hangleiter, D., Bermejo-Vega, J., Schwarz, M., Eisert, J.: Anticoncentration theorems for schemes showing a quantum speedup. Quantum 2, 65 (2018)","journal-title":"Quantum"},{"key":"10208_CR18","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1038\/s41567-018-0318-2","volume":"15","author":"A Bouland","year":"2019","unstructured":"Bouland, A., Fefferman, B., Nirkhe, C., Vazirani, U.: On the complexity and verification of quantum random circuit sampling. Nat. Phys. 15, 159 (2019)","journal-title":"Nat. Phys."},{"key":"10208_CR19","unstructured":"Morimae, T., Takeuchi, Y., Tani, S.: Sampling of globally depolarized random quantum circuit. arXiv:1911.02220"},{"key":"10208_CR20","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1137\/060670997","volume":"39","author":"J Watrous","year":"2009","unstructured":"Watrous, J.: Zero-knowledge against quantum attacks. SIAM J. Comput. 39, 25 (2009)","journal-title":"SIAM J. Comput."},{"key":"10208_CR21","doi-asserted-by":"crossref","unstructured":"Ambainis, A., Rosmanis, A., Unruh, D.: Quantum attacks on classical proof systems: The hardness of quantum rewinding. In: Proc. of the 55th Annual Symposium on Foundations of Computer Science, p. 474. IEEE, Philadelphia (2014)","DOI":"10.1109\/FOCS.2014.57"},{"key":"10208_CR22","doi-asserted-by":"crossref","unstructured":"Unruh, D.: Computationally binding quantum commitments. In: Proc. of the 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, p. 497. Springer, Vienna (2016)","DOI":"10.1007\/978-3-662-49896-5_18"},{"key":"10208_CR23","doi-asserted-by":"publisher","first-page":"3473","DOI":"10.1098\/rspa.2005.1546","volume":"461","author":"S Aaronson","year":"2005","unstructured":"Aaronson, S.: Quantum computing, postselection, and probabilistic polynomial-time. Proc. R. Soc. A 461, 3473 (2005)","journal-title":"Proc. R. Soc. A"},{"key":"10208_CR24","doi-asserted-by":"publisher","first-page":"802","DOI":"10.1038\/299802a0","volume":"299","author":"WK Wootters","year":"1982","unstructured":"Wootters, W.K., Zurek, W.H.: A single quantum cannot be cloned. Nature (London) 299, 802 (1982)","journal-title":"Nature (London)"},{"key":"10208_CR25","unstructured":"Aaronson, S., Bouland, A., Fitzsimons, J., Lee, M.: The space \u201cjust above\u201d BQP. arXiv:1412.6507"},{"key":"10208_CR26","doi-asserted-by":"crossref","unstructured":"Regev, O: On lattices, learning with errors, random linear codes, and cryptography. In: Proc. of the 37th Annual Symposium on Theory of Computing, p. 84. ACM, Baltimore (2005)","DOI":"10.1145\/1060590.1060603"},{"key":"10208_CR27","doi-asserted-by":"crossref","unstructured":"Aaronson, S.: Quantum lower bound for the collision problem. In: Proc. of the 34th Annual Symposium on Theory of Computing, p. 635. ACM, Montr\u00e9al (2002)","DOI":"10.1145\/509907.509999"},{"key":"10208_CR28","doi-asserted-by":"crossref","unstructured":"Peikert, C., Vaikuntanathan, V.: Noninteractive statistical zero-knowledge proofs for lattice problems. In: Proc. of the 28th International Cryptology Conference, p. 536. Springer, Santa Barbara (2008)","DOI":"10.1007\/978-3-540-85174-5_30"},{"key":"10208_CR29","unstructured":"Gottesman, D.: The Heisenberg representation of quantum computers. In: Group22: Proc. of the XXII International Colloquium on Group Theoretical Methods in Physics, p. 32. International Press, Cambridge (1999)"},{"key":"10208_CR30","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.111.190401","volume":"111","author":"TA Brun","year":"2013","unstructured":"Brun, T.A., Wilde, M.M., Winter, A.: Quantum state cloning using deutschian closed timelike curves. Phys. Rev. Lett. 111, 190401 (2013)","journal-title":"Phys. Rev. Lett."},{"key":"10208_CR31","doi-asserted-by":"publisher","first-page":"3197","DOI":"10.1103\/PhysRevD.44.3197","volume":"44","author":"D Deutsch","year":"1991","unstructured":"Deutsch, D.: Quantum mechanics near closed timelike lines. Phys. Rev. D 44, 3197 (1991)","journal-title":"Phys. Rev. D"},{"key":"10208_CR32","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.106.040403","volume":"106","author":"S Lloyd","year":"2011","unstructured":"Lloyd, S., Maccone, L., Garcia-Patron, R., Giovannetti, V., Shikano, Y., Pirandola, S., Rozema, L.A., Darabi, A., Soudagar, Y., Shalm, L.K., Steinberg, A.M.: Closed timelike curves via postselection: Theory and experimental test of consistency. Phys. Rev. Lett. 106, 040403 (2011)","journal-title":"Phys. Rev. Lett."},{"key":"10208_CR33","doi-asserted-by":"publisher","first-page":"631","DOI":"10.1098\/rspa.2008.0350","volume":"465","author":"S Aaronson","year":"2009","unstructured":"Aaronson, S., Watrous, J.: Closed timelike curves make quantum and classical computing equivalent. Proc. R. Soc. A 465, 631 (2009)","journal-title":"Proc. R. Soc. A"},{"key":"10208_CR34","doi-asserted-by":"crossref","unstructured":"Aaronson, S., Bouland, A., Fitzsimons, J., Lee, M.: The space \u201cJust Above\u201d BQP. In: Proc. of the 7th ACM Conference on Innovations in Theoretical Computer Science, p. 271. ACM, Cambridge (2016)","DOI":"10.1145\/2840728.2840739"},{"key":"10208_CR35","doi-asserted-by":"publisher","first-page":"1411","DOI":"10.1137\/S0097539796300921","volume":"26","author":"E Bernstein","year":"1997","unstructured":"Bernstein, E., Vazirani, U.: Quantum complexity theory. SIAM J. Comput. 26, 1411 (1997)","journal-title":"SIAM J. Comput."},{"key":"10208_CR36","doi-asserted-by":"publisher","first-page":"3","DOI":"10.3390\/cryptography5010003","volume":"5","author":"A Cojocaru","year":"2021","unstructured":"Cojocaru, A., Colisson, L., Kashefi, E., Wallden, P.: On the possibility of classical client blind quantum computing. Cryptography 5, 3 (2021)","journal-title":"Cryptography"},{"key":"10208_CR37","doi-asserted-by":"crossref","unstructured":"Cojocaru, A., Colisson, L., Kashefi, E., Wallden, P.: QFactory: Classically-instructed remote secret qubits preparation. In: Proc. of the 25th Annual International Conference on the Theory and Application of Cryptology and Information Security, p. 615. Springer, Kobe (2019)","DOI":"10.1007\/978-3-030-34578-5_22"},{"key":"10208_CR38","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804090","volume-title":"Computational Complexity: A modern approach","author":"S Arora","year":"2009","unstructured":"Arora, S., Barak, B.: Computational Complexity: A modern approach. Cambridge University Press, Cambridge (2009)"},{"key":"10208_CR39","unstructured":"Shi, Y.: Toffoli and Controlled-NOT need little help to do universal quantum computation. Preprint at arXiv:quant-ph\/0205115"},{"key":"10208_CR40","first-page":"81","volume":"6","author":"CM Dawson","year":"2006","unstructured":"Dawson, C.M., Nielsen, M.A.: The Solovay-Kitaev algorithm. Quantum Inf. Comput. 6, 81 (2006)","journal-title":"Quantum Inf. Comput."},{"key":"10208_CR41","doi-asserted-by":"publisher","first-page":"3992","DOI":"10.1103\/PhysRevLett.81.3992","volume":"81","author":"DS Abrams","year":"1998","unstructured":"Abrams, D.S., Lloyd, S.: Nonlinear quantum mechanics implies polynomial-time solution for NP-complete and # P problems. Phys. Rev. Lett. 81, 3992 (1998)","journal-title":"Phys. Rev. Lett."},{"key":"10208_CR42","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1145\/636865.636868","volume":"50","author":"A Sahai","year":"2003","unstructured":"Sahai, A., Vadhan, S.: A complete problem for statistical zero knowledge. J. ACM 50, 196 (2003)","journal-title":"J. ACM"},{"key":"10208_CR43","doi-asserted-by":"publisher","first-page":"5188","DOI":"10.1103\/PhysRevLett.86.5188","volume":"86","author":"R Raussendorf","year":"2001","unstructured":"Raussendorf, R., Briegel, H.J.: A one-way quantum computer. Phys. Rev. Lett. 86, 5188 (2001)","journal-title":"Phys. Rev. Lett."},{"key":"10208_CR44","doi-asserted-by":"crossref","unstructured":"Broadbent, A., Fitzsimons, J., Kashefi, E.: Universal blind quantum computation. In: Proc. of the 50th Annual Symposium on Foundations of Computer Science, p. 517. IEEE, Atlanta (2009)","DOI":"10.1109\/FOCS.2009.36"},{"key":"10208_CR45","doi-asserted-by":"publisher","first-page":"42861","DOI":"10.1038\/srep42861","volume":"7","author":"A Mantri","year":"2017","unstructured":"Mantri, A., Demarie, T.F., Fitzsimons, J.F.: Universality of quantum computation with cluster states and (X, Y)-plane measurements. Sci. Rep. 7, 42861 (2017)","journal-title":"Sci. Rep."},{"key":"10208_CR46","unstructured":"Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information 10th Anniversary. Cambridge University Press, Cambridge (2010)"},{"key":"10208_CR47","doi-asserted-by":"publisher","first-page":"1450026","DOI":"10.1142\/S0219749914500269","volume":"12","author":"T Morimae","year":"2014","unstructured":"Morimae, T.: Measurement-based quantum computation cannot avoid byproducts. Int. J. Quantum Inf. 12, 1450026 (2014)","journal-title":"Int. J. Quantum Inf."},{"key":"10208_CR48","doi-asserted-by":"crossref","unstructured":"Aaronson, S.: Limitations of quantum advice and one-way communication. In: Proc. of the 19th IEEE Annual Conference on Computational Complexity, p. 320. IEEE, Amherst (2004)","DOI":"10.1109\/CCC.2004.1313854"},{"key":"10208_CR49","doi-asserted-by":"crossref","unstructured":"Aaronson, S.: $${\\sf QMA\/qpoly}\\subseteq {\\sf PSPACE\/poly}$$: De-Merlinizing quantum protocols. In: Proc. of the 21st Annual IEEE Conference on Computational Complexity, p. 261. IEEE, Prague (2006)","DOI":"10.1109\/CCC.2006.36"},{"key":"10208_CR50","first-page":"959","volume":"17","author":"T Morimae","year":"2017","unstructured":"Morimae, T., Nishimura, H.: Merlinization of complexity classes above BQP. Quantum Inf. Comput. 17, 959 (2017)","journal-title":"Quantum Inf. Comput."},{"key":"10208_CR51","unstructured":"Beikidezfuli, S.A.: Quantum proof systems and entanglement theory. Ph.D. Thesis, Massachusetts Institute of Technology (2009)"},{"key":"10208_CR52","unstructured":"Kinoshita, Y.: QMA(2) with postselection equals to NEXP. arXiv:1806.09732"},{"key":"10208_CR53","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.96.032321","volume":"96","author":"N Usher","year":"2017","unstructured":"Usher, N., Hoban, M.J., Browne, D.E.: Nonunitary quantum computation in the ground space of local Hamiltonians. Phys. Rev. A 96, 032321 (2017)","journal-title":"Phys. Rev. A"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-024-10208-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-024-10208-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-024-10208-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,9]],"date-time":"2025-04-09T17:11:33Z","timestamp":1744218693000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-024-10208-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,17]]},"references-count":53,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,3]]}},"alternative-id":["10208"],"URL":"https:\/\/doi.org\/10.1007\/s00224-024-10208-5","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,1,17]]},"assertion":[{"value":"11 October 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 January 2025","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"6"}}