{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,16]],"date-time":"2025-10-16T20:43:58Z","timestamp":1760647438404,"version":"3.37.3"},"reference-count":84,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,4,30]],"date-time":"2021-04-30T00:00:00Z","timestamp":1619740800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,4,30]],"date-time":"2021-04-30T00:00:00Z","timestamp":1619740800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100004222","name":"Pembroke College, University of Cambridge","doi-asserted-by":"publisher","award":["Draper\u2019s Research Fellowship"],"award-info":[{"award-number":["Draper\u2019s Research Fellowship"]}],"id":[{"id":"10.13039\/501100004222","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001843","name":"Science and Engineering Research Board","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001843","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003342","name":"Cambridge Commonwealth Trust","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100003342","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Quantum Mach. Intell."],"published-print":{"date-parts":[[2021,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Probabilistic language models, e.g. those based on recurrent neural networks such as long short-term memory models (LSTMs), often face the problem of finding a high probability prediction from a sequence of random variables over a set of tokens. This is commonly addressed using a form of greedy decoding such as beam search, where a limited number of highest-likelihood paths (the beam width) of the decoder are kept, and at the end the maximum-likelihood path is chosen. In this work, we construct a quantum algorithm to find the globally optimal parse (i.e. for infinite beam width) with high constant success probability. When the input to the decoder follows a power law with exponent<jats:italic>k<\/jats:italic>&gt;\u20090, our algorithm has runtime<jats:italic>R<\/jats:italic><jats:sup><jats:italic>n<\/jats:italic><jats:italic>f<\/jats:italic>(<jats:italic>R<\/jats:italic>,<jats:italic>k<\/jats:italic>)<\/jats:sup>, where<jats:italic>R<\/jats:italic>is the alphabet size,<jats:italic>n<\/jats:italic>the input length; here<jats:italic>f<\/jats:italic>&lt;\u20091\/2, and<jats:inline-formula><jats:alternatives><jats:tex-math>$f\\rightarrow 0$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>f<\/mml:mi><mml:mo>\u2192<\/mml:mo><mml:mn>0<\/mml:mn><\/mml:math><\/jats:alternatives><\/jats:inline-formula>exponentially fast with increasing<jats:italic>k<\/jats:italic>, hence making our algorithm always more than quadratically faster than its classical counterpart. We further modify our procedure to recover a finite beam width variant, which enables an even stronger empirical speedup while still retaining higher accuracy than possible classically. Finally, we apply this quantum beam search decoder to Mozilla\u2019s implementation of Baidu\u2019s<jats:italic>DeepSpeech<\/jats:italic>neural net, which we show to exhibit such a power law word rank frequency.<\/jats:p>","DOI":"10.1007\/s42484-021-00041-1","type":"journal-article","created":{"date-parts":[[2021,4,30]],"date-time":"2021-04-30T08:02:54Z","timestamp":1619769774000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["A quantum search decoder for natural language processing"],"prefix":"10.1007","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3189-9162","authenticated-orcid":false,"given":"Johannes","family":"Bausch","sequence":"first","affiliation":[]},{"given":"Sathyawageeswar","family":"Subramanian","sequence":"additional","affiliation":[]},{"given":"Stephen","family":"Piddock","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,4,30]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"Aaronson S, Grier D, Schaeffer L (2019) A quantum query complexity trichotomy for regular languages. In: IEEE 60th annual symposium on foundations of computer science (FOCS). IEEE, pp 942\u2013965","key":"41_CR1","DOI":"10.1109\/FOCS.2019.00061"},{"unstructured":"Ahuja A, Kapoor S (1999) A quantum algorithm for finding the maximum","key":"41_CR2"},{"doi-asserted-by":"crossref","unstructured":"Al-Rfou R, Choe D, Constant N, Guo M (2019) Character-level language modeling with deeper self-attention. In: Proceedings of the AAAI conference on artificial intelligence, vol 33, pp 3159\u20133166","key":"41_CR3","DOI":"10.1609\/aaai.v33i01.33013159"},{"issue":"08","key":"41_CR4","doi-asserted-by":"publisher","first-page":"1840001","DOI":"10.1142\/S0219749918400014","volume":"16","author":"J Bausch","year":"2018","unstructured":"Bausch J (2018) Classifying data using near-term quantum devices. Int J Quantum Inf 16 (08):1840001","journal-title":"Int J Quantum Inf"},{"unstructured":"Bausch J (2020) Recurrent quantum neural networks. In: Advances in neural information processing systems. 34th Annual conference on neural information processing systems (NeurIPS), vol 33","key":"41_CR5"},{"doi-asserted-by":"crossref","unstructured":"Buckman J, Ballesteros M, Dyer C (2016) Transition-based dependency parsing with heuristic backtracking. In: Proceedings of the 2016 Conference on empirical methods in natural language processing. Stroudsburg, PA, USA. ACL (Association for Computational Linguistics), Association for Computational Linguistics, pp 2313\u20132318","key":"41_CR6","DOI":"10.18653\/v1\/D16-1254"},{"doi-asserted-by":"crossref","unstructured":"Berry DW, Childs AM, Cleve R, Kothari R, Somma RD (2014) Exponential improvement in precision for simulating sparse hamiltonians. In: Proceedings of the forty-sixth annual ACM symposium on theory of computing, STOC \u201914. ACM, New York, pp 283\u2013292","key":"41_CR7","DOI":"10.1145\/2591796.2591854"},{"issue":"3","key":"41_CR8","doi-asserted-by":"publisher","first-page":"1057","DOI":"10.1007\/s00220-017-3002-y","volume":"356","author":"DW Berry","year":"2017","unstructured":"Berry DW, Childs AM, Ostrander A, Wang G (2017) Quantum algorithm for linear differential equations with exponentially improved dependence on precision. Commun Math Phys 356(3):1057\u20131081","journal-title":"Commun Math Phys"},{"issue":"1-2","key":"41_CR9","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1007\/s00453-010-9446-5","volume":"62","author":"O Bernardi","year":"2012","unstructured":"Bernardi O, Gim\u00e9nez O (2012) A linear algorithm for the random sampling from regular languages. Algorithmica 62(1-2):130\u2013145","journal-title":"Algorithmica"},{"doi-asserted-by":"crossref","unstructured":"Bohnet B, McDonald R, Pitler E, Ma J (2016) Generalized transition-based dependency parsing via control parameters. In: Proceedings of the 54th Annual meeting of the association for computational linguistics (Volume 1: Long Papers). Association for Computational Linguistics, Stroudsburg, pp 150\u2013160","key":"41_CR10","DOI":"10.18653\/v1\/P16-1015"},{"issue":"35","key":"41_CR11","doi-asserted-by":"publisher","first-page":"6821","DOI":"10.1088\/0305-4470\/34\/35\/308","volume":"34","author":"H Buhrman","year":"2001","unstructured":"Buhrman H, Tromp J, Vit\u00e1nyi P (2001) Time and space bounds for reversible simulation. J Phys A Math 34(35):6821\u20136830","journal-title":"J Phys A Math"},{"issue":"1","key":"41_CR12","first-page":"011044","volume":"8","author":"R Babbush","year":"2018","unstructured":"Babbush R, Wiebe N, McClean J, McClain J, Neven H, Chan GK-L (2018) Low-depth quantum simulation of materials. Phys Rev X 8(1):011044","journal-title":"Phys Rev X"},{"issue":"3","key":"41_CR13","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1109\/TIT.1956.1056813","volume":"2","author":"N Chomsky","year":"1956","unstructured":"Chomsky N (1956) Three models for the description of language. IEEE Trans Inform Theory 2 (3):113\u2013124","journal-title":"IEEE Trans Inform Theory"},{"unstructured":"Cox R (2007) Regular expression matching can be simple and fast (but is slow in Java, Perl, PHP, Python, Ruby, ...)","key":"41_CR14"},{"issue":"5","key":"41_CR15","doi-asserted-by":"publisher","first-page":"050503","DOI":"10.1103\/PhysRevLett.123.050503","volume":"123","author":"AM Childs","year":"2019","unstructured":"Childs AM, Su Y (2019) Nearly optimal lattice simulation by product formulas. Phys Rev Lett 123(5):050503","journal-title":"Phys Rev Lett"},{"doi-asserted-by":"crossref","unstructured":"Dabrowska E (2008) Questions with long-distance dependencies: A usage-based perspective. Cogn Linguist 19(3)","key":"41_CR16","DOI":"10.1515\/COGL.2008.015"},{"doi-asserted-by":"crossref","unstructured":"Dyer C, Ballesteros M, Ling W, Matthews A, Smith NA (2015) Transition-based dependency parsing with stack long short-term memory. In: Proceedings of the 53rd annual meeting of the association for computational linguistics and the 7th international joint conference on natural language processing (Volume 1: Long Papers). Association for Computational Linguistics, Stroudsburg, pp 334\u2013343","key":"41_CR17","DOI":"10.3115\/v1\/P15-1033"},{"issue":"1","key":"41_CR18","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/0304-3975(95)00200-6","volume":"159","author":"A Denise","year":"1996","unstructured":"Denise A (1996) G\u00e9n\u00e9ration al\u00e9atoire uniforme de mots de langages rationnels. Theor Comput Sci 159(1):43\u201363","journal-title":"Theor Comput Sci"},{"unstructured":"D\u00fcrr C, H\u00f8yer P (1996) A quantum algorithm for finding the minimum in LANL e-print quantph\/9607014","key":"41_CR19"},{"doi-asserted-by":"crossref","unstructured":"Denise A, Roques O, Termier M (2000) Random generation of words of context-free languages according to the frequencies of letters. In: Mathematics and computer science. Basel, Birkh\u00e4user Basel, pp 113\u2013125","key":"41_CR20","DOI":"10.1007\/978-3-0348-8405-1_10"},{"doi-asserted-by":"crossref","unstructured":"Dai Z, Yang Z, Yang Y, Carbonell J, Le QV, Salakhutdinov R (2019) Transformer-XL: attentive language models beyond a fixed-length context. In: Proceedings of the 57th Annual meeting of the association for computational linguistics","key":"41_CR21","DOI":"10.18653\/v1\/P19-1285"},{"issue":"2","key":"41_CR22","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1145\/362007.362035","volume":"13","author":"J Earley","year":"1970","unstructured":"Earley J (1970) An efficient context-free parsing algorithm. Commun ACM 13(2):94\u2013102","journal-title":"Commun ACM"},{"issue":"2","key":"41_CR23","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1023\/A:1005634925734","volume":"47","author":"L Egghe","year":"2000","unstructured":"Egghe L (2000) The distribution of N-Grams. Scientometrics 47(2):237\u2013252","journal-title":"Scientometrics"},{"doi-asserted-by":"crossref","unstructured":"Fan A, Lewis M, Dauphin Y (2018) Hierarchical neural story generation. In: Proceedings of the 56th annual meeting of the association for computational linguistics","key":"41_CR24","DOI":"10.18653\/v1\/P18-1082"},{"doi-asserted-by":"crossref","unstructured":"Gily\u00e9n A, Arunachalam S, Wiebe N (2019) Optimizing quantum optimization algorithms via faster quantum gradient computation. In: Proceedings of the Thirtieth annual ACM-SIAM symposium on discrete algorithms. Society for Industrial and Applied Mathematics, Philadelphia, pp 1425\u20131444","key":"41_CR25","DOI":"10.1137\/1.9781611975482.87"},{"key":"41_CR26","first-page":"2335","volume":"12","author":"S Goldwater","year":"2011","unstructured":"Goldwater S, Griffiths TL, Johnson M (2011) Producing power-law distributions and damping word frequencies with two-stage language models. J Mach Learn Res 12:2335\u20132382","journal-title":"J Mach Learn Res"},{"key":"41_CR27","doi-asserted-by":"publisher","first-page":"74","DOI":"10.22331\/q-2018-06-18-74","volume":"2","author":"C Gidney","year":"2018","unstructured":"Gidney C (2018) Halving the cost of quantum addition. Quantum 2:74","journal-title":"Quantum"},{"issue":"1","key":"41_CR28","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1006\/inco.1997.2621","volume":"134","author":"V Gore","year":"1997","unstructured":"Gore V, Jerrum Mark , Kannan S, Sweedyk Z, Mahaney S (1997) A quasi-polynomial-time algorithm for sampling words from a context-free language. Inf Computat 134(1):59\u201374","journal-title":"Inf Computat"},{"doi-asserted-by":"crossref","unstructured":"Goldwurm M, Palano B, Santini M (2001) On the circuit complexity of random generation problems for regular and context-free languages. In: Ferreira A, Reichel H (eds) STACS 2001. Springer, Berlin, pp 305\u2013316","key":"41_CR29","DOI":"10.1007\/3-540-44693-1_27"},{"doi-asserted-by":"crossref","unstructured":"Graves A (2013) Generating sequences with recurrent neural networks","key":"41_CR30","DOI":"10.1007\/978-3-642-24797-2_3"},{"unstructured":"Holtzman A, Buys J, Du L, Forbes M, Choi Y (2020) The curious case of neural text degeneration. In: International conference on learning representations","key":"41_CR31"},{"issue":"4","key":"41_CR32","doi-asserted-by":"publisher","first-page":"645","DOI":"10.1137\/0212044","volume":"12","author":"T Hickey","year":"1983","unstructured":"Hickey T, Cohen J (1983) Uniform random generation of strings in a context-free language. SIAM J Comput 12(4):645\u2013655","journal-title":"SIAM J Comput"},{"unstructured":"Hannun A, Case C, Casper J, Catanzaro B, Diamos G, Elsen E, Prenger R, Satheesh S, Sengupta S, Coates A, Ng AY (2014) Deep speech: Scaling up end-to-end speech recognition","key":"41_CR33"},{"issue":"15","key":"41_CR34","doi-asserted-by":"publisher","first-page":"150502","DOI":"10.1103\/PhysRevLett.103.150502","volume":"103","author":"AW Harrow","year":"2009","unstructured":"Harrow AW, Hassidim A, Lloyd S (2009) Quantum algorithm for linear systems of equations. Phys Rev Lett 103(15):150502","journal-title":"Phys Rev Lett"},{"doi-asserted-by":"crossref","unstructured":"Hopcroft JE, Motwani R, Ullman JD (2001) Introduction to automata theory, languages, and computation, vol 32, 2nd edn.","key":"41_CR35","DOI":"10.1145\/568438.568455"},{"issue":"03n04","key":"41_CR36","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1142\/S0219525911500196","volume":"15","author":"G J\u00e4ger","year":"2012","unstructured":"J\u00e4ger G. (2012) Power laws and other heavy-tailed distributions in linguistic typology. Adv Complex Syst 15(03n04):1\u201321","journal-title":"Adv Complex Syst"},{"doi-asserted-by":"crossref","unstructured":"Khandelwal U, He H, Qi P, Jurafsky D (2018) Sharp nearby, fuzzy far away: how neural language models use context. In: Proceedings of the 56th annual meeting of the association for computational linguistics (Volume 1: Long Papers). Association for Computational Linguistics., Stroudsburg, pp 284\u2013294","key":"41_CR37","DOI":"10.18653\/v1\/P18-1027"},{"unstructured":"Kitaev N, Kaiser L, Levskaya A (2020) Reformer: The efficient transformer. In: International conference on learning representations","key":"41_CR38"},{"doi-asserted-by":"crossref","unstructured":"Kleene SC (1956) Representation of events in nerve nets and finite automata. In: Automata studies. (AM-34). Princeton University Press, Princeton, pp 3\u201342","key":"41_CR39","DOI":"10.1515\/9781400882618-002"},{"doi-asserted-by":"crossref","unstructured":"Kulikov I, Miller AH, Cho K, Weston J (2018) Importance of a search strategy in neural dialogue modelling","key":"41_CR40","DOI":"10.18653\/v1\/W19-8609"},{"unstructured":"Kerenidis I, Prakash A (2016) Quantum recommendation systems","key":"41_CR41"},{"unstructured":"Li T, Chakrabarti S, Wu X (2019) Sublinear quantum algorithms for training linear and kernel-based classifiers. In: ICML","key":"41_CR42"},{"issue":"5278","key":"41_CR43","doi-asserted-by":"publisher","first-page":"1073","DOI":"10.1126\/science.273.5278.1073","volume":"273","author":"S Lloyd","year":"1996","unstructured":"Lloyd S (1996) Universal quantum simulators. Science 273(5278):1073\u20131078","journal-title":"Science"},{"key":"41_CR44","volume-title":"From a Regular Expression to an NFA","author":"KC Louden","year":"1997","unstructured":"Louden KC (1997) From a Regular Expression to an NFA. Pearson\/Addison Wesley, Boston"},{"doi-asserted-by":"crossref","unstructured":"Lorenz WA, Ponty Y (2013) Non-redundant random generation algorithms for weighted context-free grammars, vol 502","key":"41_CR45","DOI":"10.1016\/j.tcs.2013.01.006"},{"doi-asserted-by":"crossref","unstructured":"Murray K, Chiang D (2018) Correcting length bias in neural machine translation. In: Proceedings of the third conference on machine translation: research papers. Association for Computational Linguistics, Stroudsburg, pp 212\u2013223","key":"41_CR46","DOI":"10.18653\/v1\/W18-6322"},{"unstructured":"McKenzie B (1997) Generating strings at random from a context free grammar. Technical report, Department of Computer Science, University of Canterbury, Engineering Reports","key":"41_CR47"},{"key":"41_CR48","volume-title":"Unsolvability of the halting problem","author":"ML Minsky","year":"1967","unstructured":"Minsky ML (1967) Unsolvability of the halting problem. Prentice-Hall, Inc, Upper Saddle River"},{"doi-asserted-by":"crossref","unstructured":"Montanaro A (2011) Quantum search with advice. In: Lecture notes in computer science (including subseries lecture notes in artificial intelligence and lecture notes in bioinformatics), 6519 LNCS, pp 77\u201393","key":"41_CR49","DOI":"10.1007\/978-3-642-18073-6_7"},{"issue":"1","key":"41_CR50","doi-asserted-by":"publisher","first-page":"15023","DOI":"10.1038\/npjqi.2015.23","volume":"2","author":"A Montanaro","year":"2016","unstructured":"Montanaro A (2016) Quantum algorithms: an overview. Npj Quantum Inf 2(1):15023","journal-title":"Npj Quantum Inf"},{"issue":"1","key":"41_CR51","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1007\/s00453-015-0060-4","volume":"77","author":"A Montanaro","year":"2017","unstructured":"Montanaro A (2017) Quantum pattern matching fast on average. Algorithmica 77(1):16\u201339","journal-title":"Algorithmica"},{"issue":"1","key":"41_CR52","doi-asserted-by":"publisher","first-page":"013056","DOI":"10.1103\/PhysRevResearch.2.013056","volume":"2","author":"A Montanaro","year":"2020","unstructured":"Montanaro A (2020) Quantum speedup of branch-and-bound algorithms. Phys Rev Res 2 (1):013056","journal-title":"Phys Rev Res"},{"unstructured":"Mozilla (2019) Common voice","key":"41_CR53"},{"unstructured":"Mozilla (2019) DeepSpeech","key":"41_CR54"},{"issue":"2","key":"41_CR55","doi-asserted-by":"publisher","first-page":"23023","DOI":"10.1088\/1367-2630\/18\/2\/023023","volume":"18","author":"JR McClean","year":"2016","unstructured":"McClean JR, Romero J, Babbush R, Aspuru-Guzik Al\u00e1n (2016) The theory of variational hybrid quantum-classical algorithms. New J Phys 18(2):23023","journal-title":"New J Phys"},{"key":"41_CR56","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511976667","volume-title":"Quantum computation and quantum information","author":"MA Nielsen","year":"2010","unstructured":"Nielsen MA, Chuang IL (2010) Quantum computation and quantum information. Cambridge University Press, Cambridge"},{"key":"41_CR57","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/j.tcs.2012.07.025","volume":"502","author":"J Oudinet","year":"2013","unstructured":"Oudinet J, Denise A, Gaudel M-C (2013) A new dichotomic algorithm for the uniform random generation of words in regular languages. Theor Comput Sci 502:165\u2013176","journal-title":"Theor Comput Sci"},{"issue":"5","key":"41_CR58","doi-asserted-by":"publisher","first-page":"1112","DOI":"10.3758\/s13423-014-0585-6","volume":"21","author":"ST Piantadosi","year":"2014","unstructured":"Piantadosi ST (2014) Zipf\u2019s word frequency law in natural language: A critical review and future directions. Psychon Bull Rev 21(5):1112\u20131130","journal-title":"Psychon Bull Rev"},{"unstructured":"Ponty Y (2012) Rule-weighted and terminal-weighted context-free grammars have identical expressivity. Research report","key":"41_CR59"},{"doi-asserted-by":"crossref","unstructured":"Pratap V, Xu Q, Kahn J, Avidov G, Likhomanenko T, Hannun A, Liptchinsky V, Synnaeve G, Collobert R (2020) Scaling up online speech recognition using ConvNets. facebook research","key":"41_CR60","DOI":"10.21437\/Interspeech.2020-2840"},{"issue":"13","key":"41_CR61","doi-asserted-by":"publisher","first-page":"i308","DOI":"10.1093\/bioinformatics\/btt217","volume":"29","author":"V Reinharz","year":"2013","unstructured":"Reinharz V, Ponty Y, Waldisp\u00fchl J (2013) A weighted sampling algorithm for the design of RNA sequences with targeted secondary structure and nucleotide distribution. Bioinformatics 29(13):i308\u2013i315","journal-title":"Bioinformatics"},{"issue":"2","key":"41_CR62","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1147\/rd.32.0114","volume":"3","author":"MO Rabin","year":"1959","unstructured":"Rabin MO, Scott D (1959) Finite automata and their decision problems. IBM J Res Dev 3 (2):114\u2013125","journal-title":"IBM J Res Dev"},{"doi-asserted-by":"crossref","unstructured":"Stella M, Brede M (2016) Investigating the phonetic organisation of the English language via phonological networks, percolation and markov models. pp 219\u2013229","key":"41_CR63","DOI":"10.1007\/978-3-319-29228-1_19"},{"key":"41_CR64","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/j.neunet.2014.09.003","volume":"61","author":"J Schmidhuber","year":"2014","unstructured":"Schmidhuber J (2014) Deep learning in neural networks: an overview. Neural Netw 61:85\u2013117","journal-title":"Neural Netw"},{"issue":"2","key":"41_CR65","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1137\/S0036144598347011","volume":"41","author":"PW Shor","year":"1999","unstructured":"Shor PW (1999) Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Rev 41(2):303\u2013332","journal-title":"SIAM Rev"},{"unstructured":"Ilya S, Martens J, Hinton G (2011) 1017\u20131024. In: Proceedings of the 28th international conference on international conference on machine learning, ICML\u201911. Omnipress","key":"41_CR66"},{"key":"41_CR67","first-page":"01","volume":"7","author":"DS Oliveira","year":"2007","unstructured":"Oliveira DS, Ramos R (2007) Quantum bit string comparator: circuits and applications. Quantum Comput Comput 7:01","journal-title":"Quantum Comput Comput"},{"doi-asserted-by":"crossref","unstructured":"Steinbiss V, Tran B-H, Ney H (1994) Improvements in beam search. In: Third international conference on spoken language processing","key":"41_CR68","DOI":"10.21437\/ICSLP.1994-538"},{"unstructured":"Sutskever I, Vinyals O, Le QV (2014) Sequence to sequence learning with neural networks. In: Ghahramani Z, Welling M, Cortes C, Lawrence ND, Weinberger KQ (eds) Advances in neural information processing systems, vol 27. Curran Associates, Inc., pp 3104\u20133112","key":"41_CR69"},{"doi-asserted-by":"crossref","unstructured":"Tang E (2019) A quantum-inspired classical algorithm for recommendation systems. In: Proceedings of the 51st Annual ACM SIGACT symposium on theory of computing - stoc 2019.ACM Press, New York, pp 217\u2013228","key":"41_CR70","DOI":"10.1145\/3313276.3316310"},{"issue":"6","key":"41_CR71","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1145\/363347.363387","volume":"11","author":"K Thompson","year":"1968","unstructured":"Thompson K (1968) Programming techniques: regular expression search algorithm. Commun ACM 11(6):419\u2013422","journal-title":"Commun ACM"},{"key":"41_CR72","volume-title":"Construction of an NFA from a regular expression","author":"AVA Ullman","year":"1997","unstructured":"Ullman AVA, Lam MS, Sethi R, Jeffrey D (1997) Construction of an NFA from a regular expression. PWS Pub. Co, Boston"},{"unstructured":"Vijayakumar AK, Cogswell M, Selvaraju RR, Sun Q, Lee S, Crandall D, Batra D (2016) Diverse beam search: decoding diverse solutions from neural sequence models. pp 1\u201316","key":"41_CR73"},{"doi-asserted-by":"crossref","unstructured":"Apeldoorn JV, Gily\u00e9n A, Gribling S, de Wolf R, Gilyen A, Gribling S, de Wolf R (2017) Quantum SDP-solvers: better upper and lower bounds. In: Annual symposium on foundations of computer science - Proceedings, 2017-Octob(617), pp 1\u201374","key":"41_CR74","DOI":"10.1109\/FOCS.2017.44"},{"doi-asserted-by":"crossref","unstructured":"Vilares D, Go\u0307mez-Rodri\u0307guez C (2018) Transition-based parsing with lighter feed-forward networks. UDW@EMNLP","key":"41_CR75","DOI":"10.18653\/v1\/W18-6019"},{"unstructured":"Wiebe N, Bocharov A, Smolensky P, Troyer M, Svore KM (2019) Quantum language processing","key":"41_CR76"},{"issue":"14","key":"41_CR77","doi-asserted-by":"publisher","first-page":"140504","DOI":"10.1103\/PhysRevLett.122.140504","volume":"122","author":"D Wang","year":"2019","unstructured":"Wang D, Higgott O, Brierley S (2019) Accelerated variational quantum eigensolver. Phys Rev Lett 122(14):140504","journal-title":"Phys Rev Lett"},{"doi-asserted-by":"crossref","unstructured":"Wiseman S, Rush AM (2016) Sequence-to-sequence learning as beam-search optimization. In: Proceedings of the 2016 conference on empirical methods in natural language processing. Association for Computational Linguistics, Stroudsburg, pp 1296\u20131306","key":"41_CR78","DOI":"10.18653\/v1\/D16-1137"},{"key":"41_CR79","first-page":"120","volume":"050502","author":"L Wossnig","year":"2018","unstructured":"Wossnig L, Zhao Z, Prakash A (2018) Quantum linear system algorithm for dense matrices. Phys Rev Lett 050502:120","journal-title":"Phys Rev Lett"},{"doi-asserted-by":"crossref","unstructured":"Yang Y, Huang L, Ma M (2018) Breaking the beam search curse: a study of (re-)scoring methods and stopping criteria for neural machine translation. In: Proceedings of the 2018 conference on empirical methods in natural language processing. Association for Computational Linguistics, Stroudsburg, pp 3054\u20133059","key":"41_CR80","DOI":"10.18653\/v1\/D18-1342"},{"issue":"2","key":"41_CR81","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/S0019-9958(67)80007-X","volume":"10","author":"DH Younger","year":"1967","unstructured":"Younger DH (1967) Recognition and parsing of context-free languages in time n3. Inf Control 10 (2):189\u2013208","journal-title":"Inf Control"},{"doi-asserted-by":"crossref","unstructured":"Zhang Y, Clark S (2008) A tale of two parsers: investigating and combining graph-based and transition-based dependency parsing using beam-search. In: Proceedings of the conference on empirical methods in natural language processing. Association for Computational Linguistics, pp 562\u2013571","key":"41_CR82","DOI":"10.3115\/1613715.1613784"},{"unstructured":"Zhang Y, features Joakim Nivre. (2011) Transition-based dependency parsing with rich non-local. In: Proceedings of the 49th annual meeting of the association for computational linguistics: human language technologies: short papers, vol 2. Association for Computational Linguistics, pp 188\u2013193","key":"41_CR83"},{"doi-asserted-by":"crossref","unstructured":"Zhu C, Qiu X, Huang X (2015) Transition-based dependency parsing with long distance collocations. In: Lecture notes in computer science (including subseries lecture notes in artificial intelligence and lecture notes in bioinformatics)","key":"41_CR84","DOI":"10.1007\/978-3-319-25207-0_2"}],"container-title":["Quantum Machine Intelligence"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42484-021-00041-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s42484-021-00041-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42484-021-00041-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,26]],"date-time":"2022-12-26T00:44:59Z","timestamp":1672015499000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s42484-021-00041-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,4,30]]},"references-count":84,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,6]]}},"alternative-id":["41"],"URL":"https:\/\/doi.org\/10.1007\/s42484-021-00041-1","relation":{},"ISSN":["2524-4906","2524-4914"],"issn-type":[{"type":"print","value":"2524-4906"},{"type":"electronic","value":"2524-4914"}],"subject":[],"published":{"date-parts":[[2021,4,30]]},"assertion":[{"value":"5 November 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 February 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 April 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"16"}}