New papers and algorithms #33
Description
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