selected-works.Rmd

# (PART) Everything else {-}


# Selected works on quantum algorithms

This is a work in progress, as the vast majority of works are not present here, yet. Obviously, feel free to write at "scinawa [at] luongo . pro" for suggestions, or open an issue on [github](https://github.com/scinawa/quantumalgorithms.org). Please understand that the aim of this section if to select relevant *quantum algorithms*. Special interested is devoted to works that can be applied for data analysis or used as other subroutines for other QML algorithms.

#### 2022 {-}
- [An efficient quantum algorithm for lattice problems achieving subexponential approximation factor](https://arxiv.org/abs/2201.13450) `#algo` `#crypto`
- [Improved quantum algorithms for linear and nonlinear differential equations](https://arxiv.org/abs/2202.01054) `#algo`
- [New Quantum Algorithms for Computing Quantum Entropies and Distances](https://arxiv.org/abs/2203.13522) `#algo`
- [Quantum machine learning with subspace states](https://arxiv.org/abs/2202.00054) `#algo`
- [A quantum algorithm for solving eigenproblem of the Laplacian matrix of a fully connected graph](https://arxiv.org/abs/2203.14451) `#algo`
- [Quantum State Preparation with Optimal Circuit Depth: Implementations and Applications](https://arxiv.org/abs/2201.11495) `#algo, #theory`
- [Quantum Meets Fine-Grained Complexity: Sublinear Time Quantum Algorithms for String Problems](https://drops.dagstuhl.de/opus/volltexte/2022/15693/) `#algo`
- [Two-level Quantum Walkers on Directed Graphs II: An Application to qRAM](https://arxiv.org/abs/2204.08709) `#algo`
- [Memory Compression with Quantum Random-Access Gates](https://arxiv.org/abs/2203.05599) 
- [Mean estimation when you have the source code; or, quantum Monte Carlo methods](https://arxiv.org/pdf/2208.07544.pdf)
- [Exact and efficient Lanczos method on a quantum computer](https://arxiv.org/pdf/2208.00567.pdf)
- [On establishing learning separations between classical and quantum machine learning with classical data](https://arxiv.org/pdf/2208.06339.pdf)
- [Matching Triangles and Triangle Collection: Hardness based on a Weak Quantum Conjecture](https://arxiv.org/pdf/2207.11068.pdf)
- [Partition Function Estimation: Quantum and Quantum-Inspired Algorithms](https://arxiv.org/pdf/2208.00930.pdf)
- [A Faster Quantum Algorithm for Semidefinite Programming via Robust IPM Framework](https://arxiv.org/pdf/2207.11154.pdf)
- [Quantum Subroutine Composition](https://arxiv.org/abs/2209.14146) `#algo`
- [Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis](https://arxiv.org/abs/2209.14286) `#theory`
- [Quantum Algorithms for Sampling Log-Concave Distributions and Estimating Normalizing Constants](https://arxiv.org/pdf/2210.06539.pdf) `#algo`
- [Quantum divide and conquer](https://arxiv.org/pdf/2210.06419.pdf)



#### 2021 {-}

- [Information-theoretic bounds on quantum advantage in machine learning](https://arxiv.org/abs/2101.02464) `#theory`
- [Noisy intermediate-scale quantum (NISQ) algorithms](https://arxiv.org/abs/2101.08448) `#review, #variational`
A massive review on the state-of-the-art quantum algorithms for NISQ architectures. It highlights the limitations, but also the wins of the variational paradigm.
- [Parallel Quantum Algorithm for Hamiltonian Simulation](https://arxiv.org/abs/2105.11889) `#algo`
- [Quantum Perceptron Revisited: Computational-Statistical Tradeoffs](https://arxiv.org/abs/2106.02496) `#algo`
- [Lower bounds for monotone arithmetic circuits via communication complexity](https://dl.acm.org/doi/abs/10.1145/3406325.3451069) `#theory`
- [Fast algorithm for quantum polar decomposition, pretty-goodmeasurements, and the Procrustes problem](https://arxiv.org/abs/2106.07634) `#algo`
- [Quantum Algorithms based on the Block-Encoding Framework for Matrix Functions by Contour Integrals](https://arxiv.org/abs/2106.08076) `#algo`
- [Classical and Quantum Algorithms for Orthogonal Neural Networks](https://arxiv.org/abs/2106.07198) `#algo`
- [Quantum Semi Non-negative Matrix Factorization](https://books.google.com.sg/books?hl=en&lr=&id=LMcpEAAAQBAJ&oi=fnd&pg=PA135&dq=Quantum+Semi+Non-negative+Matrix+Factorization&ots=2UP_f_twTu&sig=fvkK9Z4hCCQcSSkbF0HkZ23SRAs&redir_esc=y#v=onepage&q=Quantum%20Semi%20Non-negative%20Matrix%20Factorization&f=false) `#algo`
- [Quantum Algorithms based on the Block-Encoding Framework for Matrix Functions by Contour Integrals](https://arxiv.org/pdf/2106.08076.pdf)
- [Quantum Alphatron](https://arxiv.org/abs/2108.11670) `#algo`
- [Quantum SubGaussian Mean Estimator](https://arxiv.org/pdf/2108.12172.pdf) `#algo`
- [A randomized quantum algorithm for statistical phase estimation](https://arxiv.org/abs/2110.12071) `#algo`
- [Near-Optimal Quantum Algorithms for String Problems](https://arxiv.org/pdf/2110.09696.pdf) `#algo`
- [Quantum Algorithms and Lower Bounds for Linear Regression with Norm Constraints](https://arxiv.org/pdf/2110.13086.pdf) `#algo`
- [Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture](https://arxiv.org/abs/2111.09079) `#algo`
- [A randomized quantum algorithm for statistical phase estimation](https://arxiv.org/abs/2110.12071) `#algo`
- [Nearly Optimal Quantum Algorithm for Estimating Multiple Expectation Values](https://arxiv.org/abs/2111.09283) `#algo`
- [Quantum Algorithms for Reinforcement Learning with a Generative Model](https://arxiv.org/abs/2112.08451) `#algo` `#qrl` `#qmc` 
- [Quantum Monte-Carlo Integration: The Full Advantage in Minimal Circuit Depth](https://arxiv.org/abs/2105.09100) `#algo` `#qmc`
- [Near-Optimal Quantum Algorithms for Multivariate Mean Estimation](https://arxiv.org/abs/2111.09787) `#algo` `#qmc`
- [Quantum algorithms for multivariate Monte Carlo estimation](https://arxiv.org/abs/2107.03410) `#algo` `#qmc` 
- [Quantum Sub-Gaussian Mean Estimator](https://arxiv.org/abs/2108.12172) `#algo` `#qmc`
- [Quantum algorithm for stochastic optimal stopping problems](https://arxiv.org/abs/2111.15332) `#qfinance` `#algo`
- [Quantum Machine Learning For Classical Data](https://arxiv.org/abs/2105.03684) `#thesis`
- [Quantum algorithms for anomaly detection using amplitude estimation](https://arxiv.org/pdf/2109.13820.pdf) `#algo`
- [Two-level Quantum Walkers on Directed Graphs I: Universal Quantum Computing](https://arxiv.org/abs/2112.08119) `#algo`
- [Quantum algorithms for learning a hidden graph and beyond](https://arxiv.org/abs/2011.08611) `#algo`
- [Asymptotically Optimal Circuit Depth for Quantum State
Preparation and General Unitary Synthesis](https://arxiv.org/pdf/2108.06150.pdf)

#### 2020 {-}

- [Variational Quantum Algorithms](https://scirate.com/arxiv/2012.09265) `#review`
- [Circuit-centric Quantum Classifier](https://arxiv.org/pdf/1804.00633) `#variational`
- [Quantum polar decomposition algorithm](https://arxiv.org/abs/2006.00841) `#algo`
- [The power of quantum neural networks](https://arxiv.org/abs/2011.00027) `#variational`
- [Robust quantum minimum finding with an application to hypothesis selection](https://arxiv.org/abs/2003.11777) `#algo`
- [Quantum exploration algorithms for multi-armed bandits](https://arxiv.org/abs/2007.07049) `#algo`
- [Sublinear classical and quantum algorithms for general matrix games](https://arxiv.org/pdf/2012.06519.pdf) `#algo`


#### 2019 {-}

- [Quantum Language Processing](https://arxiv.org/pdf/1902.05162.pdf) `#NLP`
- [A Quantum Search Decoder for Natural Language Processing](https://arxiv.org/pdf/1909.05023.pdf) `#NLP`
- [Quantum and Classical Algorithms for Approximate Submodular Function Minimization](https://arxiv.org/abs/1907.05378) `#algo`
- [Quantum algorithms for zero-sum games](https://arxiv.org/abs/1904.03180) `#algo`
- [Practical implementation of a quantum backtracking algorithm](https://arxiv.org/abs/1908.11291) `#experiment`
- [Quantum speedup of branch-and-bound algorithms](https://arxiv.org/abs/1906.10375) `#algo`
- [The Quantum Version Of Classification Decision Tree Constructing Algorithm C5.0](https://arxiv.org/pdf/1907.06840.pdf) `#algo`
- [Sublinear quantum algorithms for training linear and kernel-based classifiers](http://proceedings.mlr.press/v97/li19b/li19b.pdf) `#algo`
- [Quantum Algorithms for Classical Probability Distributions](https://arxiv.org/pdf/1904.02192.pdf) `#algo` `#qmc`


#### 2018 {-}

- [Continuous-variable quantum neural networks](https://arxiv.org/pdf/1806.06871.pdf)
A work presented at TQC2018 that exploit deep similarities between the mathematical formulation of NN and photinics
- [Classification with quantum neural networks on near term processors](https://arxiv.org/pdf/1802.06002.pdf)   `#variational`
- [Artificial Quantum Neural Network: quantum neurons, logical elements and tests of convolutional nets.](https://arxiv.org/pdf/1806.09664.pdf)
A new approach to qnn \o/. This skips complitely the unitary and gate based quantum computation
Also here the model is mean to be trained by classical optimization.
- [Optimizing quantum optimization algorithmsvia faster quantum gradient computation](https://arxiv.org/pdf/1711.00465.pdf) `#algo`
- [Quantum Statistical Inference](https://arxiv.org/pdf/1812.04877.pdf) `#phdthesis, #algo`
A PhD thesis on QML and other aspects of quantum information. With focus on Gaussian Processes, Quantum Bayesian Deep Learning (and other resources about causality and correlations..).
- [Troubling Trends in Machine Learning Scholarship](https://arxiv.org/pdf/1807.03341.pdf) `#opinion-paper`
Is a self-autocritic of the ML community on the way they are doing science now. I think this might be relevant as well for the QML practicioner.
- [Quantum machine learning for data scientits](https://arxiv.org/pdf/1804.10068.pdf) `#review`  `#tutorial`
This is a very nice review of some of the most known qml algorithms.
- [Quantum algorithm implementations for beginners](https://arxiv.org/pdf/1804.03719.pdf) `#review` `#tutorial`
- [Quantum linear systems algorithms: a primer](https://arxiv.org/abs/1802.08227) `#review`
- [Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics](https://arxiv.org/abs/1806.01838) `#algo`
- [The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation](https://arxiv.org/abs/1804.01973) `#algo`
- [Applying quantum algorithms to constraint satisfaction problems](https://arxiv.org/abs/1810.05582) `#resource-estimation`
- [Quantum Chebyshev's Inequality and Applications](https://arxiv.org/abs/1807.06456) `#qmc`
- [From linear combination of quantum states to Grover’s searching algorithm](https://arxiv.org/pdf/1807.09693.pdf)


<!-- - [Quantum Algorithms for Classification](http://www.youtube.com/watch?v=KTVtMKo3g80) `#video`  -->
<!-- <br> -->
<!-- [![Quantum Algorithms for Classification](http://img.youtube.com/vi/KTVtMKo3g80/0.jpg)](http://www.youtube.com/watch?v=KTVtMKo3g80 "Quantum Algorithms for Classification")  -->


#### 2017 {-}

- [Implementing a distance based classifier with a quantum interference circuit](https://arxiv.org/abs/1703.10793)  `#algo`
- [Quantum SDP solvers: Large speed-ups, optimality, and applications to quantum learning](https://arxiv.org/pdf/1710.02581) `#algo`
- [Quantum machine learning for quantum anomaly detection](https://arxiv.org/abs/1710.07405) `#algo`
Here the authors used previous technique to perform anomaly detection. Basically they project the data on the 1-dimensional subspace of the covariance matrix of the data. In this way anomalies are supposed to lie furhter away from the rest of the dataset.
- [ Quantum machine learning: a classical perspective](https://arxiv.org/pdf/1707.08561.pdf): `#review` `#quantum learning theory`
- [Quantum Neuron: an elementary building block for machine learning on quantum computers](https://arxiv.org/pdf/1711.11240.pdf)
- [Quantum speedup of Monte Carlo methods](https://arxiv.org/abs/1504.06987) `#algo`
- [Improved quantum backtracking algorithms using effective resistance estimates](https://arxiv.org/abs/1711.05295) `#algo`


#### 2016 {-}
- [Quantum Discriminant Analysis for Dimensionality Reduction and Classification](https://iopscience.iop.org/article/10.1088/1367-2630/18/7/073011)  `#algo`
- [An efficient quantum algorithm for spectral estimation](https://arxiv.org/abs/1609.08170) `#algo`
- [Quantum Recommendation Systems](https://arxiv.org/pdf/1603.08675.pdf) `#algo`

#### 2015 {-}

- [Advances in quantum machine learning]( https://arxiv.org/pdf/1512.02900.pdf ) `#implementations`,  `#review`
It cover things up to 2015, so here you can find descriptions of Neural Networks, Bayesian Networks, HHL, PCA, Quantum Nearest Centroid, Quantum k-Nearest Neighbour, and others.
-[Quantum walk speedup of backtracking algorithms](https://arxiv.org/abs/1509.02374) `#algo`
- [Quantum algorithms for topological and geometric analysis of data]() `#algo`

#### 2014 {-}

- [Quantum Algorithms for Nearest-Neighbor Methods for Supervised and Unsupervised Learning]() `#algo`
- [Quantum support vector machine for big data classification](https://arxiv.org/abs/1307.0471) `#algo`
This was one of the first example on how to use HHL-like algorithms in order to get something useful out of them.
- [Improved Quantum Algorithm for Triangle Finding via Combinatorial Arguments](https://arxiv.org/abs/1407.0085) `#algo`
- [Fixed-point quantum search with an optimal number of queries](https://arxiv.org/abs/1409.3305) `#algo`
- [Quantum Principal Component Analysis](https://arxiv.org/abs/1307.0401)  `#algo`


#### 2013 {-}
- [Quantum algorithms for supervised and unsupervised machine learning](https://arxiv.org/pdf/1307.0411.pdf) `#algo`
- [Exponential improvement in precision for simulating sparse Hamiltonians](https://arxiv.org/abs/1312.1414) `#algo`


#### 2010 {-}
- [Variable time amplitude amplification and a faster quantum algorithm for solving systems of linear equations](https://arxiv.org/abs/1010.4458) `#algo`
- [Any and-or formula of size $n$ can be evaluated in time $n^{1/2 + o(1)}$ on a quantum computer](http://www.ucw.cz/~robert/papers/andor-siamjc.pdf)


#### 2009 {-}
- [Quantum algorithms for linear systems of equations](https://arxiv.org/abs/0811.3171) `#algo`

#### 2007 {-}

- [A Quantum Algorithm for the Hamiltonian NAND Tree](https://arxiv.org/pdf/quant-ph/0702144.pdf)


#### 2005 {-}
- [Fast quantum algorithm for numerical gradient estimation](https://arxiv.org/abs/quant-ph/0405146) `#algo`


#### 1999 {-}
- [The quantum query complexity of approximating the median and related statistics](https://arxiv.org/pdf/quant-ph/9804066.pdf) `#algo`

#### 1996 {-}
- [A fast quantum mechanical algorithm for estimating the median](https://arxiv.org/abs/quant-ph/9607024) `#algo`