格罗弗算法
格罗弗算法（）是一種量子算法，於1996年由電腦科學家洛夫·格罗弗提出。假設現在有一個未知的函數，格罗弗算法只需測試此未知的函數O(\sqrt{N})次，其中N為此未知函數的定义域的大小，即可以很高的概率找到一特定的輸入值，此輸入值能使此未知函數輸出特定的值。 同樣的問題在經典運算下，需要至少做 O(N) 次測試（因為在最壞的情況下，可能第N個定義域裡的值才是正確答案）。在格罗弗發表他的算法前後，Bennett, Bernstein, …
标签：#量子演算法
共 6 篇文章
量子傅立葉變換
量子傅立葉變換（）是一種離散傅立葉變換，將原式分解成更為簡單的多個么正矩陣的積。利用這般的分解方式，離散傅立葉變換可以用作量子電路，其包含了多個哈達瑪閘與受控移相閘。 量子傅立葉變換在量子演算法中有多處應用，以其可提供相位估算步驟的理論基礎，在一些演算法中佔核心地位，例如用在做質因數分解的秀爾演算法、順序發現(order finding)演算法以及。 細節 l2(Z/(N))是複數值函數於Z/N 的內積空間，伴有內積 : \langle…
量子演算法
量子演算法（Quantum algorithm；量子算法）是在量子計算中，於量子計算的現實模型上運行的演算法，最常用的模型是量子線路的計算模型。經典（或非量子）演算法是有限的指令序列，或用於解決問題的分步驟過程，其中每個步驟或指令都可以在經典計算機上執行。同樣地量子演算法是一個循序漸進的過程，其中每個步驟都可以在量子計算機上執行。儘管所有經典演算法也可以在量子計算機上執行，量子演算法一詞通常用於那些看起來本質上是量子的演算法，或者使用量…
秀爾演算法
秀爾演算法（）是一個于1994年發現的，以數學家彼得·秀爾命名，針對整數分解題目的的量子演算法（在量子計算機上面運作的演算法）。不正式地說，它解決的題目是：給定一個整數 N，找出它的質因數。在一個量子計算機上面，要分解整數N，秀爾演算法的運作需要多項式時間（時間是 \log N的某個多項式這麼長，\log N 在這裡的意義是輸入的檔案長度）。准确来说，该演算法花費 O((\log N)^{3}) 的時間，展示出質因數分解問題可以使用量子…
量子隨機漫步
量子随机漫步（，縮寫為 QRW、量子随机行走）是量子演算法中的重要核心，為量子資訊科學的分支，是一种利用量子力學性質產生随机過程的數學統計模型，分為离散量子隨機漫步和連續量子随机漫步，前者使用一枚量子銅板與漫步者共同演化，後者無需使用銅板而是透過马尔可夫链分析。和古典的隨機漫步相比，由於量子糾纏的非局域性和量子疊加態的相位干涉，能夠以更高的速度探索目標空間．1993年由亞基爾·阿哈羅諾夫首先提出． 參見 量子计算 隨機漫步 亞基爾·阿哈…
多伊奇-乔萨算法
多伊奇-乔萨算法（）是戴维·多伊奇和理查德·喬薩于1992年提出的一种确定性量子算法。1998年，、、基娅拉·马基亚韦洛（Chiara Macchiavello）与对其进行了改进。尽管该算法目前在现实中基本没有用途，但可以证明它比任何可能的确定性经典算法都快指数级，是最早提出的有此特性的量子算法之一。 问题描述 在多伊奇-乔萨问题中，我们有一个被称为预言机的黑盒量子计算机，它能实现某一函数 f\colon\{0,1\}^n\righta…