“九章 ”量子 计算机 为啥 快 ？玻色 采样 是 什么 ？量子 霸权 时代 来 了 吗？ (1) Why is the "Nine Chapters" quantum computer fast? What is Bose sampling? Has the era of quantum supremacy arrived? (1)

各位 同學 大家 好 我 是 李永樂 老師

最近 有壹個 大 新聞

說 是 中國 科學技術 大學 潘建偉 團隊

創造 出 了 世界 壹流 的 量子 計算機 原型機 九章

九章 計算機 在 計算 玻色 采樣 問題 的 時候

幾百 秒 的 計算結果

超級計算機 卻 需要 計算 幾十億年

有 小朋友 就問 我 說

這個 玻色 采樣 問題 到底 是 怎 麽 壹個 問題 呢

九章 計算機 真的 這 麽 能 算 嗎

那 我們 的 銀行 密碼 還 安全 不 安全 呢

今天 我們 就 來 討論 壹下 這個 問題

因為 九章 計算機 是 壹個 新型 的 計算機

我 今天 的 討論 是 基於 我 自己 的 理解

那 麽 如果 大家 有 不 同意 的 意見

也 可以 寫 在 評論 區裏

我們 首先 先來 討論 壹個 以前 討論 過的 問題

叫做 高爾頓 釘板

高爾頓 釘板

我們 在 之前 講正態 分布 的 時候 就 討論 過

高爾頓 釘板 它 長 這個 樣子

這壹個 可以 放 珠子 的 口

然後 有壹個 這樣 的 通道 有壹個 這樣 的 通道

然後 裏面 有壹些 橫著 的 釘子

壹排 兩排 三排 四排 有壹些 橫著 的 釘子

然後 在 這個 釘子 最 底下 又 有 壹些 槽

那 麽 現在 我 如果 把 壹個 小球 從 這 上面 放 過去

比如 我 在 這裏 放壹個 小球 放進去

然後 我 就問 妳 落 在 每壹個 槽 裏 的 概率 有 多 大

那 這 就是 所謂 的 高爾頓 釘板 的 問題

其實 這個 問題 也 不難 計算

妳 看 我 這個 球 過來 之後

我 到 這個 位置 只有 壹種 方法

那 麽 如果 它 想 掉 到 左邊 怎 麽 辦

妳 撞 第壹個 釘子 時 可以 往 左 跑 也 可以 往右 跑

但是 如果 妳 想 掉 到 最 左邊 這個 槽

妳 撞 第壹個 釘子 之後 必須 得 往 左 跑

妳 又 撞 了 第二個 釘子

妳 也 必須 得 往 左 跑

妳 再 往 左 再往 左

最後 妳 只有 這 麽 壹條 路徑 能夠 掉 到 這裏 邊

對 不 對

所以 最終 掉 到 左邊 的 這塊 方法 數只 有壹種

同樣 道理

如果 這個 小球 想 掉 到 最 右邊 這個 槽 裏

它 也 只能 壹路 向右走

所以 也 只有 壹種 方法 能夠 掉 到 最 右邊 這個 槽 裏

但是 如果 掉 到 中間 這些 個 槽 妳 怎 麽 計算 呢

我們 要 這 麽 想

妳 如果 想 掉 到 這個 位置 的話 妳 怎 麽 走

妳 可以 先 走 到 這 再 折回來

妳 也 可以 先 走 到 右邊 再 折回來

所以 到 這兒 的 方法 數

其實 是 到 左上 和 到 右 上 的 方法 數之 和 對 嗎

所以 到 這兒 的 方法 數 應該 有 兩種

就是 妳 可以 這 麽 走 妳 也 可以 這 麽 走 是不是

那 麽 到 這兒 方法 數有 幾種

妳 可以 從 這兒 過來 也 可以 從 這兒 過來

有 1+2 等於 3 種

到 這的 方法 數也 是 3 種 4 6 4

大家 看 出來 了 嗎

這 實際上 是 壹個 什 麽

楊輝三角 對 不 對

所以 妳有 4 種 方法 到 這個 槽 裏

有 6 種 方法 到 這個 槽 裏

有 4 種 方法 到 這個 槽 裏

每壹種 運動 的 方法 概率 都 是 相等 的

壹 共有 多少 種 方法

壹 共有 1+4+6+4+1

壹 共有 16 種 方法

所以 到 左邊 這個 槽

概率 1/16 4/16 6/16( 更正 )

4/16 和 1/16

我們 用 手算 很快 就 能夠 把 這種 4 層算 出來

但是 層數 如果 多 了 怎 麽 辦 呢

那 麽 人們 經過 計算 可以 得到 這樣 壹個 結果

說 如果 妳有 什 麽 呀

如果 妳有 n 排 釘子

如果 有 n 排 釘子

n 排 釘子 的話

比如 我 這裏 有 4 排 釘子 槽 就是 有 5 個

所以 是 有 n+1 個什 麽

n+1 個 槽

然後 我們 落入 這個 球

我 落入 第 k 個 槽 第 k 個 槽

註 意 k 壹定 小於 等於 n+1 對 吧

k 壹定 小於 等於 n+1

因為 壹 共 就 只有 n+1 個 槽

這個 概率 有 多 大 呢

這個 概率 是 可以 計算 的

概率 P 應該 是 等 C(n,k-1)/2ⁿ

咱們 仔細 看 2ⁿ 什 麽 意思

就是 妳 每 落到 壹個 釘子 上

妳 要 麽 往 左 要 麽 往右

每壹次 妳 都 有 兩種 選擇 對 吧

妳 要 遇到 n 排 釘子

所以 妳有 2ⁿ 種 選擇

每壹種 選擇 都 是 等 可能 的

因此 這個 就是 總共 的 可能性 個數

那 麽 C(n,k-1) 什 麽 意思

那 麽 妳 落到 第 k 個 槽 其實 意思 是 啥

比如 妳 落到 第壹個 槽

就是 所有 每壹次 撞 釘子 妳 都 得 往左邊 走

妳 不能 往右邊 走 對 不 對

如果 妳 落到 這兒 的話

就 說明 妳在 這 幾次 碰釘子 的 過程 中

有壹次 是 往右 的 剩下 的 都 是 往 左 的

那 這個 方法 數就 叫 組合 數 C(n,k-1)

所以 它 實際上 表示 的 是 落入 這個 球 的 方法 數

落入 這個 球 的 方法 數

壹個 是 總 方法 數

壹個 是 落入 這個 槽 的 方法 數

它 倆 壹 除 就是 這個 概率 了

那 麽 如果 我們 繼續 把 這個 問題 算壹下

這個 問題 算 完 了 之後

展開式 是 什 麽 樣子 的 呢

它 應該 是 1/2ⁿ 再 乘以

這裏 邊 這個 C(n,k-1) 它 的 寫法 是 這樣 寫 的

叫 1×2×3 壹直 乘 乘到 k-1

底下 是 k-1 的 階乘 上面 是 什 麽

是 n×(n-1) 乘 壹直 乘到 n-k+2 它 是 這 麽 個數

好 如果 我們 從 數學 上去 計算

這個 概率 的 算法 就 長 的 是 這個 樣子

但是 大家 仔細 看

如果 這個 n 比較 小 這事 還 好辦

但是 壹旦 n 要是 大 了 的話

那 這個 數就 非常 非常 龐大 計算機 可能 算不了

我舉 個例 子

如果 妳有 100 個 槽 妳 可以 帶進去 算壹下

100 排 釘子 101 個 槽 這種 情況

妳 這個 算 階乘 的 時候 妳 要 算 到 100 的 階乘

100 的 階乘

可以 達到 10¹³⁷ 那 麽 大

壹 般的 計算器 都 已經 達 不到 那 麽 大 了

所以 我們 有沒有 什 麽 辦法 去 解決 這個 問題 呢

有人 就 想到 這 麽 壹個轍

妳 說 雖然 我 直接 數學計算 不好 計算

但是 我 做 個 物理 實驗 是 很 容易 的 對 不 對

我們 能 不能 用壹個 物理 實驗

去 解決 這個 數學 問題 呢

就 把 它 反過來

這 過程 我們 可以 稱之為 采樣

就是說 妳 比如說 妳有 101 個 槽 或 100 個 槽

妳有 很 多個 槽

這 很 多個 槽 分得 非常 非常 細 對 吧

然後 妳 就 多 落壹些 球 多落 壹些 球

比如說 妳 落 1000 個球 或者 落 1 萬個 球

那 麽 有 的 時候 這球 落到 這

有 的 時候 這球 落到 這 是 吧

還有 落到 這 落到 這 都 有 可能

妳 落 的 足夠 多 的 時候

妳會 發現 這些 個球 它 會 呈現 壹種

這樣 的 正態 分布 的 這 麽 壹個 情況

那 妳 要 想問 我

比如說 妳 做到 這個 槽 它 的 概率 有 多 大

那 妳 只 需要 看 這個 槽 裏邊 的 這個 球

占 總球數 的 多少 個 不 就行了 嗎

所以 說 我們 假設 有 M 個球

M 個球 可以 稱之為 M 次 采樣 對 吧

我們 直接 的 落 了 M 個球 到 這個 高爾頓 釘板 裏面

落完 了 之後 我 發現 第 k 個 槽 有 多少 個球 啊

第 k 個 槽 有 m 個球

m 個球 這個 落入 了 k 槽 對 吧

那 m 個球 落入 k 槽 那 所以 我 就 可以 說

落入 這個 槽 的 概率 有 多 大 呢

這 概率 是 m/M

當然 前提 是 妳 這個 M 得 足夠 大

妳 比如 采樣 1 萬次 10 萬次 100 萬次

數越 大

那 麽 這個 比例 就 越接 近於 球 落到 這個 槽 的 概率

然後 妳 還 知道 說 這個 概率 等於 什 麽 呢

根據 剛才 的 計算

這個 概率 應該 等於 這個 數

等於 C(n,k-1)/2ⁿ 是不是

那 妳 現在 已經 知道 了 m M

妳 還 可以 計算 出 2ⁿ 來

那 妳 是不是 可以 反過來

把 這個 組合 數給 算 出來 對 不 對

所以 我們 就 可以 把 這個 數算 出來 了

這個 就是 我們 通過 壹個 物理 方法

解決 了 壹個 數學 問題

通過 壹個 采樣 的 方法

解決 了 壹個 我們 不好 去 計算 的 組合 數 是不是

這種 方法 其實 我們 以前 也 跟 大家 介紹 過

比如說 比較 著名 的 蒲豐 投針 實驗

那 就是 用壹個 物理 實驗 去 解決 了 壹個 問題

圓周率 怎 麽 計算 對 不 對

妳 只要 投針 投 的 次數 足夠 多

妳 就 可以 把 這個 圓周率 的 精度

精確 到 足夠 的 多 的 位數

同樣 道理 我 只要 采樣 采 的 足夠 多

我 就 可以 足夠 的 精度 獲得 這個 組合 數 對 不 對

好 我們 可以 用 采樣 的 這種 方法

解決 壹個 數學 問題

好 這個 就是 高爾頓 釘板 了

那 麽 本來 我們 說 講泊松 采樣

那 和 這個 高爾頓 釘板 其實 意思 是 差不多 的

他 都 是 通過 這種 方法 來 解決 壹個 數學 問題

那 麽 這個 數學 問題 是 什 麽

為 了 了解 它

我們 還得 介紹 壹些 數學 基礎

比如說 行列式

我們 得 介紹 這個 數學 基礎

行列式 這個 玩意 只要 妳 上 了 這個 大學 壹年 級

妳 都 會 學壹門 課 叫 線性代數 是 吧

那個 線性代數 裏邊 就 壹定 會講 行列式

什 麽 叫 行列式 呢

妳 看 我給 妳 畫壹個

矩陣 a₁₁ a₁₂ a₂₁ a₂₂

這叫 壹個 矩陣

矩陣 的 意思 是 說

把 這些 數排 成壹個 矩形 是 吧

a₁₁ 就是 第壹行 的 第壹個 元素 它 是 個數

a₁₂ 是 第壹行 的 第二個 元素 也 是 個數

a₂₁ 是 第二行 第壹個 元素

第二行 第二個 元素 它 是 個數

這個 矩陣 我 兩邊 加 直線

這就 叫 所謂 的 行列式

那 麽 這個 行列式 它 等於 什 麽 呢

它 是 等於 首先 我們 用 a₁₁×a₂₂

我們 用 這兩 個數 相乘 乘 完 了 之後

我們 再 讓 它 減去 a₁₂×a₂₁

就是 這兩 個數 是 相乘

然後 再 減去 這兩 個數 相乘 是 吧

先 把 它們 乘起來 再 把 它們 做差

就 得到 這 麽 個 結果

為 啥 呢

咱們 先別 著急 先往 下 說

那 如果 要是 三階 行列式 呢

a₁₁ a₁₂ a₁₃

a₂₁ a₂₂ a₂₃

a₃₁ a₃₂ a₃₃

壹個 矩陣 它 是 三階 的

我們 把 它求 行列式

這回 怎 麽 求 呢 方法 也 很 簡單

首先 妳 用 a₁₁ 妳 乘個 a₂₂

然後 再 乘個 a₃₃

把 這壹項 乘起來 壹共三 個數 對 吧

好 再來 繼續

妳 用 a₁₂×a₂₃ 再 乘 乘下 壹個 斜 的

它 沒有 了 對 吧

妳 往前 串 往前 串 串到 a₃₁

這 三個 再 乘起來 相加

然後 再 把 a₁₃ 再往 下 乘

×a₂₁ ×a₃₂

這些 個 黃色 線連 的 都 要 相乘 而且 相加

然後 再 做 差

減誰 呢 -a₁₃×a₂₂×a₃₁

然後 再 減什 麽 呢 a₂₃×a₃₂

再 乘以 左下 那 個數 就是 a₁₁

然後 再 減什 麽 呢

a₃₃×a₁₂×a₂₁ 是 吧

就是 往 左下 這些 數 乘起來 之後 再 相減

就是 黃色 的 線 三 個數 相乘 加 起來

這個 藍色 的 線 三 個數 相乘 做差

這個 玩意 得出 壹 個數 來

這個 數 就是 三階 行列式 的 值

那 妳 說 妳 算了 半天 行列式

這 玩意 有什 麽 意義 呢

這 玩意 還是 挺 有用 的

比如說 我們 從 幾何 含義 上講

假如 我們 有壹個 矢量

這個 矢量 它 這個 是 原點 o

然後 這個 矢量 呢

它 的 坐 標有 x 和 y 這 x 就是 a₁₁

這 y 就是 a₂₁

它 有 橫縱 坐標

完 了 另外 還有 壹個 矢量

這個 矢量 它 的 橫坐標 是 a₁₂

縱 坐標 是 a₂₂ 是 吧

橫縱 坐標 都 有 了

假如 妳 已經 知道 這 兩個 矢量 了

現在 妳 做 個 行列式

妳 知道 等於 什 麽 嗎