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

Share this post:

日期	2025-03-24

時間	12:10-13:10

地點	理學教學新大樓物理系1F 36173會議室

領域	Quantum Information Science

講者	郭恩瑞教授 - 國立陽明交通大學電子物理系

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

摘要	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