|
量子复杂性理论量子复杂性理论（Quantum complexity theory）是理论计算机科学中计算复杂性理论的一部份。该理论使用量子计算机和量子信息来研究分析复杂性类定义，量子信息是基于量子力学的计算模型。量子复杂性理论用来研究这些复杂性类的问题的困难度，和量子复杂性类与经典（非量子的）复杂性类的关系。 复杂性类是指的是一群複雜度類似的問題的集合，可以用滿足特定資源限制下的演算法求解。例如复杂性类P就是可以用图灵机在多項式時間內求解的問題。也可以用量子算法（如量子计算机或量子圖靈機）定義量子复杂性，例如複雜度BQP就是可以用量子计算机在多項式時間內解決，其錯誤的機率小於一定比例的問題。 量子复杂性中二個比較重要的复杂性類分別是BQP及QMA，分別對應複雜度P及NP (複雜度)。量子复杂性理论的一個主要目的是要找到對應傳統复杂性類（如P、NP、PSPACE、PP等）的量子复杂性。 量子查詢复杂性在量子查詢复杂性（Quantum Query Complexity）中，輸入由一預言機（黑箱）提供，演算法要用查詢預言機的方式得到和輸入相關的資訊，演算法由某個固定的量子狀態開始，當對預言機查詢時，其狀態隨之變化。 量子查詢复杂性是指要計算其對應函數，需要查詢預言機的最小次數，量子查詢复杂性是函數整體時間复杂性的下限。 像搜尋無結構資料庫的Grover演算法即為量子演算法，其量子查詢复杂性為O(N1/2)，比已知最好的傳統查詢複雜度有二次方的差距。 參考資料
外部連結
|
Index:
pl ar de en es fr it arz nl ja pt ceb sv uk vi war zh ru af ast az bg zh-min-nan bn be ca cs cy da et el eo eu fa gl ko hi hr id he ka la lv lt hu mk ms min no nn ce uz kk ro simple sk sl sr sh fi ta tt th tg azb tr ur zh-yue hy my ace als am an hyw ban bjn map-bms ba be-tarask bcl bpy bar bs br cv nv eml hif fo fy ga gd gu hak ha hsb io ig ilo ia ie os is jv kn ht ku ckb ky mrj lb lij li lmo mai mg ml zh-classical mr xmf mzn cdo mn nap new ne frr oc mhr or as pa pnb ps pms nds crh qu sa sah sco sq scn si sd szl su sw tl shn te bug vec vo wa wuu yi yo diq bat-smg zu lad kbd ang smn ab roa-rup frp arc gn av ay bh bi bo bxr cbk-zam co za dag ary se pdc dv dsb myv ext fur gv gag inh ki glk gan guw xal haw rw kbp pam csb kw km kv koi kg gom ks gcr lo lbe ltg lez nia ln jbo lg mt mi tw mwl mdf mnw nqo fj nah na nds-nl nrm nov om pi pag pap pfl pcd krc kaa ksh rm rue sm sat sc trv stq nso sn cu so srn kab roa-tara tet tpi to chr tum tk tyv udm ug vep fiu-vro vls wo xh zea ty ak bm ch ny ee ff got iu ik kl mad cr pih ami pwn pnt dz rmy rn sg st tn ss ti din chy ts kcg ve
