random-features.bib

@article{Berry2018ImprovedHamiltonians,
    title = {{Improved techniques for preparing eigenstates of fermionic Hamiltonians}},
    year = {2018},
    journal = {npj Quantum Information},
    author = {Berry, Dominic W. and Kieferov{\'{a}}, Mária and Scherer, Artur and Sanders, Yuval R. and Low, Guang Hao and Wiebe, Nathan and Gidney, Craig and Babbush, Ryan},
    number = {1},
    % % month =  {12},
    pages = {22},
    volume = {4},
    url = {http://arxiv.org/abs/1711.10460},
    doi = {10.1038/s41534-018-0071-5},
    issn = {2056-6387},
    arxivId = {1711.10460}
}

@misc{haner2018,
  title = "Optimizing Quantum Circuits for Arithmetic",
  author = {H\"{a}ner, Thomas and Roetteler, Martin and Svore, Krysta M.},
  arxivId = {1805.12445},
  arxivPrefix = {arXiv},
  URL = {https://arxiv.org/abs/1805.12445},
  year = {2018}
}

@inproceedings{LeGall2014InversionMultiplication,
 author = {Le~Gall, Fran\c{c}ois},
 title = {Powers of Tensors and Fast Matrix Multiplication},
 booktitle = {Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation},
 series = {ISSAC '14},
 year = {2014},
 isbn = {978-1-4503-2501-1},
 location = {Kobe, Japan},
 pages = {296--303},
 numpages = {8},
 url = {http://doi.acm.org/10.1145/2608628.2608664},
 doi = {10.1145/2608628.2608664},
 acmid = {2608664},
 publisher = {ACM},
 address = {New York, NY, USA},
 keywords = {algebraic complexity theory, matrix multiplication},
} 

@article{Montanaro2016,
  doi = {10.1038/npjqi.2015.23},
  url = {https://doi.org/10.1038/npjqi.2015.23},
  year = {2016},
  % % month =  jan,
  publisher = {Springer Science and Business Media {LLC}},
  volume = {2},
  number = {1},
  author = {Ashley Montanaro},
  title = {Quantum algorithms: an overview},
  journal = {npj Quantum Information}
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Now for a bad bib file
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

@Article{S1,
    author="Schaback, Robert",
    title="The missing Wendland functions",
    journal="Advances in Computational Mathematics",
    year="2011",
    % month="Jan",
    day="01",
    volume="34",
    number="1",
    pages="67--81",
    issn="1572-9044",
    doi="10.1007/s10444-009-9142-7",
    url="https://link.springer.com/article/10.1007/s10444-009-9142-7"
}

@Article{W1,
    author="Wendland, Holger",
    title="Piecewise polynomial, positive definite and compactly supported radial functions of minimal degree",
    journal="Advances in Computational Mathematics",
    year="1995",
    % month="Dec",
    day="01",
    volume="4",
    number="1",
    pages="389--396",
    issn="1572-9044",
    doi="10.1007/BF02123482",
    url="https://link.springer.com/article/10.1007/BF02123482"
}

@book{W2,
    place={Cambridge},
    series={Cambridge Monographs on Applied and Computational Mathematics},
    title={Scattered Data Approximation},
    DOI={10.1017/CBO9780511617539},
    publisher={Cambridge University Press},
    author={Wendland, Holger},
    year={2004},
    collection={Cambridge Monographs on Applied and Computational Mathematics},
    url={https://www.cambridge.org/core/books/scattered-data-approximation/980EEC9DBC4CAA711D089187818135E3}
}

@book{R1,
    place={New York},
    series={Graduate Texts in Mathematics},
    title={Matrix Analysis},
    DOI={10.1007/978-1-4612-0653-8},
    publisher={Springer-Verlag New York},
    author={Bhatia,Rajendra},
    year={1997},
    url={https://www.springer.com/gp/book/9780387948461}
}

@article{B1,
  author  = {Francis Bach},
  title   = {On the Equivalence between Kernel Quadrature Rules and Random Feature Expansions},
  journal = {Journal of Machine Learning Research},
  year    = {2017},
  volume  = {18},
  number  = {21},
  pages   = {1-38},
  url     = {http://jmlr.org/papers/v18/15-178.html}
}

@article{C1,
    title = "Closed form representations and properties of the generalised Wendland functions",
    journal = "Journal of Approximation Theory",
    volume = "177",
    pages = "17 - 33",
    year = "2014",
    issn = "0021-9045",
    doi = "https://doi.org/10.1016/j.jat.2013.09.005",
    url = "http://www.sciencedirect.com/science/article/pii/S0021904513001536",
    author = "Chernih, Andrew and Hubbert, Simon",
}


@book{S2,
    place={Cambridge},
    title={Kernel Methods for Pattern Analysis},
    DOI={10.1017/CBO9780511809682},
    publisher={Cambridge University Press},
    author={Shawe-Taylor, John and Cristianini, Nello},
    year={2004},
    url={https://www.cambridge.org/core/books/kernel-methods-for-pattern-analysis/811462F4D6CD6A536A05127319A8935A}
}

@ARTICLE{C2,
    author = {Cucker, Felipe and Smale, Steve},
    title = {On the mathematical foundations of learning},
    journal = {Bulletin of the American Mathematical Society},
    year = {2002},
    volume = {39},
    pages = {1--49},
    url={https://www.ams.org/journals/bull/2002-39-01/S0273-0979-01-00923-5/#Additional}
}

@conference{A1,
    author={Arg\'{a}ez, Carlos and Hafstein, Sigurdur and Giesl, Peter},
    title={Wendland Functions - A C++ Code to Compute Them},
    booktitle={Proceedings of the 7th International Conference on Simulation and Modeling Methodologies, Technologies and Applications - Volume 1: SIMULTECH,},
    year={2017},
    pages={323-330},
    publisher={SciTePress},
    organization={INSTICC},
    doi={10.5220/0006441303230330},
    isbn={978-989-758-265-3},
    url={http://www.scitepress.org/DigitalLibrary/Link.aspx?doi=10.5220/0006441303230330}
}

@article{K1,
  title = "Approximation theory for matrices",
  journal = "Nuclear Phys. B",
  volume = "128",
  pages = "107 - 116",
  year = "2004",
  % % month =  {Feb},
  note = "Proceedings of the 2nd Cairns Topical Workshop on Lattice Hadron Physics",
  issn = "0920-5632",
  doi = "https://doi.org/10.1016/S0920-5632(03)02466-6",
  url = "http://www.sciencedirect.com/science/article/pii/S0920563203024666",
  author = "Kennedy, A.D."
}

@unpublished{K2,
  title = "Fast Evaluation of Zolotarev Coefficients",
  author = "Kennedy, A.D.",
  arxivPrefix = {arxiv},
  arxivId = {hep-lat/0402038},
  URL = {https://arxiv.org/abs/hep-lat/0402038},
  % month={Feb},
  year = {2014},
}

@book{P1,
  place={Cambridge},
  series={Encyclopedia of Mathematics and its Applications},
  title={Rational Approximation of Real Functions},
  DOI={10.1017/CBO9781107340756},
  publisher={Cambridge University Press},
  author={Petrushev, P. P. and Popov, Vasil Atanasov},
  year={1988},
  collection={Encyclopedia of Mathematics and its Applications}
}

@article{C3,
  title={Performing Out-of Core FFTs on Parallel Disk Systems},
  author={Cormen, Thomas H. and Nicol, David M.},
  journal={Parallel Computing},
  year={1998},
  volume={24},
  pages={5-20}
}

@article{Z1,
  title = {Quantum-assisted Gaussian process regression},
  author = {Zhao, Zhikuan and Fitzsimons, Jack K. and Fitzsimons, Joseph F.},
  journal = {Phys. Rev. A},
  volume = {99},
  issue = {5},
  pages = {052331},
  numpages = {6},
  year = {2019},
  % % month =  {May},
  publisher = {American Physical Society},
  doi = {10.1103/PhysRevA.99.052331},
  url = {https://link.aps.org/doi/10.1103/PhysRevA.99.052331}
}

@unpublished{G2,
  author = {Gily\'{e}n, Andr\'{a}s and Lloyd, Seth and Tang, Ewin},
  title = {Quantum-inspired low-rank stochastic regression with logarithmic dependence on the dimension},
  arxivPrefix = {arxiv},
  arxivId = {1811.04909},
  URL = {https://arxiv.org/abs/1811.04909},
  % month={Nov},
  year = {2018},
}

@unpublished{C4,
  author = {Chia, Nai-Hui and Lin, Han-Hsuan and Wang, Chunhao},
  title = {Quantum-inspired sublinear classical algorithms for solving low-rank linear systems},
  arxivPrefix = {arxiv},
  arxivId = {1811.04852},
  URL = {https://arxiv.org/abs/1811.04852},
  % month={Nov},
  year = {2018},
}

@article{W3,
  title = {Quantum algorithm for linear regression},
  author = {Wang, Guoming},
  journal = {Phys. Rev. A},
  volume = {96},
  issue = {1},
  pages = {012335},
  numpages = {17},
  year = {2017},
  % % month =  {Jul},
  publisher = {American Physical Society},
  doi = {10.1103/PhysRevA.96.012335},
  url = {https://link.aps.org/doi/10.1103/PhysRevA.96.012335}
}


@phdthesis{Prakash2014,
  author = {Prakash, Anupam},
  title = {Quantum Algorithms for Linear Algebra and Machine Learning},
  school = {University of California, Berkeley},
  year = {2014},
  URL = {https://www2.eecs.berkeley.edu/Pubs/TechRpts/2014/EECS-2014-211.html},
}

@article{H2,
title = "Improved quantum Fourier transform algorithm and applications",
author = "Hales, Lisa and Hallgren, Sean",
pages = "515--525",
url="https://pennstate.pure.elsevier.com/en/publications/improved-quantum-Fourier-transform-algorithm-and-applications",
booktitle = {2013 IEEE 54th Annual Symposium on Foundations of Computer Science},
year = {2000},
volume = {},
issn = {0272-5428},
pages = {515},
doi = {10.1109/SFCS.2000.892139},
url = {https://doi.ieeecomputersociety.org/10.1109/SFCS.2000.892139},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA}
}

@INPROCEEDINGS{C5,
  author={Cleve, R. and Watrous, J.},
  booktitle={Proceedings 41st Annual Symposium on Foundations of Computer Science},
  title={Fast parallel circuits for the quantum Fourier transform},
  year={2000},
  volume={},
  number={},
  pages={526-536},
  doi={10.1109/SFCS.2000.892140},
  ISSN={0272-5428},
  % month={Nov},
}


@article{S4,
 author = {Sriperumbudur, Bharath K. and Fukumizu, Kenji and Lanckriet, Gert R. G.},
 title = {Universality, Characteristic Kernels and RKHS Embedding of Measures},
 journal = {J. Mach. Learn. Res.},
 issue_date = {2/1/2011},
 volume = {12},
 % % month =  jul,
 year = {2011},
 issn = {1532-4435},
 pages = {2389--2410},
 numpages = {22},
 url = {http://dl.acm.org/citation.cfm?id=1953048.2021077},
 acmid = {2021077},
 publisher = {JMLR.org},
} 

@book{S5,
 author = {Sch\"{o}lkopf, Bernhard and Smola, Alexander J.},
 title = {Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond},
 year = {2001},
 isbn = {0262194759},
 publisher = {MIT Press},
 address = {Cambridge, MA, USA},
} 

@article{D1,
  title={Analysis of Langevin Monte Carlo via Convex Optimization},
  author={Durmus, Alain and Majewski, Szymon and Miasojedow, Blazej},
  journal={J. Mach. Learn. Res.},
  year={2018},
  volume={20},
  pages={73:1-73:46}
}

@unpublished{A2,
  author = {Aaronson, Scott and Rall, Patrick},
  title = {Quantum Approximate Counting, Simplified},
  arxivPrefix = {arxiv},
  arxivId = {1908.10846},
  URL = {https://arxiv.org/abs/1908.10846},
  % month={Aug},
  year = {2019},
}

@article{B2,
url = {https://www.nowpublishers.com/article/Details/MAL-050},
year = {2015},
volume = {8},
journal = {Foundations and Trends in Machine Learning},
title = {Convex Optimization: Algorithms and Complexity},
doi = {10.1561/2200000050},
issn = {1935-8237},
number = {3-4},
pages = {231-357},
author = {Bubeck, S\'{e}bastien}
}

@book{N1,
    place={Springer Nature Switzerland AG},
    series={Springer Optimization and Its Applications},
    title={Lectures on Convex Optimization},
    DOI={10.1007/978-3-319-91578-4},
    publisher={Springer, Cham},
    author={Nesterov, Yurii},
    year={2018},
    collection={Springer Optimization and Its Applications},
    url={https://link.springer.com/book/10.1007\%2F978-3-319-91578-4}
}

@unpublished{Y1,
  author = {Yu, Chao-Hua and Gao, Fei and Wen, Qiao-Yan},
  title = {An improved quantum algorithm for ridge regression},
  arxivPrefix = {arxiv},
  arxivId = {1707.09524},
  URL = {https://arxiv.org/abs/1707.09524},
  % month={Jul},
  year = {2017},
}

@incollection{R2,
title = {Random Features for Large-Scale Kernel Machines},
author = {Rahimi, Ali and Recht, Benjamin},
booktitle = {Advances in Neural Information Processing Systems 20},
editor = {J. C. Platt and D. Koller and Y. Singer and S. T. Roweis},
pages = {1177--1184},
year = {2008},
publisher = {Curran Associates, Inc.},
url = {http://papers.nips.cc/paper/3182-random-features-for-large-scale-kernel-machines.pdf}
}

@incollection{R3,
title = {Weighted Sums of Random Kitchen Sinks: Replacing minimisation with randomization in learning},
author = {Rahimi, Ali and Recht, Benjamin},
booktitle = {Advances in Neural Information Processing Systems 21},
editor = {D. Koller and D. Schuurmans and Y. Bengio and L. Bottou},
pages = {1313--1320},
year = {2009},
publisher = {Curran Associates, Inc.},
url = {http://papers.nips.cc/paper/3495-weighted-sums-of-random-kitchen-sinks-replacing-minimisation-with-randomization-in-learning.pdf}
}

@InProceedings{L1,
  title = 	 {Fastfood - Computing Hilbert Space Expansions in loglinear time},
  author = 	 {Le, Quoc and Sarlos, Tamas and Smola, Alexander},
  booktitle = 	 {Proceedings of the 30th International Conference on Machine Learning},
  pages = 	 {244--252},
  year = 	 {2013},
  editor = 	 {Sanjoy Dasgupta and David McAllester},
  volume = 	 {28},
  number =       {3},
  series = 	 {Proceedings of Machine Learning Research},
  address = 	 {Atlanta, Georgia, USA},
  % % month =  	 {17--19 Jun},
  publisher = 	 {PMLR},
  pdf = 	 {http://proceedings.mlr.press/v28/le13.pdf},
  url = 	 {http://proceedings.mlr.press/v28/le13.html},
}

@inproceedings{R4,
 author = {Rakhlin, Alexander and Shamir, Ohad and Sridharan, Karthik},
 title = {Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization},
 booktitle = {Proceedings of the 29th International Coference on International Conference on Machine Learning},
 series = {ICML'12},
 year = {2012},
 isbn = {978-1-4503-1285-1},
 location = {Edinburgh, Scotland},
 pages = {1571--1578},
 numpages = {8},
 url = {http://dl.acm.org/citation.cfm?id=3042573.3042774},
 acmid = {3042774},
 publisher = {Omnipress},
 address = {USA},
 arXivId={1109.5647},
 arXivPrefix = {arXiv}
}

@book{B3,
 author = {Boyd, Stephen and Vandenberghe, Lieven},
 title = {Convex Optimization},
 year = {2004},
 isbn = {0521833787},
 publisher = {Cambridge University Press},
 address = {New York, NY, USA},
}

@InProceedings{H3,
  title = 	 {Tight analyses for non-smooth stochastic gradient descent},
  author = 	 {Harvey, Nicholas J.~A. and Liaw, Christopher and Plan, Yaniv and Randhawa, Sikander},
  booktitle = 	 {Proceedings of the Thirty-Second Conference on Learning Theory},
  pages = 	 {1579--1613},
  year = 	 {2019},
  editor = 	 {Beygelzimer, Alina and Hsu, Daniel},
  volume = 	 {99},
  series = 	 {Proceedings of Machine Learning Research},
  address = 	 {Phoenix, USA},
  % % month =  	 {25--28 Jun},
  publisher = 	 {PMLR},
  pdf = 	 {http://proceedings.mlr.press/v99/harvey19a/harvey19a.pdf},
  url = 	 {http://proceedings.mlr.press/v99/harvey19a.html},
}


@unpublished{J1,
  author = {Jain, Prateek and Nagaraj, Dheeraj and Netrapalli, Praneeth},
  title = {Making the Last Iterate of SGD Information Theoretically Optimal},
  arxivPrefix = {arxiv},
  arxivId = {1904.12443},
  URL = {https://arxiv.org/abs/1904.12443},
  % month={Apr},
  year = {2019},
}

@unpublished{H4,
  author = {Harvey, Nicholas J. A. and Liaw, Christopher and Randhawa, Sikander},
  title = {Simple and optimal high-probability bounds for strongly-convex stochastic gradient descent},
  arxivPrefix = {arxiv},
  arxivId = {1909.00843},
  URL = {https://arxiv.org/abs/1909.00843},
  % month={Sep},
  year = {2019},
}

@unpublished{harvey:hal-02070778,
  TITLE = {{Integer multiplication in time O(n log n)}},
  AUTHOR = {Harvey, David and Van Der Hoeven, Joris},
  URL = {https://hal.archives-ouvertes.fr/hal-02070778},
  YEAR = {2019},
  journal = {Technical Report, HAL},
  % % month =  Mar,
  PDF = {https://hal.archives-ouvertes.fr/hal-02070778/file/nlogn.pdf},
}

@book{berlinet2011reproducing,
  title={Reproducing kernel Hilbert spaces in probability and statistics},
  author={Berlinet, Alain and Thomas-Agnan, Christine},
  year={2011},
  publisher={Springer Science \& Business Media}
}

@article{PhysRevLett.109.050505,
  title = {Quantum Algorithm for Data Fitting},
  author = {Wiebe, Nathan and Braun, Daniel and Lloyd, Seth},
  journal = {Phys. Rev. Lett.},
  volume = {109},
  issue = {5},
  pages = {050505},
  numpages = {5},
  year = {2012},
  % % month =  {Aug},
  publisher = {American Physical Society},
  doi = {10.1103/PhysRevLett.109.050505},
  url = {https://link.aps.org/doi/10.1103/PhysRevLett.109.050505}
}

@article{lloyd2016quantum,
  title={Quantum algorithms for topological and geometric analysis of data},
  author={Lloyd, Seth and Garnerone, Silvano and Zanardi, Paolo},
  journal={Nature communications},
  volume={7},
  pages={10138},
  year={2016},
  publisher={Nature Publishing Group},
  url={https://www.nature.com/articles/ncomms10138}
}


@article{PhysRevLett.113.130503,
  title = {Quantum Support Vector Machine for Big Data Classification},
  author = {Rebentrost, Patrick and Mohseni, Masoud and Lloyd, Seth},
  journal = {Phys. Rev. Lett.},
  volume = {113},
  issue = {13},
  pages = {130503},
  numpages = {5},
  year = {2014},
  % % month =  {Sep},
  publisher = {American Physical Society},
  doi = {10.1103/PhysRevLett.113.130503},
  url = {https://link.aps.org/doi/10.1103/PhysRevLett.113.130503}
}


@unpublished{arXiv:1910.06151,
  author ={Chia, Nai-Hui and Gily\'{e}n, Andr\'{a}s and Li, Tongyang and Lin, Han-Hsuan and Tang, Ewin and Wang, Chunhao},
  title = {Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning},
  arxivPrefix = {arxiv},
  arxivId = {1910.06151},
  URL = {https://arxiv.org/abs/1910.06151},
  % month={Oct},
  year = {2019},
}

@unpublished{arXiv:1910.05699,
  author ={Jethwani, Dhawal and Le Gall, Fran\c{c}ois and Singh, Sanjay K.},
  title = {Quantum-Inspired Classical Algorithms for Singular Value Transformation},
  arxivPrefix = {arxiv},
  arxivId = {1910.05699},
  URL = {https://arxiv.org/abs/1910.05699},
  % month={Oct},
  year = {2019},
}

@Inbook{Zhang2012,
author="Zhang, Shengyu",
editor="Rozenberg, Grzegorz
and B{\"a}ck, Thomas
and Kok, Joost N.",
title="BQP-Complete Problems",
bookTitle="Handbook of Natural Computing",
year="2012",
publisher="Springer Berlin Heidelberg",
address="Berlin, Heidelberg",
pages="1545--1571",
isbn="978-3-540-92910-9",
doi="10.1007/978-3-540-92910-9_46",
url="https://doi.org/10.1007/978-3-540-92910-9_46"
}

@article{arute2019quantum,
  title={Quantum supremacy using a programmable superconducting processor},
  author={Arute, Frank and Arya, Kunal and Babbush, Ryan and Bacon, Dave and Bardin, Joseph C and Barends, Rami and Biswas, Rupak and Boixo, Sergio and Brandao, Fernando GSL and Buell, David A and others},
  journal={Nature},
  volume={574},
  number={7779},
  pages={505--510},
  year={2019},
  publisher={Nature Publishing Group},
  url={https://www.nature.com/articles/s41586-019-1666-5}
}

@unpublished{deWolf2019notes,
  author ={de Wolf, Ronald},
  title = {Quantum Computing: Lecture Notes},
  arxivPrefix = {arxiv},
  arxivId = {1907.09415},
  URL = {https://arxiv.org/abs/1907.09415},
  year = {2019},
}

@ARTICLE{Shannon1949communication,
author={{Shannon},C. E.},
journal={Proceedings of the IRE},
title={Communication in the Presence of Noise},
year={1949},
volume={37},
number={1},
pages={10-21},
keywords={Electron tubes;Voltage;Bandwidth;Circuits;Shape;Klystrons;Frequency measurement;Gain measurement;Communication systems;Telephony},
doi={10.1109/JRPROC.1949.232969},
ISSN={2162-6634},
% month={Jan},
url={https://ieeexplore.ieee.org/abstract/document/1697831}
}

@article{PhysRevLett.100.160501,
  title = {Quantum Random Access Memory},
  author = {Giovannetti, Vittorio and Lloyd, Seth and Maccone, Lorenzo},
  journal = {Phys. Rev. Lett.},
  volume = {100},
  issue = {16},
  pages = {160501},
  numpages = {4},
  year = {2008},
  % % month =  {Apr},
  publisher = {American Physical Society},
  doi = {10.1103/PhysRevLett.100.160501},
  url = {https://link.aps.org/doi/10.1103/PhysRevLett.100.160501}
}

@article{PhysRevA.78.052310,
  title = {Architectures for a quantum random access memory},
  author = {Giovannetti, Vittorio and Lloyd, Seth and Maccone, Lorenzo},
  journal = {Phys. Rev. A},
  volume = {78},
  issue = {5},
  pages = {052310},
  numpages = {9},
  year = {2008},
  % % month =  {Nov},
  publisher = {American Physical Society},
  doi = {10.1103/PhysRevA.78.052310},
  url = {https://link.aps.org/doi/10.1103/PhysRevA.78.052310}
}

@article{jiang2019experimental,
  title={Experimental realization of 105-qubit random access quantum memory},
  author={Jiang, N and Pu, Y-F and Chang, W and Li, C and Zhang, S and Duan, L-M},
  journal={npj Quantum Information},
  volume={5},
  number={1},
  pages={28},
  year={2019},
  publisher={Nature Publishing Group},
  url={https://www.nature.com/articles/s41534-019-0144-0}
}

@article{PhysRevLett.123.250501,
  title = {Hardware-Efficient Quantum Random Access Memory with Hybrid Quantum Acoustic Systems},
  author = {Hann, Connor T. and Zou, Chang-Ling and Zhang, Yaxing and Chu, Yiwen and Schoelkopf, Robert J. and Girvin, S. M. and Jiang, Liang},
  journal = {Phys. Rev. Lett.},
  volume = {123},
  issue = {25},
  pages = {250501},
  numpages = {7},
  year = {2019},
  % % month =  {Dec},
  publisher = {American Physical Society},
  doi = {10.1103/PhysRevLett.123.250501},
  url = {https://link.aps.org/doi/10.1103/PhysRevLett.123.250501}
}

@unpublished{arXiv:1609.04747,
  title = "An overview of gradient descent optimization algorithms",
  author = "Ruder,Sebastian",
  arxivPrefix = {arxiv},
  arxivId = {1609.04747},
  URL = {https://arxiv.org/abs/1609.04747},
  % month={Sep},
  year = {2016},
}

@article{biamonte2017quantum,
  title={Quantum machine learning},
  author={Biamonte, Jacob and Wittek, Peter and Pancotti, Nicola and Rebentrost, Patrick and Wiebe, Nathan and Lloyd, Seth},
  journal={Nature},
  volume={549},
  number={7671},
  pages={195},
  year={2017},
  publisher={Nature Publishing Group},
  url={https://www.nature.com/articles/nature23474}
}


@article{dunjko2018machine,
  doi = {10.1088/1361-6633/aab406},
  url = {https://iopscience.iop.org/article/10.1088/1361-6633/aab406},
  year = 2018,
  % % month =  {jun},
  publisher = {{IOP} Publishing},
  volume = {81},
  number = {7},
  pages = {074001},
  author = {Vedran Dunjko and Hans J Briegel},
  title = {Machine learning {\&} artificial intelligence in the quantum domain: a review of recent progress},
  journal = {Reports on Progress in Physics},
}

@article{aaronson2015read,
  title={Read the fine print},
  author={Aaronson, Scott},
  journal={Nature Physics},
  volume={11},
  number={4},
  pages={291},
  year={2015},
  publisher={Nature Publishing Group},
  url={https://www.nature.com/articles/nphys3272}
}

@book{proakis2001digital,
  title={Digital signal processing: principles algorithms and applications},
  author={Proakis, John G},
  publisher = {Pearson Prentice Hall}, 
  year = {2007},
  address = {Upper Saddle River, N.J},
  isbn = {978-0131873742}
}

@incollection{NIPS2016_6246,
  title = {Orthogonal Random Features},
  author = {Yu, Felix Xinnan X and Suresh, Ananda Theertha and Choromanski, Krzysztof M and Holtmann-Rice, Daniel N and Kumar, Sanjiv},
  booktitle = {Advances in Neural Information Processing Systems 29},
  editor = {D. D. Lee and M. Sugiyama and U. V. Luxburg and I. Guyon and R. Garnett},
  pages = {1975--1983},
  year = {2016},
  publisher = {Curran Associates, Inc.},
  url = {http://papers.nips.cc/paper/6246-orthogonal-random-features.pdf}
}


@incollection{carratino2018learning,
title = {Learning with SGD and Random Features},
author = {Carratino, Luigi and Rudi, Alessandro and Rosasco, Lorenzo},
booktitle = {Advances in Neural Information Processing Systems 31},
editor = {S. Bengio and H. Wallach and H. Larochelle and K. Grauman and N. Cesa-Bianchi and R. Garnett},
pages = {10192--10203},
year = {2018},
publisher = {Curran Associates, Inc.},
url = {http://papers.nips.cc/paper/8222-learning-with-sgd-and-random-features.pdf}
}

@inproceedings{10.5555/2999611.2999698,
  author = {Bach, Francis and Moulines, Eric},
  title = {Non-Strongly-Convex Smooth Stochastic Approximation with Convergence Rate O(1/n)},
  year = {2013},
  publisher = {Curran Associates Inc.},
  address = {Red Hook, NY, USA},
  booktitle = {Proceedings of the 26th International Conference on Neural Information Processing Systems - Volume 1},
  pages = {773–781},
  numpages = {9},
  location = {Lake Tahoe, Nevada},
  series = {NIPS’13}
}

@article{JMLR:v18:16-595,
  author  = {Prateek Jain and Sham M. Kakade and Rahul Kidambi and Praneeth Netrapalli and Aaron Sidford},
  title   = {Parallelizing Stochastic Gradient Descent for Least Squares Regression: Mini-batching, Averaging, and Model Misspecification},
  journal = {Journal of Machine Learning Research},
  year    = {2018},
  volume  = {18},
  number  = {223},
  pages   = {1-42},
  url     = {http://jmlr.org/papers/v18/16-595.html}
}

@article{10.5555/3122009.3176845,
  author = {Dieuleveut, Aymeric and Flammarion, Nicolas and Bach, Francis},
  title = {Harder, Better, Faster, Stronger Convergence Rates for Least-Squares Regression},
  year = {2017},
  issue_date = {January 2017},
  publisher = {JMLR.org},
  volume = {18},
  number = {1},
  issn = {1532-4435},
  journal = {J. Mach. Learn. Res.},
  % % month =  jan,
  pages = {3520–3570},
  numpages = {51},
  keywords = {accelerated gradient, least-squares regression, convex optimization, stochastic gradient, non-parametric estimation}
}

@incollection{NIPS2017_6914,
  title = {Generalization Properties of Learning with Random Features},
  author = {Rudi, Alessandro and Rosasco, Lorenzo},
  booktitle = {Advances in Neural Information Processing Systems 30},
  editor = {I. Guyon and U. V. Luxburg and S. Bengio and H. Wallach and R. Fergus and S. Vishwanathan and R. Garnett},
  pages = {3215--3225},
  year = {2017},
  publisher = {Curran Associates, Inc.},
  url = {http://papers.nips.cc/paper/6914-generalization-properties-of-learning-with-random-features.pdf}
}

@incollection{NIPS2018_7961,
title = {Streaming Kernel PCA with tilde O(sqrt n) Random Features},
author = {Ullah, Enayat and Mianjy, Poorya and Marinov, Teodor Vanislavov and Arora, Raman},
booktitle = {Advances in Neural Information Processing Systems 31},
editor = {S. Bengio and H. Wallach and H. Larochelle and K. Grauman and N. Cesa-Bianchi and R. Garnett},
pages = {7311--7321},
year = {2018},
publisher = {Curran Associates, Inc.},
url = {http://papers.nips.cc/paper/7961-streaming-kernel-pca-with-tildeosqrtn-random-features.pdf}
}

@incollection{NIPS2017_6978,
  title = {FALKON: An Optimal Large Scale Kernel Method},
  author = {Rudi, Alessandro and Carratino, Luigi and Rosasco, Lorenzo},
  booktitle = {Advances in Neural Information Processing Systems 30},
  editor = {I. Guyon and U. V. Luxburg and S. Bengio and H. Wallach and R. Fergus and S. Vishwanathan and R. Garnett},
  pages = {3888--3898},
  year = {2017},
  publisher = {Curran Associates, Inc.},
  url = {http://papers.nips.cc/paper/6978-falkon-an-optimal-large-scale-kernel-method.pdf}
}

@incollection{NIPS2016_6180,
  title = {Learning Kernels with Random Features},
  author = {Sinha, Aman and Duchi, John C},
  booktitle = {Advances in Neural Information Processing Systems 29},
  editor = {D. D. Lee and M. Sugiyama and U. V. Luxburg and I. Guyon and R. Garnett},
  pages = {1298--1306},
  year = {2016},
  publisher = {Curran Associates, Inc.},
  url = {http://papers.nips.cc/paper/6180-learning-kernels-with-random-features.pdf}
}

@article{10.1137/S0097539795293172,
 author = {Shor, Peter W.},
 title = {Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer},
 year = {1997},
 issue_date = {October 1997},
 publisher = {Society for Industrial and Applied Mathematics},
 address = {USA},
 volume = {26},
 number = {5},
 issn = {0097-5397},
 url={https://epubs.siam.org/doi/10.1137/S0097539795293172},
 doi = {10.1137/S0097539795293172},
 journal = {SIAM J. Comput.},
 % % month =  oct,
 pages = {1484–1509},
 numpages = {26},
 keywords = {discrete logarithms, algorithmic number theory, prime factorization, spin systems, foundations of quantum mechanics, Fourier transforms, quantum computers, Church’s thesis}
}

@Article{Mengoni2019,
author="Mengoni, Riccardo
and Di Pierro, Alessandra",
title="Kernel methods in Quantum Machine Learning",
journal="Quantum Machine Intelligence",
year="2019",
% month="Dec",
day="01",
volume="1",
number="3",
pages="65--71",
issn="2524-4914",
doi="10.1007/s42484-019-00007-4",
url="https://link.springer.com/article/10.1007/s42484-019-00007-4"
}

@article{10.5555/2946645.3007073,
  author  = {Haim Avron and Vikas Sindhwani and Jiyan Yang and Michael W. Mahoney},
  title   = {Quasi-Monte Carlo Feature Maps for Shift-Invariant Kernels},
  journal = {Journal of Machine Learning Research},
  year    = {2016},
  volume  = {17},
  number  = {120},
  pages   = {1-38},
  url     = {http://jmlr.org/papers/v17/14-538.html}
}

@inproceedings{10.5555/3172077.3172095,
  author    = {Chang, Wei-Cheng and Li, Chun-Liang and Yang, Yiming and P\'{o}czos, Barnab\'{a}s},
  title     = {Data-driven Random Fourier Features using Stein Effect},
  booktitle = {Proceedings of the Twenty-Sixth International Joint Conference on
              Artificial Intelligence, {IJCAI-17}},
  % pages     = {1497--1503},
  year      = {2017},
  doi       = {10.24963/ijcai.2017/207},
  url       = {https://www.ijcai.org/Proceedings/2017/207},
}


@article{doi:10.1098/rspa.2017.0551,
author = {Ciliberto, Carlo  and Herbster, Mark  and Ialongo, Alessandro Davide  and Pontil, Massimiliano  and Rocchetto, Andrea  and Severini, Simone  and Wossnig, Leonard },
title = {Quantum machine learning: a classical perspective},
journal = {Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences},
volume = {474},
number = {2209},
pages = {20170551},
year = {2018},
doi = {10.1098/rspa.2017.0551},
URL = {https://royalsocietypublishing.org/doi/abs/10.1098/rspa.2017.0551},
eprint = {https://royalsocietypublishing.org/doi/pdf/10.1098/rspa.2017.0551},
}

@inproceedings{10.5555/645529.657980,
author = {Smola, Alex J. and Sch\"{o}kopf, Bernhard},
title = {Sparse Greedy Matrix Approximation for Machine Learning},
year = {2000},
isbn = {1558607072},
publisher = {Morgan Kaufmann Publishers Inc.},
address = {San Francisco, CA, USA},
booktitle = {Proceedings of the Seventeenth International Conference on Machine Learning},
pages = {911–918},
numpages = {8},
series = {ICML ’00},
url={https://dl.acm.org/doi/10.5555/645529.657980}
}

@incollection{10.5555/3008751.3008847,
  title = {Using the Nystr\"{o}m Method to Speed Up Kernel Machines},
  author = {Williams, Christopher K. I. and Seeger, Matthias},
  booktitle = {Advances in Neural Information Processing Systems 13},
  editor = {T. K. Leen and T. G. Dietterich and V. Tresp},
  pages = {682--688},
  year = {2001},
  publisher = {MIT Press},
  url = {http://papers.nips.cc/paper/1866-using-the-nystrom-method-to-speed-up-kernel-machines.pdf}
}

@article{10.5555/944790.944812,
  author = {Fine, Shai and Scheinberg, Katya},
  title = {Efficient Svm Training Using Low-Rank Kernel Representations},
  year = {2002},
  issue_date = {March 2002},
  publisher = {JMLR.org},
  volume = {2},
  issn = {1532-4435},
  journal = {Journal of Machine Learning Research},
  % % month =  mar,
  pages = {243–264},
  numpages = {22},
  url={http://www.jmlr.org/papers/v2/fine01a.html}
}

@incollection{NIPS2014_5238,
  title = {Scalable Kernel Methods via Doubly Stochastic Gradients},
  author = {Dai, Bo and Xie, Bo and He, Niao and Liang, Yingyu and Raj, Anant and Balcan, Maria-Florina F and Song, Le},
  booktitle = {Advances in Neural Information Processing Systems 27},
  editor = {Z. Ghahramani and M. Welling and C. Cortes and N. D. Lawrence and K. Q. Weinberger},
  pages = {3041--3049},
  year = {2014},
  publisher = {Curran Associates, Inc.},
  url = {http://papers.nips.cc/paper/5238-scalable-kernel-methods-via-doubly-stochastic-gradients.pdf}
}

@InProceedings{pmlr-v99-jain19a,
  title = 	 {Making the Last Iterate of SGD Information Theoretically Optimal},
  author = 	 {Jain, Prateek and Nagaraj, Dheeraj and Netrapalli, Praneeth},
  booktitle = 	 {Proceedings of the Thirty-Second Conference on Learning Theory},
  pages = 	 {1752--1755},
  year = 	 {2019},
  editor = 	 {Beygelzimer, Alina and Hsu, Daniel},
  volume = 	 {99},
  series = 	 {Proceedings of Machine Learning Research},
  address = 	 {Phoenix, USA},
  % % month =  	 {25--28 Jun},
  publisher = 	 {PMLR},
  pdf = 	 {http://proceedings.mlr.press/v99/jain19a/jain19a.pdf},
  url = 	 {http://proceedings.mlr.press/v99/jain19a.html},
}

@article{montanaro2016quantum,
  title={Quantum algorithms: an overview},
  author={Montanaro, Ashley},
  journal={npj Quantum Information},
  volume={2},
  number={1},
  pages={1--8},
  year={2016},
  publisher={Nature Publishing Group},
  url={https://www.nature.com/articles/npjqi201523}
}


@incollection{NIPS2018_7598,
title = {But How Does It Work in Theory? Linear SVM with Random Features},
author = {Sun, Yitong and Gilbert, Anna and Tewari, Ambuj},
booktitle = {Advances in Neural Information Processing Systems 31},
editor = {S. Bengio and H. Wallach and H. Larochelle and K. Grauman and N. Cesa-Bianchi and R. Garnett},
pages = {3379--3388},
year = {2018},
publisher = {Curran Associates, Inc.},
url = {http://papers.nips.cc/paper/7598-but-how-does-it-work-in-theory-linear-svm-with-random-features.pdf}
}

@unpublished{Shahrampour2019,
  title = "On Sampling Random Features From Empirical Leverage Scores: Implementation and Theoretical Guarantees",
  author={Shahrampour, Shahin and Kolouri, Soheil},
  arxivPrefix = {arxiv},
  arxivId = {1903.08329},
  URL = {https://arxiv.org/abs/1903.08329},
  % month={Mar},
  year = {2019},
}

@InProceedings{pmlr-v70-avron17a,
  title =      {Random {F}ourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guarantees},
  author =   {Avron, Haim and Kapralov, Michael and Musco, Cameron and Musco, Christopher and Velingker, Ameya and Zandieh, Amir},
  booktitle =      {Proceedings of the 34th International Conference on Machine Learning},
  pages =    {253--262},
  year =   {2017},
  editor =   {Doina Precup and Yee Whye Teh},
  volume =     {70},
  series =   {Proceedings of Machine Learning Research},
  address =    {International Convention Centre, Sydney, Australia},
  % % month =     {06--11 Aug},
  publisher =      {PMLR},
  pdf =      {http://proceedings.mlr.press/v70/avron17a/avron17a.pdf},
  url =    {http://proceedings.mlr.press/v70/avron17a.html},
}

@article{Havlivcek2019supervised,
  doi = {10.1038/s41586-019-0980-2},
  url = {https://doi.org/10.1038/s41586-019-0980-2},
  year = {2019},
  % % month =  mar,
  publisher = {Springer Science and Business Media {LLC}},
  volume = {567},
  number = {7747},
  pages = {209--212},
  author = {Vojt{{e}}ch Havl{\'{i}}{{c}}ek and Antonio D. C{\'{o}}rcoles and Kristan Temme and Aram W. Harrow and Abhinav Kandala and Jerry M. Chow and Jay M. Gambetta},
  title = {Supervised learning with quantum-enhanced feature spaces},
  journal = {Nature}
} 


@article{Liu2019,
  title = "Random Fourier Features via Fast Surrogate Leverage Weighted Sampling",
  author={Liu, Fanghui and Huang, Xiaolin and Chen, Yudong and Yang, Jie and Suykens, Johan A.K.},
  arxivId = {1911.09158},
  arxivPrefix = {arXiv},
  URL = {https://arxiv.org/abs/1911.09158},
  % month={Nov},
  year = {2019},
}


@InProceedings{pmlr-v30-Bach13,
  title = 	 {Sharp analysis of low-rank  kernel matrix approximations},
  author = 	 {Francis Bach},
  booktitle = 	 {Proceedings of the 26th Annual Conference on Learning Theory},
  pages = 	 {185--209},
  year = 	 {2013},
  editor = 	 {Shai Shalev-Shwartz and Ingo Steinwart},
  volume = 	 {30},
  series = 	 {Proceedings of Machine Learning Research},
  address = 	 {Princeton, NJ, USA},
  % month = 	 {12--14 Jun},
  publisher = 	 {PMLR},
  pdf = 	 {http://proceedings.mlr.press/v30/Bach13.pdf},
  url = 	 {http://proceedings.mlr.press/v30/Bach13.html},
}

@incollection{NIPS2015_5716,
  title = {Fast Randomized Kernel Ridge Regression with Statistical Guarantees},
  author = {Alaoui, Ahmed and Mahoney, Michael W},
  booktitle = {Advances in Neural Information Processing Systems 28},
  editor = {C. Cortes and N. D. Lawrence and D. D. Lee and M. Sugiyama and R. Garnett},
  pages = {775--783},
  year = {2015},
  publisher = {Curran Associates, Inc.},
  url = {http://papers.nips.cc/paper/5716-fast-randomized-kernel-ridge-regression-with-statistical-guarantees.pdf}
}

@incollection{NIPS2018_7810,
title = {On Fast Leverage Score Sampling and Optimal Learning},
author = {Rudi, Alessandro and Calandriello, Daniele and Carratino, Luigi and Rosasco, Lorenzo},
booktitle = {Advances in Neural Information Processing Systems 31},
editor = {S. Bengio and H. Wallach and H. Larochelle and K. Grauman and N. Cesa-Bianchi and R. Garnett},
pages = {5672--5682},
year = {2018},
publisher = {Curran Associates, Inc.},
url = {http://papers.nips.cc/paper/7810-on-fast-leverage-score-sampling-and-optimal-learning.pdf}
}

@article{Subramanian_2019,
  doi = {10.1088/2399-6528/ab25a2},
  url = {https://iopscience.iop.org/article/10.1088/2399-6528/ab25a2},
  year = 2019,
  % month = {jun},
  publisher = {{IOP} Publishing},
  volume = {3},
  number = {6},
  pages = {065002},
  author = {Sathyawageeswar Subramanian and Stephen Brierley and Richard Jozsa},
  title = {Implementing smooth functions of a Hermitian matrix on a quantum computer},
  journal = {Journal of Physics Communications},
  arxivPrefix = {arXiv},
  arxivID  = {1806.06885}
}


@InProceedings{pmlr-v97-li19k,
  title = 	 {Towards a Unified Analysis of Random {F}ourier Features},
  author = 	 {Li, Zhu and Ton, Jean-Francois and Oglic, Dino and Sejdinovic, Dino},
  booktitle = 	 {Proceedings of the 36th International Conference on Machine Learning},
  pages = 	 {3905--3914},
  year = 	 {2019},
  editor = 	 {Chaudhuri, Kamalika and Salakhutdinov, Ruslan},
  volume = 	 {97},
  series = 	 {Proceedings of Machine Learning Research},
  address = 	 {Long Beach, California, USA},
  % month = 	 {09--15 Jun},
  publisher = 	 {PMLR},
  pdf = 	 {http://proceedings.mlr.press/v97/li19k/li19k.pdf},
  url = 	 {http://proceedings.mlr.press/v97/li19k.html},
}


@article{Arunachalam2017,
archivePrefix = {arXiv},
arxivId = {1701.06806},
author = {Arunachalam, Srinivasan and de Wolf, Ronald},
doi = {10.1145/3106700.3106710},
eprint = {1701.06806},
file = {:home/agni/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Arunachalam, de Wolf - 2017 - A Survey of Quantum Learning Theory.pdf:pdf;:home/agni/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Arunachalam, de Wolf - 2017 - A Survey of Quantum Learning Theory(2).pdf:pdf},
issn = {0163-5700},
journal = {ACM SIGACT News},
% month = {jan},
number = {2},
pages = {41--67},
title = {{A Survey of Quantum Learning Theory}},
url = {http://arxiv.org/abs/1701.06806},
volume = {48},
year = {2017}
}

@inproceedings{Bshouty1995,
  doi = {10.1145/225298.225312},
  url = {https://doi.org/10.1145/225298.225312},
  year = {1995},
  publisher = {{ACM} Press},
  author = {Nader H. Bshouty and Jeffrey C. Jackson},
  title = {Learning {DNF} over the uniform distribution using a quantum example oracle},
  booktitle = {Proceedings of the eighth annual conference on Computational learning theory  - {COLT} {\textquotesingle}95}
}

%---------------------------------
% ham-sim, quantum algos
%---------------------------------

@misc{wang2018quantum,
    title={A quantum algorithm for simulating non-sparse Hamiltonians},
    author={Chunhao Wang and Leonard Wossnig},
    year={2018},
    eprint={1803.08273},
    archivePrefix={arXiv},
    primaryClass={quant-ph}
}

@article{Gidney2018halvingAddition,
  doi = {10.22331/q-2018-06-18-74},
  url = {https://doi.org/10.22331/q-2018-06-18-74},
  title = {Halving the cost of quantum addition},
  author = {Gidney, Craig},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {2},
  pages = {74},
  % month = jun,
  year = {2018}
}




%---------------------------------
% sparsity testing
%---------------------------------

@Inbook{Brassard2002QuantumEstimation,
  doi = {10.1090/conm/305/05215},
  url = {https://doi.org/10.1090/conm/305/05215},
  year = {2002},
  bookTitle="Quantum Computation and Information",
  publisher = {AMS Contemporary Mathematics series},
  pages = {53--74},
  author = {Gilles Brassard and Peter H{\o}yer and Michele Mosca and Alain Tapp},
  title = {Quantum amplitude amplification and estimation},
  volume = {305},
  url = {http://arxiv.org/abs/quant-ph/0005055},
  arxivId = {quant-ph/0005055},
  editor="Samuel J. Lomonaco and Jr. and Howard E. Brandt"
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@article{Berry2014High-orderEquations,
    title = {{High-order quantum algorithm for solving linear differential equations}},
    year = {2014},
    journal = {Journal of Physics A: Mathematical and Theoretical},
    author = {Berry, Dominic W.},
    number = {10},
    % month = {3},
    pages = {105301},
    volume = {47},
    url = {http://stacks.iop.org/1751-8121/47/i=10/a=105301?key=crossref.3b213c2a3b3e8d0c4d50d617e8e8d3bb},
    doi = {10.1088/1751-8113/47/10/105301},
    issn = {1751-8113},
    arxivId = {1010.2745}
}


@article{Berry2012,
    title = {{Black-box Hamiltonian Simulation and Unitary Implementation}},
    year = {2012},
    journal = {Quantum Information {\&} Computation},
    author = {Berry, Dominic W. and Childs, Andrew M.},
    number = {1-2},
    pages = {29–62},
    volume = {12},
    url = {https://dl.acm.org/doi/10.5555/2231036.2231040},
    issn = {1533-7146},
    arxivId = {0910.4157},
    doi={10.26421/QIC12.1-2}
}


@article{Berry2015SimulatingSeries,
    title = {{Simulating Hamiltonian dynamics with a truncated taylor series}},
    year = {2015},
    journal = {Physical Review Letters},
    author = {Berry, Dominic W. and Childs, Andrew M. and Cleve, Richard and Kothari, Robin and Somma, Rolando D.},
    number = {9},
    pages = {1--5},
    volume = {114},
    isbn = {0031-9007},
    doi = {10.1103/PhysRevLett.114.090502},
    issn = {10797114},
    pmid = {25793789},
    arxivId = {1412.4687}
}



@article{Berry2015HamiltonianParameters,
    title = {{Hamiltonian Simulation with Nearly Optimal Dependence on all Parameters}},
    year = {2015},
    journal = {Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS},
    author = {Berry, Dominic W. and Childs, Andrew M. and Kothari, Robin},
    pages = {792--809},
    volume = {2015-Decem},
    isbn = {9781467381918},
    doi = {10.1109/FOCS.2015.54},
    issn = {02725428},
    arxivId = {1501.01715v1},
    keywords = {Hamiltonian simulation, quantum algorithms}
}

@article{Berry2017,
author="Berry, Dominic W.
and Childs, Andrew M.
and Ostrander, Aaron
and Wang, Guoming",
title="Quantum Algorithm for Linear Differential Equations with Exponentially Improved Dependence on Precision",
journal="Communications in Mathematical Physics",
year="2017",
% month="Dec",
day="01",
volume="356",
number="3",
pages="1057--1081",
issn="1432-0916",
doi="10.1007/s00220-017-3002-y",
url="https://doi.org/10.1007/s00220-017-3002-y"
}

@InProceedings{Brandao2017ExponentialLearning,
  author =  {Fernando G. S. L. Brand{\~a}o and Amir Kalev and Tongyang Li and Cedric Yen-Yu Lin and Krysta M. Svore and Xiaodi Wu},
  title = {{Quantum SDP Solvers: Large Speed-Ups, Optimality, and Applications to Quantum Learning}},
  booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages = {27:1--27:14},
  series =  {Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =  {978-3-95977-109-2},
  ISSN =  {1868-8969},
  year =  {2019},
  volume =  {132},
  editor =  {Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi},
  publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address = {Dagstuhl, Germany},
  URL =   {http://drops.dagstuhl.de/opus/volltexte/2019/10603},
  URN =   {urn:nbn:de:0030-drops-106036},
  doi =   {10.4230/LIPIcs.ICALP.2019.27},
  annote =  {Keywords: quantum algorithms, semidefinite program, convex optimization},
  url = {http://arxiv.org/abs/1710.02581},
  arxivId = {1710.02581},
  arxivPrefix = {arXiv}
}


@article{Cao2013QuantumEquation,
    title = {{Quantum algorithm and circuit design solving the Poisson equation}},
    year = {2013},
    journal = {New Journal of Physics},
    author = {Cao, Yudong and Papageorgiou, Anargyros and Petras, Iasonas and Traub, Joseph and Kais, Sabre},
    number = {1},
    % month = {1},
    pages = {013021},
    volume = {15},
    url = {http://stacks.iop.org/1367-2630/15/i=1/a=013021?key=crossref.58e36dfe0f38518927f23933e4448c71},
    doi = {10.1088/1367-2630/15/1/013021},
    issn = {1367-2630},
    arxivId = {1207.2485}
}

@InProceedings{Chakraborty2018TheSimulation,
  author =  {Shantanav Chakraborty and Andr{\'a}s Gily{\'e}n and Stacey Jeffery},
  title = {{The Power of Block-Encoded Matrix Powers: Improved Regression Techniques via Faster Hamiltonian Simulation}},
  booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages = {33:1--33:14},
  series =  {Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =  {978-3-95977-109-2},
  ISSN =  {1868-8969},
  year =  {2019},
  volume =  {132},
  editor =  {Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi},
  publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address = {Dagstuhl, Germany},
  URL =   {http://drops.dagstuhl.de/opus/volltexte/2019/10609},
  URN =   {urn:nbn:de:0030-drops-106092},
  doi =   {10.4230/LIPIcs.ICALP.2019.33},
  annote =  {Keywords: Quantum algorithms, Hamiltonian simulation, Quantum machine learning},
  url = {http://arxiv.org/abs/1804.01973},
  arxivId = {1804.01973},
  arxivPrefix = {arxiv}
}


@article{Childs2015,
    title = {{Quantum Algorithm for Systems of Linear Equations with Exponentially Improved Dependence on Precision}},
    year = {2017},
    journal = {SIAM Journal on Computing},
    author = {Childs, Andrew M. and Kothari, Robin and Somma, Rolando D.},
    number = {6},
    % month = {1},
    pages = {1920--1950},
    volume = {46},
    url = {http://arxiv.org/abs/1511.02306},
    doi = {10.1137/16M1087072},
    issn = {0097-5397},
    arxivId = {1511.02306},
    keywords = {()}
}

@article{Childs2012HamiltonianOperations,
 author = {Childs, Andrew M. and Wiebe, Nathan},
 title = {Hamiltonian Simulation Using Linear Combinations of Unitary Operations},
 journal = {Quantum Information {\&} Computation},
 issue_date = {November 2012},
 volume = {12},
 number = {11-12},
 % month = nov,
 year = {2012},
 issn = {1533-7146},
 pages = {901--924},
 numpages = {24},
 url = {http://dl.acm.org/citation.cfm?id=2481569.2481570},
 acmid = {2481570},
 publisher = {Rinton Press, Incorporated},
 address = {Paramus, NJ},
 keywords = {quantum computing, quantum simulation},
} 

@article{Chowdhury2016,
 author = {Chowdhury, Anirban Narayan and Somma, Rolando D.},
 title = {Quantum Algorithms for Gibbs Sampling and Hitting-time Estimation},
 journal = {Quantum Information {\&} Computation},
 issue_date = {February 2017},
 volume = {17},
 number = {1-2},
 year = {2017},
 issn = {1533-7146},
 pages = {41--64},
 url = {http://dl.acm.org/citation.cfm?id=3179483.3179486},
 acmid = {3179486},
 publisher = {Rinton Press, Incorporated},
 keywords = {quantum algorithms, stochastic processes},
 arxivId = {1603.02940},
 arxivPrefix = {arXiv}
} 

@article{Grover2002CreatingDistributions,
    title = {{Creating superpositions that correspond to efficiently integrable probability distributions}},
    year = {2002},
    author = {Grover, Lov and Rudolph, Terry},
    url = {http://arxiv.org/abs/quant-ph/0208112},
    journal = {quant-ph/0208112}
}

@article{Harrow2009QuantumEquations,
    title = {{Quantum Algorithm for Linear Systems of Equations}},
    year = {2009},
    journal = {Physical Review Letters},
    author = {Harrow, Aram W and Hassidim, Avinatan and Lloyd, Seth},
    number = {15},
    % month = {10},
    pages = {150502},
    volume = {103},
    url = {http://arxiv.org/abs/0811.3171},
    doi = {10.1103/PhysRevLett.103.150502},
    issn = {0031-9007},
    arxivId = {0811.3171}
}

@InProceedings{Kerenidis2016QuantumSystems,
  author =  {Iordanis Kerenidis and Anupam Prakash},
  title = {{Quantum Recommendation Systems}},
  booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
  pages = {49:1--49:21},
  series =  {Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =  {978-3-95977-029-3},
  ISSN =  {1868-8969},
  year =  {2017},
  volume =  {67},
  editor =  {Christos H. Papadimitriou},
  publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address = {Dagstuhl, Germany},
  URL =   {http://drops.dagstuhl.de/opus/volltexte/2017/8154},
  URN =   {urn:nbn:de:0030-drops-81541},
  doi =   {10.4230/LIPIcs.ITCS.2017.49},
  arxivPrefix = {arXiv},
  arxivId = {1603.08675}
}


@article{Klappenecker2003EngineeringAlgorithms,
    title = {{Engineering functional quantum algorithms}},
    year = {2003},
    journal = {Physical Review A},
    author = {Klappenecker, Andreas and R{\"{o}}tteler, Martin},
    number = {1},
    % month = {1},    
    volume = {67},
    url = {http://arxiv.org/abs/quant-ph/0208130},
    doi = {10.1103/PhysRevA.67.010302},
    issn = {1050-2947},
    arxivId = {quant-ph/0208130}
}


@article{Kothari2014EfficientComplexity,
    title = {{Efficient algorithms in quantum query complexity}},
    publisher = {University of Waterloo},
    year = {2014},
    author = {Kothari, Robin},
    % pages = {1-137},
    url = {http://hdl.handle.net/10012/8625}
}

% https://uwspace.uwaterloo.ca/bitstream/handle/10012/8625/Kothari_Robin.pdf%5Cnhttps://uwspace.uwaterloo.ca/handle/10012/8625

@article{Leyton2008AEquations,
    title = {{A quantum algorithm to solve nonlinear differential equations}},
    year = {2008},
    author = {Leyton, Sarah K. and Osborne, Tobias J.},
    url = {http://arxiv.org/abs/0812.4423},
    journal = {arXiv:0812.4423}
}

@article{Lloyd2014QuantumAnalysis,
    title = {{Quantum principal component analysis}},
    year = {2014},
    journal = {Nature Physics},
    author = {Lloyd, Seth and Mohseni, Masoud and Rebentrost, Patrick},
    number = {9},
    pages = {631--633},
    volume = {10},
    url = {http://www.nature.com/doifinder/10.1038/nphys3029},
    isbn = {1745-2473{\textbackslash}r1745-2481},
    doi = {10.1038/nphys3029},
    issn = {1745-2473},
    arxivPrefix = {arXiv},
    arxivId = {arXiv:1307.0401v2}
}

@article{Low2017OptimalProcessing,
    title = {{Optimal Hamiltonian Simulation by Quantum Signal Processing}},
    year = {2017},
    journal = {Physical Review Letters},
    author = {Low, Guang Hao and Chuang, Isaac L},
    number = {1},
    % month = {1},
    pages = {010501},
    volume = {118},
    url = {http://arxiv.org/abs/1606.02685},
    doi = {10.1103/PhysRevLett.118.010501},
    issn = {0031-9007},
    arxivId = {1606.02685},
    keywords = {0367Ac, 8970Eg, PACS numbers}
}


@article{Low2016,
    title = {{Hamiltonian Simulation by Qubitization}},
    year = {2016},
    author = {Low, Guang Hao and Chuang, Isaac L.},
    url = {http://arxiv.org/abs/1610.06546},
    journal = {arXiv:1610.06546}
}

@article{Patel2017EfficientApplications,
  doi = {10.1142/s021974991850048x},
  url = {http://arxiv.org/abs/1710.01984},
  year = {2018},
  month = sep,
  publisher = {World Scientific Pub Co Pte Lt},
  volume = {16},
  number = {06},
  pages = {1850048},
  author = {Apoorva Patel and Anjani Priyadarsini},
  title = {Efficient quantum algorithms for state measurement and linear algebra applications},
  journal = {International Journal of Quantum Information},
  arxivId = {1710.01984},
  arxivPrefix = {arXiv}
}

@article{Romero2017StrategiesAnsatz,
arxivPrefix = {arXiv}, 
arxivId = {1701.02691},
author = {Romero, Jonathan and Babbush, Ryan and McClean, Jarrod R. and Hempel, Cornelius and Love, Peter and Aspuru-Guzik, Al{\'{a}}n},
doi = {10.1088/2058-9565/aad3e4},
eprint = {1701.02691},
isbn = {1070-9878},
issn = {2058-9565},
journal = {Quantum Science and Technology},
% month = {jul},
number = {1},
pages = {4--11},
pmid = {24335434},
title = {{Strategies for quantum computing molecular energies using the unitary coupled cluster ansatz}},
url = {http://arxiv.org/abs/1701.02691},
volume = {5},
year = {2017}
}


@article{Somma2002SimulatingNetworks,
    title = {{Simulating physical phenomena by quantum networks}},
    year = {2002},
    journal = {Physical Review A},
    author = {Somma, Rolando D. and Rtiz, G. and Gubernatis, J. E. and Knill, E. and Laflamme, R.},
    number = {4},
    pages = {042323},
    volume = {65},
    url = {http://link.aps.org/doi/10.1103/PhysRevA.65.042323},
    doi = {10.1103/PhysRevA.65.042323},
    issn = {1050-2947},
    arxivId = {arXiv:quant-ph/0108146v1},
    arxivPrefix = {arXiv},
    eprint = {0108146v1},
    primaryClass = {quant-ph}
}

@article{VanApeldoorn2018ImprovementsApplications,
    title = {{Improvements in Quantum SDP-Solving with Applications}},
    year = {2018},
    author = {van Apeldoorn, Joran and Gily{\'{e}}n, András},
    journal = {arXiv:1804.05058v1}
}

@article{vanApeldoorn2017QuantumBounds,
    title = {{Quantum SDP-Solvers: Better upper and lower bounds}},
    year = {2017},
    journal = {Proceedings of the IEEE Annual Symposium on Foundations of Computer Science},
    author = {Van Apeldoorn, Joran and Gily{\'{e}}n, Andr{\'{a}}s and Gribling, Sander and de Wolf, Ronald and Gilyen, Andras and Gribling, Sander and de Wolf, Ronald},
    number = {617},
    % month =  {5},
    url = {http://arxiv.org/abs/1705.01843},
    isbn = {9781538634646},
    doi = {10.1109/FOCS.2017.44},
    issn = {02725428},
    arxivId = {1705.01843},
    keywords = {Linear programs, Lower bounds, Quantum algorithms, Semidefinite programs}
}


@article{KP2017,
    title = {{Quantum gradient descent for linear systems and least squares}},
    year = {2017},
    author = {Kerenidis, Iordanis  and Prakash, Anupam},
    arxivId = {1704.04992},
    arXivPrefix = {arXiv},
    url = {http://arxiv.org/abs/1704.04992}
}

@inproceedings{Gilyen2018QuantumArithmetics,
 author = {Gily\'{e}n, Andr\'{a}s and Su, Yuan and Low, Guang Hao and Wiebe, Nathan},
 title = {Quantum Singular Value Transformation and beyond: Exponential Improvements for Quantum Matrix Arithmetics},
 year = {2019},
 isbn = {9781450367059},
 % publisher = {Association for Computing Machinery},
 address = {New York, NY, USA},
 url={https://dl.acm.org/doi/10.1145/3313276.3316366},
 doi = {10.1145/3313276.3316366},
 booktitle = {Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing},
 pages = {193–204},
 numpages = {12},
 keywords = {block-encdoing, quantum signal processing, qubitization},
 location = {Phoenix, AZ, USA},
 arxivPrefix = {arXiv},
 arxivId = {1806.01838},
 series = {STOC 2019},
 eprint = {1806.01838},
}

@article{Thacher1964,
 author = {Thacher,Jr., Henry C.},
 title = {Conversion of a Power to a Series of Chebyshev Polynomials},
 journal = {Commun. ACM},
 issue_date = {March 1964},
 volume = {7},
 number = {3},
 % month = mar,
 year = {1964},
 issn = {0001-0782},
 pages = {181--182},
 numpages = {2},
 url = {http://doi.acm.org/10.1145/363958.363998},
 doi = {10.1145/363958.363998},
 acmid = {363998},
 publisher = {ACM},
 address = {New York, NY, USA},
} 


@article{Sanders2019statePrep,
  title = {Black-Box Quantum State Preparation without Arithmetic},
  author = {Sanders, Yuval R. and Low, Guang Hao and Scherer, Artur and Berry, Dominic W.},
  journal = {Phys. Rev. Lett.},
  volume = {122},
  issue = {2},
  pages = {020502},
  numpages = {5},
  year = {2019},
  % month = {Jan},
  publisher = {American Physical Society},
  doi = {10.1103/PhysRevLett.122.020502},
  url = {https://link.aps.org/doi/10.1103/PhysRevLett.122.020502},
  arxivPrefix = {arXiv},
  arxivId = {1807.03206},
  eprint = {1807.03206},
}

@article{guerreschi18,
  title = {Repeat-until-success circuits with fixed-point oblivious amplitude amplification},
  author = {Guerreschi, Gian Giacomo},
  journal = {Phys. Rev. A},
  volume = {99},
  issue = {2},
  pages = {022306},
  numpages = {10},
  year = {2019},
 % % month = {Feb},
  publisher = {American Physical Society},
  doi = {10.1103/PhysRevA.99.022306},
  url = {https://link.aps.org/doi/10.1103/PhysRevA.99.022306},
  arxivPrefix = {arXiv},
  eprint = {1808.02900}
}

@misc{Herbert,
    title={Spectral sparsification of matrix inputs as a preprocessing step for quantum algorithms},
    author={Steven Herbert and Sathyawageeswar Subramanian},
    year={2019},
    eprint={1910.02861},
    archivePrefix={arXiv},
    primaryClass={quant-ph}
}

@misc{Yamasaki,
    title={Fast Quantum Algorithm for Learning with Optimized Random Features},
    author={Hayata Yamasaki and Sathyawageeswar Subramanian and Sho Sonoda and Masato Koashi},
    year={2020},
    eprint={2004.10756},
    archivePrefix={arXiv},
    primaryClass={quant-ph}
}

@misc{Bausch,
    title={A Quantum Search Decoder for Natural Language Processing},
    author={Johannes Bausch and Sathyawageeswar Subramanian and Stephen Piddock},
    year={2019},
    eprint={1909.05023},
    archivePrefix={arXiv},
    primaryClass={quant-ph}
}

@misc{Hsieh,
    title={Quantum algorithm for estimating Renyi entropies of quantum states},
    author={Sathyawageeswar Subramanian and Min-Hsiu Hsieh},
    year={2019},
    eprint={1908.05251},
    archivePrefix={arXiv},
    primaryClass={quant-ph}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@article{PhysRevA.51.2738,
  title = {Quantum coding},
  author = {Schumacher, Benjamin},
  journal = {Phys. Rev. A},
  volume = {51},
  issue = {4},
  pages = {2738--2747},
  numpages = {0},
  year = {1995},
  % month =  {Apr},
  publisher = {American Physical Society},
  doi = {10.1103/PhysRevA.51.2738},
  url = {https://link.aps.org/doi/10.1103/PhysRevA.51.2738}
}

@article{Low2016,
archivePrefix = {arXiv},
arxivId = {1610.06546},
author = {Low, Guang Hao and Chuang, Isaac L.},
doi = {10.1103/PhysRevLett.118.010501},
eprint = {1610.06546},
issn = {0031-9007},
journal = {Physical Review Letters},
keywords = {0367Ac,8970Eg,PACS numbers,novel?},
% month =  {jan},
number = {1},
pages = {010501},
title = {{Optimal Hamiltonian Simulation by Quantum Signal Processing}},
url = {http://arxiv.org/abs/1606.02685 http://dx.doi.org/10.1103/PhysRevLett.118.010501 https://link.aps.org/doi/10.1103/PhysRevLett.118.010501 http://arxiv.org/abs/1610.06546},
volume = {118},
year = {2017}
}


    
@article{Zhang2018tailInequalities, 
    title = {{Matrix Infinitely Divisible Series: Tail Inequalities and Applications in Optimization}}, 
    year = {2018}, 
    author = {Zhang, Chao and Gao, Xianjie and Hsieh, Min-Hsiu and Hang, Hanyuan and Tao, Dacheng}, 
    arxivId = {1809.00781},
    arxivPrefix = {arXiv}, eprint = {1809.00781}}

@article{Hastings2010MeasuringSimulations, 
  title = {{Measuring renyi entanglement entropy in quantum Monte Carlo simulations}}, 
  year = {2010}, 
  journal = {Physical Review Letters}, 
  author = {Hastings, Matthew B. and Gonz{\'{a}}lez, Iv{\'{a}}n and Kallin, Ann B. and Melko, Roger G.}, 
  number = {15}, 
  pages = {157201}, 
  volume = {104}, 
  isbn = {1476-4687 (Electronic) 0028-0836 (Linking)}, 
  doi = {10.1103/PhysRevLett.104.157201}, 
  issn = {00319007}, 
  pmid = {20482013}, 
  arxivId = {1001.2335} 
}

@article{Datta08DQC,
  title = {Quantum Discord and the Power of One Qubit},
  author = {Datta, Animesh and Shaji, Anil and Caves, Carlton M.},
  journal = {Phys. Rev. Lett.},
  volume = {100},
  issue = {5},
  pages = {050502},
  numpages = {4},
  year = {2008},
  % month =  {Feb},
  publisher = {American Physical Society},
  doi = {10.1103/PhysRevLett.100.050502},
  url = {https://link.aps.org/doi/10.1103/PhysRevLett.100.050502}
}

@article{Fujii18DQC1,
  title = {Impossibility of Classically Simulating One-Clean-Qubit Model with Multiplicative Error},
  author = {Fujii, Keisuke and Kobayashi, Hirotada and Morimae, Tomoyuki and Nishimura, Harumichi and Tamate, Shuhei and Tani, Seiichiro},
  journal = {Phys. Rev. Lett.},
  volume = {120},
  issue = {20},
  pages = {200502},
  numpages = {6},
  year = {2018},
  % month =  {May},
  publisher = {American Physical Society},
  doi = {10.1103/PhysRevLett.120.200502},
  url = {https://link.aps.org/doi/10.1103/PhysRevLett.120.200502}
}

@article{Morimae14DQC1hardness,
  title = {Hardness of Classically Simulating the One-Clean-Qubit Model},
  author = {Morimae, Tomoyuki and Fujii, Keisuke and Fitzsimons, Joseph F.},
  journal = {Phys. Rev. Lett.},
  volume = {112},
  issue = {13},
  pages = {130502},
  numpages = {5},
  year = {2014},
  % month =  {Apr},
  publisher = {American Physical Society},
  doi = {10.1103/PhysRevLett.112.130502},
  url = {https://link.aps.org/doi/10.1103/PhysRevLett.112.130502}
}

@inproceedings{Schulman99NMR,
 author = {Schulman, Leonard J. and Vazirani, Umesh V.},
 title = {Molecular Scale Heat Engines and Scalable Quantum Computation},
 booktitle = {Proceedings of the Thirty-first Annual ACM Symposium on Theory of Computing},
 series = {STOC '99},
 year = {1999},
 isbn = {1-58113-067-8},
 location = {Atlanta, Georgia, USA},
 pages = {322--329},
 numpages = {8},
 url = {http://doi.acm.org/10.1145/301250.301332},
 doi = {10.1145/301250.301332},
 acmid = {301332},
 publisher = {ACM},
 address = {New York, NY, USA},
} 

@article{Berry2018ImprovedHamiltonians,
    title = {{Improved techniques for preparing eigenstates of fermionic Hamiltonians}},
    year = {2018},
    journal = {npj Quantum Information},
    author = {Berry, Dominic W. and Kieferov{\'{a}}, Mária and Scherer, Artur and Sanders, Yuval R. and Low, Guang Hao and Wiebe, Nathan and Gidney, Craig and Babbush, Ryan},
    number = {1},
    % month =  {12},
    pages = {22},
    volume = {4},
    url = {http://arxiv.org/abs/1711.10460%0Ahttp://dx.doi.org/10.1038/s41534-018-0071-5 http://www.nature.com/articles/s41534-018-0071-5},
    doi = {10.1038/s41534-018-0071-5},
    issn = {2056-6387},
    arxivId = {1711.10460}
}

@article{Ge2017FasterQubits,
    title = {{Faster ground state preparation and high-precision ground energy estimation with fewer qubits}},
    year = {2017},
    author = {Ge, Yimin and Tura, Jordi and Cirac, J. Ignacio},
    pages = {1--25},
    url = {http://arxiv.org/abs/1712.03193},
    arxivId = {1712.03193}
}

@article{McClean2014,
    title = {{Exploiting locality in quantum computation for quantum chemistry}},
    year = {2014},
    journal = {Journal of Physical Chemistry Letters},
    author = {McClean, Jarrod R. and Babbush, Ryan and Love, Peter J. and Aspuru-Guzik, Alán},
    number = {24},
    pages = {4368--4380},
    volume = {5},
    isbn = {1948-7185},
    doi = {10.1021/jz501649m},
    issn = {19487185},
    pmid = {26273989},
    arxivId = {arXiv:1407.7863v1}
}


@article{Bernstein1998,
author = {Bernstein, Daniel J},
doi = {10.1090/S0025-5718-98-00952-1},
issn = {0025-5718},
journal = {Mathematics of Computation},
% month =  {jul},
number = {223},
pages = {1253--1284},
title = {{Detecting perfect powers in essentially linear time}},
url = {http://www.ams.org/journal-getitem?pii=S0025-5718-98-00952-1},
volume = {67},
year = {1998}
}


@article{Aharonov2007PottsTutte,
Author = {Dorit Aharonov and Itai Arad and Elad Eban and Zeph Landau},
Title = {Polynomial Quantum Algorithms for Additive approximations of the Potts model and other Points of the Tutte Plane},
Year = {2007},
Eprint = {arXiv:quant-ph/0702008},
}

article{Higham1986MatrixSquareRootbyNewton,
 author = {Higham, Nicholas J},
 title = {Newton's Method for the Matrix Square Root},
 journal = {Math. Comput.},
 issue_date = {April 1986},
 volume = {46},
 number = {174},
 % month =  apr,
 year = {1986},
 issn = {0025-5718},
 pages = {537--549},
 numpages = {13},
 url = {http://dx.doi.org/10.2307/2007992},
 doi = {10.2307/2007992},
 acmid = {20814},
 publisher = {American Mathematical Society},
 address = {Boston, MA, USA},
} 

@article{Guo2006Matrix-pth-root_bySchurNewton,
 author = {Guo, Chun-Hua and Higham, Nicholas J.},
 title = {A Schur-Newton Method for the Matrix \lowercase{\boldmath\$P\$}th Root and Its Inverse},
 journal = {SIAM J. Matrix Anal. Appl.},
 issue_date = {August 2006},
 volume = {28},
 number = {3},
 % month =  aug,
 year = {2006},
 issn = {0895-4798},
 pages = {788--804},
 numpages = {17},
 url = {http://dx.doi.org/10.1137/050643374},
 doi = {10.1137/050643374},
 acmid = {1237713},
 publisher = {Society for Industrial and Applied Mathematics},
 address = {Philadelphia, PA, USA},
 keywords = {Markov model, Newton's method, Schur decomposition, convergence, inverse, matrix \$p\$th root, matrix logarithm, numerical stability, preprocessing, principal \$p\$th root, transition matrix},
} 

@article{Lashkari2018PerturbationLogarithm,
Author = {Nima Lashkari and Hong Liu and Srivatsan Rajagopal},
Title = {Perturbation Theory for the Logarithm of a Positive Operator},
Year = {2018},
Eprint = {arXiv:1811.05619},
}

@Inbook{Kallberg2012,
author={K\"{a}llberg, David
and Leonenko, Nikolaj
and Seleznjev, Oleg},
editor={D\"{u}sterh\"{o}ft, Antje
and Klettke, Meike
and Schewe, Klaus-Dieter},
title="Statistical Inference for R\'{e}nyi Entropy Functionals",
bookTitle="Conceptual Modelling and Its Theoretical Foundations: Essays Dedicated to Bernhard Thalheim on the Occasion of His 60th Birthday",
year="2012",
publisher="Springer Berlin Heidelberg",
address="Berlin, Heidelberg",
pages="36--51",
isbn="978-3-642-28279-9",
doi="10.1007/978-3-642-28279-9_5",
url="https://doi.org/10.1007/978-3-642-28279-9_5"
}

@article{Montanaro2013,
archivePrefix = {arXiv},
arxivId = {1310.2035},
author = {Montanaro, Ashley and de Wolf, Ronald},
doi = {10.4086/toc.gs.2016.007},
eprint = {1310.2035},
issn = {1557-2862},
pages = {1--67},
title = {{A Survey of Quantum Property Testing}},
  url = {https://doi.org/10.4086/toc.gs.2016.007},
  year  = {2016},
  publisher = {Theory of Computing Exchange},
  volume = {1},
  number = {1},
  pages = {1--81},
  author = {Ashley Montanaro and Ronald de Wolf},
  journal = {Theory of Computing}
}

@article{Gilyen2019,
archivePrefix = {arXiv},
arxivId = {1902.00814},
author = {Gily{\'{e}}n, Andr{\'{a}}s and Li, Tongyang},
eprint = {1902.00814},
pages = {1--18},
title = {{Distributional property testing in a quantum world}},
url = {http://arxiv.org/abs/1902.00814},
year = {2019}
}

@article{Belovs2019,
archivePrefix = {arXiv},
arxivId = {1904.02192},
author = {Belovs, Aleksandrs},
eprint = {1904.02192},
pages = {1--14},
title = {{Quantum Algorithms for Classical Probability Distributions}},
url = {http://arxiv.org/abs/1904.02192},
year = {2019}
}

@article{Acharya2017,
archivePrefix = {arXiv},
arxivId = {1711.00814},
author = {Acharya, Jayadev and Issa, Ibrahim and Shende, Nirmal V. and Wagner, Aaron B.},
eprint = {1711.00814},
title = {{Measuring Quantum Entropy}},
url = {http://arxiv.org/abs/1711.00814},
year = {2017}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@inproceedings{Tang2019,
address = {New York, New York, USA},
author = {Tang, Ewin},
booktitle = {Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing - STOC 2019},
doi = {10.1145/3313276.3316310},
isbn = {9781450367059},
pages = {217--228},
publisher = {ACM Press},
title = {{A quantum-inspired classical algorithm for recommendation systems}},
url = {http://dl.acm.org/citation.cfm?doid=3313276.3316310},
isbn = {9781450367059},
year = {2019},
archivePrefix = {arXiv},
arxivId = {1807.04271}
}


@article{Montanaro2011,
archivePrefix = {arXiv},
arxivId = {arXiv:0908.3066v1},
author = {Montanaro, Ashley},
doi = {10.1007/978-3-642-18073-6_7},
eprint = {arXiv:0908.3066v1},
isbn = {3642180728},
issn = {03029743},
journal = {Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)},
pages = {77--93},
title = {{Quantum search with advice}},
volume = {6519 LNCS},
year = {2011}
}

@book{Hopcroft2001,
author = {Hopcroft, John E. and Motwani, Rajeev and Ullman, Jeffrey D.},
doi = {10.1145/568438.568455},
issn = {01635700},
journal = {ACM SIGACT News},
% month = {mar},
number = {1},
pages = {60},
title = {{Introduction to automata theory, languages, and computation, 2nd edition}},
url = {http://portal.acm.org/citation.cfm?doid=568438.568455},
volume = {32},
year = {2001}
}


@article{Jager2012,
author = {J{\"{a}}ger, Gerhard},
doi = {10.1142/S0219525911500196},
issn = {0219-5259},
journal = {Advances in Complex Systems},
% month = {may},
number = {03n04},
pages = {1--21},
title = {{Power Laws And Other Heavy-Tailed Distributions In Linguistic Typology}},
url = {http://www.worldscientific.com/doi/abs/10.1142/S0219525911500196},
volume = {15},
year = {2012}
}
@incollection{Stella2016,
author = {Stella, Massimo and Brede, Markus},
doi = {10.1007/978-3-319-29228-1_19},
pages = {219--229},
title = {{Investigating the Phonetic Organisation of the English Language via Phonological Networks, Percolation and Markov Models}},
url = {http://link.springer.com/10.1007/978-3-319-29228-1{\_}19},
year = {2016}
}


@article{nakaya1991,
author = {Nakaya, Hideki},
journal = {Nagoya Math. J.},
pages = {149--159},
publisher = {Nagoya Mathematical Journal},
title = {{The generalized divisor problem and the Riemann hypothesis}},
url = {https://projecteuclid.org:443/euclid.nmj/1118782879},
volume = {122},
year = {1991}
}

@article{Egghe2000,
author = {Egghe, Leo},
doi = {10.1023/A:1005634925734},
issn = {1588-2861},
journal = {Scientometrics},
% month = {feb},
number = {2},
pages = {237--252},
title = {{The Distribution of N-Grams}},
url = {https://doi.org/10.1023/A:1005634925734},
volume = {47},
year = {2000}
}
@article{Piantadosi2014,
author = {Piantadosi, Steven T.},
doi = {10.3758/s13423-014-0585-6},
issn = {1069-9384},
journal = {Psychonomic Bulletin {\&} Review},
% month = {oct},
number = {5},
pages = {1112--1130},
title = {{Zipf's word frequency law in natural language: A critical review and future directions}},
url = {http://link.springer.com/10.3758/s13423-014-0585-6},
volume = {21},
year = {2014}
}

@article{Goldwater2011,
author = {Goldwater, Sharon and Griffiths, Thomas L and Johnson, Mark},
journal = {Journal of Machine Learning Research},
pages = {2335--2382},
title = {{Producing Power-Law Distributions and Damping Word Frequencies with Two-Stage Language Models}},
volume = {12},
year = {2011}
}

@book{Apostol1976,
  doi = {10.1007/978-1-4757-5579-4},
  url = {https://doi.org/10.1007/978-1-4757-5579-4},
  year  = {1976},
  publisher = {Springer New York},
  author = {Tom M. Apostol},
  title = {Introduction to Analytic Number Theory}
}

@misc{Cox2007,
author = {Cox, Russ},
title = {{Regular Expression Matching Can Be Simple And Fast (but is slow in Java, Perl, PHP, Python, Ruby, ...)}},
url = {https://swtch.com/{~}rsc/regexp/regexp1.html},
year = {2007}
}
@article{Thompson1968,
author = {Thompson, Ken},
doi = {10.1145/363347.363387},
issn = {00010782},
journal = {Communications of the ACM},
% month = {jun},
number = {6},
pages = {419--422},
title = {{Programming Techniques: Regular expression search algorithm}},
url = {http://portal.acm.org/citation.cfm?doid=363347.363387},
volume = {11},
year = {1968}
}


@book{NFAFromRegexUllman1997,
address = {Boston},
author = {Ullman, Alfred Vaino Aho and Lam, Monica S. and Sethi, Ravi and D., Jeffrey},
booktitle = {Compiler construction : principles and practice},
chapter = {3.7.2},
isbn = {9780534939724},
pages = {159--163},
publisher = {PWS Pub. Co},
title = {{Construction of an NFA from a Regular Expression}},
year = {1997}
}
@incollection{Kleene1956,
address = {Princeton},
author = {Kleene, S. C.},
booktitle = {Automata Studies. (AM-34)},
doi = {10.1515/9781400882618-002},
pages = {3--42},
publisher = {Princeton University Press},
title = {{Representation of Events in Nerve Nets and Finite Automata}},
url = {https://www.degruyter.com/view/books/9781400882618/9781400882618-002/9781400882618-002.xml},
year = {1956}
}
@book{aho2007compilers,
address = {Boston},
author = {Louden, Kenneth C},
booktitle = {Compilers : principles, techniques, {\&} tools},
chapter = {2.4.1},
isbn = {9780321486813},
publisher = {Pearson/Addison Wesley},
title = {{From a Regular Expression to an NFA}},
year = {1997}
}
@article{Rabin1959,
author = {Rabin, M. O. and Scott, D.},
doi = {10.1147/rd.32.0114},
issn = {0018-8646},
journal = {IBM Journal of Research and Development},
% month = {apr},
number = {2},
pages = {114--125},
title = {{Finite Automata and Their Decision Problems}},
url = {http://ieeexplore.ieee.org/document/5392601/},
volume = {3},
year = {1959}
}
@article{Chomsky1956,
author = {Chomsky, N.},
doi = {10.1109/TIT.1956.1056813},
issn = {0018-9448},
journal = {IEEE Transactions on Information Theory},
% month = {sep},
number = {3},
pages = {113--124},
title = {{Three models for the description of language}},
url = {http://ieeexplore.ieee.org/document/1056813/},
volume = {2},
year = {1956}
}
@article{Earley1970,
author = {Earley, Jay},
doi = {10.1145/362007.362035},
issn = {00010782},
journal = {Communications of the ACM},
% month = {feb},
number = {2},
pages = {94--102},
title = {{An efficient context-free parsing algorithm}},
url = {http://portal.acm.org/citation.cfm?doid=362007.362035},
volume = {13},
year = {1970}
}


@inproceedings{Zhu2015,
author = {Zhu, Chenxi and Qiu, Xipeng and Huang, Xuanjing},
booktitle = {Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)},
doi = {10.1007/978-3-319-25207-0_2},
pages = {12--24},
title = {{Transition-Based Dependency Parsing with Long Distance Collocations}},
url = {http://link.springer.com/10.1007/978-3-319-25207-0{\_}2},
year = {2015},
isbn = {9783319252063},
issn = {16113349}
}

@inproceedings{Bohnet2016,
address = {Stroudsburg, PA, USA},
author = {Bohnet, Bernd and McDonald, Ryan and Pitler, Emily and Ma, Ji},
booktitle = {Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)},
doi = {10.18653/v1/P16-1015},
pages = {150--160},
publisher = {Association for Computational Linguistics},
title = {{Generalized Transition-based Dependency Parsing via Control Parameters}},
url = {http://aclweb.org/anthology/P16-1015},
year = {2016}
}
@inproceedings{buckman2016transition,
address = {Stroudsburg, PA, USA},
author = {Buckman, Jacob and Ballesteros, Miguel and Dyer, Chris},
booktitle = {Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing},
doi = {10.18653/v1/D16-1254},
organization = {ACL (Association for Computational Linguistics)},
pages = {2313--2318},
publisher = {Association for Computational Linguistics},
title = {{Transition-Based Dependency Parsing with Heuristic Backtracking}},
url = {http://aclweb.org/anthology/D16-1254},
year = {2016}
}

@article{vilares2018transition,
archivePrefix = {arXiv},
arxivId = {1810.08997},
author = {Vilares, David and G{\'{o}}mez-Rodr{\'{i}}guez, Carlos},
eprint = {1810.08997},
% month = {oct},
title = {{Transition-based Parsing with Lighter Feed-Forward Networks}},
url = {http://arxiv.org/abs/1810.08997},
year = {2018}
}

@inproceedings{zhang2011transition,
  title={Transition-based dependency parsing with rich non-local features},
  author={Zhang, Yue and Nivre, Joakim},
  booktitle={Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies: short papers-Volume 2},
  pages={188--193},
  year={2011},
  organization={Association for Computational Linguistics}
}
@inproceedings{zhang2008tale,
  title={A tale of two parsers: investigating and combining graph-based and transition-based dependency parsing using beam-search},
  author={Zhang, Yue and Clark, Stephen},
  booktitle={Proceedings of the Conference on Empirical Methods in Natural Language Processing},
  pages={562--571},
  year={2008},
  organization={Association for Computational Linguistics}
}
@article{Vijayakumar2016a,
archivePrefix = {arXiv},
arxivId = {1610.02424},
author = {Vijayakumar, Ashwin K and Cogswell, Michael and Selvaraju, Ramprasath R. and Sun, Qing and Lee, Stefan and Crandall, David and Batra, Dhruv},
eprint = {1610.02424},
% month = {oct},
pages = {1--16},
title = {{Diverse Beam Search: Decoding Diverse Solutions from Neural Sequence Models}},
url = {http://arxiv.org/abs/1610.02424},
year = {2016}
}
@book{Bird2009,
author = {Bird, Steven and Klein, Ewan and Loper, Edward},
edition = {1},
isbn = {978-0596516499},
pages = {504},
publisher = {O'Reilly Media},
title = {{Natural Language Processing with Python}},
url = {https://www.nltk.org/book},
year = {2009}
}


@article{Younger1967,
author = {Younger, Daniel H.},
doi = {10.1016/S0019-9958(67)80007-X},
issn = {00199958},
journal = {Information and Control},
% month = {feb},
number = {2},
pages = {189--208},
title = {{Recognition and parsing of context-free languages in time n3}},
url = {https://linkinghub.elsevier.com/retrieve/pii/S001999586780007X},
volume = {10},
year = {1967}
}

@book{Minsky1967,
address = {Upper Saddle River, NJ, USA},
annote = {quote from book:

any finite-state machine, if left completely to itself, will fall eventually into a perfectly periodic repetitive pattern},
author = {Minsky, Marvin L},
booktitle = {Computation: Finite and Infinite Machines},
chapter = {8.2},
isbn = {0-13-165563-9},
publisher = {Prentice-Hall, Inc.},
title = {{Unsolvability of the Halting Problem.}},
year = {1967}
}

@article{Aaronson2018,
archivePrefix = {arXiv},
arxivId = {1812.04219},
author = {Aaronson, Scott and Grier, Daniel and Schaeffer, Luke},
eprint = {1812.04219},
% month = {dec},
title = {{A Quantum Query Complexity Trichotomy for Regular Languages}},
url = {http://arxiv.org/abs/1812.04219},
year = {2018}
}

@inproceedings{Dyer2015,
address = {Stroudsburg, PA, USA},
author = {Dyer, Chris and Ballesteros, Miguel and Ling, Wang and Matthews, Austin and Smith, Noah A.},
booktitle = {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)},
doi = {10.3115/v1/P15-1033},
pages = {334--343},
publisher = {Association for Computational Linguistics},
title = {{Transition-Based Dependency Parsing with Stack Long Short-Term Memory}},
url = {http://dx.doi.org/10.3115/v1/P15-1033 http://aclweb.org/anthology/P15-1033},
year = {2015}
}

@inproceedings{Ambainis2012VariableTimeAmpAmp,
  TITLE = {{Variable time amplitude amplification and quantum algorithms for linear algebra problems}},
  AUTHOR = {Ambainis, Andris},
  URL = {https://hal.archives-ouvertes.fr/hal-00678197},
  BOOKTITLE = {{STACS'12 (29th Symposium on Theoretical Aspects of Computer Science)}},
  ADDRESS = {Paris, France},
  EDITOR = {Christoph D{\"u}rr, Thomas Wilke},
  PUBLISHER = {{LIPIcs}},
  VOLUME = {14},
  PAGES = {636-647},
  YEAR = {2012},
  % month = Feb,
  KEYWORDS = {amplitude amplification ; linear equations ; quantum algorithms ; quantum computing},
  PDF = {https://hal.archives-ouvertes.fr/hal-00678197/file/42.pdf},
  HAL_ID = {hal-00678197},
  HAL_VERSION = {v1},
  doi = {10.4230/LIPIcs.STACS.2012.636}
}

@article{Hannun2014,
archivePrefix = {arXiv},
arxivId = {1412.5567},
author = {Hannun, Awni and Case, Carl and Casper, Jared and Catanzaro, Bryan and Diamos, Greg and Elsen, Erich and Prenger, Ryan and Satheesh, Sanjeev and Sengupta, Shubho and Coates, Adam and Ng, Andrew Y.},
eprint = {1412.5567},
% month = {dec},
title = {{Deep Speech: Scaling up end-to-end speech recognition}},
url = {http://arxiv.org/abs/1412.5567},
year = {2014}
}
@misc{Mozilla2019,
author = {Mozilla},
title = {{DeepSpeech v.0.41}},
url = {https://github.com/mozilla/DeepSpeech},
year = {2019}
}
@misc{Mozilla2019a,
author = {Mozilla},
title = {{Common Voice}},
url = {http://voice.mozilla.org/},
year = {2019}
}
@inproceedings{Holzer2017,
address = {Cham},
author = {Holzer, Markus and Kutrib, Martin},
booktitle = {Reversible Computation},
editor = {Phillips, Iain and Rahaman, Hafizur},
isbn = {978-3-319-59936-6},
pages = {35--51},
publisher = {Springer International Publishing},
title = {{Reversible Nondeterministic Finite Automata}},
year = {2017}
}
@inproceedings{Kutrib2014,
address = {Cham},
author = {Kutrib, Martin and Worsch, Thomas},
booktitle = {Reversible Computation},
editor = {Yamashita, Shigeru and Minato, Shin-ichi},
isbn = {978-3-319-08494-7},
pages = {40--53},
publisher = {Springer International Publishing},
title = {{Degrees of Reversibility for DFA and DPDA}},
year = {2014}
}
@inproceedings{chen1976pattern,
address = {Hyannis, Massachusetts},
author = {Mermelstein, Paul},
booktitle = {Pattern Recognition and Artificial Intelligence: Proceedings of the Joint Workshop on Pattern Recognition and Artificial Intelligence},
editor = {Chen, C. H.},
isbn = {9780121709501},
pages = {374----388},
publisher = {Academic Press},
title = {{"Distance measures for speech recognition, psychological and instrumental,}},
url = {https://books.google.co.uk/books?id=wW9QAAAAMAAJ},
year = {1976}
}
@article{Kutrib2012,
author = {Kutrib, Martin and Malcher, Andreas},
doi = {10.1016/j.jcss.2011.12.004},
issn = {00220000},
journal = {Journal of Computer and System Sciences},
% month = {nov},
number = {6},
pages = {1814--1827},
title = {{Reversible pushdown automata}},
url = {https://linkinghub.elsevier.com/retrieve/pii/S0022000011001498},
volume = {78},
year = {2012}
}

@article{Karacuba1972,
author = {Karacuba, A A},
doi = {10.1070/IM1972v006n03ABEH001883},
issn = {0025-5726},
journal = {Mathematics of the USSR-Izvestiya},
% month = {jun},
number = {3},
pages = {467--475},
title = {{Uniform Approximation of the Remainder Term in the Dirichlet Divisor Problem}},
url = {http://stacks.iop.org/0025-5726/6/i=3/a=A01?key=crossref.88fb5ada165ed83cbbfe48253aefe3bf},
volume = {6},
year = {1972}
}
@article{Takeda2018,
archivePrefix = {arXiv},
arxivId = {1804.03785},
author = {Takeda, Wataru},
eprint = {1804.03785},
% month = {apr},
title = {{Uniform bounds of Piltz divisor problem over number fields}},
url = {http://arxiv.org/abs/1804.03785},
year = {2018}
}
@article{Bourgain2017,
archivePrefix = {arXiv},
arxivId = {1709.04340},
author = {Bourgain, Jean and Watt, Nigel},
eprint = {1709.04340},
% month = {sep},
title = {{Mean square of zeta function, circle problem and divisor problem revisited}},
url = {http://arxiv.org/abs/1709.04340},
year = {2017}
}
@article {Karacuba1972orig,
    AUTHOR = {Karacuba, A. A.},
     TITLE = {A uniform estimate for the remainder term in {D}irichlet's
              problem of divisors},
   JOURNAL = {Izv. Akad. Nauk SSSR Ser. Mat.},
  FJOURNAL = {Izvestiya Akademii Nauk SSSR. Seriya Matematicheskaya},
    VOLUME = {36},
      YEAR = {1972},
     PAGES = {475--483},
      ISSN = {0373-2436},
   MRCLASS = {10H15},
  MRNUMBER = {0318077},
MRREVIEWER = {H.-E. Richert},
}

@article{Bernstein1997,
author = {Bernstein, Ethan and Vazirani, Umesh},
doi = {10.1137/S0097539796300921},
issn = {0097-5397},
journal = {SIAM Journal on Computing},
% month = {oct},
number = {5},
pages = {1411--1473},
title = {{Quantum Complexity Theory}},
url = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.144.7852 http://epubs.siam.org/doi/abs/10.1137/S0097539796300921},
volume = {26},
year = {1997}
}
@article{Buhrman2001,
archivePrefix = {arXiv},
arxivId = {arXiv:quant-ph/0101133v2},
author = {Buhrman, Harry and Tromp, John and Vit{\'{a}}nyi, Paul},
doi = {10.1088/0305-4470/34/35/308},
eprint = {0101133v2},
issn = {03054470},
journal = {Journal of Physics A: Mathematical and General},
number = {35},
pages = {6821--6830},
primaryClass = {arXiv:quant-ph},
title = {{Time and space bounds for reversible simulation}},
volume = {34},
year = {2001}
}
@book{Perumalla2013,
annote = {how to make UTMs reversible},
author = {Perumalla, Kalyan S.},
isbn = {1439873410},
pages = {325},
publisher = {CRC Press},
title = {{Introduction to Reversible Computing}},
url = {https://books.google.com/books?id=Lq{\_}MBQAAQBAJ{\&}pgis=1},
year = {2013}
}
@incollection{Tomita1986,
address = {Boston, MA},
author = {Tomita, Masaru},
booktitle = {Efficient Parsing for Natural Language},
doi = {10.1007/978-1-4757-1885-0_5},
pages = {71--77},
publisher = {Springer US},
title = {{Comparison with Other Algorithms}},
url = {http://link.springer.com/10.1007/978-1-4757-1885-0{\_}5},
year = {1986}
}


@article{Boyer1998ExpSearch,
archivePrefix = {arXiv},
arxivId = {arXiv:quant-ph/9605034v1},
author = {Boyer, Michel and Brassard, Gilles and H{\O}yer, Peter and Tapp, Alain},
doi = {10.1002/(SICI)1521-3978(199806)46:4/5<493::AID-PROP493>3.0.CO;2-P},
eprint = {9605034v1},
issn = {00158208},
journal = {Fortschritte der Physik},
keywords = {Lower bound,Quantum computation,Searching},
number = {4-5},
pages = {493--505},
primaryClass = {arXiv:quant-ph},
title = {{Tight bounds on quantum searching}},
volume = {46},
year = {1998}
}


@article{Grover97,
  title = {Quantum Mechanics Helps in Searching for a Needle in a Haystack},
  author = {Grover, Lov K.},
  journal = {Phys. Rev. Lett.},
  volume = {79},
  issue = {2},
  pages = {325--328},
  numpages = {0},
  year = {1997},
  % month = {Jul},
  publisher = {American Physical Society},
  doi = {10.1103/PhysRevLett.79.325},
  url = {https://link.aps.org/doi/10.1103/PhysRevLett.79.325}
}


@inproceedings{Berry14ObliviousAmpAmp,
 author = {Berry, Dominic W. and Childs, Andrew M. and Cleve, Richard and Kothari, Robin and Somma, Rolando D.},
 title = {Exponential Improvement in Precision for Simulating Sparse Hamiltonians},
 booktitle = {Proceedings of the Forty-sixth Annual ACM Symposium on Theory of Computing},
 series = {STOC '14},
 year = {2014},
 isbn = {978-1-4503-2710-7},
 location = {New York, New York},
 pages = {283--292},
 numpages = {10},
 url = {http://doi.acm.org/10.1145/2591796.2591854},
 doi = {10.1145/2591796.2591854},
 acmid = {2591854},
 publisher = {ACM},
 address = {New York, NY, USA},
 keywords = {Hamiltonian simulation, quantum algorithms},
} 


@article{Graves2013,
archivePrefix = {arXiv},
arxivId = {1308.0850},
author = {Graves, Alex},
eprint = {1308.0850},
% month = {aug},
title = {{Generating Sequences With Recurrent Neural Networks}},
url = {http://arxiv.org/abs/1308.0850},
year = {2013}
}
@incollection{NIPS2014_5346,
title = {Sequence to Sequence Learning with Neural Networks},
author = {Sutskever, Ilya and Vinyals, Oriol and Le, Quoc V},
booktitle = {Advances in Neural Information Processing Systems 27},
editor = {Z. Ghahramani and M. Welling and C. Cortes and N. D. Lawrence and K. Q. Weinberger},
pages = {3104--3112},
year = {2014},
publisher = {Curran Associates, Inc.},
url = {http://papers.nips.cc/paper/5346-sequence-to-sequence-learning-with-neural-networks.pdf}
}
@article{Schmidhuber2014,
archivePrefix = {arXiv},
arxivId = {1404.7828},
author = {Schmidhuber, Juergen},
doi = {10.1016/j.neunet.2014.09.003},
eprint = {1404.7828},
issn = {08936080},
journal = {Neural Networks},
% month = {apr},
pages = {85--117},
title = {{Deep Learning in Neural Networks: An Overview}},
url = {https://linkinghub.elsevier.com/retrieve/pii/S0893608014002135 http://arxiv.org/abs/1404.7828 http://dx.doi.org/10.1016/j.neunet.2014.09.003},
volume = {61},
year = {2014}
}

@inproceedings{Wiseman2016,
address = {Stroudsburg, PA, USA},
author = {Wiseman, Sam and Rush, Alexander M.},
booktitle = {Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing},
doi = {10.18653/v1/D16-1137},
pages = {1296--1306},
publisher = {Association for Computational Linguistics},
title = {{Sequence-to-Sequence Learning as Beam-Search Optimization}},
url = {http://aclweb.org/anthology/D16-1137},
year = {2016}
}
@inproceedings{Sutskever:2011:GTR:3104482.3104610,
 author = {Sutskever, Ilya and Martens, James and Hinton, Geoffrey},
 title = {Generating Text with Recurrent Neural Networks},
 booktitle = {Proceedings of the 28th International Conference on International Conference on Machine Learning},
 series = {ICML'11},
 year = {2011},
 isbn = {978-1-4503-0619-5},
 location = {Bellevue, Washington, USA},
 pages = {1017--1024},
 numpages = {8},
 url = {http://dl.acm.org/citation.cfm?id=3104482.3104610},
 acmid = {3104610},
 publisher = {Omnipress},
 address = {USA},
}

@inproceedings{steinbiss1994improvements,
  title={Improvements in beam search},
  author={Steinbiss, Volker and Tran, Bach-Hiep and Ney, Hermann},
  booktitle={Third International Conference on Spoken Language Processing},
  year={1994}
}
@article{Kulikov2018,
archivePrefix = {arXiv},
arxivId = {1811.00907},
author = {Kulikov, Ilya and Miller, Alexander H. and Cho, Kyunghyun and Weston, Jason},
eprint = {1811.00907},
% month = {nov},
title = {{Importance of a Search Strategy in Neural Dialogue Modelling}},
url = {http://arxiv.org/abs/1811.00907},
year = {2018}
}
@inproceedings{Murray2018CorrectingLB,
address = {Stroudsburg, PA, USA},
author = {Murray, Kenton and Chiang, David},
booktitle = {Proceedings of the Third Conference on Machine Translation: Research Papers},
doi = {10.18653/v1/W18-6322},
pages = {212--223},
publisher = {Association for Computational Linguistics},
title = {{Correcting Length Bias in Neural Machine Translation}},
url = {http://aclweb.org/anthology/W18-6322},
year = {2018}
}

@inproceedings{Yang2018,
address = {Stroudsburg, PA, USA},
archivePrefix = {arXiv},
arxivId = {1808.09582},
author = {Yang, Yilin and Huang, Liang and Ma, Mingbo},
booktitle = {Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing},
doi = {10.18653/v1/D18-1342},
eprint = {1808.09582},
% month = {aug},
pages = {3054--3059},
publisher = {Association for Computational Linguistics},
title = {{Breaking the Beam Search Curse: A Study of (Re-)Scoring Methods and Stopping Criteria for Neural Machine Translation}},
url = {http://arxiv.org/abs/1808.09582 http://aclweb.org/anthology/D18-1342},
year = {2018}
}

@article{Fan2018,
archivePrefix = {arXiv},
arxivId = {1805.04833},
author = {Fan, Angela and Lewis, Mike and Dauphin, Yann},
eprint = {1805.04833},
% month = {may},
title = {{Hierarchical Neural Story Generation}},
url = {http://arxiv.org/abs/1805.04833},
year = {2018}
}
@article{Holtzman2019,
archivePrefix = {arXiv},
arxivId = {1904.09751},
author = {Holtzman, Ari and Buys, Jan and Forbes, Maxwell and Choi, Yejin},
eprint = {1904.09751},
% month = {apr},
title = {{The Curious Case of Neural Text Degeneration}},
url = {http://arxiv.org/abs/1904.09751},
year = {2019}
}
@article{Cai2018,
author = {Cai, Zi and Liu, Jinguo},
doi = {10.1103/PhysRevB.97.035116},
issn = {2469-9950},
journal = {Physical Review B},
% month = {jan},
number = {3},
pages = {035116},
title = {{Approximating quantum many-body wave functions using artificial neural networks}},
url = {https://link.aps.org/doi/10.1103/PhysRevB.97.035116},
volume = {97},
year = {2018}
}
@article{Deng2017,
author = {Deng, Dong-Ling and Li, Xiaopeng and {Das Sarma}, S.},
doi = {10.1103/PhysRevX.7.021021},
issn = {2160-3308},
journal = {Physical Review X},
% month = {may},
number = {2},
pages = {021021},
title = {{Quantum Entanglement in Neural Network States}},
url = {http://link.aps.org/doi/10.1103/PhysRevX.7.021021},
volume = {7},
year = {2017}
}
@article{Jia2018,
archivePrefix = {arXiv},
arxivId = {1802.03738},
author = {Jia, Zhih-Ahn and Zhang, Yuan-Hang and Wu, Yu-Chun and Guo, Guang-Can and Guo, Guo-Ping},
eprint = {1802.03738},
% month = {feb},
title = {{Efficient Machine Learning Representations of Surface Code with Boundaries, Defects, Domain Walls and Twists}},
url = {http://arxiv.org/abs/1802.03738},
year = {2018}
}
@article{Bausch2018a,
archivePrefix = {arXiv},
arxivId = {1806.08781},
author = {Bausch, Johannes and Leditzky, Felix},
eprint = {1806.08781},
% month = {jun},
title = {{Quantum Codes from Neural Networks}},
url = {http://arxiv.org/abs/1806.08781},
year = {2018}
}

@article{Carleo2017,
author = {Carleo, Giuseppe and Troyer, Matthias},
doi = {10.1126/science.aag2302},
issn = {0036-8075},
journal = {Science},
% month = {feb},
number = {6325},
pages = {602--606},
title = {{Solving the quantum many-body problem with artificial neural networks}},
url = {http://www.sciencemag.org/lookup/doi/10.1126/science.aag2302},
volume = {355},
year = {2017}
}
@incollection{Gilyen2019Opt,
address = {Philadelphia, PA},
author = {Gily{\'{e}}n, Andr{\'{a}}s and Arunachalam, Srinivasan and Wiebe, Nathan},
booktitle = {Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms},
doi = {10.1137/1.9781611975482.87},
% month = {jan},
pages = {1425--1444},
publisher = {Society for Industrial and Applied Mathematics},
title = {{Optimizing quantum optimization algorithms via faster quantum gradient computation}},
url = {https://epubs.siam.org/doi/10.1137/1.9781611975482.87},
year = {2019},
archivePrefix = {arXiv},
arxivId = {1711.00465},
eprint = {1711.00465}
}
@article{Wiebe2019,
archivePrefix = {arXiv},
arxivId = {1902.05162},
author = {Wiebe, Nathan and Bocharov, Alex and Smolensky, Paul and Troyer, Matthias and Svore, Krysta M},
eprint = {1902.05162},
% month = {feb},
title = {{Quantum Language Processing}},
url = {http://arxiv.org/abs/1902.05162},
year = {2019}
}
@article{Bausch2018,
author = {Bausch, Johannes},
doi = {10.1142/S0219749918400014},
issn = {0219-7499},
journal = {International Journal of Quantum Information},
% month = {dec},
number = {08},
pages = {1840001},
title = {{Classifying data using near-term quantum devices}},
url = {https://www.worldscientific.com/doi/abs/10.1142/S0219749918400014},
volume = {16},
year = {2018}
}

@article {Lloyd1996,
  author = {Lloyd, Seth},
  title = {Universal Quantum Simulators},
  volume = {273},
  number = {5278},
  pages = {1073--1078},
  year = {1996},
  doi = {10.1126/science.273.5278.1073},
  publisher = {American Association for the Advancement of Science},
  issn = {0036-8075},
  URL = {https://science.sciencemag.org/content/273/5278/1073},
  eprint = {https://science.sciencemag.org/content/273/5278/1073.full.pdf},
  journal = {Science}
}

@article{Oliveira2007comp,
author = {Sena Oliveira, David and Ramos, Rubens},
year = {2007},
% month = {01},
pages = {},
title = {Quantum bit string comparator: Circuits and applications},
volume = {7},
journal = {Quantum Computers and Computing}
}

@book{Nielsen2010,
address = {Cambridge},
author = {Nielsen, Michael A. and Chuang, Isaac L.},
doi = {10.1017/CBO9780511976667},
isbn = {9780511976667},
% pages = {676},
publisher = {Cambridge University Press},
title = {{Quantum Computation and Quantum Information}},
url = {http://books.google.com/books?id=-s4DEy7o-a0C{\&}pgis=1 http://ebooks.cambridge.org/ref/id/CBO9780511976667},
year = {2010}
}

@article{Reinharz2013,
author = {Reinharz, Vladimir and Ponty, Yann and Waldisp{\"{u}}hl, J{\'{e}}r{\^{o}}me},
doi = {10.1093/bioinformatics/btt217},
issn = {1367-4803},
journal = {Bioinformatics},
% month = {jul},
number = {13},
pages = {i308--i315},
title = {{A weighted sampling algorithm for the design of RNA sequences with targeted secondary structure and nucleotide distribution}},
url = {https://academic.oup.com/bioinformatics/article-lookup/doi/10.1093/bioinformatics/btt217},
volume = {29},
year = {2013}
}

@incollection{Re2018BeyondLogConcave,
title = {Beyond Log-concavity: Provable Guarantees for Sampling Multi-modal Distributions using Simulated Tempering Langevin Monte Carlo},
author = {LEE, HOLDEN and Risteski, Andrej and Ge, Rong},
booktitle = {Advances in Neural Information Processing Systems 31},
editor = {S. Bengio and H. Wallach and H. Larochelle and K. Grauman and N. Cesa-Bianchi and R. Garnett},
pages = {7847--7856},
year = {2018},
publisher = {Curran Associates, Inc.},
url = {http://papers.nips.cc/paper/8010-beyond-log-concavity-provable-guarantees-for-sampling-multi-modal-distributions-using-simulated-tempering-langevin-monte-carlo.pdf}
}

@article{Wossnig2018denseHHL,
  title = {Quantum Linear System Algorithm for Dense Matrices},
  author = {Wossnig, Leonard and Zhao, Zhikuan and Prakash, Anupam},
  journal = {Phys. Rev. Lett.},
  volume = {120},
  issue = {5},
  pages = {050502},
  numpages = {5},
  year = {2018},
  % month = {Jan},
  publisher = {American Physical Society},
  doi = {10.1103/PhysRevLett.120.050502},
  url = {https://link.aps.org/doi/10.1103/PhysRevLett.120.050502},
  archivePrefix = {arXiv},
  archiveId = {1704.06174},
}