BQP - BQP

Ve výpočetní složitosti teorie , ohraničený-error quantum polynom času ( BQP ) je třída rozhodovacích problémů řešitelných pomocí kvantového počítače v polynomiálním čase , s chybovou pravděpodobností nanejvýš 1/3 pro všechny instance. Je to kvantový analog ke třídě složitosti BPP .

Rozhodovací problém je členem BQP, pokud existuje kvantový algoritmus ( algoritmus, který běží na kvantovém počítači), který s vysokou pravděpodobností řeší problém s rozhodováním a je zaručeno, že poběží v polynomiálním čase. Spuštění algoritmu správně vyřeší rozhodovací problém s pravděpodobností alespoň 2/3.

Algoritmus BQP (1 běh)
Odpovědět vyrobeno Správná odpověď	Ano	Ne
Ano	≥ 2/3	≤ 1/3
Ne	≤ 1/3	≥ 2/3
Algoritmus BQP ( k běží)
Odpovědět vyrobeno Správná odpověď	Ano	Ne
Ano	> 1 - 2 ^{- ck}	<2 ^{- ck}
Ne	<2 ^{- ck}	> 1 - 2 ^{- ck}
pro nějakou konstantu c > 0

Definice

BQP lze považovat za jazyky spojené s určitými uniformními rodinami kvantových obvodů s omezenou chybou . Jazyk L je v BQP právě tehdy, pokud existuje polynomiálně-časová uniformní rodina kvantových obvodů , taková, že ${\ Displaystyle \ {Q_ {n} \ colon n \ in \ mathbb {N} \}}$

Pro všechny , Q _n má n qubits jako vstup a výstupy 1 bit ${\ displaystyle n \ in \ mathbb {N}}$
Pro všechna x v L , ${\ Displaystyle \ mathrm {Pr} (Q_ {| x |} (x) = 1) \ geq {\ tfrac {2} {3}}}$
Pro všechna x, která nejsou v L , ${\ displaystyle \ mathrm {Pr} (Q_ {| x |} (x) = 0) \ geq {\ tfrac {2} {3}}}$

Alternativně lze definovat BQP z hlediska kvantových Turingových strojů . Jazyk L je v BQP právě tehdy, pokud existuje polynomiální kvantový Turingův stroj, který přijímá L s pravděpodobností chyby nejvýše 1/3 pro všechny instance.

Podobně jako u jiných pravděpodobnostních tříd „ohraničené chyby“ je výběr 1/3 v definici libovolný. Algoritmus můžeme spouštět konstantně několikrát a získat většinový hlas, abychom dosáhli jakékoli požadované pravděpodobnosti správnosti menší než 1, pomocí Chernoffovy vazby . Třída složitosti se nemění tím, že umožňuje chybu tak vysokou jako 1/2 - n ^{- c} na jedné straně, nebo vyžaduje chybu tak malou jako 2 ^{- n ^c} na straně druhé, kde c je jakákoli kladná konstanta a n je délka vstupu.

Úplný problém BQP

Podobně jako u pojmu úplnosti NP a dalších úplných problémů můžeme problém s úplným BQP definovat jako problém, který je v BQP a že každý problém v BQP se na něj v polynomiálním čase redukuje.

Zde je intuitivní problém úplného BQP, který vyplývá přímo z definice BQP.

Problém APPROX-QCIRCUIT-PROB

Vzhledem k popisu kvantového obvodu působícího na qubity s branami, kde je polynom a každá brána působí na jeden nebo dva qubity a dvě čísla , rozlišujte mezi následujícími dvěma případy: ${\ displaystyle C}$ ${\ displaystyle n}$ ${\ displaystyle m}$ ${\ displaystyle m}$ ${\ displaystyle n}$ ${\ Displaystyle \ alpha, \ beta \ in [0,1], \ alpha> \ beta}$

měření prvního qubitu státních výnosů s pravděpodobností ${\ Displaystyle C | 0 \ rangle ^{\ otimes n}}$ ${\ displaystyle | 1 \ rangle}$ ${\ Displaystyle \ geq \ alpha}$
měření prvního qubitu státních výnosů s pravděpodobností ${\ Displaystyle C | 0 \ rangle ^{\ otimes n}}$ ${\ displaystyle | 1 \ rangle}$ ${\ displaystyle \ leq \ beta}$

Všimněte si, že problém neurčuje chování, pokud instance není pokryta těmito dvěma případy.

Nárok. Jakýkoli problém s BQP se sníží na APPROX-QCIRCUIT-PROB.

Důkaz. Předpokládejme, že máme algoritmus, který řeší APPROX-QCIRCUIT-PROB, tj. Vzhledem k tomu, že kvantový obvod působí na qubity a dvě čísla , rozlišuje mezi dvěma výše uvedenými případy. S tímto orákulem můžeme vyřešit jakýkoli problém v BQP nastavením . ${\ displaystyle A}$ ${\ displaystyle C}$ ${\ displaystyle n}$ ${\ Displaystyle \ alpha, \ beta \ in [0,1], \ alpha> \ beta}$ ${\ displaystyle A}$ ${\ Displaystyle \ alpha = 2/3, \ beta = 1/3}$

Pro všechny , existuje rodina kvantových obvodech tak, že pro všechny , stát of qubits, pokud ; jinak kdyby . Fix vstup z qubits, a odpovídající kvantové obvodu . Nejprve můžeme zkonstruovat obvod takový, že . To lze snadno provést pevným zapojením a použitím sekvence bran CNOT k převrácení qubits. Pak můžeme zkombinovat dva obvody, abychom získali , a teď . A nakonec nutně jsou výsledky získány měřením několika qubitů a aplikovány na ně některé (klasické) logické brány. Vždy můžeme odložit měření a přesměrovat obvody tak, že měřením prvního qubitu získáme výstup. Toto bude náš okruh a o členství v se rozhodneme spuštěním s . Podle definice BQP budeme buď spadat do prvního případu (přijetí), nebo do druhého případu (odmítnutí), takže se sníží na APPROX-QCIRCUIT-PROB. ${\ Displaystyle L \ in \ mathrm {BQP}}$ ${\ Displaystyle \ {Q_ {n} \ colon n \ in \ mathbb {N} \}}$ ${\ displaystyle n \ in \ mathbb {N}}$ ${\ displaystyle | x \ rangle}$ ${\ displaystyle n}$ ${\ Displaystyle x \ in L, Pr (Q_ {n} (| x \ rangle) = 1) \ geq 2/3}$ ${\ Displaystyle x \ notin L, Pr (Q_ {n} (| x \ rangle) = 0) \ geq 2/3}$ ${\ displaystyle | x \ rangle}$ ${\ displaystyle n}$ ${\ displaystyle Q_ {n}}$ ${\ displaystyle C_ {x}}$ ${\ Displaystyle C_ {x} | 0 \ rangle ^{\ otimes n} = | x \ rangle}$ ${\ displaystyle | x \ rangle}$ ${\ displaystyle C '= C_ {x} Q_ {n}}$ ${\ Displaystyle C '| 0 \ rangle ^{\ otimes n} = Q_ {n} | x \ rangle}$ ${\ displaystyle Q_ {n}}$ ${\ Displaystyle C '| 0 \ rangle ^{\ otimes n} = Q_ {n} | x \ rangle}$ ${\ displaystyle C}$ ${\ displaystyle x}$ ${\ displaystyle L}$ ${\ displaystyle A (C)}$ ${\ Displaystyle \ alpha = 2/3, \ beta = 1/3}$ ${\ Displaystyle L \ in \ mathrm {BQP}}$

APPROX-QCIRCUIT-PROB přijde vhod, když se pokusíme prokázat vztahy mezi některými známými třídami složitosti a BQP.

Vztah k jiným třídám složitosti

Nevyřešený problém v informatice :

Jaký je vztah mezi a ? ${\ displaystyle {\ mathsf {BQP}}}$ ${\ displaystyle {\ mathsf {NP}}}$

(více nevyřešených problémů v informatice)

Podezřelý vztah BQP k jiným problémovým prostorům

BQP ve vztahu k dalším třídám pravděpodobnostní složitosti ( ZPP , RP , co-RP, BPP , PP ), které generalizují P v rámci PSPACE . Není známo, zda jsou některé z těchto omezení přísné.

BQP je definován pro kvantové počítače; odpovídající třída složitosti pro klasické počítače (nebo formálněji pro pravděpodobnostní Turingovy stroje ) je BPP . Stejně jako P a BPP , BQP je nízká pro sebe, což znamená, že BQP ^BQP = BQP . Neformálně to platí, protože polynomiální časové algoritmy jsou uzavřeny pod složením. Pokud algoritmus polynomiálního času volá algoritmy polynomiálního času jako podprogramy, je výsledný algoritmus stále polynomiálním časem.

BQP obsahuje P a BPP a je obsažen v AWPP , PP a PSPACE . Ve skutečnosti BQP je nízká pro PP , což znamená, že PP stroj dosahuje žádnou výhodu z být schopný řešit BQP problémy okamžitě, údaje o možném rozdílu ve výkonu mezi těmito podobných tříd. Známé vztahy s klasickými třídami složitosti jsou:

{\ displaystyle {\ mathsf {P \ subseteq BPP \ subseteq BQP \ subseteq AWPP \ subseteq PP \ subseteq PSPACE \ subseteq EXP}}}

Protože problém P ≟ PSPACE nebyl dosud vyřešen, má být prokázání nerovnosti mezi BQP a výše uvedenými třídami obtížné. Vztah mezi BQP a NP není znám. V květnu 2018 vydali počítačoví vědci Ran Raz z Princetonské univerzity a Avishay Tal ze Stanfordské univerzity článek, který ukázal, že ve srovnání s věštcem nebyl BQP obsažen v PH .

Přidání postselection k BQP má za následek třídu složitosti PostBQP, která se rovná PP .

Některé z těchto výsledků níže dokážeme nebo probereme.

BQP a EXP

Začínáme snadnějším zadržením. Abychom to ukázali , stačí ukázat, že APPROX-QCIRCUIT-PROB je v EXP, protože APPROX-QCIRCUIT-PROB je BQP-kompletní. ${\ displaystyle {\ mathsf {BQP}} \ subseteq {\ mathsf {EXP}}}$

Nárok - ${\ displaystyle {\ text {APPROX-QCIRCUIT-PROB}} \ in {\ mathsf {EXP}}}$

Důkaz -

Myšlenka je jednoduchá. Protože máme exponenciální sílu, danou kvantovým obvodem $C$ , můžeme použít klasický počítač ke stimulaci každé brány v $C,$ abychom získali konečný stav.

Formálněji nechť $C$ je kvantový obvod o velikosti polynomu na $n$ qubitech a $m$ branách, kde m je polynom v n. Nechť a je stav po aplikaci $i$ -té brány v obvodu . Každý stav může být v klasickém počítači reprezentován jako jednotkový vektor v . Kromě toho může být každá brána reprezentována maticí v . Konečný stav lze tedy vypočítat v čase, a proto máme dohromady časový algoritmus pro výpočet konečného stavu, a tedy pravděpodobnost, že první qubit bude změřen jako jeden. Z toho vyplývá . ${\ Displaystyle | \ psi _ {0} \ rangle = | 0 \ rangle ^{\ otimes n}}$ ${\ Displaystyle | \ psi _ {i} \ rangle}$ ${\ Displaystyle | \ psi _ {i-1} \ rangle}$ ${\ Displaystyle | \ psi _ {i} \ rangle}$ ${\ Displaystyle \ mathbb {C} ^{2 ^{n}}}$ ${\ Displaystyle \ mathbb {C}^{2^{n} \ times 2^{n}}}$ ${\ Displaystyle | \ psi _ {m} \ rangle}$ ${\ displaystyle O (m2^{2n})}$ ${\ Displaystyle 2^{O (n)}}$ ${\ displaystyle {\ text {APPROX-QCIRCUIT-PROB}} \ in {\ mathsf {EXP}}}$

Všimněte si, že tento algoritmus také vyžaduje místo pro uložení vektorů a matic. V následující části ukážeme, že můžeme zlepšit složitost vesmíru. ${\ Displaystyle 2^{O (n)}}$

BQP a PSPACE

Abychom to dokázali , nejprve představíme techniku nazývanou součet dějin. ${\ displaystyle {\ mathsf {BQP}} \ subseteq {\ mathsf {PSPACE}}}$

Součet dějin

Součet dějin je technika zavedená fyzikem Richardem Feynmanem pro formulaci integrálu cesty . Tuto techniku aplikujeme na kvantové počítače, abychom vyřešili APPROX-QCIRCUIT-PROB.

Součet stromů historie

Uvažujme kvantový obvod $C$ , který se skládá z $t$ bran, kde každý pochází z univerzální brány a působí na maximálně dva qubity. Abychom pochopili, jaký je součet dějin, vizualizujeme si vývoj kvantového stavu daného kvantovému obvodu jako strom. Kořen je vstup a každý uzel ve stromu má podřízené objekty, z nichž každý představuje stav v . Váha na okraji stromu od uzlu na $j$ -té úrovni představující stav k uzlu na -té úrovni představující stav je amplituda po aplikaci na . Amplituda přechodu cesty od kořene k listu je součinem všech závaží na okrajích podél cesty. Abychom získali pravděpodobnost, že konečný stav bude , sečteme amplitudy všech cest root-to-leave, které končí v uzlu představujícím . ${\ displaystyle g_ {1}, g_ {2}, \ cdots, g_ {m}}$ ${\ displaystyle g_ {j}}$ ${\ Displaystyle | 0 \ rangle ^{\ otimes n}}$ ${\ displaystyle 2^{n}}$ ${\ displaystyle \ mathbb {C} ^{n}}$ ${\ displaystyle | x \ rangle}$ ${\ displaystyle j+1}$ ${\ displaystyle | y \ rangle}$ ${\ Displaystyle \ langle y | g_ {j+1} | x \ rangle}$ ${\ displaystyle | y \ rangle}$ ${\ displaystyle g_ {j+1}}$ ${\ displaystyle | x \ rangle}$ ${\ Displaystyle | \ psi \ rangle}$ ${\ Displaystyle | \ psi \ rangle}$

Formálněji, pro kvantový obvod $C$ je jeho součet stromů historie stromem hloubky $m$ , s jednou úrovní pro každou bránu kromě kořene as faktorem větvení . ${\ displaystyle g_ {i}}$ ${\ displaystyle 2^{n}}$

Definovat - Historie je cesta ve stromu souhrnu historií. Pro nějaký konečný stav $x$ budeme označovat historii posloupností . ${\ Displaystyle (u_ {0} = | 0 \ rangle ^{\ otimes n} \ rightarrow u_ {1} \ rightarrow \ cdots \ rightarrow u_ {m-1} \ rightarrow u_ {m} = x)}$

Definovat - Let . Nechť je amplituda okraje v $j$ -té úrovni součtu přes strom historie . U jakékoli historie je produktem přechodová amplituda historie . ${\ Displaystyle u, v \ in \ {0,1 \}^{n}}$ ${\ Displaystyle (| u \ rangle, | v \ rangle)}$ ${\ Displaystyle \ alpha _ {j} (u \ rightarrow v) = \ langle v | g_ {j} | u \ rangle}$ ${\ Displaystyle h = (u_ {0} \ rightarrow u_ {1} \ rightarrow \ cdots \ rightarrow u_ {m-1} \ rightarrow u_ {m})}$ ${\ Displaystyle \ alpha _ {h} = \ alpha _ {1} (| 0 \ rangle ^{\ otimes n} \ rightarrow u_ {1}) \ alpha _ {2} (u_ {1} \ rightarrow u_ {2 }) \ cdots \ alpha _ {m} (u_ {m-1} \ rightarrow x)}$

Nárok - Za historii . Amplituda přechodu historie je vypočítatelná v polynomiálním čase. ${\ displaystyle (u_ {0} \ rightarrow \ cdots \ rightarrow u_ {m})}$

Důkaz -

Každá brána může být rozložena na nějaký unitární operátor působící na dva qubity, které bez ztráty obecnosti mohou být považovány za první dva. Proto lze vypočítat v polynomiálním čase v $n$ . Protože $m$ je polynom v $n$ , lze amplitudu přechodu historie vypočítat v polynomiálním čase. ${\ displaystyle g_ {j}}$ ${\ displaystyle g_ {j} = I \ otimes {\ tilde {g}} _ {j}}$ ${\ displaystyle {\ tilde {g}} _ {j}}$ ${\ Displaystyle \ langle v | g_ {j} | u \ rangle = \ langle v_ {1}, v_ {2} | {\ tilde {g}} _ {j} | u_ {1}, u_ {2} \ rangle \ langle v_ {3}, \ cdots, v_ {n} | u_ {3}, \ cdots, u_ {n} \ rangle}$

Claim - Nechť je konečný stav kvantového obvodu. U některých lze amplitudu vypočítat podle . ${\ Displaystyle C | 0 \ rangle ^{\ otimes n} = \ sum _ {x \ in \ {0,1 \} ^{n}} \ alpha _ {x} | x \ rangle}$ ${\ displaystyle x \ in \ {0,1 \}^{n}}$ ${\ displaystyle \ alpha _ {x}}$ ${\ Displaystyle \ alpha _ {x} = \ sum _ {h = (| 0 \ rangle ^{\ otimes n} \ rightarrow u_ {1} \ rightarrow \ cdots \ rightarrow u_ {t-1} \ rightarrow | x \ rangle)} \ alpha _ {h}}$

Důkaz -

Máme . Výsledek se dostaví přímo vložením mezi , a , a tak dále, a poté rozbalte rovnici. Pak každý výraz odpovídá a , kde ${\ Displaystyle \ alpha _ {x} = \ langle x | C | 0 \ rangle ^{\ otimes n} = \ langle x | g_ {t} g_ {t-1} \ cdots g_ {1} | C | 0 \ rangle ^{\ otimes n}}$ ${\ Displaystyle I = \ sum _ {x \ in \ {0,1 \}^{n}} | x \ rangle \ langle x |}$ ${\ displaystyle g_ {1}, g_ {2}}$ ${\ displaystyle g_ {2}, g_ {3}}$ ${\ displaystyle \ alpha _ {h}}$ ${\ Displaystyle h = (| 0 \ rangle ^{\ otimes n} \ rightarrow u_ {1} \ rightarrow \ cdots \ rightarrow u_ {t-1} \ rightarrow | x \ rangle)}$

Nárok - ${\ displaystyle {\ text {APPROX-QCIRCUIT-PROB}} \ in {\ mathsf {PSPACE}}}$

Všimněte si v algoritmu součtu nad historiemi pro výpočet určité amplitudy , v každém bodě výpočtu je uložena pouze jedna historie. Algoritmus součtu nad historiemi tedy využívá prostor pro výpočet pro libovolné $x,$ protože k ukládání dějin kromě některých proměnných pracovního prostoru jsou potřeba bity. ${\ displaystyle \ alpha _ {x}}$ ${\ Displaystyle O (nm)}$ ${\ displaystyle \ alpha _ {x}}$ ${\ Displaystyle O (nm)}$

Proto v polynomiálním prostoru můžeme vypočítat všechna $x$ s tím, že první qubit je ${\ Displaystyle \ sum _ {x} | \ alpha _ {x} |^{2}}$ 1 , což je pravděpodobnost, že první qubit bude na konci obvodu změřen jako 1.

Všimněte si, že ve srovnání se simulací uvedenou jako důkaz, že náš algoritmus zde zabírá mnohem méně místa, ale místo toho mnohem více času. Ve skutečnosti to vyžaduje čas na výpočet jediné amplitudy! ${\ displaystyle {\ mathsf {BQP}} \ subseteq {\ mathsf {EXP}}}$ ${\ displaystyle O (m2^{mn})}$

BQP a PP

K tomu lze použít podobný argument součtu přes historii . ${\ displaystyle {\ mathsf {BQP}} \ subseteq {\ mathsf {PP}}}$

BQP, P a NP

Předně víme , protože každý klasický obvod lze simulovat kvantovým obvodem. ${\ displaystyle {\ mathsf {P}} \ subseteq {\ mathsf {BQP}}}$

Předpokládá se, že BQP řeší těžké problémy mimo P, konkrétně problémy v NP. Tvrzení je neurčité, protože nevíme, zda P = NP, takže nevíme, zda jsou tyto problémy skutečně v P. Níže jsou uvedeny některé důkazy o dohadech:

Faktorizace celého čísla (viz Shorův algoritmus )
Diskrétní logaritmus
Simulace kvantových systémů (viz univerzální kvantový simulátor )
Aproximace Jonesova polynomu v určitých kořenech jednoty
Harrow-Hassidim-Lloyd (HHL) algoritmus

Známe však také analogii ve smyslu „černé skříňky“. Zvažte nestrukturovaný problém hledání: vzhledem k věšteckému přístupu k neznámé funkci najděte $x$ takových . Tento problém je jednoznačně v NP. Optimálním kvantovým algoritmem pro tento problém je na druhé straně Groverův algoritmus , který má složitost, pokud je mu povolen přístup k $f pouze$ prostřednictvím orákula. ${\ displaystyle {\ mathsf {NP}} \ not \ subseteq {\ mathsf {BQP}}}$ ${\ Displaystyle f: \ {0,1 \}^{n} \ to \ {0,1 \}}$ ${\ displaystyle f (x) = 1}$ ${\ displaystyle O ({\ sqrt {2^{n}}})}$