如何在量子計算機上實現經典計算

已完成

15 分鐘

現在你理解了要嘗試解決的經典問題，來看看如何將這個問題描述轉換為一個量子操作，它可以被 Grover 的搜索算法使用并在量子計算機上運行。

如何在疊加態上進行計算？

量子計算的關鍵特性之一是不僅能夠對單個輸入執行計算，而且能夠對輸入的疊加執行計算。 在處理一個搜索問題和一個描述要嘗試解決的搜索問題實例的特定函數 $f(x)$ 時，我們需要能夠在輸入的疊加上也計算這個函數。

備注

量子黑盒是一個“不透明盒子”操作，它被用作另一種算法(在本例中為 Grover 的算法)的輸入，但術語“黑盒”也廣泛用于經典計算。 有些量子算法是用量子黑盒來描述的，這是為了強調它們可以應用于一類廣泛的問題，前提是該問題可以有效地作為量子黑盒實現。 對于這類算法，其運行時分析通常與黑盒調用次數(即函數計算)相關，而不是指算法執行的基元運算。

使用量子黑盒描述的算法解決特定問題時，需要為此問題實現量子黑盒。 如果使用 Grover 算法，黑盒會計算我們要嘗試反轉的函數 $f(x)$ 的值。

有兩種常見的方法可以對計算疊加態的函數的效果進行編碼：使用“相位黑盒”，或使用“標記黑盒”。

假設我們要實現一個量子運算符 $U$，它計算一個函數 $f(x)$，這個函數將一個位作為輸入并生成一個位作為輸出。 我們從一個疊加態 $a_0 |0\rangle + a_1 |1\rangle$ 開始。

可以在基態 $|0\rangle$ 和 $|1\rangle$ 的相對相位中分別對值 $f(0)$ 和 $f(1)$ 進行編碼。

在這種情況下，應用運算符$U_\textrm{phase}$ 將狀態 $a_0 |0\rangle + a_1 |1\rangle$ 轉換為狀態 $(-1)^{f(0)} a_0 |0\rangle + (-1)^{f(1)} a_1 |1\rangle$。 換句話說，運算符 $U_\textrm{phase}$ 不會改變 $f(x) = 0$ 的基態的相位，而是將 $f(x) = 1$ 的基態的相位乘以 $-1$。

運算符 $U_\textrm{phase}$ 稱為“相位黑盒”。

此外，我們還可以分配額外的量子位 $y$，并對處于該量子位狀態的 $f(0)$ 和 $f(1)$ 值進行編碼。

在這種情況下，我們將數據量子位和額外的量子位的聯合狀態拆分為基態 $a_{00} |0\rangle_x|0\rangle_y + a_{01} |0\rangle_x|1\rangle_y + a_{10} |1\rangle_x|0\rangle_y + a_{11} |1\rangle_x|1\rangle_y$ 的線性組合，并對每個基態分別應用運算符 $U_\textrm{mark}$。 此運算符將基態 $|x\rangle|y\rangle$ 轉換為 $|x\rangle|y \oplus f(x)\rangle$($\oplus$ 為模 2 加法)。 換句話說，運算符 $U_\textrm{mark}$ 不會改變 $f(x) = 0$ 的基態，而是翻轉 $f(x) = 1$ 的狀態的額外量子位狀態。 通過量子運算符是線性的這一事實可以推導對疊加的全部效果：也就是說，我們的起始狀態將被轉換為 $a_{00} |0\rangle_x|f(0)\rangle_y + a_{01} |0\rangle_x|1 \oplus f(0)\rangle_y + a_{10} |1\rangle_x|f(1)\rangle_y + a_{11} |1\rangle_x|1 \oplus f(1)\rangle_y$。 在這種情況下，額外的量子位往往最終會與數據量子位相互牽連。

運算符 $U_\textrm{mark}$ 稱為“標記黑盒”。

備注

以這種方式進行計算，并不等于“能夠同時計算所有輸入的函數”！ 回想一下，量子測量限制了我們從量子系統中提取的信息量，因此，在這兩種情況下，我們無法從這樣的計算中提取所有的函數值。 我們需要構造一種巧妙的算法，利用在疊加中執行計算的優勢來尋找答案。

在量子算法中表示經典計算的最佳方式取決于目標：

許多量子算法要求使用第一種方法，在基態的相位中對經典函數值編碼，因為這種方法可以簡化算法的表達。

第二種方法是在額外的量子位狀態中對經典函數值編碼，使經典計算的實現更加容易。

在實踐中，經常會看到用標記黑盒來實現經典計算，然后轉換為相位黑盒(作為的最后一步)，再將操作插入量子算法的其他部分。

經典計算機科學有一個分支是“可逆計算”，它為我們提供了在量子計算機上實現經典計算所需的技術。 在本模塊的最后一個單元中，當我們討論可以從 Grover 算法中獲益的問題類型時，將回到高效實現量子黑盒的問題。

在下一個單元中，你將了解如何使用 Q# 將圖形著色示例問題實現為量子黑盒。

總結

以上是生活随笔為你收集整理的量子计算机怎么算有用,如何在量子计算机上实现经典计算的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。