{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,24]],"date-time":"2026-03-24T01:16:01Z","timestamp":1774314961899,"version":"3.50.1"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2026,2,7]],"date-time":"2026-02-07T00:00:00Z","timestamp":1770422400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,2,7]],"date-time":"2026-02-07T00:00:00Z","timestamp":1770422400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Quantum Inf Process"],"DOI":"10.1007\/s11128-026-05074-8","type":"journal-article","created":{"date-parts":[[2026,2,7]],"date-time":"2026-02-07T06:10:03Z","timestamp":1770444603000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Quantum approximation optimization algorithm for the trellis-based viterbi decoding of classical error-correcting codes"],"prefix":"10.1007","volume":"25","author":[{"given":"Mainak","family":"Bhattacharyya","sequence":"first","affiliation":[]},{"given":"Ankur","family":"Raina","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2026,2,7]]},"reference":[{"issue":"7","key":"5074_CR1","doi-asserted-by":"publisher","first-page":"2249","DOI":"10.1109\/TIT.2005.850102","volume":"51","author":"V Guruswami","year":"2005","unstructured":"Guruswami, V., Vardy, A.: Maximum-likelihood decoding of Reed\u2013Solomon codes is np-hard. IEEE Trans. Inf. Theory 51(7), 2249\u20132256 (2005). https:\/\/doi.org\/10.1109\/TIT.2005.850102","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"3","key":"5074_CR2","doi-asserted-by":"publisher","first-page":"384","DOI":"10.1109\/TIT.1978.1055873","volume":"24","author":"E Berlekamp","year":"1978","unstructured":"Berlekamp, E., McEliece, R., Van Tilborg, H.: On the inherent intractability of certain coding problems (Corresp.). IEEE Trans. Inf. Theory 24(3), 384\u2013386 (1978). https:\/\/doi.org\/10.1109\/TIT.1978.1055873","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"2","key":"5074_CR3","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1109\/18.52484","volume":"36","author":"J Bruck","year":"1990","unstructured":"Bruck, J., Naor, M.: The hardness of decoding linear codes with preprocessing. IEEE Trans. Inf. Theory 36(2), 381\u2013385 (1990). https:\/\/doi.org\/10.1109\/18.52484","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"1907","key":"5074_CR4","doi-asserted-by":"publisher","first-page":"553","DOI":"10.1098\/rspa.1992.0167","volume":"439","author":"D Deutsch","year":"1992","unstructured":"Deutsch, D., Jozsa, R.: Rapid solution of problems by quantum computation. Proc. R. Soc. Lond. Ser. A: Math. Phys. Sci. 439(1907), 553\u2013558 (1992). https:\/\/doi.org\/10.1098\/rspa.1992.0167","journal-title":"Proc. R. Soc. Lond. Ser. A: Math. Phys. Sci."},{"key":"5074_CR5","doi-asserted-by":"publisher","unstructured":"Bernstein, E., Vazirani, U.: Quantum complexity theory. In: Proceedings of the Twenty-fifth Annual ACM Symposium on Theory of Computing, pp 11\u201320 (1993). https:\/\/doi.org\/10.1145\/167088.167097","DOI":"10.1145\/167088.167097"},{"issue":"5","key":"5074_CR6","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":"5074_CR7","doi-asserted-by":"publisher","unstructured":"Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, pp. 212\u2013219 (1996). https:\/\/doi.org\/10.1145\/237814.237866","DOI":"10.1145\/237814.237866"},{"key":"5074_CR8","doi-asserted-by":"publisher","unstructured":"Jung, H., Kang, J., Ha, J.: Quantum maximum likelihood decoding for linear block codes. In: 2020 International Conference on Information and Communication Technology Convergence (ICTC). IEEE, pp. 227\u2013232 (2020). https:\/\/doi.org\/10.1109\/ICTC49870.2020.9289350","DOI":"10.1109\/ICTC49870.2020.9289350"},{"key":"5074_CR9","doi-asserted-by":"publisher","unstructured":"Bhattacharyya, M., Raina, A.: A quantum algorithm for syndrome decoding of classical error-correcting linear block codes. In: 2022 IEEE\/ACM 7th Symposium on Edge Computing (SEC). IEEE, pp. 456\u2013461 (2022). https:\/\/doi.org\/10.1109\/SEC54971.2022.00069","DOI":"10.1109\/SEC54971.2022.00069"},{"key":"5074_CR10","doi-asserted-by":"publisher","unstructured":"Durr, C., Hoyer, P.: A quantum algorithm for finding the minimum. arXiv preprint quant-ph\/9607014 (1996). https:\/\/doi.org\/10.48550\/arXiv.quant-ph\/9607014","DOI":"10.48550\/arXiv.quant-ph\/9607014"},{"key":"5074_CR11","doi-asserted-by":"publisher","first-page":"79","DOI":"10.22331\/q-2018-08-06-79","volume":"2","author":"J Preskill","year":"2018","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","journal-title":"Quantum"},{"issue":"1","key":"5074_CR12","doi-asserted-by":"publisher","DOI":"10.1103\/RevModPhys.94.015004","volume":"94","author":"K Bharti","year":"2022","unstructured":"Bharti, K., Cervera-Lierta, A., Kyaw, T.H., Haug, T., Alperin-Lea, S., Anand, A., Degroote, M., Heimonen, H., Kottmann, J.S., Menke, T., et al.: Noisy intermediate-scale quantum algorithms. Rev. Mod. Phys. 94(1), 015004 (2022). https:\/\/doi.org\/10.1103\/RevModPhys.94.015004","journal-title":"Rev. Mod. Phys."},{"issue":"2","key":"5074_CR13","doi-asserted-by":"publisher","DOI":"10.1088\/1367-2630\/18\/2\/023023","volume":"18","author":"JR McClean","year":"2016","unstructured":"McClean, J.R., Romero, J., Babbush, R., Aspuru-Guzik, A.: The theory of variational hybrid quantum-classical algorithms. New J. Phys. 18(2), 023023 (2016). https:\/\/doi.org\/10.1088\/1367-2630\/18\/2\/023023","journal-title":"New J. Phys."},{"issue":"9","key":"5074_CR14","doi-asserted-by":"publisher","first-page":"625","DOI":"10.1038\/s42254-021-00348-9","volume":"3","author":"M Cerezo","year":"2021","unstructured":"Cerezo, M., Arrasmith, A., Babbush, R., Benjamin, S.C., Endo, S., Fujii, K., McClean, J.R., Mitarai, K., Yuan, X., Cincio, L., et al.: Variational quantum algorithms. Nat. Rev. Phys. 3(9), 625\u2013644 (2021). https:\/\/doi.org\/10.1038\/s42254-021-00348-9","journal-title":"Nat. Rev. Phys."},{"issue":"1","key":"5074_CR15","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.106.010101","volume":"106","author":"A Callison","year":"2022","unstructured":"Callison, A., Chancellor, N.: Hybrid quantum-classical algorithms in the noisy intermediate-scale quantum era and beyond. Phys. Rev. A 106(1), 010101 (2022). https:\/\/doi.org\/10.1103\/PhysRevA.106.010101","journal-title":"Phys. Rev. A"},{"key":"5074_CR16","doi-asserted-by":"publisher","unstructured":"Farhi, E., Goldstone, J., Gutmann, S.: A quantum approximate optimization algorithm. arXiv preprint arXiv:1411.4028 (2014). https:\/\/doi.org\/10.48550\/arXiv.1411.4028","DOI":"10.48550\/arXiv.1411.4028"},{"issue":"3","key":"5074_CR17","doi-asserted-by":"publisher","first-page":"1237","DOI":"10.32604\/cmc.2020.010001","volume":"63","author":"Y Ruan","year":"2020","unstructured":"Ruan, Y., Marsh, S., Xue, X., Liu, Z., Wang, J., et al.: The quantum approximate algorithm for solving traveling salesman problem. Comput. Mater. Contin. 63(3), 1237\u20131247 (2020). https:\/\/doi.org\/10.32604\/cmc.2020.010001","journal-title":"Comput. Mater. Contin."},{"key":"5074_CR18","doi-asserted-by":"publisher","unstructured":"Awasthi, A., B\u00e4r, F., Doetsch, J., Ehm, H., Erdmann, M., Hess, M., Klepsch, J., Limacher, P.A., Luckow, A., Niedermeier, C., et al: Quantum computing techniques for multi-knapsack problems. In: Science and Information Conference, Springer, Berlin, pp. 264\u2013284 (2023). https:\/\/doi.org\/10.1007\/978-3-031-37963-5_19","DOI":"10.1007\/978-3-031-37963-5_19"},{"issue":"1","key":"5074_CR19","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1140\/epjqt\/s40507-022-00131-4","volume":"9","author":"C Moussa","year":"2022","unstructured":"Moussa, C., Wang, H., B\u00e4ck, T., Dunjko, V.: Unsupervised strategies for identifying optimal parameters in quantum approximate optimization algorithm. EPJ Quantum Technol. 9(1), 11 (2022). https:\/\/doi.org\/10.1140\/epjqt\/s40507-022-00131-4","journal-title":"EPJ Quantum Technol."},{"issue":"1","key":"5074_CR20","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.104.012403","volume":"104","author":"M Streif","year":"2021","unstructured":"Streif, M., Yarkoni, S., Skolik, A., Neukart, F., Leib, M.: Beating classical heuristics for the binary paint shop problem with the quantum approximate optimization algorithm. Phys. Rev. A 104(1), 012403 (2021). https:\/\/doi.org\/10.1103\/PhysRevA.104.012403","journal-title":"Phys. Rev. A"},{"issue":"4","key":"5074_CR21","doi-asserted-by":"publisher","first-page":"031","DOI":"10.48550\/arXiv.2006.15438","volume":"4","author":"A Borle","year":"2021","unstructured":"Borle, A., Elfving, V., Lomonaco, S.J.: Quantum approximate optimization for hard problems in linear algebra. SciPost Phys. Core 4(4), 031 (2021). https:\/\/doi.org\/10.48550\/arXiv.2006.15438","journal-title":"SciPost Phys. Core"},{"issue":"3","key":"5074_CR22","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevApplied.14.034009","volume":"14","author":"P Vikst\u00e5l","year":"2020","unstructured":"Vikst\u00e5l, P., Gr\u00f6nkvist, M., Svensson, M., Andersson, M., Johansson, G., Ferrini, G.: Applying the quantum approximate optimization algorithm to the tail-assignment problem. Phys. Rev. Appl. 14(3), 034009 (2020). https:\/\/doi.org\/10.1103\/PhysRevApplied.14.034009","journal-title":"Phys. Rev. Appl."},{"key":"5074_CR23","doi-asserted-by":"publisher","unstructured":"Farhi, E., Harrow, A.W.: Quantum supremacy through the quantum approximate optimization algorithm. arXiv preprint arXiv:1602.07674 (2016). https:\/\/doi.org\/10.48550\/arXiv.1602.07674","DOI":"10.48550\/arXiv.1602.07674"},{"key":"5074_CR24","doi-asserted-by":"publisher","unstructured":"Matsumine, T., Koike-Akino, T., Wang, Y.: Channel decoding with quantum approximate optimization algorithm. In: 2019 IEEE International Symposium on Information Theory (ISIT). IEEE, pp. 2574\u20132578 (2019). https:\/\/doi.org\/10.1109\/ISIT.2019.8849710","DOI":"10.1109\/ISIT.2019.8849710"},{"issue":"7","key":"5074_CR25","doi-asserted-by":"publisher","first-page":"2307","DOI":"10.1007\/s11128-015-1003-3","volume":"14","author":"JR Grice","year":"2015","unstructured":"Grice, J.R., Meyer, D.A.: A quantum algorithm for viterbi decoding of classical convolutional codes. Quantum Inf. Process. 14(7), 2307\u20132321 (2015). https:\/\/doi.org\/10.1007\/s11128-015-1003-3","journal-title":"Quantum Inf. Process."},{"issue":"1","key":"5074_CR26","doi-asserted-by":"publisher","first-page":"1791","DOI":"10.1038\/s41467-021-21728-w","volume":"12","author":"M Cerezo","year":"2021","unstructured":"Cerezo, M., Sone, A., Volkoff, T., Cincio, L., Coles, P.J.: Cost function dependent barren plateaus in shallow parametrized quantum circuits. Nat. Commun. 12(1), 1791 (2021). https:\/\/doi.org\/10.1038\/s41467-021-21728-w","journal-title":"Nat. Commun."},{"issue":"12","key":"5074_CR27","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.127.120502","volume":"127","author":"L Bittel","year":"2021","unstructured":"Bittel, L., Kliesch, M.: Training variational quantum algorithms is np-hard. Phys. Rev. Lett. 127(12), 120502 (2021). https:\/\/doi.org\/10.1103\/PhysRevLett.127.120502","journal-title":"Phys. Rev. Lett."},{"key":"5074_CR28","doi-asserted-by":"publisher","unstructured":"Lee, X., Saito, Y., Cai, D., Asai, N.: Parameters fixing strategy for quantum approximate optimization algorithm. In: 2021 IEEE International Conference on Quantum Computing and Engineering (QCE), pp. 10\u201316 (2021). https:\/\/doi.org\/10.1109\/QCE52317.2021.00016 . IEEE","DOI":"10.1109\/QCE52317.2021.00016"},{"key":"5074_CR29","unstructured":"Crooks, G.E.: Performance of the quantum approximate optimization algorithm on the maximum cut problem. arXiv preprint arXiv:1811.08419 (2018)"},{"key":"5074_CR30","doi-asserted-by":"crossref","unstructured":"Blekos, K., Brand, D., Ceschini, A., Chou, C.-H., Li, R.-H., Pandya, K., Summer, A.: A review on quantum approximate optimization algorithm and its variants. arXiv preprint arXiv:2306.09198 (2023)","DOI":"10.1016\/j.physrep.2024.03.002"},{"issue":"2","key":"5074_CR31","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3498331","volume":"3","author":"D An","year":"2022","unstructured":"An, D., Lin, L.: Quantum linear system solver based on time-optimal adiabatic quantum computing and quantum approximate optimization algorithm. ACM Trans. Quantum Comput. 3(2), 1\u201328 (2022). https:\/\/doi.org\/10.1145\/3498331","journal-title":"ACM Trans. Quantum Comput."},{"key":"5074_CR32","doi-asserted-by":"publisher","DOI":"10.1016\/j.asoc.2022.108554","volume":"118","author":"Y Zhang","year":"2022","unstructured":"Zhang, Y., Mu, X., Liu, X.-W., Wang, X., Zhang, X., Li, K., Wu, T., Zhao, D., Dong, C.: Applying the quantum approximate optimization algorithm to the minimum vertex cover problem. Appl. Soft Comput. 118, 108554 (2022). https:\/\/doi.org\/10.1016\/j.asoc.2022.108554","journal-title":"Appl. Soft Comput."},{"issue":"6","key":"5074_CR33","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.95.062317","volume":"95","author":"Z Jiang","year":"2017","unstructured":"Jiang, Z., Rieffel, E.G., Wang, Z.: Near-optimal quantum circuit for Grover\u2019s unstructured search using a transverse field. Phys. Rev. A 95(6), 062317 (2017). https:\/\/doi.org\/10.1103\/PhysRevA.95.062317","journal-title":"Phys. Rev. A"},{"key":"5074_CR34","doi-asserted-by":"publisher","unstructured":"Golden, J., B\u00e4rtschi, A., Eidenbenz, S., O\u2019Malley, D.: Evidence for super-polynomial advantage of QAOA over unstructured search. arXiv preprint arXiv:2202.00648 (2022). https:\/\/doi.org\/10.1109\/QCE57702.2023.00063","DOI":"10.1109\/QCE57702.2023.00063"},{"issue":"2","key":"5074_CR35","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1109\/TIT.1967.1054010","volume":"13","author":"A Viterbi","year":"1967","unstructured":"Viterbi, A.: Error bounds for convolutional codes and an asymptotically optimum decoding algorithm. IEEE Trans. Inf. Theory 13(2), 260\u2013269 (1967). https:\/\/doi.org\/10.1109\/TIT.1967.1054010","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"3","key":"5074_CR36","doi-asserted-by":"publisher","first-page":"268","DOI":"10.1109\/PROC.1973.9030","volume":"61","author":"GD Forney","year":"1973","unstructured":"Forney, G.D.: The Viterbi algorithm. Proc. IEEE 61(3), 268\u2013278 (1973). https:\/\/doi.org\/10.1109\/PROC.1973.9030","journal-title":"Proc. IEEE"},{"key":"5074_CR37","volume-title":"Error Control Coding","author":"S Lin","year":"2004","unstructured":"Lin, S., Costello, D.J.: Error Control Coding, 2nd edn. Prentice-Hall Inc, Saddle River (2004)","edition":"2"},{"issue":"2","key":"5074_CR38","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1109\/TIT.1974.1055186","volume":"20","author":"L Bahl","year":"1974","unstructured":"Bahl, L., Cocke, J., Jelinek, F., Raviv, J.: Optimal decoding of linear codes for minimizing symbol error rate (corresp.). IEEE Trans. Inf. Theory 20(2), 284\u2013287 (1974). https:\/\/doi.org\/10.1109\/TIT.1974.1055186","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"1","key":"5074_CR39","doi-asserted-by":"publisher","first-page":"7760","DOI":"10.1038\/s41467-022-35364-5","volume":"13","author":"ER Anschuetz","year":"2022","unstructured":"Anschuetz, E.R., Kiani, B.T.: Quantum variational algorithms are swamped with traps. Nat. Commun. 13(1), 7760 (2022). https:\/\/doi.org\/10.1038\/s41467-022-35364-5","journal-title":"Nat. Commun."},{"issue":"1","key":"5074_CR40","doi-asserted-by":"publisher","first-page":"4812","DOI":"10.1038\/s41467-018-07090-4","volume":"9","author":"JR McClean","year":"2018","unstructured":"McClean, J.R., Boixo, S., Smelyanskiy, V.N., Babbush, R., Neven, H.: Barren plateaus in quantum neural network training landscapes. Nat. Commun. 9(1), 4812 (2018). https:\/\/doi.org\/10.1038\/s41467-018-07090-4","journal-title":"Nat. Commun."},{"issue":"4","key":"5074_CR41","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3478519","volume":"2","author":"S Hadfield","year":"2021","unstructured":"Hadfield, S.: On the representation of Boolean and real functions as Hamiltonians for quantum computing. ACM Trans. Quantum Comput. 2(4), 1\u201321 (2021). https:\/\/doi.org\/10.1145\/3478519","journal-title":"ACM Trans. Quantum Comput."},{"issue":"1","key":"5074_CR42","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1038\/s41534-022-00599-z","volume":"8","author":"Y Zhang","year":"2022","unstructured":"Zhang, Y., Cincio, L., Negre, C.F., Czarnik, P., Coles, P.J., Anisimov, P.M., Mniszewski, S.M., Tretiak, S., Dub, P.A.: Variational quantum Eigensolver with reduced circuit complexity. NPJ Quantum Inf. 8(1), 96 (2022). https:\/\/doi.org\/10.1038\/s41534-022-00599-z","journal-title":"NPJ Quantum Inf."}],"container-title":["Quantum Information Processing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-026-05074-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11128-026-05074-8","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-026-05074-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,23]],"date-time":"2026-02-23T10:51:49Z","timestamp":1771843909000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11128-026-05074-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,2,7]]},"references-count":42,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2026,2]]}},"alternative-id":["5074"],"URL":"https:\/\/doi.org\/10.1007\/s11128-026-05074-8","relation":{},"ISSN":["1573-1332"],"issn-type":[{"value":"1573-1332","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,2,7]]},"assertion":[{"value":"16 May 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 January 2026","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 February 2026","order":3,"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 Conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"52"}}