BQP (複雜度)

在計算複雜度理論內，有限錯誤量子多項式時間（英語：bounded error quantum polynomial time，BQP）是一個決定性問題的複雜度類，並且其內的問題可以在多項式時間內以量子電腦解決，錯誤的機率小於1/3。BQP也可以視為是複雜度類BPP的量子電腦版。

換句話說，對BQP裡面的問題，存在一個使用量子電腦的演算法（量子演算法）花費多項式時間運作，並且有很高的機率回答正確的答案。對任何狀況，回答錯誤答案的機率小於三分之一。

與其他「有限錯誤」的機率演算法相同，這裡所提到的1/3是一個比較隨意的定義。如果原本演算法的錯誤機率比較大，我們可以運作多次該演算法，然後取多數回答正確的答案以取得比較高的準確率。詳細的分析顯示錯誤的下限可以高達1/2 − n−c或者低達2−nc，所包含的題目範圍均不會有變化。這裡c是一個正數的常數，n是輸入的長度。

量子計算

演算法所使用量子位元的數目可以為輸入大小的任何多項式。舉例來說，因式分解n位元整數的演算法使用大約2'n'個量子位元（參考秀爾演算法）。

一般狀況之下，量子電腦的計算停止於量子測量上面。測量行為會導致量子位元塌縮到其中一個量子態上。我們可以說量子位元在經過運算之後，最終的測量會讓他有極高的機會出現正確的答案。

量子電腦受到許多矚目，因為有許多問題已知在BQP內，但是一般認為在P之外（換句話說，使用量子電腦比起一般電腦，能大幅縮短計算這些問題的時間）。一些著名的例子有：

參考資料

  1. ^ 1.0 1.1 arXiv:quant-ph/9508027v2 Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, Peter W. Shor. [2012-12-02]. （原始内容存档于2014-12-04）. 

外部連接

Read other articles:

Samaritans (charity)

United Kingdom and Ireland mental health charity The Samaritans redirects here. For the ethnoreligious group, see Samaritans. For other uses, see Samaritan (disambiguation). Not to be confused with Samaritan's Purse. SamaritansSamaritans logo as of 2019Formation1953HeadquartersEwell, England[1]Region served Great Britain[2][3][4]Ireland[5]See also International reachFounderChad VarahWebsitesamaritans.org Samaritans is a registered charity aimed at provi...

 

Flash Gordon (serial)

Flash GordonPoster untuk versi fitur 1936 dari serial (garis tagar catatan), dikeluarkan kembali dengan judul Rocketship pada 1949.SutradaraFrederick StephaniRay Taylor (tak disebutkan)ProduserHenry MacRaeDitulis olehBasil DickeyElla O'NeillGeorge H. PlymptonFrederick StephaniAlex Raymond (based on the comic strip by)PemeranBuster CrabbeJean RogersCharles B. MiddletonPriscilla LawsonFrank ShannonSinematograferJerome AshRichard FryerDistributorUniversal PicturesTanggal rilis 06 April 1936 ...

 

Lahung

Untuk jenis lainnya, lihat Durian. Lahung Klasifikasi ilmiah Kerajaan: Plantae (tanpa takson): Angiospermae (tanpa takson): Eudikotil (tanpa takson): Rosidae Ordo: Malvales Famili: Malvaceae Genus: Durio Spesies: D. dulcis Nama binomial Durio dulcisBecc. Durio dulcis, atau dikenal dengan sebutan lahung, adalah pohon dalam genus Durio (durian). Tingginya bisa mencapai 40 m. Durian jenis ini memiliki ciri khas berupa Kulit buahnya yang berwarna merah tua sampai coklat-merah, dan ditutupi d...

Annegret Kramp-Karrenbauer

Annegret Kramp-Karrenbauer Menteri Pertahanan FederalMasa jabatan17 Juli 2019 – 8 Desember 2021KanselirAngela Merkel PendahuluUrsula von der LeyenPenggantiChristine LambrechtPemimpin Uni Demokrat KristenMasa jabatan7 Desember 2018 – 22 Januari 2021WakilVolker BouffierJulia KlöcknerArmin LaschetUrsula von der LeyenThomas Strobl PendahuluAngela MerkelPenggantiArmin LaschetSekretaris Jenderal Uni Demokrat KristenMasa jabatan26 Februari 2018 – 7 Desember 2018Pemi...

 

Baden

Baden adalah bekas negara di Jerman barat daya. Baden dari tahun 1806 hingga 1945:    Baden    Palatinate (bagian dari Bavaria hingga 1945)    Kadipaten Agung Hesse    Hohenzollern (bagian dari Prusia dari 1850)    Württemberg    Prancis    Swiss Margraviat Baden (Jerman: Markgrafschaft Badencode: de is deprecated ) didirikan tahun 1112. Dari tahun 1190 hingga 1771, Baden terpecah menjadi negara-negara yang lebih kecil. Ke...

 

1838 en France

Chronologie de la France ◄◄ 1834 1835 1836 1837 1838 1839 1840 1841 1842 ►► Chronologies Boulevard du Temple, de Louis Daguerre.Données clés 1835 1836 1837  1838  1839 1840 1841Décennies :1800 1810 1820  1830  1840 1850 1860Siècles :XVIIe XVIIIe  XIXe  XXe XXIeMillénaires :-Ier Ier  IIe  IIIe Chronologies géographiques Afrique Afrique du Sud, Algérie, Angola, Bénin, Botswana, Burkina Faso, Burundi, Cameroun, Cap-Vert, Ré...

Первородный грех

Об экономическом термине см. Первородный грех (экономика). ХристианствоБиблия Ветхий Завет Новый Завет Евангелие Десять заповедей Нагорная проповедь Апокрифы Бог, Троица Бог Отец Иисус Христос Святой Дух История христианства Апостолы Хронология христианства Ран�...

 

Troisième circonscription du Rhône

Troisième circonscription du Rhône Carte de la circonscription.Géographie Pays France Région Auvergne-Rhône-Alpes Département Rhône Subdivisions Cantons 4 Communes 1 Représentation Député Marie-Charlotte Garin Législature XVIe (Cinquième République) Groupe parlementaire ÉCO Autres informations Population 111 033 hab. (1999) Date de création 24 novembre 1986 modifier La troisième circonscription du Rhône est l'une des 14 circonscriptions législatives que compte le dépa...

 

Darius Morris

Darius Morris Morris con la maglia di Michigan Nazionalità  Stati Uniti Altezza 193 cm Peso 86 kg Pallacanestro Ruolo Playmaker Termine carriera 2020 Carriera Giovanili 2005-2009Windward School2009-2011 Michigan Wolver.67 (666) Squadre di club 2011-2013 L.A. Lakers67 (240)2012-2013→  L.A. D-Fenders3 (51)2013 Philadelphia 76ers12 (83)2014 L.A. Clippers10 (9)2014 Memphis Grizzlies5 (15)2014 R.G.V. Vipers9 (154)2014-2015 Brooklyn Nets38 (83)2016-2...

大字 (数字)

この項目には、一部のコンピュータや閲覧ソフトで表示できない文字が含まれています（詳細）。 数字の大字（だいじ）は、漢数字の一種。通常用いる単純な字形の漢数字（小字）の代わりに同じ音の別の漢字を用いるものである。 概要 壱万円日本銀行券（「壱」が大字） 弐千円日本銀行券（「弐」が大字） 漢数字には「一」「二」「三」と続く小字と、「壱」「�...

 

Навчально-науковий інститут інноваційних освітніх технологій Західноукраїнського національного університету

Навчально-науковий інститут інноваційних освітніх технологій Західноукраїнського національного університету Герб навчально-наукового інституту інноваційних освітніх технологій ЗУНУ Скорочена назва ННІІОТ ЗУНУ Основні дані Засновано 2013 Заклад Західноукраїнський �...

 

Філософія

Частина серії проФілософіяLeft to right: Plato, Kant, Nietzsche, Buddha, Confucius, AverroesПлатонКантНіцшеБуддаКонфуційАверроес Філософи Епістемологи Естетики Етики Логіки Метафізики Соціально-політичні філософи Традиції Аналітична Арістотелівська Африканська Близькосхідна іранська Буддій�...

اشتعالية

رمز التحذير قابلية الاشتعال أو قابلية الالتهاب[1] ترجع لمدى السهولة التي تشتعل بها المادة لتسبب نار أو احتراق.[2][3][4] المواد التي تشتعل في درجات الحرارة العادية تعتبر قابلة للاشتعال، باختلاف التعريفات النوعية لدرجة الحرارة. فمثلا، نقطة الوميض هي أهم الخصائ�...

 

Laser

Device which emits light via optical amplification For other uses, see Laser (disambiguation). Laser beam redirects here. Not to be confused with LazarBeam or Lazer Beam. A telescope in the Very Large Telescope system producing four orange laser guide stars A laser is a device that emits light through a process of optical amplification based on the stimulated emission of electromagnetic radiation. The word laser is an anacronym that originated as an acronym for light amplification by stimulat...

 

Capcom

Capcom Co., Ltd.JenisPublikIndustriIndustri permainan video dan komputerIndustri hiburanDidirikan30 Mei 1979Kantorpusat Osaka, Jepang California, Amerika Serikat(Kantor pusat & studio)Asia: Hong KongEropa: Britania RayaKantor: Jerman Inggris KanadaTokohkunciKenzo Tsujimoto, CEOYoshiki OkamotoTokuro FujiwaraShinji MikamiKeiji InafuneProdukMega Man Resident Evil Devil May CryStreet Fighter Captain CommandoStriderBreath of FireDarkstalkersFinal FightMarvel vs. CapcomSNK vs. Capcom dan lain-l...

2004 Utah State Aggies football team

American college football season 2004 Utah State Aggies footballConferenceSun Belt ConferenceRecord3–8 (2–5 Sun Belt)Head coachMick Dennehy (5th season)Offensive coordinatorBob Cole (5th season)Defensive coordinatorDavid Kotulski (2nd season)Home stadiumRomney StadiumSeasons← 20032005 → 2004 Sun Belt Conference football standings vte Conf Overall Team   W   L     W   L   North Texas $   7 – 0     ...

 

Gail O'Grady

Questa voce sull'argomento attori statunitensi è solo un abbozzo. Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Segui i suggerimenti del progetto di riferimento. Gail Ann O'Grady Gail Ann O'Grady (Detroit, 23 gennaio 1963) è un'attrice statunitense, nota soprattutto per la sua partecipazione alle serie NYPD - New York Police Department, American Dreams e Hellcats, quest'ultima accanto all'attrice e cantante Ashley Tisdale. Indice 1 Filmografia parziale 1.1 Cinema 1.2...

 

Deahnne McIntyre

Australian Paralympic powerlifter Deahnne McIntyre2000 Australian Paralympic team portraitPersonal informationFull nameDeahnne Mary McIntyreNationality AustraliaBorn9 June 1971 Medal record Athletics Paralympic Games 1988 Seoul Women's 200 m 5–6 1988 Seoul Women's 400 m 5–6 1988 Seoul Women's 4 × 400 m 2–6 1988 Seoul Women's 100 m 5–6 World Championships and Games for the Disabled 1990 Assen Women's 100m T1 Deahnne Mary McIntyre, OAM[1] (born 9 J...

26th (Cameronian) Regiment of Foot

26th (Cameronian) Regiment of FootColours of the regiment in 1862Active1689–1881Country Kingdom of Scotland (1689–1707)  Kingdom of Great Britain (1707–1800)  United Kingdom of Great Britain and Ireland (1801–1881)BranchArmyTypeLine InfantryGarrison/HQHamilton Barracks, HamiltonMarchWithin a Mile of Edinburgh TownEngagementsNine Years' WarWar of the Spanish SuccessionJacobite risingsAmerican Revolutionary WarFrench Revolutionary WarsNapoleonic WarsFirst Opium WarCrimea...

 

Víctor Pecci

Victor PecciNazionalità Paraguay Altezza193 cm Peso86 kg Tennis Carriera Singolare1 Vittorie/sconfitte 358-243 Titoli vinti 10 Miglior ranking 9º (21 aprile 1980) Risultati nei tornei del Grande Slam  Australian Open 2T (1980)  Roland Garros F (1979)  Wimbledon 3T (1979, 1980)  US Open 3T (1979) Doppio1 Vittorie/sconfitte 194-170 Titoli vinti 12 Miglior ranking 28 (8 agosto 1983) Risultati nei tornei del Grande Slam  Australian Open 1T (1982)  Roland Garro...