EUVIMEDEUVIMED entdecken
Crossref

Superpolynomial quantum-classical separation for density modeling

Niklas Pirnay, Ryan Sweke, Jens Eisert, Jean-Pierre Seifert

Physical Review A · 13.04.2023 · 107 (4)

DOI: 10.1103/physreva.107.042416 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Physical Review A, online erschienen am 13.04.2023. Verfasst von Niklas Pirnay und 3 weiteren Autor:innen. Die Arbeit wurde bisher 21-mal zitiert (Crossref) und nennt 20 Literaturangaben. Gefördert von: Berlin University Alliance, Deutsche Forschungsgemeinschaft, Bundesministerium für Bildung und Forschung.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Density modelling is the task of learning an unknown probability density function from samples, and is one of the central problems of unsupervised machine learning. In this work, we show that there exists a density modelling problem for which fault-tolerant quantum computers can offer a super-polynomial advantage over classical learning algorithms, given standard cryptographic assumptions. Along the way, we provide a variety of additional results and insights, of potential interest for proving future distribution learning separations between quantum and classical learning algorithms. Specifically, we (a) provide an overview of the relationships between hardness results in supervised learning and distribution learning, and (b) show that any weak pseudo-random function can be used to construct a classically hard density modelling problem. The latter result opens up the possibility of proving quantum-classical separations for density modelling based on weaker assumptions than those necessary for pseudo-random functions.

Förderung

  • Berlin University Alliance
  • Deutsche Forschungsgemeinschaft
  • Bundesministerium für Bildung und Forschung
  • Berlin Institute for the Foundations of Learning and Data

Zitieren

APA

Pirnay, N., Sweke, R., Eisert, J., & Seifert, J. (2023). Superpolynomial quantum-classical separation for density modeling. Physical Review A, 107(4). https://doi.org/10.1103/physreva.107.042416

Vancouver

Pirnay N, Sweke R, Eisert J, Seifert J. Superpolynomial quantum-classical separation for density modeling. Physical Review A. 2023;107(4). doi:10.1103/physreva.107.042416

BibTeX
@article{Pirnay2023,
  author = {Pirnay, Niklas and Sweke, Ryan and Eisert, Jens and Seifert, Jean-Pierre},
  title = {Superpolynomial quantum-classical separation for density modeling},
  journal = {Physical Review A},
  year = {2023},
  volume = {107},
  number = {4},
  doi = {10.1103/physreva.107.042416}
}
Kostenlos starten →