{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,17]],"date-time":"2026-07-17T11:08:14Z","timestamp":1784286494671,"version":"3.55.0"},"reference-count":115,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T00:00:00Z","timestamp":1779062400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T00:00:00Z","timestamp":1779062400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100003626","name":"Defense Acquisition Program Administration","doi-asserted-by":"publisher","award":["KRIT-CT-23-031"],"award-info":[{"award-number":["KRIT-CT-23-031"]}],"id":[{"id":"10.13039\/501100003626","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Quantum Inf Process"],"DOI":"10.1007\/s11128-026-05201-5","type":"journal-article","created":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T04:58:57Z","timestamp":1779080337000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Analysis of quantum primitives for quantum utility"],"prefix":"10.1007","volume":"25","author":[{"given":"Tae-Won","family":"Kim","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Byung-Soo","family":"Choi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,5,18]]},"reference":[{"key":"5201_CR1","doi-asserted-by":"publisher","DOI":"10.1017\/9781009639651","volume-title":"Quantum Algorithms: A Survey of Applications and End-to-end Complexities","author":"AM Dalzell","year":"2025","unstructured":"Dalzell, A.M., McArdle, S., Berta, M., Bienias, P., Chen, C.-F., Gily\u00e9n, A., Hann, C.T., Kastoryano, M.J., Khabiboulline, E.T., Kubica, A., Salton, G., Wang, S., Brand\u00e3o, F.G.S.L.: Quantum Algorithms: A Survey of Applications and End-to-end Complexities. Cambridge University Press, Cambridge (2025)"},{"key":"5201_CR2","unstructured":"Arnault, P., Arrighi, P., Herbert, S., Kasnetsi, E., Li, T.: A typology of quantum algorithms (2024). https:\/\/arxiv.org\/abs\/2407.05178"},{"key":"5201_CR3","doi-asserted-by":"publisher","DOI":"10.1103\/PRXQuantum.2.010103","volume":"2","author":"R Babbush","year":"2021","unstructured":"Babbush, R., McClean, J.R., Newman, M., Gidney, C., Boixo, S., Neven, H.: Focus beyond quadratic speedups for error-corrected quantum advantage. PRX Quantum 2, 010103 (2021). https:\/\/doi.org\/10.1103\/PRXQuantum.2.010103","journal-title":"PRX Quantum"},{"key":"5201_CR4","doi-asserted-by":"crossref","unstructured":"Jaques, S., Rattew, A.G.: QRAM: a survey and critique. Quantum 9, 1922 (2025). https:\/\/doi.org\/10.22331\/q-2025-12-02-1922","DOI":"10.22331\/q-2025-12-02-1922"},{"issue":"1","key":"5201_CR5","doi-asserted-by":"publisher","first-page":"133","DOI":"10.4086\/toc.2014.v010a006","volume":"10","author":"S Aaronson","year":"2014","unstructured":"Aaronson, S., Ambainis, A.: The need for structure in quantum speedups. Theory Comput. 10(1), 133\u2013166 (2014). https:\/\/doi.org\/10.4086\/toc.2014.v010a006","journal-title":"Theory Comput."},{"key":"5201_CR6","unstructured":"Lall, D., Agarwal, A., Zhang, W., Lindoy, L., Lindstr\u00f6m, T., Webster, S., Hall, S., Chancellor, N., Wallden, P., Garcia-Patron, R., Kashefi, E., Kendon, V., Pritchard, J., Rossi, A., Datta, A., Kapourniotis, T., Georgopoulos, K., Rungger, I.: A review and collection of metrics and benchmarks for quantum computers: definitions, methodologies and software, (2025). arXiv:2502.06717"},{"issue":"2","key":"5201_CR7","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1038\/s42254-024-00796-z","volume":"7","author":"T Proctor","year":"2025","unstructured":"Proctor, T., Young, K., Baczewski, A.D., Blume-Kohout, R.: Benchmarking quantum computers. Nat. Rev. Phys. 7(2), 105\u2013118 (2025). https:\/\/doi.org\/10.1038\/s42254-024-00796-z. arXiv:2407.08828 [quant-ph]","journal-title":"Nat. Rev. Phys."},{"key":"5201_CR8","unstructured":"McGeoch, C.: How not to fool the masses when giving performance results for quantum computers (2024). https:\/\/arxiv.org\/abs\/2411.08860"},{"key":"5201_CR9","doi-asserted-by":"publisher","unstructured":"Acuaviva, A., Aguirre, D., Pe\u00f1a, R., Sanz, M.: Benchmarking quantum computers: towards a standard performance evaluation approach. Quantum Sci. Technol. 11(2), 025004 (2026). https:\/\/doi.org\/10.1088\/2058-9565\/ae4269","DOI":"10.1088\/2058-9565\/ae4269"},{"key":"5201_CR10","unstructured":"Preskill, J.: Quantum computing and the entanglement frontier (2012). https:\/\/arxiv.org\/abs\/1203.5813"},{"key":"5201_CR11","unstructured":"Pednault, E., Gunnels, J.A., Nannicini, G., Horesh, L., Wisnieff, R.: Leveraging secondary storage to simulate deep 54-qubit sycamore circuits (2019). https:\/\/arxiv.org\/abs\/1910.09534"},{"issue":"5","key":"5201_CR12","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1145\/3571725","volume":"66","author":"T Hoefler","year":"2023","unstructured":"Hoefler, T., H\u00e4ner, T., Troyer, M.: Disentangling hype from practicality: on realistically achieving quantum advantage. Commun. ACM 66(5), 82\u201387 (2023). https:\/\/doi.org\/10.1145\/3571725","journal-title":"Commun. ACM"},{"key":"5201_CR13","doi-asserted-by":"crossref","unstructured":"Preskill, J.: Beyond NISQ: The Megaquop machine. ACM Trans. Quantum Comput. 6(3), 1\u20137 (2025). https:\/\/doi.org\/10.1145\/3723153","DOI":"10.1145\/3723153"},{"key":"5201_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1109\/TQE.2023.3253761","volume":"4","author":"T Lubinski","year":"2023","unstructured":"Lubinski, T., Johri, S., Varosy, P., Coleman, J., Zhao, L., Necaise, J., Baldwin, C.H., Mayer, K., Proctor, T.: Application-oriented performance benchmarks for quantum computing. IEEE Trans. Quantum Eng. 4, 1\u201332 (2023). https:\/\/doi.org\/10.1109\/TQE.2023.3253761","journal-title":"IEEE Trans. Quantum Eng."},{"key":"5201_CR15","unstructured":"Lubinski, T., Goings, J.J., Mayer, K., Johri, S., Reddy, N., Mehta, A., Bhatia, N., Rappaport, S., Mills, D., Baldwin, C.H., Zhao, L., Barbosa, A., Maity, S., Mundada, P.S.: Quantum algorithm exploration using application-oriented performance benchmarks (2024). https:\/\/arxiv.org\/abs\/2402.08985"},{"key":"5201_CR16","doi-asserted-by":"crossref","unstructured":"Chen, J.-S., Nielsen, E., Ebert, M., Inlek, V., Wright, K., Chaplin, V., Maksymov, A., P\u00e1ez, E., Poudel, A., Maunz, P., Gamble, J.: Benchmarking a trapped-ion quantum computer with 30 qubits. Quantum 8, 1516 (2024). https:\/\/doi.org\/10.22331\/q-2024-11-07-1516","DOI":"10.22331\/q-2024-11-07-1516"},{"key":"5201_CR17","unstructured":"Quantinuum: Debunking algorithmic qubits. https:\/\/www.quantinuum.com\/blog\/debunking-algorithmic-qubits (2024). Accessed 22 Jan 2026"},{"key":"5201_CR18","unstructured":"Seritan, S.K., Dhumuntarao, A., Wilber-Gauthier, A.Q., Rudinger, K.M., Russo, A.E., Blume-Kohout, R., Baczewski, A.D., Proctor, T.: Benchmarking quantum computers with any quantum algorithm (2025). https:\/\/arxiv.org\/abs\/2508.05754"},{"key":"5201_CR19","doi-asserted-by":"publisher","unstructured":"Tomesh, T., Gokhale, P., Omole, V., Ravi, G.S., Smith, K.N., Viszlai, J., Wu, X.-C., Hardavellas, N., Martonosi, M.R., Chong, F.T.: Supermarq: A scalable quantum benchmark suite. In: 2022 IEEE International Symposium on High-Performance Computer Architecture (HPCA), pp. 587\u2013603. (2022). https:\/\/doi.org\/10.1109\/HPCA53966.2022.00050","DOI":"10.1109\/HPCA53966.2022.00050"},{"issue":"1","key":"5201_CR20","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1145\/991124.991126","volume":"32","author":"LK John","year":"2004","unstructured":"John, L.K.: More on finding a single number to indicate overall performance of a benchmark suite. SIGARCH Comput. Archit. News 32(1), 3\u20138 (2004). https:\/\/doi.org\/10.1145\/991124.991126","journal-title":"SIGARCH Comput. Archit. News"},{"key":"5201_CR21","unstructured":"Kitaev, A.Y.: Quantum measurements and the abelian stabilizer problem (1995). https:\/\/arxiv.org\/abs\/quant-ph\/9511026"},{"issue":"1","key":"5201_CR22","doi-asserted-by":"publisher","first-page":"4213","DOI":"10.1038\/ncomms5213","volume":"5","author":"A Peruzzo","year":"2014","unstructured":"Peruzzo, A., McClean, J., Shadbolt, P., Yung, M.-H., Zhou, X.-Q., Love, P.J., Aspuru-Guzik, A., O\u2019Brien, J.L.: A variational eigenvalue solver on a photonic quantum processor. Nat. Commun. 5(1), 4213 (2014). https:\/\/doi.org\/10.1038\/ncomms5213","journal-title":"Nat. Commun."},{"key":"5201_CR23","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/305\/05215","author":"G Brassard","year":"2002","unstructured":"Brassard, G., H\u00f8yer, P., Mosca, M., Tapp, A.: Quantum amplitude amplification and estimation. Quantum Comput. Inf. (2002). https:\/\/doi.org\/10.1090\/conm\/305\/05215","journal-title":"Quantum Comput. Inf."},{"issue":"2","key":"5201_CR24","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1038\/s41567-019-0704-4","volume":"16","author":"M Motta","year":"2020","unstructured":"Motta, M., Sun, C., Tan, A.T.K., O\u2019Rourke, M.J., Ye, E., Minnich, A.J., Brand\u00e3o, F.G.S.L., Chan, G.K.-L.: Determining eigenstates and thermal states on a quantum computer using quantum imaginary time evolution. Nat. Phys. 16(2), 205\u2013210 (2020). https:\/\/doi.org\/10.1038\/s41567-019-0704-4","journal-title":"Nat. Phys."},{"key":"5201_CR25","unstructured":"Farhi, E., Goldstone, J., Gutmann, S., Sipser, M.: Quantum computation by adiabatic evolution (2000). https:\/\/arxiv.org\/abs\/quant-ph\/0001106"},{"key":"5201_CR26","doi-asserted-by":"publisher","unstructured":"Deutsch, D., Jozsa, R.: Rapid solution of problems by quantum computation. Proc. Royal Soc. Lond. Ser. A: Math. Phys. Sci. 439(1907), 553\u2013558 (1992). https:\/\/doi.org\/10.1098\/rspa.1992.0167","DOI":"10.1098\/rspa.1992.0167"},{"issue":"5","key":"5201_CR27","doi-asserted-by":"publisher","first-page":"1474","DOI":"10.1137\/S0097539796298637","volume":"26","author":"DR Simon","year":"1997","unstructured":"Simon, D.R.: On the power of quantum computation. SIAM J. Comput. 26(5), 1474\u20131483 (1997). https:\/\/doi.org\/10.1137\/S0097539796298637","journal-title":"SIAM J. Comput."},{"key":"5201_CR28","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.101.062310","volume":"101","author":"C Bravo-Prieto","year":"2020","unstructured":"Bravo-Prieto, C., Garc\u00eda-Mart\u00edn, D., Latorre, J.I.: Quantum singular value decomposer. Phys. Rev. A 101, 062310 (2020). https:\/\/doi.org\/10.1103\/PhysRevA.101.062310","journal-title":"Phys. Rev. A"},{"key":"5201_CR29","unstructured":"Chakraborty, S., Gily\u00e9n, A., Jeffery, S.: The Power of Block-Encoded Matrix Powers: Improved Regression Techniques via Faster Hamiltonian Simulation. In: Baier, C., Chatzigiannakis, I., Flocchini, P., Leonardi, S. (eds.) 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), vol. 132, pp. 33\u201313314. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2019). doi: 10.4230\/LIPIcs.ICALP.2019.33"},{"issue":"10","key":"5201_CR30","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1007\/s11128-024-04553-0","volume":"23","author":"S Patil","year":"2024","unstructured":"Patil, S., Banerjee, S., Panigrahi, P.K.: NISQ-friendly measurement-based quantum clustering algorithms. Quantum Inf. Process. 23(10), 341 (2024). https:\/\/doi.org\/10.1007\/s11128-024-04553-0","journal-title":"Quantum Inf. Process."},{"issue":"6","key":"5201_CR31","doi-asserted-by":"publisher","first-page":"60002","DOI":"10.1209\/0295-5075\/119\/60002","volume":"119","author":"M Schuld","year":"2017","unstructured":"Schuld, M., Fingerhuth, M., Petruccione, F.: Implementing a distance-based classifier with a quantum interference circuit. Europhys. Lett. 119(6), 60002 (2017). https:\/\/doi.org\/10.1209\/0295-5075\/119\/60002","journal-title":"Europhys. Lett."},{"issue":"2","key":"5201_CR32","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1007\/s00220-006-0150-x","volume":"270","author":"DW Berry","year":"2007","unstructured":"Berry, D.W., Ahokas, G., Cleve, R., Sanders, B.C.: Efficient quantum algorithms for simulating sparse hamiltonians. Commun. Math. Phys. 270(2), 359\u2013371 (2007). https:\/\/doi.org\/10.1007\/s00220-006-0150-x","journal-title":"Commun. Math. Phys."},{"key":"5201_CR33","doi-asserted-by":"crossref","unstructured":"Childs, A.M., Wiebe, N.: Hamiltonian simulation using linear combinations of unitary operations. Quantum Inf. Comput. 12(11 and 12) (2012) https:\/\/doi.org\/10.26421\/qic12.11-12","DOI":"10.26421\/QIC12.11-12-1"},{"issue":"7969","key":"5201_CR34","doi-asserted-by":"publisher","first-page":"282","DOI":"10.1038\/s41586-023-06095-4","volume":"619","author":"D Layden","year":"2023","unstructured":"Layden, D., Mazzola, G., Mishmash, R.V., Motta, M., Wocjan, P., Kim, J.-S., Sheldon, S.: Quantum-enhanced Markov chain Monte Carlo. Nature 619(7969), 282\u2013287 (2023). https:\/\/doi.org\/10.1038\/s41586-023-06095-4","journal-title":"Nature"},{"key":"5201_CR35","doi-asserted-by":"crossref","unstructured":"Khatri, S., LaRose, R., Poremba, A., Cincio, L., Sornborger, A.T., Coles, P.J.: Quantum-assisted quantum compiling. Quantum 3, 140 (2019). https:\/\/doi.org\/10.22331\/q-2019-05-13-140","DOI":"10.22331\/q-2019-05-13-140"},{"key":"5201_CR36","unstructured":"Aharonov, D., Landau, Z., Makowsky, J.: The quantum FFT can be classically simulated (2006). https:\/\/arxiv.org\/abs\/quant-ph\/0611156"},{"issue":"5","key":"5201_CR37","doi-asserted-by":"publisher","first-page":"1541","DOI":"10.1137\/S0097539796302452","volume":"26","author":"A Barenco","year":"1997","unstructured":"Barenco, A., Berthiaume, A., Deutsch, D., Ekert, A., Jozsa, R., Macchiavello, C.: Stabilization of quantum computations by symmetrization. SIAM J. Comput. 26(5), 1541\u20131557 (1997). https:\/\/doi.org\/10.1137\/S0097539796302452","journal-title":"SIAM J. Comput."},{"key":"5201_CR38","doi-asserted-by":"publisher","unstructured":"Aaronson, S., Arkhipov, A.: The computational complexity of linear optics. STOC \u201911, pp. 333\u2013342. Association for Computing Machinery, New York, NY, USA (2011). https:\/\/doi.org\/10.1145\/1993636.1993682","DOI":"10.1145\/1993636.1993682"},{"key":"5201_CR39","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevApplied.9.044036","volume":"9","author":"Z Jiang","year":"2018","unstructured":"Jiang, Z., Sung, K.J., Kechedzhi, K., Smelyanskiy, V.N., Boixo, S.: Quantum algorithms to simulate many-body physics of correlated fermions. Phys. Rev. Appl. 9, 044036 (2018). https:\/\/doi.org\/10.1103\/PhysRevApplied.9.044036","journal-title":"Phys. Rev. Appl."},{"key":"5201_CR40","doi-asserted-by":"crossref","unstructured":"Eon, N., Molfetta, G.D., Magnifico, G., Arrighi, P.: A relativistic discrete spacetime formulation of 3+1 QED. Quantum 7, 1179 (2023). https:\/\/doi.org\/10.22331\/q-2023-11-08-1179","DOI":"10.22331\/q-2023-11-08-1179"},{"key":"5201_CR41","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.126.062001","volume":"126","author":"B Nachman","year":"2021","unstructured":"Nachman, B., Provasoli, D., Jong, W.A., Bauer, C.W.: Quantum algorithm for high energy physics simulations. Phys. Rev. Lett. 126, 062001 (2021). https:\/\/doi.org\/10.1103\/PhysRevLett.126.062001","journal-title":"Phys. Rev. Lett."},{"key":"5201_CR42","doi-asserted-by":"publisher","DOI":"10.1103\/PRXQuantum.3.020364","volume":"3","author":"M Bagherimehrab","year":"2022","unstructured":"Bagherimehrab, M., Sanders, Y.R., Berry, D.W., Brennen, G.K., Sanders, B.C.: Nearly optimal quantum algorithm for generating the ground state of a free quantum field theory. PRX Quantum 3, 020364 (2022). https:\/\/doi.org\/10.1103\/PRXQuantum.3.020364","journal-title":"PRX Quantum"},{"issue":"10","key":"5201_CR43","doi-asserted-by":"publisher","first-page":"1459","DOI":"10.1038\/s41567-023-02133-0","volume":"19","author":"Y Yao","year":"2023","unstructured":"Yao, Y., Xiang, L., Guo, Z., Bao, Z., Yang, Y.-F., Song, Z., Shi, H., Zhu, X., Jin, F., Chen, J., Xu, S., Zhu, Z., Shen, F., Wang, N., Zhang, C., Wu, Y., Zou, Y., Zhang, P., Li, H., Wang, Z., Song, C., Cheng, C., Mondaini, R., Wang, H., You, J.Q., Zhu, S.-Y., Ying, L., Guo, Q.: Observation of many-body Fock space dynamics in two dimensions. Nat. Phys. 19(10), 1459\u20131465 (2023). https:\/\/doi.org\/10.1038\/s41567-023-02133-0","journal-title":"Nat. Phys."},{"key":"5201_CR44","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.109.042412","volume":"109","author":"JG Smith","year":"2024","unstructured":"Smith, J.G., Barnes, C.H.W., Arvidsson-Shukur, D.R.M.: Adaptive Bayesian quantum algorithm for phase estimation. Phys. Rev. A 109, 042412 (2024). https:\/\/doi.org\/10.1103\/PhysRevA.109.042412","journal-title":"Phys. Rev. A"},{"key":"5201_CR45","doi-asserted-by":"publisher","first-page":"6920","DOI":"10.1103\/PhysRevD.49.6920","volume":"49","author":"I Bialynicki-Birula","year":"1994","unstructured":"Bialynicki-Birula, I.: Weyl, Dirac, and Maxwell equations on a lattice as unitary cellular automata. Phys. Rev. D 49, 6920\u20136927 (1994). https:\/\/doi.org\/10.1103\/PhysRevD.49.6920","journal-title":"Phys. Rev. D"},{"key":"5201_CR46","unstructured":"Childs, A.M.: Lecture Notes on Quantum Algorithms. Institute for Advanced Computer Studies, and Joint Center for Quantum Information and Computer Science University of Maryland. (2025) Accessed 21 Jan 2026"},{"key":"5201_CR47","doi-asserted-by":"publisher","unstructured":"Raussendorf, R.: Putting Paradoxes to Work: Contextuality in Measurement-Based Quantum Computation. Presented at the (2023). https:\/\/doi.org\/10.1007\/978-3-031-24117-8","DOI":"10.1007\/978-3-031-24117-8"},{"key":"5201_CR48","unstructured":"Shahandeh, F.: Quantum computational advantage implies contextuality (2021). https:\/\/arxiv.org\/abs\/2112.00024"},{"issue":"11","key":"5201_CR49","doi-asserted-by":"publisher","first-page":"692","DOI":"10.1038\/s42254-022-00511-w","volume":"4","author":"E Tang","year":"2022","unstructured":"Tang, E.: Dequantizing algorithms to understand quantum advantage in machine learning. Nat. Rev. Phys. 4(11), 692\u2013693 (2022). https:\/\/doi.org\/10.1038\/s42254-022-00511-w","journal-title":"Nat. Rev. Phys."},{"key":"5201_CR50","doi-asserted-by":"publisher","first-page":"1","DOI":"10.4204\/eptcs.26.1","volume":"26","author":"AA Abbott","year":"2010","unstructured":"Abbott, A.A., Calude, C.S.: Understanding the quantum computational speed-up via de-quantisation. Electron. Proc. Theor. Comput. Sci. 26, 1\u201312 (2010). https:\/\/doi.org\/10.4204\/eptcs.26.1","journal-title":"Electron. Proc. Theor. Comput. Sci."},{"issue":"1","key":"5201_CR51","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1007\/BF01459088","volume":"99","author":"W Ackermann","year":"1928","unstructured":"Ackermann, W.: Zum hilbertschen aufbau der reellen zahlen. Math. Ann. 99(1), 118\u2013133 (1928). https:\/\/doi.org\/10.1007\/BF01459088","journal-title":"Math. Ann."},{"key":"5201_CR52","unstructured":"Kretschmer, W.: Quantum Pseudorandomness and Classical Complexity. In: Hsieh, M.-H. (ed.) 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021). Leibniz International Proceedings in Informatics (LIPIcs), vol. 197, pp. 2\u20131220. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2021). doi: 10.4230\/LIPIcs.TQC.2021.2"},{"key":"5201_CR53","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevD.105.114501","volume":"105","author":"MS Alam","year":"2022","unstructured":"Alam, M.S., Hadfield, S., Lamm, H., Li, A.C.Y.: Primitive quantum gates for dihedral gauge theories. Phys. Rev. D 105, 114501 (2022). https:\/\/doi.org\/10.1103\/PhysRevD.105.114501","journal-title":"Phys. Rev. D"},{"key":"5201_CR54","unstructured":"nLab authors: partial recursive function. https:\/\/ncatlab.org\/nlab\/show\/partial+recursive+function. Revision 21 (2025)"},{"key":"5201_CR55","volume-title":"Introduction to Metamathematics","author":"SC Kleene","year":"1952","unstructured":"Kleene, S.C.: Introduction to Metamathematics. P. Noordhoff N.V, Groningen (1952)"},{"key":"5201_CR56","volume-title":"An Introduction to G\u00f6del\u2019s Theorems","author":"P Smith","year":"2007","unstructured":"Smith, P.: An Introduction to G\u00f6del\u2019s Theorems. Cambridge University Press, New York (2007)"},{"key":"5201_CR57","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/j.tcs.2022.02.002","volume":"920","author":"Y Gurevich","year":"2022","unstructured":"Gurevich, Y., Blass, A.: Quantum circuits with classical channels and the principle of deferred measurements. Theoret. Comput. Sci. 920, 21\u201332 (2022). https:\/\/doi.org\/10.1016\/j.tcs.2022.02.002","journal-title":"Theoret. Comput. Sci."},{"key":"5201_CR58","doi-asserted-by":"crossref","unstructured":"Abramsky, S., Barbosa, R.S., Car\u00f9, G., Perdrix, S.: A complete characterization of all-versus-nothing arguments for stabilizer states. Philos. Trans. Royal Soc. A: Math., Phys. Eng. Sci. 375(2106), 20160385 (2017). doi: 10.1098\/rsta.2016.0385","DOI":"10.1098\/rsta.2016.0385"},{"key":"5201_CR59","unstructured":"Lamport, L.: Constructing digital signatures from a one way function. Technical Report CSL-98, Computer Science Labratory (October 1979). This paper was published by IEEE in the Proceedings of HICSS-43 in January, 2010. https:\/\/www.microsoft.com\/en-us\/research\/publication\/constructing-digital-signatures-one-way-function\/"},{"key":"5201_CR60","doi-asserted-by":"publisher","unstructured":"Yao, A.C.: Theory and application of trapdoor functions. In: 23rd Annual Symposium on Foundations of Computer Science (SFCS 1982), pp. 80\u201391. (1982). https:\/\/doi.org\/10.1109\/SFCS.1982.45","DOI":"10.1109\/SFCS.1982.45"},{"key":"5201_CR61","unstructured":"Brakerski, Z., Canetti, R., Qian, L.: On the Computational Hardness Needed for Quantum Cryptography. In: Tauman Kalai, Y. (ed.) 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), vol. 251, pp. 24\u201312421. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2023). doi: 10.4230\/LIPIcs.ITCS.2023.24"},{"key":"5201_CR62","doi-asserted-by":"publisher","unstructured":"Khurana, D., Tomer, K.: Commitments from quantum one-wayness. In: Proceedings of the 56th Annual ACM Symposium on Theory of Computing. STOC 2024, pp. 968\u2013978. Association for Computing Machinery, New York, NY, USA (2024). https:\/\/doi.org\/10.1145\/3618260.3649654","DOI":"10.1145\/3618260.3649654"},{"key":"5201_CR63","doi-asserted-by":"publisher","unstructured":"Chung, K.-M., Goldin, E., Gray, M.: On central primitives for quantum cryptography with classical communication. In: Advances in Cryptology - CRYPTO 2024: 44th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18\u201322, 2024, Proceedings, Part VII, pp. 215\u2013248. Springer, Berlin, Heidelberg (2024). https:\/\/doi.org\/10.1007\/978-3-031-68394-7_8","DOI":"10.1007\/978-3-031-68394-7_8"},{"key":"5201_CR64","doi-asserted-by":"crossref","unstructured":"Preskill, J.: Quantum Computing in the NISQ era and beyond. Quantum 2, 79 (2018). https:\/\/doi.org\/10.22331\/q-2018-08-06-79","DOI":"10.22331\/q-2018-08-06-79"},{"key":"5201_CR65","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.physrep.2022.08.003","volume":"986","author":"J Tilly","year":"2022","unstructured":"Tilly, J., Chen, H., Cao, S., Picozzi, D., Setia, K., Li, Y., Grant, E., Wossnig, L., Rungger, I., Booth, G.H., Tennyson, J.: The variational quantum eigensolver: a review of methods and best practices. Phys. Rep. 986, 1\u2013128 (2022). https:\/\/doi.org\/10.1016\/j.physrep.2022.08.003","journal-title":"Phys. Rep."},{"key":"5201_CR66","unstructured":"Terhal, B.M., DiVincenzo, D.P.: Adaptive quantum computation, constant depth quantum circuits and arthur-merlin games (2002). https:\/\/arxiv.org\/abs\/quant-ph\/0205133"},{"issue":"2","key":"5201_CR67","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1038\/s41567-018-0318-2","volume":"15","author":"A Bouland","year":"2018","unstructured":"Bouland, A., Fefferman, B., Nirkhe, C., Vazirani, U.: On the complexity and verification of quantum random circuit sampling. Nat. Phys. 15(2), 159\u2013163 (2018). https:\/\/doi.org\/10.1038\/s41567-018-0318-2","journal-title":"Nat. Phys."},{"issue":"2","key":"5201_CR68","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"LG Valiant","year":"1979","unstructured":"Valiant, L.G.: The complexity of computing the permanent. Theoret. Comput. Sci. 8(2), 189\u2013201 (1979). https:\/\/doi.org\/10.1016\/0304-3975(79)90044-6","journal-title":"Theoret. Comput. Sci."},{"key":"5201_CR69","doi-asserted-by":"publisher","unstructured":"Bouland, A., Fefferman, B., Landau, Z., Liu, Y.: Noise and the frontier of quantum supremacy. In: 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pp. 1308\u20131317. (2022). https:\/\/doi.org\/10.1109\/FOCS52979.2021.00127","DOI":"10.1109\/FOCS52979.2021.00127"},{"key":"5201_CR70","unstructured":"Fefferman, B.: On the theory of near-term quantum advantage. http:\/\/www.billfefferman.com\/wp-content\/uploads\/2023\/12\/lectures-pcmi-billfefferman.pdf. IAS\/Park City Mathematics Institute, Summer 2023 (2025)"},{"key":"5201_CR71","doi-asserted-by":"publisher","unstructured":"Aharonov, D., Gao, X., Landau, Z., Liu, Y., Vazirani, U.: A polynomial-time classical algorithm for noisy random circuit sampling. In: Proceedings of the 55th Annual ACM Symposium on Theory of Computing. STOC 2023, pp. 945\u2013957. Association for Computing Machinery, New York, NY, USA (2023). https:\/\/doi.org\/10.1145\/3564246.3585234","DOI":"10.1145\/3564246.3585234"},{"issue":"2","key":"5201_CR72","doi-asserted-by":"publisher","first-page":"1531","DOI":"10.1007\/s00220-023-04675-z","volume":"401","author":"AW Harrow","year":"2023","unstructured":"Harrow, A.W., Mehraban, S.: Approximate unitary t-designs by short random quantum circuits using nearest-neighbor and long-range gates. Commun. Math. Phys. 401(2), 1531\u20131626 (2023). https:\/\/doi.org\/10.1007\/s00220-023-04675-z","journal-title":"Commun. Math. Phys."},{"key":"5201_CR73","doi-asserted-by":"publisher","DOI":"10.1103\/PRXQuantum.3.010333","volume":"3","author":"AM Dalzell","year":"2022","unstructured":"Dalzell, A.M., Hunter-Jones, N., Brand\u00e3o, F.G.S.L.: Random quantum circuits anticoncentrate in log depth. PRX Quantum 3, 010333 (2022). https:\/\/doi.org\/10.1103\/PRXQuantum.3.010333","journal-title":"PRX Quantum"},{"issue":"7779","key":"5201_CR74","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1038\/s41586-019-1666-5","volume":"574","author":"F Arute","year":"2019","unstructured":"Arute, F., et al.: Quantum supremacy using a programmable superconducting processor. Nature 574(7779), 505\u2013510 (2019). https:\/\/doi.org\/10.1038\/s41586-019-1666-5. arXiv:1910.11333 [quant-ph]","journal-title":"Nature"},{"issue":"8033","key":"5201_CR75","doi-asserted-by":"publisher","first-page":"328","DOI":"10.1038\/s41586-024-07998-6","volume":"634","author":"A Morvan","year":"2024","unstructured":"Morvan, A., Villalonga, B., Mi, X., Mandr\u00e0, S., Bengtsson, A., Klimov, P.V., Chen, Z., Hong, S., Erickson, C., Drozdov, I.K., Chau, J., Laun, G., Movassagh, R., Asfaw, A., Brand\u00e3o, L.T.A.N., Peralta, R., Abanin, D., Acharya, R., Allen, R., Andersen, T.I., Anderson, K., Ansmann, M., Arute, F., Arya, K., Atalaya, J., Bardin, J.C., Bilmes, A., Bortoli, G., Bourassa, A., Bovaird, J., Brill, L., Broughton, M., Buckley, B.B., Buell, D.A., Burger, T., Burkett, B., Bushnell, N., Campero, J., Chang, H.-S., Chiaro, B., Chik, D., Chou, C., Cogan, J., Collins, R., Conner, P., Courtney, W., Crook, A.L., Curtin, B., Debroy, D.M., Barba, A.D.T., Demura, S., Paolo, A.D., Dunsworth, A., Faoro, L., Farhi, E., Fatemi, R., Ferreira, V.S., Burgos, L.F., Forati, E., Fowler, A.G., Foxen, B., Garcia, G., Genois, E., Giang, W., Gidney, C., Gilboa, D., Giustina, M., Gosula, R., Dau, A.G., Gross, J.A., Habegger, S., Hamilton, M.C., Hansen, M., Harrigan, M.P., Harrington, S.D., Heu, P., Hoffmann, M.R., Huang, T., Huff, A., Huggins, W.J., Ioffe, L.B., Isakov, S.V., Iveland, J., Jeffrey, E., Jiang, Z., Jones, C., Juhas, P., Kafri, D., Khattar, T., Khezri, M., Kieferov\u00e1, M., Kim, S., Kitaev, A., Klots, A.R., Korotkov, A.N., Kostritsa, F., Kreikebaum, J.M., Landhuis, D., Laptev, P., Lau, K.-M., Laws, L., Lee, J., Lee, K.W., Lensky, Y.D., Lester, B.J., Lill, A.T., Liu, W., Livingston, W.P., Locharla, A., Malone, F.D., Martin, O., Martin, S., McClean, J.R., McEwen, M., Miao, K.C., Mieszala, A., Montazeri, S., Mruczkiewicz, W., Naaman, O., Neeley, M., Neill, C., Nersisyan, A., Newman, M., Ng, J.H., Nguyen, A., Nguyen, M., Niu, M.Y., O\u2019Brien, T.E., Omonije, S., Opremcak, A., Petukhov, A., Potter, R., Pryadko, L.P., Quintana, C., Rhodes, D.M., Rocque, C., Rosenberg, E., Rubin, N.C., Saei, N., Sank, D., Sankaragomathi, K., Satzinger, K.J., Schurkus, H.F., Schuster, C., Shearn, M.J., Shorter, A., Shutty, N., Shvarts, V., Sivak, V., Skruzny, J., Smith, W.C., Somma, R.D., Sterling, G., Strain, D., Szalay, M., Thor, D., Torres, A., Vidal, G., Heidweiller, C.V., White, T., Woo, B.W.K., Xing, C., Yao, Z.J., Yeh, P., Yoo, J., Young, G., Zalcman, A., Zhang, Y., Zhu, N., Zobrist, N., Rieffel, E.G., Biswas, R., Babbush, R., Bacon, D., Hilton, J., Lucero, E., Neven, H., Megrant, A., Kelly, J., Roushan, P., Aleiner, I., Smelyanskiy, V., Kechedzhi, K., Chen, Y., Boixo, S.: Phase transitions in random circuit sampling. Nature 634(8033), 328\u2013333 (2024). https:\/\/doi.org\/10.1038\/s41586-024-07998-6","journal-title":"Nature"},{"issue":"8052","key":"5201_CR76","doi-asserted-by":"publisher","first-page":"920","DOI":"10.1038\/s41586-024-08449-y","volume":"638","author":"GQ Ai","year":"2025","unstructured":"Ai, G.Q.: Collaborators: quantum error correction below the surface code threshold. Nature 638(8052), 920\u2013926 (2025). https:\/\/doi.org\/10.1038\/s41586-024-08449-y","journal-title":"Nature"},{"issue":"8086","key":"5201_CR77","doi-asserted-by":"publisher","first-page":"825","DOI":"10.1038\/s41586-025-09526-6","volume":"646","author":"DA Abanin","year":"2025","unstructured":"Abanin, D.A., Acharya, R., Aghababaie-Beni, L., Aigeldinger, G., Ajoy, A., Alcaraz, R., Aleiner, I., Andersen, T.I., Ansmann, M., Arute, F., Arya, K., Asfaw, A., Astrakhantsev, N., Atalaya, J., Babbush, R., Bacon, D., Ballard, B., Bardin, J.C., Bengs, C., Bengtsson, A., Bilmes, A., Boixo, S., Bortoli, G., Bourassa, A., Bovaird, J., Bowers, D., Brill, L., Broughton, M., Browne, D.A., Buchea, B., Buckley, B.B., Buell, D.A., Burger, T., Burkett, B., Bushnell, N., Cabrera, A., Campero, J., Chang, H.-S., Chen, Y., Chen, Z., Chiaro, B., Chih, L.-Y., Chik, D., Chou, C., Claes, J., Cleland, A.Y., Cogan, J., Cohen, S., Collins, R., Conner, P., Courtney, W., Crook, A.L., Curtin, B., Das, S., De Lorenzo, L., Debroy, D.M., Demura, S., Devoret, M., Di Paolo, A., Donohoe, P., Drozdov, I., Dunsworth, A., Earle, C., Eickbusch, A., Elbag, A.M., Elzouka, M., Erickson, C., Faoro, L., Farhi, E., Ferreira, V.S., Burgos, L.F., Forati, E., Fowler, A.G., Foxen, B., Ganjam, S., Garcia, G., Gasca, R., Genois, \u00c9., Giang, W., Gidney, C., Gilboa, D., Gosula, R., Dau, A.G., Graumann, D., Greene, A., Gross, J.A., Gu, H., Habegger, S., Hall, J., Hamamura, I., Hamilton, M.C., Hansen, M., Harrigan, M.P., Harrington, S.D., Heslin, S., Heu, P., Higgott, O., Hill, G., Hilton, J., Hong, S., Huang, H.-Y., Huff, A., Huggins, W.J., Ioffe, L.B., Isakov, S.V., Iveland, J., Jeffrey, E., Jiang, Z., Jin, X., Jones, C., Jordan, S., Joshi, C., Juhas, P., Kabel, A., Kafri, D., Kang, H., Karamlou, A.H., Kechedzhi, K., Kelly, J., Khaire, T., Khattar, T., Khezri, M., Kim, S., King, R., Klimov, P.V., Klots, A.R., Kobrin, B., Korotkov, A.N., Kostritsa, F., Kothari, R., Kreikebaum, J.M., Kurilovich, V.D., Kyoseva, E., Landhuis, D., Lange-Dei, T., Langley, B.W., Laptev, P., Lau, K.-M., Le Guevel, L., Ledford, J., Lee, J., Lee, K., Lensky, Y.D., Leon, S., Lester, B.J., Li, W.Y., Lill, A.T., Liu, W., Livingston, W.P., Locharla, A., Lucero, E., Lundahl, D., Lunt, A., Madhuk, S., Malone, F.D., Maloney, A., Mandr\u00e0, S., Manyika, J.M., Martin, L.S., Martin, O., Martin, S., Matias, Y., Maxfield, C., McClean, J.R., McEwen, M., Meeks, S., Megrant, A., Mi, X., Miao, K.C., Mieszala, A., Minev, Z., Molavi, R., Molina, S., Montazeri, S., Morvan, A., Movassagh, R., Mruczkiewicz, W., Naaman, O., Neeley, M., Neill, C., Nersisyan, A., Neven, H., Newman, M., Ng, J.H., Nguyen, A., Nguyen, M., Ni, C.-H., Niu, M.Y., Oas, L., O\u2019Brien, T.E., Oliver, W.D., Opremcak, A., Ottosson, K., Petukhov, A., Pizzuto, A., Platt, J., Potter, R., Pritchard, O., Pryadko, L.P., Quintana, C., Ramachandran, G., Ramanathan, C., Reagor, M.J., Redding, J., Rhodes, D.M., Roberts, G., Rosenberg, E., Rosenfeld, E., Roushan, P., Rubin, N.C., Saei, N., Sank, D., Sankaragomathi, K., Satzinger, K.J., Schmidhuber, A., Schurkus, H.F., Schuster, C., Schuster, T., Shearn, M.J., Shorter, A., Shutty, N., Shvarts, V., Sivak, V., Skruzny, J., Small, S., Smelyanskiy, V., Smith, W.C., Somma, R.D., Springer, S., Sterling, G., Strain, D., Suchard, J., Suchsland, P., Szasz, A., Sztein, A., Thor, D., Tomita, E., Torres, A., Torunbalci, M.M., Vaishnav, A., Vargas, J., Vdovichev, S., Vidal, G., Villalonga, B., Heidweiller, C.V., Waltman, S., Wang, S.X., Ware, B., Weber, K., Weidel, T., Westerhout, T., White, T., Wong, K., Woo, B.W.K., Xing, C., Yao, Z.J., Yeh, P., Ying, B., Yoo, J., Yosri, N., Young, G., Zalcman, A., Zhang, C., Zhang, Y., Zhu, N., Zobrist, N., Ai, G.Q.: Collaborators: observation of constructive interference at the edge of quantum ergodicity. Nature 646(8086), 825\u2013830 (2025). https:\/\/doi.org\/10.1038\/s41586-025-09526-6","journal-title":"Nature"},{"issue":"1","key":"5201_CR78","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/j.amc.2011.06.057","volume":"219","author":"AA Abbott","year":"2012","unstructured":"Abbott, A.A.: De-quantisation of the quantum Fourier transform. Appl. Math. Comput. 219(1), 3\u201313 (2012). https:\/\/doi.org\/10.1016\/j.amc.2011.06.057","journal-title":"Appl. Math. Comput."},{"issue":"11","key":"5201_CR79","doi-asserted-by":"publisher","first-page":"8","DOI":"10.1145\/3623641","volume":"66","author":"D Monroe","year":"2023","unstructured":"Monroe, D.: Quantum speedup for the fast Fourier transform? Commun. ACM 66(11), 8\u201310 (2023). https:\/\/doi.org\/10.1145\/3623641","journal-title":"Commun. ACM"},{"issue":"05","key":"5201_CR80","doi-asserted-by":"publisher","first-page":"797","DOI":"10.1142\/s0129054103002035","volume":"14","author":"P Jorrand","year":"2003","unstructured":"Jorrand, P., Mhalla, M.: Separability of pure n-qubit states: two characterizations. Int. J. Found. Comput. Sci. 14(05), 797\u2013814 (2003). https:\/\/doi.org\/10.1142\/s0129054103002035","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"1","key":"5201_CR81","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/s11047-011-9276-7","volume":"11","author":"AA Abbott","year":"2012","unstructured":"Abbott, A.A.: The Deutsch-Jozsa problem: de-quantisation and entanglement. Nat. Comput. 11(1), 3\u201311 (2012). https:\/\/doi.org\/10.1007\/s11047-011-9276-7","journal-title":"Nat. Comput."},{"key":"5201_CR82","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.64.022319","volume":"64","author":"G Ortiz","year":"2001","unstructured":"Ortiz, G., Gubernatis, J.E., Knill, E., Laflamme, R.: Quantum algorithms for fermionic simulations. Phys. Rev. A 64, 022319 (2001). https:\/\/doi.org\/10.1103\/PhysRevA.64.022319","journal-title":"Phys. Rev. A"},{"issue":"22","key":"5201_CR83","doi-asserted-by":"publisher","DOI":"10.1063\/1.4768229","volume":"137","author":"JT Seeley","year":"2012","unstructured":"Seeley, J.T., Richard, M.J., Love, P.J.: The Bravyi-Kitaev transformation for quantum computation of electronic structure. J. Chem. Phys. 137(22), 224109 (2012). https:\/\/doi.org\/10.1063\/1.4768229","journal-title":"J. Chem. Phys."},{"issue":"5","key":"5201_CR84","doi-asserted-by":"publisher","first-page":"735","DOI":"10.1080\/00268976.2011.552441","volume":"109","author":"JD Whitfield","year":"2011","unstructured":"Whitfield, J.D., Biamonte, J., Aspuru-Guzik, A.: Simulation of electronic structure Hamiltonians using quantum computers. Mol. Phys. 109(5), 735\u2013750 (2011). https:\/\/doi.org\/10.1080\/00268976.2011.552441","journal-title":"Mol. Phys."},{"key":"5201_CR85","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2020.104605","volume":"275","author":"D Qiu","year":"2020","unstructured":"Qiu, D., Zheng, S.: Revisiting Deutsch-Jozsa algorithm. Inf. Comput. 275, 104605 (2020). https:\/\/doi.org\/10.1016\/j.ic.2020.104605","journal-title":"Inf. Comput."},{"key":"5201_CR86","doi-asserted-by":"crossref","unstructured":"Low, G.H., Chuang, I.L.: Hamiltonian Simulation by Qubitization. Quantum 3, 163 (2019). https:\/\/doi.org\/10.22331\/q-2019-07-12-163","DOI":"10.22331\/q-2019-07-12-163"},{"key":"5201_CR87","doi-asserted-by":"publisher","unstructured":"Gily\u00e9n, A., Su, Y., Low, G.H., Wiebe, N.: Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics. In: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. STOC 2019, pp. 193\u2013204. Association for Computing Machinery, New York, NY, USA (2019). https:\/\/doi.org\/10.1145\/3313276.3316366","DOI":"10.1145\/3313276.3316366"},{"key":"5201_CR88","unstructured":"Tang, E.: Quantum Machine Learning Without Any Quantum. PhD thesis, U. Washington, Seattle (main) (2023)"},{"key":"5201_CR89","doi-asserted-by":"publisher","unstructured":"Gharibian, S., Le Gall, F.: Dequantizing the quantum singular value transformation: hardness and applications to quantum chemistry and the quantum pcp conjecture. In: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing. STOC 2022, pp. 19\u201332. Association for Computing Machinery, New York, NY, USA (2022). https:\/\/doi.org\/10.1145\/3519935.3519991","DOI":"10.1145\/3519935.3519991"},{"issue":"1","key":"5201_CR90","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1007\/s00037-024-00262-3","volume":"34","author":"F Le Gall","year":"2025","unstructured":"Le Gall, F.: Robust dequantization of the quantum singular value transformation and quantum machine learning algorithms. Comput. Complex. 34(1), 2 (2025). https:\/\/doi.org\/10.1007\/s00037-024-00262-3","journal-title":"Comput. Complex."},{"key":"5201_CR91","unstructured":"Phillipson, F.: Fair Benchmarking of Optimisation Applications (2025). https:\/\/arxiv.org\/abs\/2512.07915"},{"key":"5201_CR92","unstructured":"King, A.D., Nocera, A., Rams, M.M., Dziarmaga, J., Wiersema, R., Bernoudy, W., Raymond, J., Kaushal, N., Heinsdorf, N., Harris, R., Boothby, K., Altomare, F., Berkley, A.J., Boschnak, M., Chern, K., Christiani, H., Cibere, S., Connor, J., Dehn, M.H., Deshpande, R., Ejtemaee, S., Farr\u00e9, P., Hamer, K., Hoskinson, E., Huang, S., Johnson, M.W., Kortas, S., Ladizinsky, E., Lai, T., Lanting, T., Li, R., MacDonald, A.J.R., Marsden, G., McGeoch, C.C., Molavi, R., Neufeld, R., Norouzpour, M., Oh, T., Pasvolsky, J., Poitras, P., Poulin-Lamarre, G., Prescott, T., Reis, M., Rich, C., Samani, M., Sheldan, B., Smirnov, A., Sterpka, E., Clavera, B.T., Tsai, N., Volkmann, M., Whiticar, A., Whittaker, J.D., Wilkinson, W., Yao, J., Yi, T.J., Sandvik, A.W., Alvarez, G., Melko, R.G., Carrasquilla, J., Franz, M., Amin, M.H.: Computational supremacy in quantum simulation (2024). https:\/\/arxiv.org\/abs\/2403.00910"},{"key":"5201_CR93","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1109\/TQE.2021.3090207","volume":"2","author":"S Martiel","year":"2021","unstructured":"Martiel, S., Ayral, T., Allouche, C.: Benchmarking quantum coprocessors in an application-centric, hardware-agnostic, and scalable way. IEEE Trans. Quantum Eng. 2, 1\u201311 (2021). https:\/\/doi.org\/10.1109\/TQE.2021.3090207","journal-title":"IEEE Trans. Quantum Eng."},{"key":"5201_CR94","doi-asserted-by":"publisher","unstructured":"Fin\u017egar, J.R., Ross, P., H\u00f6lscher, L., Klepsch, J., Luckow, A.: Quark: A framework for quantum computing application benchmarking. In: 2022 IEEE International Conference on Quantum Computing and Engineering (QCE), pp. 226\u2013237. (2022). https:\/\/doi.org\/10.1109\/QCE53715.2022.00042","DOI":"10.1109\/QCE53715.2022.00042"},{"key":"5201_CR95","unstructured":"Barbaresco, F., Rioux, L., Labreuche, C., Nowak, M., Olivier, N., Nicolazic, D., Hess, O., Guilmin, A.-L., Wang, R., Sassolas, T., Louise, S., Snizhko, K., Misguich, G., Auff\u00e8ves, A., Whitney, R., Vergnaud, E., Schopfer, F.: Bacq - application-oriented benchmarks for quantum computing (2024). https:\/\/arxiv.org\/abs\/2403.12205"},{"key":"5201_CR96","doi-asserted-by":"crossref","unstructured":"Sawaya, N.P., Marti-Dafcik, D., Ho, Y., Tabor, D.P., Neira, D.E.B., Magann, A.B., Premaratne, S., Dubey, P., Matsuura, A., Bishop, N., Jong, W.A.D., Benjamin, S., Parekh, O., Tubman, N., Klymko, K., Camps, D.: HamLib: a library of Hamiltonians for benchmarking quantum algorithms and hardware. Quantum 8, 1559 (2024). https:\/\/doi.org\/10.22331\/q-2024-12-11-1559","DOI":"10.22331\/q-2024-12-11-1559"},{"key":"5201_CR97","doi-asserted-by":"publisher","unstructured":"Gilbert, V., Rodriguez, J., Louise, S.: Benchmarking quantum annealers with near-optimal minor-embedded instances. In: 2024 IEEE International Conference on Quantum Computing and Engineering (QCE), vol. 01, pp. 531\u2013537. (2024). https:\/\/doi.org\/10.1109\/QCE60285.2024.00068","DOI":"10.1109\/QCE60285.2024.00068"},{"key":"5201_CR98","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.97.062111","volume":"97","author":"P Arrighi","year":"2018","unstructured":"Arrighi, P., Di Molfetta, G., M\u00e1rquez-Mart\u00edn, I., P\u00e9rez, A.: Dirac equation as a quantum walk over the honeycomb and triangular lattices. Phys. Rev. A 97, 062111 (2018). https:\/\/doi.org\/10.1103\/PhysRevA.97.062111","journal-title":"Phys. Rev. A"},{"key":"5201_CR99","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.110.042418","volume":"110","author":"U Nzongani","year":"2024","unstructured":"Nzongani, U., Eon, N., M\u00e1rquez-Mart\u00edn, I., P\u00e9rez, A., Di Molfetta, G., Arrighi, P.: Dirac quantum walk on tetrahedra. Phys. Rev. A 110, 042418 (2024). https:\/\/doi.org\/10.1103\/PhysRevA.110.042418","journal-title":"Phys. Rev. A"},{"key":"5201_CR100","doi-asserted-by":"publisher","unstructured":"Yamakawa, T., Zhandry, M.: Verifiable quantum advantage without structure. In: 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pp. 69\u201374. (2022). https:\/\/doi.org\/10.1109\/FOCS54457.2022.00014","DOI":"10.1109\/FOCS54457.2022.00014"},{"key":"5201_CR101","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.93.012111","volume":"93","author":"M Hillery","year":"2016","unstructured":"Hillery, M.: Coherence as a resource in decision problems: the Deutsch-Jozsa algorithm and a variation. Phys. Rev. A 93, 012111 (2016). https:\/\/doi.org\/10.1103\/PhysRevA.93.012111","journal-title":"Phys. Rev. A"},{"key":"5201_CR102","doi-asserted-by":"publisher","first-page":"1633","DOI":"10.1103\/PhysRevA.58.R1633","volume":"58","author":"D Collins","year":"1998","unstructured":"Collins, D., Kim, K.W., Holton, W.C.: Deutsch-Jozsa algorithm as a test of quantum computation. Phys. Rev. A 58, 1633\u20131636 (1998). https:\/\/doi.org\/10.1103\/PhysRevA.58.R1633","journal-title":"Phys. Rev. A"},{"key":"5201_CR103","doi-asserted-by":"publisher","DOI":"10.1016\/j.future.2024.107480","volume":"162","author":"V Gheorghiu","year":"2025","unstructured":"Gheorghiu, V., Mosca, M.: Quantum resource estimation for large scale quantum algorithms. Futur. Gener. Comput. Syst. 162, 107480 (2025). https:\/\/doi.org\/10.1016\/j.future.2024.107480","journal-title":"Futur. Gener. Comput. Syst."},{"key":"5201_CR104","doi-asserted-by":"publisher","unstructured":"Jordan, S.P., Shutty, N., Wootters, M., Zalcman, A., Schmidhuber, A., King, R., Isakov, S.V., Babbush, R.: Optimization by decoded quantum interferometry. Nature 646(8086), 831\u2013836, (2025). https:\/\/doi.org\/10.1038\/s41586-025-09527-5","DOI":"10.1038\/s41586-025-09527-5"},{"key":"5201_CR105","doi-asserted-by":"crossref","unstructured":"S\u00fcnderhauf, C., Campbell, E., Camps, J.: Block-encoding structured matrices for data input in quantum computing. Quantum 8, 1226 (2024). https:\/\/doi.org\/10.22331\/q-2024-01-11-1226","DOI":"10.22331\/q-2024-01-11-1226"},{"key":"5201_CR106","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1109\/tqe.2022.3231194","volume":"3","author":"BD Clader","year":"2022","unstructured":"Clader, B.D., Dalzell, A.M., Stamatopoulos, N., Salton, G., Berta, M., Zeng, W.J.: Quantum resources required to block-encode a matrix of classical data. IEEE Trans. Quantum Eng. 3, 1\u201323 (2022). https:\/\/doi.org\/10.1109\/tqe.2022.3231194","journal-title":"IEEE Trans. Quantum Eng."},{"key":"5201_CR107","unstructured":"Harrigan, M.P., Khattar, T., Yuan, C., Peduri, A., Yosri, N., Malone, F.D., Babbush, R., Rubin, N.C.: Expressing and Analyzing Quantum Algorithms with Qualtran (2024). https:\/\/arxiv.org\/abs\/2409.04643"},{"key":"5201_CR108","doi-asserted-by":"crossref","unstructured":"Rall, P.: Faster Coherent Quantum Algorithms for Phase, Energy, and Amplitude Estimation. Quantum 5, 566 (2021). https:\/\/doi.org\/10.22331\/q-2021-10-19-566","DOI":"10.22331\/q-2021-10-19-566"},{"key":"5201_CR109","unstructured":"Tang, E., Wright, J.: Amplitude amplification and estimation require inverses (2025). https:\/\/arxiv.org\/abs\/2507.23787"},{"key":"5201_CR110","doi-asserted-by":"crossref","unstructured":"Degen, C.L., Reinhard, F., Cappellaro, P.: Quantum sensing. Rev. Mod. Phys. 89(3), (2017). https:\/\/doi.org\/10.1103\/revmodphys.89.035002","DOI":"10.1103\/RevModPhys.89.035002"},{"issue":"42","key":"5201_CR111","doi-asserted-by":"publisher","DOI":"10.1088\/1751-8113\/47\/42\/424006","volume":"47","author":"G T\u00f3th","year":"2014","unstructured":"T\u00f3th, G., Apellaniz, I.: Quantum metrology from a quantum information science perspective. J. Phys. A: Math. Theor. 47(42), 424006 (2014). https:\/\/doi.org\/10.1088\/1751-8113\/47\/42\/424006","journal-title":"J. Phys. A: Math. Theor."},{"key":"5201_CR112","doi-asserted-by":"crossref","unstructured":"Silva, M.P., Landon-Cardinal, O., Poulin, D.: Practical characterization of quantum devices without tomography. Phys. Rev. Lett. 107(21), (2011). https:\/\/doi.org\/10.1103\/physrevlett.107.210404","DOI":"10.1103\/PhysRevLett.107.210404"},{"key":"5201_CR113","unstructured":"Certo, S., Pham, A.D., Beaulieu, D.: Benchmarking Amplitude Estimation on a Superconducting Quantum Computer (2022). https:\/\/arxiv.org\/abs\/2201.06987"},{"key":"5201_CR114","doi-asserted-by":"publisher","unstructured":"Jong, J., Hoek, C.R.: The significance of the quantum volume for other algorithms: A case study for quantum amplitude estimation. In: Computational Science - ICCS 2024: 24th International Conference, Malaga, Spain, July 2\u20134, 2024, Proceedings, Part VI, pp. 221\u2013234. Springer, Berlin, Heidelberg (2024). https:\/\/doi.org\/10.1007\/978-3-031-63778-0_16","DOI":"10.1007\/978-3-031-63778-0_16"},{"key":"5201_CR115","unstructured":"Omanakuttan, S., He, Z., Zhang, Z., Hao, T., Babakhani, A., Boulebnane, S., Chakrabarti, S., Herman, D., Sullivan, J., Perlin, M.A., Shaydulin, R., Pistoia, M.: Threshold for Fault-tolerant Quantum Advantage with the Quantum Approximate Optimization Algorithm (2025). https:\/\/arxiv.org\/abs\/2504.01897"}],"container-title":["Quantum Information Processing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-026-05201-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11128-026-05201-5","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-026-05201-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,7,17]],"date-time":"2026-07-17T10:50:43Z","timestamp":1784285443000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11128-026-05201-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5,18]]},"references-count":115,"journal-issue":{"issue":"6","published-online":{"date-parts":[[2026,6]]}},"alternative-id":["5201"],"URL":"https:\/\/doi.org\/10.1007\/s11128-026-05201-5","relation":{},"ISSN":["1573-1332"],"issn-type":[{"value":"1573-1332","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,5,18]]},"assertion":[{"value":"31 March 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 April 2026","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 May 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"The authors declare no conflict of interest.","order":1,"name":"Ethics","label":"Conflict of interest","group":{"name":"EthicsHeading","label":"Declarations"}}],"article-number":"181"}}