最近終於 搞了一個純理論的文章 好久沒有搞這種了
The Computational Complexity of Quantum Determinants
這文章大概去年五月我開始有想法 在TQC 上認識了 aaronson底下的cs博士後 台灣洪學長 跟他開始完成這個crazy idea
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
No comments:
Post a Comment