Quantum Algorithms for Feedforward Neural Networks
Open accessThe DOI matches its Crossref record; 26 of the 26 references it cites were found in a registry or an index.
Abstract
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Deep Residual Learning for Image Recognition
He, K., Zhang, X., Ren, S., & Sun, J. (2016) · 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR) · doi:10.1109/cvpr.2016.90 · Cited by 235,474
ImageNet classification with deep convolutional neural networks
Krizhevsky, A., Sutskever, I., & Hinton, G. E. (2017) · Communications of the ACM · doi:10.1145/3065386 · Cited by 112,155
Learning representations by back-propagating errors
Rumelhart, D. E., Hinton, G. E., & Williams, R. J. (1986) · Nature · doi:10.1038/323533a0 · Cited by 31,892
Biamonte, J., Wittek, P., Pancotti, N., Rebentrost, P., Wiebe, N., & Lloyd, S. (2017) · Nature · doi:10.1038/nature23474 · Cited by 4,779
Quantum Support Vector Machine for Big Data Classification
Rebentrost, P., Mohseni, M., & Lloyd, S. (2014) · Physical Review Letters · doi:10.1103/physrevlett.113.130503 · Cited by 1,951
Quantum amplitude amplification and estimation
Brassard, G., Høyer, P., Mosca, M., & Tapp, A. (2002) · Contemporary Mathematics · doi:10.1090/conm/305/05215 · Cited by 1,680 · cited 4×
“• Performing amplitude estimation [4] on |Ψ〉 with logM ancilla qubits returns a value ã”
BackgroundMethodInfluentialQuantum convolutional neural networks
Cong, I., Choi, S., & Lukin, M. D. (2019) · Nature Physics · doi:10.1038/s41567-019-0648-8 · Cited by 1,517 · cited 1×
“However, although quantum generalizations of neural networks have been proposed for feedforward networks [5, 7, 12, 27, 35, 38, 47], Boltzmann machines [25, 46, 50, 51], and Hopfield networks [33], the current work presents, to the best of our knowledge, the first proposed quantum algorithms for training and evaluatin…”
BackgroundExploiting Linear Structure Within Convolutional Networks for Efficient Evaluation
Denton, R., Zaremba, W., Bruna, J., LeCun, Y., & Fergus, R. (2014) · arXiv · doi:10.48550/arxiv.1404.0736 · Cited by 1,414
An introduction to quantum machine learning
Schuld, M., Sinayskiy, I., & Petruccione, F. (2015) · Contemporary Physics · doi:10.1080/00107514.2014.964942 · Cited by 1,381
Giovannetti, V., Lloyd, S., & Maccone, L. (2008) · Physical Review Letters · doi:10.1103/physrevlett.100.160501 · Cited by 935 · cited 5×
“A network with L = 3 layers, dimension [n1, n2, n3] = [4,10,3], tanh activation function and mean squared error cost function was chosen, with M = 10, T = 1200 and η = 0.”
BackgroundMethodInfluentialThe quest for a Quantum Neural Network
Schuld, M., Sinayskiy, I., & Petruccione, F. (2014) · Quantum Information Processing · doi:10.1007/s11128-014-0809-8 · Cited by 671 · cited 1×
“Quantum machine learning [3, 6, 11, 39, 40] in general and quantum supervised learning [22, 28, 29, 34, 41, 49] in particular are fast-growing areas of research.”
BackgroundClassification with Quantum Neural Networks on Near Term Processors
Farhi, E., & Neven, H. (2018) · arXiv · doi:10.48550/arxiv.1802.06002 · Cited by 598
Low-rank matrix factorization for Deep Neural Network training with high-dimensional output targets
Sainath, T. N., Kingsbury, B., Sindhwani, V., Arisoy, E., & Ramabhadran, B. (2013) · 2013 IEEE International Conference on Acoustics, Speech and Signal Processing · doi:10.1109/icassp.2013.6638949 · Cited by 593 · cited 2×
“[39] Tara N Sainath, Brian Kingsbury, Vikas Sindhwani, Ebru Arisoy, and Bhuvana Ramabhadran.”
BackgroundQuantum autoencoders for efficient compression of quantum data
Romero, J., Olson, J. P., & Aspuru-Guzik, A. (2017) · Quantum Science and Technology · doi:10.1088/2058-9565/aa8072 · Cited by 559
Quantum algorithms for supervised and unsupervised machine learning
Lloyd, S., Mohseni, M., & Rebentrost, P. (2013) · arXiv · doi:10.48550/arxiv.1307.0411 · Cited by 542
Quantum machine learning: a classical perspective
Ciliberto, C., Herbster, M., Ialongo, A. D., Pontil, M., Rocchetto, A., Severini, S., & Wossnig, L. (2018) · Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences · doi:10.1098/rspa.2017.0551 · Cited by 518
A quantum-inspired classical algorithm for recommendation systems
Tang, E. (2019) · Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing · doi:10.1145/3313276.3316310 · Cited by 360
Architectures for a quantum random access memory
Giovannetti, V., Lloyd, S., & Maccone, L. (2008) · Physical Review A · doi:10.1103/physreva.78.052310 · Cited by 306
Quantum generalisation of feedforward neural networks
Wan, K. H., Dahlsten, O., Kristjánsson, H., Gardner, R., & Kim, M. S. (2017) · npj Quantum Information · doi:10.1038/s41534-017-0032-4 · Cited by 276
Quantum Recommendation Systems
Kerenidis, I., & Prakash, A. (2016) · arXiv · doi:10.48550/arxiv.1603.08675 · Cited by 270
Self-citationTomography and generative training with quantum Boltzmann machines
Kieferová, M., & Wiebe, N. (2017) · Physical Review A · doi:10.1103/physreva.96.062327 · Cited by 170
Circuit-Based Quantum Random Access Memory for Classical Data
Park, D. K., Petruccione, F., & Rhee, J.-K. K. (2019) · Scientific Reports · doi:10.1038/s41598-019-40439-3 · Cited by 151
Tang, E. (2018) · arXiv · doi:10.48550/arxiv.1811.00414 · Cited by 141
Tang, E. (2021) · Physical Review Letters · doi:10.1103/physrevlett.127.060503 · Cited by 140
A quantum algorithm to train neural networks using low-depth circuits
Verdon, G., Broughton, M., & Biamonte, J. (2017) · arXiv · doi:10.48550/arxiv.1712.05304 · Cited by 87
Quantum-inspired low-rank stochastic regression with logarithmic dependence on the dimension
Gilyén, A., Lloyd, S., & Tang, E. (2018) · arXiv · doi:10.48550/arxiv.1811.04909 · Cited by 63
Cited by
Herman, D., Googin, C., Liu, X., Sun, Y., Galda, A., Safro, I., Pistoia, M., & Alexeev, Y. (2023) · Nature Reviews Physics · doi:10.1038/s42254-023-00603-1 · Cited by 284
Quantum Algorithms for Deep Convolutional Neural Networks
Kerenidis, I., Landman, J., & Prakash, A. (2019) · arXiv · doi:10.48550/arxiv.1911.01117 · Cited by 102
“Quantum deep learning, the problem of creating quantum circuit that enhance the operations of neural networks, has been studied in several works [9, 10, 11].”
BackgroundSelf-citationBiology and medicine in the landscape of quantum advantages
Cordier, B. A., Sawaya, N. P. D., Guerreschi, G. G., & McWeeney, S. K. (2022) · Journal of The Royal Society Interface · doi:10.1098/rsif.2022.0541 · Cited by 87
“Neural Networks [276, 277, 278, 273, 213, 228, 279, 280, 226, 227] Yes Universal Gate-Based Quantum Device QML Polynomial and superpolynomial (e.”
A co-design framework of neural networks and quantum circuits towards quantum advantage
Jiang, W., Xiong, J., & Shi, Y. (2021) · Nature Communications · doi:10.1038/s41467-020-20729-5 · Cited by 63
Prospects and challenges of quantum finance
Bouland, A., van Dam, W., Joorati, H., Kerenidis, I., & Prakash, A. (2020) · arXiv · doi:10.48550/arxiv.2011.06492 · Cited by 46
Self-citation
Metadata
- Authors
- Allcock, J., Hsieh, C.-Y., Kerenidis, I., & Zhang, S.
- Venue
- ACM Transactions on Quantum Computing
- Published
- 2020-10-02
- Volume
- 1
- Issue
- 1
- Pages
- 1-24
- ISSN
- 2643-6809 (ISSN-L)
- 2643-6817
- OpenAlex
- W2904594696
- Cited by
- 46
- References
- 26
- FWCI
- 2.65
- Type
- journal article
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.