QLS Seminar - Mon. 29 July at 10:00am - "Quantum computing with classical data: Beyond time complexity" by Dar Gilboa, Google

[Quantitative Life Sciences]

Dear All,

On Monday, 29 July at 10:00 CET, Dar Gilboa (Google) will give a seminar 
titled:

*Quantum computing with classical data: Beyond time complexity
*

_Abstract:_

  If large, fault-tolerant quantum computers are ever built, it is 
widely believed that they will greatly enhance our understanding of 
quantum systems.
However, the impact of these computers on the processing of classical 
data remains uncertain. While there are a number of quantum algorithms 
offering potentially exponential speedups on generically useful 
classical tasks such as matrix inversion, it is unclear if any such 
speedups hold when including the cost of moving classical data to and 
from a quantum computer, and after carefully accounting for the scaling 
of stability parameters that determine the time complexity of these 
algorithms.
Nevertheless, quantum advantage is not restricted to time complexity, 
and there are many known examples of advantages in terms of other 
resources such as communication or space.
We prove that for generic tasks such as inference and gradient 
computation in distributed, parameterized models, networked quantum 
computers require exponentially less communication compared to any 
classical analog. This advantage applies to certain graph networks, and 
we demonstrate that these achieve competitive performance with state of 
the art neural networks on standard benchmarks. In addition, we prove 
that for some distributed computations, encoding classical data in 
quantum states prevents it from being re-used for repeated computation. 
This is a consequence of the destructive nature of quantum measurement, 
and does not require the use of any cryptographic primitives or 
computational assumptions. This phenomenon could have implications in 
incentivising the creation of datasets and the design of data markets.
_
The seminar will take place in the *Common area*, Ex SISSA building, 
Second floor, via Beirut 2_
__
You are all most welcome to attend!

Best regards,
Erica

Erica Sarnataro
Group Secretary
Quantitative Life Sciences
The Abdus Salam International Centre for Theoretical Physics (ICTP)
Trieste, Italy
Tel. +39-040-2240623
www.ictp.it/research/qls.aspx
e-mail: qls at ictp.it
<https://www.ictp.it/home/ictps-60th-anniversary>