Perspectives on Noisy Quantum Computation and the Computational Complexity of Quantum Determinants

Share this post:

DATE	2025-03-24

TIME	12:10-13:10

PLACE	R36173, 1F, Dept. of Physics, Building of Science College, NCKU

FIELD	Quantum Information Science

SPEAKER	Prof. En-Jui Kuo - Department of Electrophysics, National Yang Ming Chiao Tung University

TITLE	Perspectives on Noisy Quantum Computation and the Computational Complexity of Quantum Determinants

ABSTRACT	In this commentary, we investigate the computational complexity of noisy quantum circuits and quantum determinants, drawing insights from severak key results. The first establishes an oracle separation between noisy intermediate-scale quantum (NISQ) computation and the Polynomial Hierarchy (PH), demonstrating that even shallow quantum circuits with constant error rates can achieve separation without requiring error correction. This underscores the potential computational advantages of noisy quantum systems over classical models. The second result concerns the complexity of quantum determinants, specifically the q-deformed permanent, and proves its worst-case hardness. In particular, computing the q-permanent at certain roots of unity is shown to be #P-hard, implying that an efficient algorithm would lead to a collapse of PH. Furthermore, connections to algebraic number theory and random self-reducibility offer deeper insights into the inherent difficulty of approximating quantum determinants. Together, these findings illuminate the intricate interplay between noise, quantum computational power, and complexity theory.

2025-03-24 12:10:00 ~ 2025-03-24 13:10:00