Time:12:10, Monday, Mar. 24, 2025
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
Place : R36173, 1F, Dept. of Physics, Building of Science College, NCKU

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.