周一 · 知古通今|周二 · 牧夫專欄

周三 · 太空探索|周四·觀測指南

周五·深空探索|周六·茶余星話|周日·視頻天象

原創作者：雷豐圖

校對：牧夫天文校對組

后期：胡永葳

責任編輯：王啟儒

導引

近年來，量子計算方面的突破接二連三，今天突破了多少多少量子比特，明天解決了某個需要超級經典計算機幾萬年才能解決的數學或物理問題。聽起來很厲害, 但是小編，有沒有什么簡單的例子就能體現量子計算的優越性呢?

有的，同學，有的，今天小編就從數學的角度來介紹一個只需要兩個量子比特，但又能體現量子優越性的算法——多伊奇算法。

2月19日微軟發布的Majorana 1芯片，使用了拓撲量子比特。

Credit: Positive News

核心問題

首先我們來看一下多伊奇算法想要解決的問題。現有任意函數f(x) : {0,1} —> {0,1}, 即輸入0或1，得到0或1。如何判斷f(x)是常數函數平衡函數：

常數函數：f(x) = f(1) = f(0) = 0或者1

平衡函數：正好有一種情況f(x) =0,一種情況f(x) = 1。

讓我們先來想一下經典計算機會怎么解決這個問題。最直觀的解法應該是，分別求出 f(0) , f(1)的具體值，然后看 f(0) 是否等于 f(1)。如果等于，則 f 是常數函數，反之則f為平衡函數。

在這個經典算法中我們調用了 f 函數兩次，因為我們在輸入端共有兩種可能性。

每一個量子比特都是0和1狀態的線性組合。稱為量子疊加態

Credit: Medium

量子門

不幸的是，量子算法中所用的量子門并不能直觀的和經典計算機中的門掛鉤，因此我們還需要定義一個新的門，即Hadamard 門，以下簡稱H。它的作用是將一個量子比特從經典狀態（∣0? 或 ∣1?）轉換為疊加態。總的來說，H門的結果如下：

如果輸入是 ∣0?，輸出是 1/√2 (∣0?+∣1?)

如果輸入是 ∣1?，輸出是 1/√2(∣0??∣1?)

測量以上的任意一種疊加態，得到∣0? 或 ∣1? 的可能性都將是1/2。

接下來我們將定義量子電路里的異或門（Uf gate），與經典電路相似，當輸入信號相異時，輸出為1；當輸入信號相同時，輸出為0。 在量子電路中，異或門需要兩個量子比特輸入∣x? ∣y?, 并得到兩個輸出∣x?∣f(x)⊕y?。

上下兩條線表示兩個量子比特由時間從左向右運行。∣Ψ1?代表在時刻1時，兩個量子比特所處的量子態。

Credit: Medium

多伊奇算法

現在，我們終于有了足夠的知識來跟著量子電路走一圈了！

想知道具體公式嗎，點擊下方即可

首先我們將兩個量子比特的狀態設置為∣Ψ1

? =∣0? ∣1?。第一步是在兩個量子比特上各進行一次H門，那么

接著我們對兩個量子比特進行異或門運算：

由于我們最后只需要對第一個量子比特進行測量，所以后面的運算將忽略第二個量子比特

如果f是常數函數，f(0) = f(1), 則f(0)⊕f(1) = 0, 這時對第一個量子比特進行測量就只有可能得到∣0?。反之如果f是平衡函數，f(0)⊕f(1) = 1，則第一個量子比特只有可能是∣1?。因此，我們可以通過量子比特的最終狀態來總結出f的性質。

?? 點擊紅字，查看公式

在多伊奇算法中，我們只調用了一次關于f的邏輯門（即異或門）。而經典算法則需要兩次，當該算法應用到輸入為n時，經典算法將會需要調用f 2^(n?1)+1次，而多伊奇算法仍然只需要一次異或門的運算即可得出f的性質，因此會對經典算法形成指數級的提升。我們稱該類優勢為量子優越性。

『天文濕刻』 牧夫出品

微信公眾號：astronomycn

Credit: Pixabay/CC0 Public Domain

牧夫

薦書

“太空的一天”系列以太空中的“一天”為時間線，給讀者講述了20 余個航天器在太空中的一天的故事。本套書為孩子呈現了浪漫、廣袤又充滿神秘的宇宙畫卷，用擬人化的手法展現了在太空中工作和旅行的航天器角色，用故事串聯起航天科普知識，讓孩子在唯美清新的插畫、幽默風趣的故事中學習前沿的科學文化知識。

兩年手繪巨制

呈現最美宇宙

謝謝閱讀