Abstract
Quantum computers promise superior computational power over classical computers for some structured problems. While this insight is not new, only in recent years, steps have been taken to actually build intermediate-sized quantum devices, creating an exciting state of affairs. For some paradigmatic problems, there is some evidence that quantum computers may outperform classical devices [1]. For practically motivated problems in machine learning [2, 3] and in optimization [4], fault tolerant quantum computers may indeed perform better than classical ones. While this is promising, actual systems to date are relatively small and noisy. The main part of the talk is actually concerned with identifying limitations to near-term quantum computing. We discuss notions of learnability of output distributions of short quantum circuits - as they can be seen as parts of variational quantum algorithms - and find that a single T-gate renders learning them hard [5]. We identify exponentially tighter bounds on limitations of quantum error mitigation [6]. We finally - and with the greatest emphasis - discuss the impact of non-unital noise on quantum computing, with quite unexpected results [7]. We end on the note that while fault tolerant quantum computers offer substantial computational benefits, the race is still open for near-term quantum devices.
[1] Computational advantage of quantum random sampling, D. Hangleiter, J. Eisert, Rev. Mod. Phys. 95, 035001 (2023).
[2] Towards provably efficient quantum algorithms for large-scale machine-learning models, J. Liu, M. Liu, J.-P. Liu, Z. Ye, Y. Wang, Y. Alexeev, J. Eisert, L. Jiang, Nature Comm. 15, 434 (2024).
[3] A super-polynomial quantum-classical separation for density modelling, N. Pirnay, R. Sweke, J. Eisert, J.-P. Seifert, Phys. Rev. A 107, 042416 (2023).
[4] An in-principle super-polynomial quantum advantage for approximating combinatorial optimization problems via computational learning theory, N. Pirnay, V. Ulitzsch, F. Wilde, J. Eisert, J.-P. Seifert, arXiv:2212.08678, Science Adv. (2024).
[5] A single T-gate makes distribution learning hard, M. Hinsche, M. Ioannou, A. Nietner, J. Haferkamp, Y. Quek, D. Hangleiter, J.-P. Seifert, J. Eisert, R. Sweke, Phys. Rev. Lett. 130, 240602 (2023).
[6] Exponentially tighter bounds on limitations of quantum error mitigation, Y. Quek, D. Stilck França, S. Khatri, J. Jakob Meyer, J. Eisert, arXiv:2210.11505, Nature Phys., in press (2024).
[7] Noise-induced shallow circuits and absence of barren plateaus, A. A. Mele, A. Angrisani, S. Ghosh, A. Khatri, J. Eisert, Y. Quek, D. Stilck Franca, arXiv:2403.13927 (2024).