BEGIN:VCALENDAR VERSION:2.0 PRODID:-//TYPO3/NONSGML News system (news)//EN BEGIN:VEVENT UID:news-24971@cs.au.dk DTSTAMP:20250506T113009Z DTSTART:20250519T121500Z DTEND:20250519T140000Z END:VEVENT END:VCALENDAR

QUBITS Semniar: Talk by Professor Kasper Green Larsen

In this talk, Kasper Green Larsen presents the first provable exponential separation between quantum and quantum-inspired classical algorithms. The separation is shown for the basic problem of solving a linear system when the input matrix is well-conditioned and has sparse rows and columns.

Foto af Kasper Green Larsen

Info about event

Time

Monday 19 May 2025,  at 14:15 - 16:00

Add to calendar

Location

iNANO Auditorium (1593-012)

Event website

The QUIBITS Seminar Commitee welcomes all! The talk is followed by refreshments and informal discussions.

ABSTRACT Achieving a provable exponential quantum speedup for an important machine learning task has been a central research goal since the seminal HHL quantum algorithm for solving linear systems and the subsequent quantum recommender systems algorithm by Kerenidis and Prakash. These algorithms were initially believed to be strong candidates for exponential speedups, but a lower bound ruling out similar classical improvements remained absent. In breakthrough work by Tang, it was demonstrated that this lack of progress in classical lower bounds was for good reasons. Concretely, she provided a classical counterpart to the quantum recommender systems algorithm, reducing the quantum advantage to a mere polynomial. Her approach is quite general and was named quantum-inspired classical algorithms. Since then, almost all the initially exponential quantum machine learning speedups have been reduced to polynomial via new quantum-inspired classical algorithms. From the current state of affairs, it remains unclear whether exponential quantum speedups can be achieved for any natural machine learning task.

This is joint work with Allan Grønlund, Kvantify.