1樓：Peter Pan
你應該已經知道怎麼回事了，不過我還是想補充下前乙個答案沒提到的東西。
在量子演算法裡面，假設乙個Oracle能實現，要麼是有經典的知識證明這個東西在經典世界是可以有效實現的（進而對應到量子），要麼很可能（公認或者符合直覺）在量子上可以有效實現。經典的計算複雜度我不大懂，不過在量子上用Oracle是把主要的精力放在演算法的其他方面，畢竟乙個量子演算法的方方面面都考慮到的話會非常難設計。但Oracle的提出也是要「令人信服」的。
Grover演算法的Oracle主要完成的是兩步：1、按序號儲存資料，對應於經典的儲存；2、根據資料計算函式值，對應於經典上的一次查詢。很多情況下這兩步看成一步，直接按序號求函式值。
2樓：鹹魚之友
所有的Oracle在本質上都是一樣的，無論是量子演算法、計算複雜性或者密碼學。當我們考慮一種問題的難解性時，我們通常會問以下問題。給定乙個需要求解的問題例項，也許我們沒有容易的（多項式時間）解法。
如果給乙個Oracle（先知、神仙、預言機）來幫忙求解多項式個問題例項（這些問題可以具有相關性），那麼，是否可以更容易地求解出所給定的難題。
例子：給你乙個大整數N，要求把它分解成若干個小整數的乘積。同時，讓你擁有Oracle，這個Oracle可以幫助你分解任何除N之外的大整數。請問，這個Oracle是否有幫助？
Oracle通常用於理論證明，實現的意義不大。鑑於直觀上Oracle源自具體的問題，也可以在現實生活中找到Oracle的「實現」，比如，SSL協議的某些錯誤實現可認為是幫助攻擊者解密的Oracle。
有哪些用計算複雜性理論考慮自然界中的問題的例子
Climber.pI 自己答一發好了.包括 Feynman 關於量子模擬的想法 嗯,就是湊數的.QMA和QMA Complete,以及 Quantum Hamiltonian Complexity.Richard Feynman 最初關於量子模擬和量子計算機的想法,其實就是個例子.雖然我不知道 Fe...
複雜性是如何產生的？
複雜性很難定義，可以先從什麼不是複雜性開始 1，能夠被還原為簡單的事物來處理的，即化簡為非複雜系統的 2，確定了事物不同層次的問題或性質後能夠截然分割處理的，即割裂為非複雜系統的 複雜性是統一性與多樣性的統一，有序與無序的統一。以上大部分引自莫蘭 複雜性思想導論 加入了少量自己的理解。蜂群思維 水的...
如何看待北大佘振蘇的「神課」《面向複雜性的系統思維》？
指囷相贈子敬 憑什麼不可以講玄學？只有 科學 能登大雅之堂的社會是不健康的。再者，何為科學？科學的定義難道統一過？為了傳播其道，說是科學無可厚非，不然說是宗教課，玄學課，哲學課？那樣更加不妥吧。那些說什麼沒有數學，沒有實驗種種的，面向複雜性的系統思維 不過是與你們日常浸溺其中的 科學 大相徑庭罷了，...