Chapter 14 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
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
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
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 In the paper the authors were able to implement a neuron based on a thing called RUC-circuit (repeat until success), which allowed them to capture the nonlinearity of the sigmoid used often in the classical neuron as activation function. It is not very clear to me how to use this model to solve a problem in a data analysis.
- Quantum speedup of Monte Carlo methods
#algo
- Improved quantum backtracking algorithms using effective resistance estimates
#algo
2016
- Quantum Discriminant Analysis for Dimensionality Reduction and Classification
#algo
Here the authors wrote two different algorithm, one for dimensionality reduction and the second for classification, with the same capabilities - An efficient quantum algorithm for spectral estimation
#algo
- Quantum Recommendation Systems
#algo
It is where you can learn about QRAM and quantum singular value estimation.
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
This paper offer two approaches for calculating distances between vectors. The idea for k-NN is to calculate distances between the test point and the training set in superposition and then use amplitude amplification tecniques to find the minimum, thus getting a quadratic speedup.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
Quantum Principal Component Analysis
#algo
The authors discovered how partial application of the swap test are sufficient to transform a quantum state \(\sigma\) into \(U\sigma U^\dagger\) where \(U=e^{-i\rho}\) given the ability to create multiples copies of \(\rho\). This work uses a particular access model of the data (sample complexity), which can be obtained from a QRAM
2013
- Quantum algorithms for supervised and unsupervised machine learning
#algo
This explain how to use swap test in order to calculate distances. Then it shows how this swap-test-for-distances can be used to do NearestCentroid and k-Means with adiabatic quantum computation - Exponential improvement in precision for simulating sparse Hamiltonians
#algo