BQP (複雜度)和計算複雜性理論

快捷方式: 差异，相似，杰卡德相似系数，参考。

BQP (複雜度)和計算複雜性理論之间的区别

BQP (複雜度) vs. 計算複雜性理論

在計算複雜度理論內，有限錯誤量子多項式時間（bounded error quantum polynomial time，BQP）是一個決定性問題的複雜度類，並且其內的問題可以在多項式時間內以量子電腦解決，錯誤的機率小於1/3。BQP也可以視為是複雜度類BPP的量子電腦版。 換句話說，對BQP裡面的問題，存在一個使用量子電腦的演算法（量子演算法）花費多項式時間運作，並且有很高的機率回答正確的答案。對任何狀況，回答錯誤答案的機率小於三分之一。 與其他「有限錯誤」的機率演算法相同，這裡所提到的1/3是一個比較隨意的定義。如果原本演算法的錯誤機率比較大，我們可以運作多次該演算法，然後取多數回答正確的答案以取得比較高的準確率。詳細的分析顯示錯誤的下限可以高達1/2 − n−c或者低達2−nc，所包含的題目範圍均不會有變化。這裡c是一個正數的常數，n是輸入的長度。. 计算复杂性理论（Computational complexity theory）是理论计算机科学和数学的一个分支，它致力于将可计算问题根据它们本身的复杂性分类，以及将这些类别联系起来。一个可计算问题被认为是一个原则上可以用计算机解决的问题，亦即这个问题可以用一系列机械的数学步骤解决，例如算法。 如果一个问题的求解需要相当多的资源（无论用什么算法），则被认为是难解的。计算复杂性理论通过引入数学计算模型来研究这些问题以及定量计算解决问题所需的资源（时间和空间），从而将资源的确定方法正式化了。其他复杂性测度同样被运用，比如通信量（应用于通信复杂性），电路中门的数量（应用于电路复杂性）以及中央处理器的数量（应用于并行计算）。计算复杂性理论的一个作用就是确定一个能或不能被计算机求解的问题的所具有的实际限制。 在理论计算机科学领域，与此相关的概念有算法分析和可计算性理论。两者之间一个关键的区别是前者致力于分析用一个确定的算法来求解一个问题所需的资源量，而后者则是在更广泛意义上研究用所有可能的算法来解决相同问题。更精确地说，它尝试将问题分成能或不能在现有的适当受限的资源条件下解决这两类。相应地，在现有资源条件下的限制正是区分计算复杂性理论和可计算性理论的一个重要指标：后者关心的是何种问题原则上可以用算法解决。.

算法

-- 算法（algorithm），在數學（算學）和電腦科學之中，為任何良定义的具體計算步驟的一个序列，常用於計算、和自動推理。精確而言，算法是一個表示爲有限長列表的。算法應包含清晰定義的指令用於計算函數。 算法中的指令描述的是一個計算，當其時能從一個初始狀態和初始輸入（可能爲空）開始，經過一系列有限而清晰定義的狀態最終產生輸出並停止於一個終態。一個狀態到另一個狀態的轉移不一定是確定的。隨機化算法在内的一些算法，包含了一些隨機輸入。 形式化算法的概念部分源自尝试解决希尔伯特提出的判定问题，並在其后尝试定义或者中成形。这些尝试包括库尔特·哥德尔、雅克·埃尔布朗和斯蒂芬·科尔·克莱尼分别于1930年、1934年和1935年提出的遞歸函數，阿隆佐·邱奇於1936年提出的λ演算，1936年的Formulation 1和艾倫·圖靈1937年提出的圖靈機。即使在當前，依然常有直覺想法難以定義爲形式化算法的情況。.

BQP (複雜度)和算法 · 算法和計算複雜性理論 · 查看更多 »