京都大學的一個研究小組等首次從理論上證明,即使是只能使用一個量子比特的“弱”量子計算機,也比經典計算機“強”。
量子計算機是基於解釋微觀世界的物理理論“量子力學”運行的計算機。據說遠超我們目前使用的“經典計算機”的超高速計算是可能的。
然而,能夠自由處理大量量子比特的巨型通用量子計算機的實現仍遙遙無期。因此,有大量研究表明,即使是在不久的將來可以實現的“弱”量子計算機,也比經典計算機具有優勢(量子霸權)。
例如,“one-clean qubit model”是 1998 年提出的最古老的“弱”量子計算模型之一。 雖然只能使用一個量子位並且看起來很弱,但它已被證明能夠有效地計算沒有已知有效方法來計算瓊斯多項式的量。但是,如果發現了一種計算瓊斯多項式的有效經典算法,則單淨量子比特模型就失去了對經典的優越性,因此不能說它是可靠的量子超前性。
在這種情況下,課題組首次採用新的方法,成功地從理論上證明了one-clean qubit模型的優越性。此外,本次發現的方法可以應用於其他類型的弱量子計算模型,我們已經成功地在比以前更強的計算複雜性理論基礎上證明了這些模型的量子先行性。
這一成果為正在世界範圍內推進的量子超前性研究奠定了理論基礎,並有望為未來量子計算研究的發展做出巨大貢獻。