English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Several quantum algorithms for linear algebra problems, and in particularquantum machine learning problems, have been "dequantized" in the past fewyears. These dequantization results typically hold when classical algorithmscan access the data via length-squared sampling. In this work we investigatehow robust these dequantization results are. We introduce the notion ofapproximate length-squared sampling, where classical algorithms are only ableto sample from a distribution close to the ideal distribution in totalvariation distance. While quantum algorithms are natively robust against smallperturbations, current techniques in dequantization are not. Our main technicalcontribution is showing how many techniques from randomized linear algebra canbe adapted to work under this weaker assumption as well. We then use thesetechniques to show that the recent low-rank dequantization framework by Chia,Gily\'en, Li, Lin, Tang and Wang (JACM 2022) and the dequantization frameworkfor sparse matrices by Gharibian and Le Gall (STOC 2022), which are both basedon the Quantum Singular Value Transformation, can be generalized to the case ofapproximate length-squared sampling access to the input. We also apply theseresults to obtain a robust dequantization of many quantum machine learningalgorithms, including quantum algorithms for recommendation systems, supervisedclustering and low-rank matrix inversion.

Robust Dequantization of the Quantum Singular value Transformation and Quantum Machine Learning Algorithms