“九章 ”量子 计算机 为啥 快 ？玻色 采样 是 什么 ？量子 霸权 时代 来 了 吗？ (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₂₂ 是 吧
橫縱 坐標 都 有 了
假如 妳 已經 知道 這 兩個 矢量 了
現在 妳 做 個 行列式
妳 知道 等於 什 麽 嗎
