New papers and algorithms

[Scinawa]

Subroutines, ideas, foundational material.

• Quantum algorithm for finding the minimum https://arxiv.org/abs/quant-ph/9607014
• Quantum algorithms revisited https://arxiv.org/pdf/quant-ph/9708016.pdf
• Quantum approximate counting simplified https://arxiv.org/pdf/1908.10846
• Variable time amplitude amplification and a faster quantumalgorithm for solving systems of linear equations https://arxiv.org/pdf/1010.4458.pdf
• Quantum linear systems algorithms: a primer https://arxiv.org/abs/1802.08227
• Quantum polar decomposition algorithm https://arxiv.org/pdf/2006.00841.pdf
• Quantum and Classical Algorithms forApproximate Submodular Function Minimization https://arxiv.org/pdf/1907.05378.pdf
• Robust Quantum Minimum Finding with an Application to Hypothesis Selection ( https://arxiv.org/abs/2003.11777 )
• Improved Quantum Algorithm for Triangle Finding via Combinatorial Arguments https://arxiv.org/pdf/1407.0085.pdf
• Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics https://arxiv.org/abs/1806.01838
• The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation https://arxiv.org/abs/1804.01973
• Oblivious amplitude amplification : https://arxiv.org/abs/1312.1414 https://simons.berkeley.edu/sites/default/files/docs/10091/algorithmicprimitives.pdf
• Fast Quantum Algorithm for Numerical Gradient Estimation https://arxiv.org/abs/quant-ph/0405146 and followups
• Quantum coupon collector ( https://arxiv.org/pdf/2002.07688.pdf )
• Quantum algorithms for zero-sum games https://arxiv.org/abs/1904.03180
• Median finding algorithms: An optimal quantum algorithm to approximate themean and its application for approximating the median of a set of points over an arbitrary distance with https://dl.acm.org/doi/pdf/10.1145/301250.301349, https://arxiv.org/abs/quant-ph/9607024

SDP and optimization

• Quantum SDP-Solvers: Better upper and lower bounds https://arxiv.org/pdf/1705.01843.pdf
• (Also the zero-sum games paper included above)
• ...

Quantum monte carlo

• Quantum Speed-ups of Monte Carlo methods https://arxiv.org/abs/1504.06987

Backtracking and branch and bound (also optimization)

• Quantum walk speedup of backtracking algorithms https://arxiv.org/abs/1509.02374 with taking into consideration also the implementation (https://arxiv.org/pdf/1908.11291.pdf ) and the resource estimation by Montanaro ( https://quantum-journal.org/papers/q-2019-07-18-167/ )
• Quantum branch and bound (https://arxiv.org/abs/1906.10375 )
• Improved backtracking using effective resistance https://arxiv.org/abs/1711.05295

Property testing

• Distributional property testing in a quantum world https://arxiv.org/abs/1902.00814
• A survey on quantum property testing: https://arxiv.org/pdf/1310.2035.pdf

Quantum algorithms for math problems in crypto

• Quantum algorithm for the collision problem https://arxiv.org/pdf/quant-ph/9705002.pdf
• Quantum algorithm for element distinctness https://arxiv.org/pdf/quant-ph/0311001.pdf
• Improved Classical and Quantum Algorithms for Subset-Sum https://arxiv.org/abs/2002.05276

New wavelet transforms

Improve QFT part with other non-Fourier transform (wavelet, fourier transform on groups, cosine transform).

https://cds.cern.ch/record/525836/files/0111038.pdf
https://arxiv.org/pdf/quant-ph/9809004.pdf
https://arxiv.org/pdf/quant-ph/0601043.pdf
qft on groups..

AI

• Quantum multi armed bandit ( https://arxiv.org/abs/2007.07049 )

Quantum algorithms for training NN

• Quantum neural networks https://arxiv.org/abs/1911.01117
• Quantum CNN https://arxiv.org/abs/1812.03089

QML

• Quantum algorithms for linear regression https://arxiv.org/pdf/1402.0660.pdf
• Quantum Support Vector Machine for Big Data Classification https://arxiv.org/abs/1307.0471
• A Quantum Search Decoder for Natural Language Processing ( https://arxiv.org/abs/1909.05023 )
• Quantum algorithms for training Gaussian Processes https://arxiv.org/abs/1803.10520
• Quantum nearest-neighbor algorithms for machine learning. https://arxiv.org/abs/1401.2142
• Quantum Inference on Bayesian Networks https://arxiv.org/pdf/1402.7359.pdf
• Quantum PCA https://www.nature.com/articles/nphys3029 (the idea for Hamiltonian simulation with density matrices, as we will have an improved version of QPCA from QADRA's paper..)
• Quantum recommendation systems https://arxiv.org/abs/1603.08675
• Quantum perceptron models https://papers.nips.cc/paper/2016/file/d47268e9db2e9aa3827bba3afb7ff94a-Paper.pdf ( I would also consider adding some explanation on the experiments conducted on this model. )
• Learning with Optimized Random Features: Exponential Speedup by Quantum Machine Learning without Sparsity and Low-Rank Assumptions https://arxiv.org/abs/2004.10756

Graph theory

• Quantum query complexity of some graph problems https://arxiv.org/pdf/quant-ph/0401091
• Quantum Speedup for Graph Sparsification, Cut Approximation and Laplacian Solving https://arxiv.org/abs/1911.07306
• Quantum walk search algorithms and effective resistance https://arxiv.org/abs/1912.04196 (and others)
• A Query-Efficient Quantum Algorithm for Maximum Matching on General Graphs.
• Quantum Algorithms for Connectivity and Related Problems https://arxiv.org/abs/1804.10591 and its applications https://arxiv.org/abs/1904.05995
• Learning graph based quantum query algorithms for finding constant-size subgraphs http://cjtcs.cs.uchicago.edu/articles/2012/10/cj12-10.pdf
• quantum algorithms for tree size estimation..

Theory

• A survey of quantum learning theory. https://arxiv.org/abs/1701.06806
• Quantum lower bounds by polynomials https://arxiv.org/pdf/quant-ph/9802049.pdf

Quantum algorithms for algebraic problems

• https://arxiv.org/abs/0812.0380

[mspronesti]

Hello @Scinawa , I suggest considering Quantum NLP for quantumalgorithms.org . Here are two papers I recommend:

• https://arxiv.org/abs/2012.03755
• https://arxiv.org/abs/2102.12846

[Scinawa]

Massimiliano, Thanks so much for pointing out those papers.

We know very well the work of these reserchers, and we think it's great work. However, these work are not yet algorithms, i.e. in the sense that they don't work in our fault-tolerant model of quantum computers, and there are no algorithms (i.e. theorems) with proofs showing runtimes/failure probability, so we decided to not include those results here (along with other papers of this kind, like QAOA/VQE/QNN circuits.)

But thanks anyway! :)