The Computational Complexity of Quantum Determinants
這文章大概去年五月我開始有想法 在TQC 上認識了 aaronson底下的cs博士後 台灣洪學長 跟他開始完成這個crazy idea
大致上是說 我們知道boson 交換會沒有phase 如果用unitary 去act on boson 產生的amplitude 就是 permanent 的模平方 permanent of 一個矩陣就是 determinant 但沒有minus sign
Valiant 197x證明 Permanent is sharp p hard in complexity point of view 之後inspire aaronson 的文章 證明exact boson sampling 不能被古典電腦simulated 否則PH collapses
反之 如果是用determinant 就有高斯消去法 所以fermion 就會好模擬
所以我問 如果交換差一個phase 但不是正負一會怎樣 複雜度是簡單還是困難
後來調查 這就是數學家20年前開始在 representation theory 中的q-deformation 會出現的function 被前人取名叫做Quantum Determinants
當q=1就是permanent 當q=-1就是determinant
但沒有人研究過它的複雜度 所有關於這東西的文獻幾乎都是純代數的 也出現在很多群表現的研究上 hopf algebra 之類
所以我們就開始這個研究 這個東西的計算複雜度
結論我們˙證明發現 當q 是prime power roof of unity 時候
q-permanent 是 mod p hard 然後再利用toda theorem 證明
如果存在poly算法計算 這樣的東西 PH也會塌縮
這用到的數論當中 cyclotomic polynomial 的性質
第二部分更難的是證明這樣的function 很難去近似
permanent 的狀況之下 因為permanent是整數 所以兩個整數之間
至少差1 藉由這個性質 可以輕鬆做出reduction 用binary search
但在我們的情況之下 q-permanent 是一堆root of unity 的power +再一起 不一定是整數 兩個不同的數字差距 也可能無限小 證明就過不去 但發現 q-permanent 雖然不是整數
但卻是 代數整數 (algebraic number!!!)
之後用到algebraic number theory 一些heavy 的tool 最重要的 用有理數逼近的liouville theorem
去估計下界 在完成這個證明 很辛苦
結論是 當q 是prime power roof of unity 時候
q-permanent 是 mod p hard
且 也是hard to approximate
證明技巧用到數論 cyclotomic polynomial, euler function, algebraic number theory 這些東西 再加上一些複雜度的知識
總算對科學有一點點貢獻
Open question:
對，non prime power 跟real q 我們沒辦法做
因為使用的數論工具做不動這個問題
有賴版上有興趣的朋友一起想 可以一起做
感謝學長接受我常常跳痛的證明思維
其實真難 做數學 想一下 可能是對 在想一下 怪怪的 又想一下 沒問題 在想一下 又怪怪的 來來往往 無數的夜晚在邊看妹直播中 想證明
可以去竹科了 阿 竹科不收 乾 arxiv link
