Exploring the Computational Limitations of Noisy Quantum Devices

Exploring the Computational Limitations of Noisy Quantum Devices
Date & Time: 
Thursday, March 21, 2024 - 16:00 to 17:00
Xiongfeng Ma, Tsinghua University
Room S306, NYU Shanghai New Bund Campus (Please RSVP) & Hosted via Zoom

- RSVP if attending onsite -

- Join via Zoom -


Quantum computing promises significant enhancement in computational capabilities, provided we navigate the inherent challenges of noise within quantum systems. However, scalable quantum error correction remains out of reach, primarily due to the high noise levels and the limited qubit count. Consequently, current quantum devices, ranging from dozens to several hundred noisy qubits, are situated between classical computing and fault-tolerant quantum computing, known as Noisy Intermediate-Scale Quantum (NISQ) devices.

In this talk, I shall present the intrinsic computational limitation and entanglement generation capabilities of noisy quantum devices without error correction. Our investigation reveals that devices exceeding circuit depths of $\omega(\log(n))$ become computationally indistinguishable from conventional classical processes when examined through polynomial-time algorithms. This constraint decisively eliminates the potential for executing renowned quantum algorithms, including those devised by Shor, Grover, and the Harrow-Hassidim-Lloyd, and polynomial-depth variational quantum algorithms and simulations within this noisy regime. Furthermore, we extend our analysis to entanglement, unveiling an upper bound of $O(\log(n))$ for entanglement generation within linear qubit arrays. This study underscores the scalability challenges noisy quantum systems face in harnessing the full power of quantum entanglement. This talk is primarily based on the work [arXiv:2306.02836].


Xiongfeng Ma is currently a Professor at Tsinghua University. His main research interest lies in quantum information and optics, particularly in quantum cryptography, quantum foundation, and quantum computing. After obtaining his BSc at Peking University in 2003, Xiongfeng attended the University of Toronto for his PhD. In 2012, he joined Tsinghua University. In 2023, Xiongfeng was elected as an APS Fellow in the Division of Quantum Information.

Seminar by the NYU-ECNU Institute of Physics at NYU Shanghai