Berlin 2024 – scientific programme

Parts | Days | Selection | Search | Updates | Downloads | Help

QI: Fachverband Quanteninformation

QI 9: Quantum Machine Learning and Classical Simulability

QI 9.10: Talk

Tuesday, March 19, 2024, 12:15–12:30, HFT-FT 101

On the average-case complexity of learning output distributions of quantum circuits — Alexander Nietner¹, Marios Ioannou¹, Ryan Sweke^1,3, Richard Kueng², Jens Eisert¹, •Marcel Hinsche¹, and Jonas Haferkamp^1,4 — ¹FU Berlin — ²JKU Linz — ³IBM Quantum — ⁴Harvard University

In this work, we show that learning the output distributions of brickwork random quantum circuits is average-case hard in the statistical query model, which models most practical algorithms. Our main results are:

• At super logarithmic circuit depth d=ω(log(n)), any learning algorithm requires super polynomially many queries to achieve a constant probability of success over the randomly drawn instance.
• There exists a d=O(n), such that any learning algorithm requires Ω(2ⁿ) queries to achieve a Ω(2⁻ⁿ) probability of success over the randomly drawn instance.
• At infinite circuit depth d→∞, any learning algorithm requires 2^2Ω(n) many queries to achieve a 2^−2O(n) probability of success over the randomly drawn instance.

Moreover, we confirm a variant of a conjecture by Aaronson and Chen and show that the output distribution of a brickwork random quantum circuit is constantly far from any fixed distribution in total variation distance with probability 1−O(2⁻ⁿ).

Keywords: Random Quantum Circuits; Learning Quantum States; Average Case Complexity