Dear all,

Join us for the next QUBITS Seminar on May 19, 2025, where Professor Kasper Green Larsen (Dept. of Computer Science, AU) will give a talk entitled:

An Exponential Separation Between Quantum and Quantum-Inspired Classical Algorithms for Machine Learning

Date: May 19, 2025
Time: 14:15–16:00
Location: iNANO Auditorium (1593-012)
Format: 45-minute talk followed by refreshments

All are welcome! Drinks and snacks will be served after the talk.

Please accept this calendar invitation if you plan to attend—it helps us estimate catering needs.

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.

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.

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

For details and upcoming QUBITS Seminars, visit: https://projects.au.dk/quantum/qubit-seminars

We look forward to seeing you there.

Kindly note: You are receiving this email because you are part of the Quantum Campus Aarhus mailing list. If you wish to be removed, please contact me directly.

On behalf of the QUBITS Seminar Committee,
Jill Miwa (PHYS, iNANO), Tobias Weidner (CHEM, iNANO), Victoria Birkedal (CHEM, iNANO), Jaco van de Pol (CS), Christian Pascal Hirsch (MATH), and Andreas Roepstorff (AIAS, ARTS).

Best regards,

Lise (Quantum Campus Aarhus Coordinator)

Med venlig hilsen / Best regards,

Lise Refstrup Linnebjerg Pedersen

Special Consultant, MSc, PhD, Dip. Com.

ACT coordinator – Innovative Science Communication

Quantum Campus Aarhus (QCA) Coordinator (quantum.au.dk)

Trade Union Representative (DM, IDA, DJØF, PharmaDanmark)

Office: Bldg. 1590 room 222

Tel: +45 31 36 16 93

E-mail: lrlp@inano.au.dk

Personal website: au.dk/lrlp@inano.au.dk

Interdisciplinary Nanoscience Center (iNANO) 

Aarhus University

Gustav Wieds Vej 14

8000 Aarhus C, Denmark

Website: http://inano.au.dk/