{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,6]],"date-time":"2026-07-06T17:16:33Z","timestamp":1783358193448,"version":"3.54.6"},"reference-count":52,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2020,10,2]],"date-time":"2020-10-02T00:00:00Z","timestamp":1601596800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM Transactions on Quantum Computing"],"published-print":{"date-parts":[[2020,12,31]]},"abstract":"<jats:p>Quantum machine learning has the potential for broad industrial applications, and the development of quantum algorithms for improving the performance of neural networks is of particular interest given the central role they play in machine learning today. We present quantum algorithms for training and evaluating feedforward neural networks based on the canonical classical feedforward and backpropagation algorithms. Our algorithms rely on an efficient quantum subroutine for approximating inner products between vectors in a robust way, and on implicitly storing intermediate values in quantum random access memory for fast retrieval at later stages. The running times of our algorithms can be quadratically faster in the size of the network than their standard classical counterparts since they depend linearly on the number of neurons in the network, and not on the number of connections between neurons. Furthermore, networks trained by our quantum algorithm may have an intrinsic resilience to overfitting, as the algorithm naturally mimics the effects of classical techniques used to regularize networks. Our algorithms can also be used as the basis for new quantum-inspired classical algorithms with the same dependence on the network dimensions as their quantum counterparts but with quadratic overhead in other parameters that makes them relatively impractical.<\/jats:p>","DOI":"10.1145\/3411466","type":"journal-article","created":{"date-parts":[[2020,10,2]],"date-time":"2020-10-02T16:28:51Z","timestamp":1601656131000},"page":"1-24","source":"Crossref","is-referenced-by-count":36,"title":["Quantum Algorithms for Feedforward Neural Networks"],"prefix":"10.1145","volume":"1","author":[{"given":"Jonathan","family":"Allcock","sequence":"first","affiliation":[{"name":"Tencent Quantum Laboratory, Guangdong, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Chang-Yu","family":"Hsieh","sequence":"additional","affiliation":[{"name":"Tencent Quantum Laboratory, Guangdong, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Iordanis","family":"Kerenidis","sequence":"additional","affiliation":[{"name":"CNRS, IRIF, Universit\u00e9 Paris Diderot, Paris, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shengyu","family":"Zhang","sequence":"additional","affiliation":[{"name":"Tencent Quantum Laboratory, Guangdong, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,10,2]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Bhaskar Roy Bardhan, and Seth Lloyd","author":"Arrazola Juan Miguel","year":"2019"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1088\/1367-2630\/17\/12\/123010"},{"key":"e_1_2_1_3_1","volume-title":"Quantum machine learning. Nature 549, 7671","author":"Biamonte Jacob","year":"2017"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/305\/05215"},{"key":"e_1_2_1_5_1","volume-title":"Gian Giacomo Guerreschi, and Al\u00e1n Aspuru-Guzik","author":"Cao Yudong","year":"2017"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1098\/rspa.2017.0551"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41567-019-0648-8"},{"key":"e_1_2_1_8_1","unstructured":"Emily L. Denton Wojciech Zaremba Joan Bruna Yann LeCun and Rob Fergus. 2014. Exploiting linear structure within convolutional networks for efficient evaluation. In Advances in Neural Information Processing Systems. 1269--1277.  Emily L. Denton Wojciech Zaremba Joan Bruna Yann LeCun and Rob Fergus. 2014. Exploiting linear structure within convolutional networks for efficient evaluation. In Advances in Neural Information Processing Systems. 1269--1277."},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1109\/TQE.2020.2965803","article-title":"Fault-tolerant resource estimation of quantum random-access memories","volume":"1","author":"Matteo Olivia Di","year":"2020","journal-title":"IEEE Transactions on Quantum Engineering"},{"key":"e_1_2_1_10_1","volume-title":"Do we have brain to spare?Neurology 64, 12","author":"Drachman David A.","year":"2005"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1088\/1361-6633\/aab406"},{"key":"e_1_2_1_12_1","unstructured":"Edward Farhi and Hartmut Neven. 2018. Classification with quantum neural networks on near term processors. arXiv:1802.06002.  Edward Farhi and Hartmut Neven. 2018. Classification with quantum neural networks on near term processors. arXiv:1802.06002."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02650179"},{"key":"e_1_2_1_14_1","unstructured":"Andr\u00e1s Gily\u00e9n Seth Lloyd and Ewin Tang. 2018. Quantum-inspired low-rank stochastic regression with logarithmic dependence on the dimension. arXiv:1811.04909  Andr\u00e1s Gily\u00e9n Seth Lloyd and Ewin Tang. 2018. Quantum-inspired low-rank stochastic regression with logarithmic dependence on the dimension. arXiv:1811.04909"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.78.052310"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.100.160501"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 13th International Conference on Artificial Intelligence and Statistics. 249--256","author":"Glorot Xavier","year":"2010"},{"key":"e_1_2_1_18_1","volume-title":"Deep Learning","author":"Goodfellow Ian"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","first-page":"250501","DOI":"10.1103\/PhysRevLett.123.250501","article-title":"Hardware-efficient quantum random access memory with hybrid quantum acoustic systems","volume":"123","author":"Hann Connor T.","year":"2019","journal-title":"Physical Review Letters"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2016.90"},{"key":"e_1_2_1_21_1","unstructured":"Iordanis Kerenidis Jonas Landman Alessandro Luongo and Anupam Prakash. 2019. q-means: A quantum algorithm for unsupervised machine learning. In Advances in Neural Information Processing Systems. 4136--4146.  Iordanis Kerenidis Jonas Landman Alessandro Luongo and Anupam Prakash. 2019. q-means: A quantum algorithm for unsupervised machine learning. In Advances in Neural Information Processing Systems. 4136--4146."},{"key":"e_1_2_1_22_1","unstructured":"Iordanis Kerenidis and Alessandro Luongo. 2018. Quantum classification of the MNIST dataset via Slow Feature Analysis. arXiv:1805.08837.  Iordanis Kerenidis and Alessandro Luongo. 2018. Quantum classification of the MNIST dataset via Slow Feature Analysis. arXiv:1805.08837."},{"key":"e_1_2_1_23_1","volume-title":"LIPIcs-Leibniz International Proceedings in Informatics.","volume":"67","author":"Kerenidis Iordanis","year":"2017"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.101.022316"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.96.062327"},{"key":"e_1_2_1_26_1","volume-title":"Hinton","author":"Krizhevsky Alex","year":"2012"},{"key":"e_1_2_1_27_1","unstructured":"Yidong Liao Oscar Dahlsten Daniel Ebler and Feiyang Liu. 2018. Quantum advantage in training binary neural networks. arXiv:1810.12948.  Yidong Liao Oscar Dahlsten Daniel Ebler and Feiyang Liu. 2018. Quantum advantage in training binary neural networks. arXiv:1810.12948."},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the International Workshop on Frontiers in Algorithmics. 204--216","author":"Liu Yang","year":"2015"},{"key":"e_1_2_1_29_1","unstructured":"Seth Lloyd Masoud Mohseni and Patrick Rebentrost. 2013. Quantum algorithms for supervised and unsupervised machine learning. arXiv:1307.0411.  Seth Lloyd Masoud Mohseni and Patrick Rebentrost. 2013. Quantum algorithms for supervised and unsupervised machine learning. arXiv:1307.0411."},{"key":"e_1_2_1_30_1","volume-title":"Neural Networks and Deep Learning","author":"Nielsen Michael"},{"key":"e_1_2_1_31_1","first-page":"1","article-title":"Circuit-based quantum random access memory for classical data","volume":"9","author":"Park Daniel K.","year":"2019","journal-title":"Scientific Reports"},{"key":"e_1_2_1_33_1","doi-asserted-by":"crossref","first-page":"042308","DOI":"10.1103\/PhysRevA.98.042308","article-title":"Quantum hopfield neural network","volume":"98","author":"Rebentrost Patrick","year":"2018","journal-title":"Physical Review A"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.113.130503"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1088\/2058-9565\/aa8072"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1038\/323533a0"},{"key":"e_1_2_1_37_1","volume-title":"Proceedings of the 2013 IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP\u201913)","author":"Sainath Tara N.","year":"2013"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.122.040504"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.5555\/2684509.2684546"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1080\/00107514.2014.964942"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.94.022342"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.5555\/2627435.2670313"},{"key":"e_1_2_1_43_1","unstructured":"Cheng Tai Tong Xiao Yi Zhang Xiaogang Wang and Weinan E. 2015. Convolutional neural networks with low-rank regularization. arXiv:1511.06067.  Cheng Tai Tong Xiao Yi Zhang Xiaogang Wang and Weinan E. 2015. Convolutional neural networks with low-rank regularization. arXiv:1511.06067."},{"key":"e_1_2_1_44_1","unstructured":"Ewin Tang. 2018. Quantum-inspired classical algorithms for principal component analysis and supervised clustering. arXiv:1811.00414.  Ewin Tang. 2018. Quantum-inspired classical algorithms for principal component analysis and supervised clustering. arXiv:1811.00414."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316310"},{"key":"e_1_2_1_46_1","unstructured":"Guillaume Verdon Michael Broughton and Jacob Biamonte. 2017. A quantum algorithm to train neural networks using low-depth circuits. arXiv:1712.05304.  Guillaume Verdon Michael Broughton and Jacob Biamonte. 2017. A quantum algorithm to train neural networks using low-depth circuits. arXiv:1712.05304."},{"key":"e_1_2_1_47_1","doi-asserted-by":"crossref","unstructured":"Kwok Ho Wan Oscar Dahlsten Hl\u00e9r Kristj\u00e1nsson Robert Gardner and M. S. Kim. 2017. Quantum generalisation of feedforward neural networks. npj Quantum Information 3 1 (2017) 36.  Kwok Ho Wan Oscar Dahlsten Hl\u00e9r Kristj\u00e1nsson Robert Gardner and M. S. Kim. 2017. Quantum generalisation of feedforward neural networks. npj Quantum Information 3 1 (2017) 36.","DOI":"10.1038\/s41534-017-0032-4"},{"key":"e_1_2_1_48_1","volume-title":"Proceedings of the International Conference on Machine Learning. 1058--1066","author":"Wan Li","year":"2013"},{"key":"e_1_2_1_49_1","volume-title":"Svore","author":"Wiebe Nathan","year":"2015"},{"key":"e_1_2_1_50_1","volume-title":"Svore","author":"Wiebe Nathan","year":"2016"},{"key":"e_1_2_1_51_1","unstructured":"Nathan Wiebe and Leonard Wossnig. 2019. Generative training of quantum Boltzmann machines with hidden units. arXiv:1905.09902.  Nathan Wiebe and Leonard Wossnig. 2019. Generative training of quantum Boltzmann machines with hidden units. arXiv:1905.09902."},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.120.050502"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2017.15"}],"container-title":["ACM Transactions on Quantum Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3411466","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3411466","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:01:29Z","timestamp":1750197689000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3411466"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,10,2]]},"references-count":52,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,12,31]]}},"alternative-id":["10.1145\/3411466"],"URL":"https:\/\/doi.org\/10.1145\/3411466","relation":{},"ISSN":["2643-6809","2643-6817"],"issn-type":[{"value":"2643-6809","type":"print"},{"value":"2643-6817","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,10,2]]}}}