# Quantum machine learning of large datasets using randomized measurements

arXiv: https://arxiv.org/abs/2108.01039 · HTML: https://mlsanity.com/paper/2108.01039/

## Key facts

- Cited by 30 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 65 references that are in the map.
- First posted on arXiv 2 Aug 2021.

## Builds on (most cited first, 14 of 14)

- [Supervised learning with quantum enhanced feature spaces](https://mlsanity.com/paper/1804.11326/) (2018)
- [Barren plateaus in quantum neural network training landscapes](https://mlsanity.com/paper/1803.11173/) (2018)
- [Power of data in quantum machine learning](https://mlsanity.com/paper/2011.01938/) (2020)
- [The effect of data encoding on the expressive power of variational quantum machine learning models](https://mlsanity.com/paper/2008.08605/) (2020)
- [A rigorous and robust quantum speed-up in supervised machine learning](https://mlsanity.com/paper/2010.02174/) (2020)
- [Predicting Many Properties of a Quantum System from Very Few Measurements](https://mlsanity.com/paper/2002.08953/) (2020)
- [Supervised quantum machine learning models are kernel methods](https://mlsanity.com/paper/2101.11020/) (2021)
- [Provably efficient machine learning for quantum many-body problems](https://mlsanity.com/paper/2106.12627/) (2021)
- [Experimental Quantum Generative Adversarial Networks for Image Generation](https://mlsanity.com/paper/2010.06201/) (2020)
- [Training Quantum Embedding Kernels on Near-Term Quantum Computers](https://mlsanity.com/paper/2105.02276/) (2021)
- [Capacity and quantum geometry of parametrized quantum circuits](https://mlsanity.com/paper/2102.01659/) (2021)
- [Experimental kernel-based quantum machine learning in finite feature space](https://mlsanity.com/paper/1906.04137/) (2019)
- [Optimal training of variational quantum algorithms without barren plateaus](https://mlsanity.com/paper/2104.14543/) (2021)
- [Noisy intermediate-scale quantum algorithm for semidefinite programming](https://mlsanity.com/paper/2106.03891/) (2021)

## Built on by (most cited first, 30 of 30)

- [Quantum machine learning beyond kernel methods](https://mlsanity.com/paper/2110.13162/) (2021)
- [Shadows of quantum machine learning](https://mlsanity.com/paper/2306.00061/) (2023)
- [Universal expressiveness of variational quantum classifiers and quantum kernels for support vector machines](https://mlsanity.com/paper/2207.05865/) (2022)
- [Quantum Kernel Methods under Scrutiny: A Benchmarking Study](https://mlsanity.com/paper/2409.04406/) (2024)
- [High Dimensional Quantum Machine Learning With Small Quantum Computers](https://mlsanity.com/paper/2203.13739/) (2022)
- [Quantum Machine Learning on Near-Term Quantum Devices: Current State of Supervised and Unsupervised Techniques for Real-World Applications](https://mlsanity.com/paper/2307.00908/) (2023)
- [An Invitation to Distributed Quantum Neural Networks](https://mlsanity.com/paper/2211.07056/) (2022)
- ['Eliv'agar: Efficient Quantum Circuit Search for Classification](https://mlsanity.com/paper/2401.09393/) (2024)
- [Generalization of Quantum Machine Learning Models Using Quantum Fisher Information Metric](https://mlsanity.com/paper/2303.13462/) (2023)
- [Quantum Gaussian Process Regression for Bayesian Optimization](https://mlsanity.com/paper/2304.12923/) (2023)
- [Reinforcement learning-based architecture search for quantum machine learning](https://mlsanity.com/paper/2406.02717/) (2024)
- [Neural auto-designer for enhanced quantum kernels](https://mlsanity.com/paper/2401.11098/) (2024)
- [Demonstration of Robust and Efficient Quantum Property Learning with Shallow Shadows](https://mlsanity.com/paper/2402.17911/) (2024)
- [Adaptive Non-local Observable on Quantum Neural Networks](https://mlsanity.com/paper/2504.13414/) (2025)
- [Compositional optimization of quantum circuits for quantum kernels of support vector machines](https://mlsanity.com/paper/2203.13848/) (2022)
- [Distributed Quantum Neural Networks via Partitioned Features Encoding](https://mlsanity.com/paper/2312.13650/) (2023)
- [Automating quantum feature map design via large language models](https://mlsanity.com/paper/2504.07396/) (2025)
- [Quantum Reinforcement Learning by Adaptive Non-local Observables](https://mlsanity.com/paper/2507.19629/) (2025)
- [sQUlearn -- A Python Library for Quantum Machine Learning](https://mlsanity.com/paper/2311.08990/) (2023)
- [On the similarity of bandwidth-tuned quantum kernels and classical kernels](https://mlsanity.com/paper/2503.05602/) (2025)
- [A Modified Depolarization Approach for Efficient Quantum Machine Learning](https://mlsanity.com/paper/2404.07330/) (2024)
- [QuXAI: Explainers for Hybrid Quantum Machine Learning Models](https://mlsanity.com/paper/2505.10167/) (2025)
- [Quantum Text Classifier -- A Synchronistic Approach Towards Classical and Quantum Machine Learning](https://mlsanity.com/paper/2305.12783/) (2023)
- [Experimental robustness benchmarking of quantum neural networks on a superconducting quantum processor](https://mlsanity.com/paper/2505.16714/) (2025)
- [Optimal algorithmic complexity of inference in quantum kernel methods](https://mlsanity.com/paper/2604.15214/) (2026)
- [AutoQML: A Framework for Automated Quantum Machine Learning](https://mlsanity.com/paper/2502.21025/) (2025)
- [Predicting fermionic densities using a Projected Quantum Kernel method](https://mlsanity.com/paper/2504.14002/) (2025)
- [Maritime object classification with SAR imagery using quantum kernel methods](https://mlsanity.com/paper/2512.11367/) (2025)
- [Tackling Heterogeneity in Quantum Federated Learning: An Integrated Sporadic-Personalized Approach](https://mlsanity.com/paper/2601.07882/) (2026)
- [Parameterized Quantum Circuits as Feature Maps: Representation Quality and Readout Effects in Multispectral Land-Cover Classification](https://mlsanity.com/paper/2604.26675/) (2026)

## Abstract (arXiv)

Quantum computers promise to enhance machine learning for practical applications. Quantum machine learning for real-world data has to handle extensive amounts of high-dimensional data. However, conventional methods for measuring quantum kernels are impractical for large datasets as they scale with the square of the dataset size. Here, we measure quantum kernels using randomized measurements. The quantum computation time scales linearly with dataset size and quadratic for classical post-processing. While our method scales in general exponentially in qubit number, we gain a substantial speed-up when running on intermediate-sized quantum computers. Further, we efficiently encode high-dimensional data into quantum computers with the number of features scaling linearly with the circuit depth. The encoding is characterized by the quantum Fisher information metric and is related to the radial basis function kernel. Our approach is robust to noise via a cost-free error mitigation scheme. We demonstrate the advantages of our methods for noisy quantum computers by classifying images with the IBM quantum computer. To achieve further speedups we distribute the quantum computational tasks between different quantum computers. Our method enables benchmarking of quantum machine learning algorithms with large datasets on currently available quantum computers.