QLS Seminar: Quantum computing with classical data: Beyond time complexity
Starts 29 Jul 2024 10:00
Ends 29 Jul 2024 11:00
Central European Time
ICTP
Common Area, ex SISSA building, second floor
Via Beirut, 2
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.