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, #variationalA 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, #algoA 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-paperIs 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#tutorialThis 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
#algoHere 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,#reviewIt 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
#algoThis 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