# Chapter 15 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. 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
`#algo`

`#crypto`

- Improved quantum algorithms for linear and nonlinear differential equations
`#algo`

- New Quantum Algorithms for Computing Quantum Entropies and Distances
`#algo`

- Quantum machine learning with subspace states
`#algo`

- A quantum algorithm for solving eigenproblem of the Laplacian matrix of a fully connected graph
`#algo`

- Quantum State Preparation with Optimal Circuit Depth: Implementations and Applications
`#algo, #theory`

- Quantum Meets Fine-Grained Complexity: Sublinear Time Quantum Algorithms for String Problems
`#algo`

- Two-level Quantum Walkers on Directed Graphs II: An Application to qRAM
`#algo`

- Memory Compression with Quantum Random-Access Gates
- Mean estimation when you have the source code; or, quantum Monte Carlo methods
- Exact and efficient Lanczos method on a quantum computer
- On establishing learning separations between classical and quantum machine learning with classical data
- Matching Triangles and Triangle Collection: Hardness based on a Weak Quantum Conjecture
- Partition Function Estimation: Quantum and Quantum-Inspired Algorithms
- A Faster Quantum Algorithm for Semidefinite Programming via Robust IPM Framework
- Quantum Subroutine Composition
`#algo`

- Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis
`#theory`

- Quantum Algorithms for Sampling Log-Concave Distributions and Estimating Normalizing Constants
`#algo`

- Quantum divide and conquer

#### 2021

- Information-theoretic bounds on quantum advantage in machine learning
`#theory`

- Noisy intermediate-scale quantum (NISQ) algorithms
`#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
`#algo`

- Quantum Perceptron Revisited: Computational-Statistical Tradeoffs
`#algo`

- Lower bounds for monotone arithmetic circuits via communication complexity
`#theory`

- Fast algorithm for quantum polar decomposition, pretty-goodmeasurements, and the Procrustes problem
`#algo`

- Quantum Algorithms based on the Block-Encoding Framework for Matrix Functions by Contour Integrals
`#algo`

- Classical and Quantum Algorithms for Orthogonal Neural Networks
`#algo`

- Quantum Semi Non-negative Matrix Factorization
`#algo`

- Quantum Algorithms based on the Block-Encoding Framework for Matrix Functions by Contour Integrals
- Quantum Alphatron
`#algo`

- Quantum SubGaussian Mean Estimator
`#algo`

- A randomized quantum algorithm for statistical phase estimation
`#algo`

- Near-Optimal Quantum Algorithms for String Problems
`#algo`

- Quantum Algorithms and Lower Bounds for Linear Regression with Norm Constraints
`#algo`

- Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture
`#algo`

- A randomized quantum algorithm for statistical phase estimation
`#algo`

- Nearly Optimal Quantum Algorithm for Estimating Multiple Expectation Values
`#algo`

- Quantum Algorithms for Reinforcement Learning with a Generative Model
`#algo`

`#qrl`

`#qmc`

- Quantum Monte-Carlo Integration: The Full Advantage in Minimal Circuit Depth
`#algo`

`#qmc`

- Near-Optimal Quantum Algorithms for Multivariate Mean Estimation
`#algo`

`#qmc`

- Quantum algorithms for multivariate Monte Carlo estimation
`#algo`

`#qmc`

- Quantum Sub-Gaussian Mean Estimator
`#algo`

`#qmc`

- Quantum algorithm for stochastic optimal stopping problems
`#qfinance`

`#algo`

- Quantum Machine Learning For Classical Data
`#thesis`

- Quantum algorithms for anomaly detection using amplitude estimation
`#algo`

- Two-level Quantum Walkers on Directed Graphs I: Universal Quantum Computing
`#algo`

- Quantum algorithms for learning a hidden graph and beyond
`#algo`

- Asymptotically Optimal Circuit Depth for Quantum State Preparation and General Unitary Synthesis

#### 2020

- Variational Quantum Algorithms
`#review`

- Circuit-centric Quantum Classifier
`#variational`

- Quantum polar decomposition algorithm
`#algo`

- The power of quantum neural networks
`#variational`

- Robust quantum minimum finding with an application to hypothesis selection
`#algo`

- Quantum exploration algorithms for multi-armed bandits
`#algo`

- Sublinear classical and quantum algorithms for general matrix games
`#algo`

#### 2019

- Quantum Language Processing
`#NLP`

- A Quantum Search Decoder for Natural Language Processing
`#NLP`

- Quantum and Classical Algorithms for Approximate Submodular Function Minimization
`#algo`

- Quantum algorithms for zero-sum games
`#algo`

- Practical implementation of a quantum backtracking algorithm
`#experiment`

- Quantum speedup of branch-and-bound algorithms
`#algo`

- The Quantum Version Of Classification Decision Tree Constructing Algorithm C5.0
`#algo`

- Sublinear quantum algorithms for training linear and kernel-based classifiers
`#algo`

- Quantum Algorithms for Classical Probability Distributions
`#algo`

`#qmc`

#### 2018

- Continuous-variable quantum neural networks 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
`#variational`

- Artificial Quantum Neural Network: quantum neurons, logical elements and tests of convolutional nets. A new approach to qnn /. 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
`#algo`

- Quantum Statistical Inference
`#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
`#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
`#review`

`#tutorial`

This is a very nice review of some of the most known qml algorithms. - Quantum algorithm implementations for beginners
`#review`

`#tutorial`

- Quantum linear systems algorithms: a primer
`#review`

- Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
`#algo`

- The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation
`#algo`

- Applying quantum algorithms to constraint satisfaction problems
`#resource-estimation`

- Quantum Chebyshev’s Inequality and Applications
`#qmc`

- From linear combination of quantum states to Grover’s searching algorithm

#### 2017

- Implementing a distance based classifier with a quantum interference circuit
`#algo`

- Quantum SDP solvers: Large speed-ups, optimality, and applications to quantum learning
`#algo`

- Quantum machine learning for quantum anomaly detection
`#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:
`#review`

`#quantum learning theory`

- Quantum Neuron: an elementary building block for machine learning on quantum computers
- Quantum speedup of Monte Carlo methods
`#algo`

- Improved quantum backtracking algorithms using effective resistance estimates
`#algo`

#### 2015

- Advances in quantum machine learning
`#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`#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
`#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
`#algo`

- Fixed-point quantum search with an optimal number of queries
`#algo`

- Quantum Principal Component Analysis
`#algo`