Kvantový algoritmus pro lineární systémy rovnic - Quantum algorithm for linear systems of equations - Wikipedia

The kvantový algoritmus pro lineární systémy rovnic, navrhl Aram Harrow, Avinatan Hassidim a Seth Lloyd, je kvantový algoritmus formulované v roce 2009 k řešení lineární systémy. Algoritmus odhaduje výsledek skalárního měření na vektoru řešení k dané lineární soustavě rovnic.^[1]

Algoritmus je jedním z hlavních základních algoritmů, u nichž se očekává, že zajistí zrychlení oproti jejich klasickým protějškům Shorův factoringový algoritmus, Groverův vyhledávací algoritmus a kvantová simulace. Za předpokladu, že lineární systém je řídký a má nízký číslo podmínky ${ displaystyle kappa}$, a že se uživatel zajímá o výsledek skalárního měření na vektoru řešení, místo hodnot samotného vektoru řešení má algoritmus runtime ${ displaystyle O ( log (N) kappa ^ {2})}$, kde ${ displaystyle N}$ je počet proměnných v lineárním systému. To nabízí exponenciální zrychlení oproti nejrychlejšímu klasickému algoritmu, který běží ${ displaystyle O (N kappa)}$ (nebo ${ displaystyle O (N { sqrt { kappa}})}$ pro kladné semidefinitní matice).

Implementace kvantového algoritmu pro lineární systémy rovnic byla poprvé demonstrována v roce 2013 Cai et al., Barz et al. a Pan et al. paralelně. Demonstrace sestávala z jednoduchých lineárních rovnic na speciálně navržených kvantových zařízeních.^[2][3][4] První demonstrace univerzální verze algoritmu se objevila v roce 2018 v práci Zhao et al.^[5]

Kvůli převládání lineárních systémů prakticky ve všech oblastech vědy a techniky má kvantový algoritmus pro lineární systémy rovnic potenciál pro širokou použitelnost.^[6]

Postup

Problém, který se snažíme vyřešit, je: daný a ${ displaystyle N krát N}$ Hermitova matice ${ displaystyle A}$ a a jednotkový vektor ${ displaystyle { overrightarrow {b}}}$, najděte vektor řešení ${ displaystyle { overrightarrow {x}}}$ uspokojující ${ displaystyle A { overrightarrow {x}} = { overrightarrow {b}}}$. Tento algoritmus předpokládá, že uživatele nezajímají hodnoty ${ displaystyle { overrightarrow {x}}}$ sám, ale spíše výsledek použití nějakého operátora ${ displaystyle M}$ na x, ${ displaystyle langle x | M | x rangle}$.

Nejprve algoritmus představuje vektor ${ displaystyle { overrightarrow {b}}}$ jako kvantový stav formuláře:

${ displaystyle | b rangle = sum _ {i mathop {=} 1} ^ {N} b_ {i} | i rangle.}$

Dále se k aplikaci unitárního operátoru používají Hamiltonovské simulační techniky ${ displaystyle e ^ {iAt}}$ na ${ displaystyle | b rangle}$ pro superpozici různých časů ${ displaystyle t}$. Schopnost rozložit se ${ displaystyle | b rangle}$ do vlastního základu ${ displaystyle A}$ a najít odpovídající vlastní čísla ${ displaystyle lambda _ {j}}$ je usnadněno použitím odhad kvantové fáze.

Stav systému po tomto rozkladu je přibližně:

${ displaystyle sum _ {j mathop {=} 1} ^ {N} beta _ {j} | u_ {j} rangle | lambda _ {j} rangle,}$

kde ${ displaystyle u_ {j}}$ je základem vlastního vektoru ${ displaystyle A}$, a ${ displaystyle | b rangle = sum _ {j mathop {=} 1} ^ {N} beta _ {j} | u_ {j} rangle}$.

Potom bychom chtěli provést lineární mapování ${ displaystyle | lambda _ {j} rangle}$ na ${ displaystyle C lambda _ {j} ^ {- 1} | lambda _ {j} rangle}$, kde ${ displaystyle C}$ je normalizační konstanta. Operace lineárního mapování není jednotná, a proto bude vyžadovat několik opakování, protože existuje určitá pravděpodobnost selhání. Poté, co uspěje, provedeme výpočet ${ displaystyle | lambda _ {j} rangle}$ zaregistrujte se a ponechte jim stav úměrný:

${ displaystyle sum _ {i mathop {=} 1} ^ {N} beta _ {i} lambda _ {j} ^ {- 1} | u_ {j} rangle = A ^ {- 1} | b rangle = | x rangle,}$

kde ${ displaystyle | x rangle}$ je kvantově-mechanická reprezentace požadovaného vektoru řešeníX. Přečíst všechny součásti X by vyžadovalo alespoň opakování postupu N krát. Často se však stává, že o něj někdo nemá zájem ${ displaystyle x}$ sám o sobě, ale spíše nějaká očekávaná hodnota lineárního operátoru M jednající naX. Mapováním M kvantově-mechanickému operátorovi a provedení kvantového měření odpovídajícímu M, získáme odhad očekávané hodnoty ${ displaystyle langle x | M | x rangle}$. To umožňuje širokou škálu funkcí vektoru X které mají být extrahovány včetně normalizace, váh v různých částech stavového prostoru a momentů bez skutečného výpočtu všech hodnot vektoru řešeníX.

Vysvětlení algoritmu

Inicializace

Za prvé, algoritmus vyžaduje, aby matice ${ displaystyle A}$ být Hermitian aby jej bylo možné převést na a nečleněný operátor. V případě, že ${ displaystyle A}$ není Hermitian, definujte

${ displaystyle mathbf {C} = { begin {bmatrix} 0 & A A ^ { dagger} & 0 end {bmatrix}}.}$

Tak jako ${ displaystyle C}$ je Hermitian, algoritmus lze nyní použít k řešení ${ displaystyle Cy = { begin {bmatrix} b 0 end {bmatrix}}.}$ získat ${ displaystyle y = { začátek {bmatrix} 0 x konec {bmatrix}}}$.

Zadruhé, Algoritmus vyžaduje efektivní postup přípravy ${ displaystyle | b rangle}$, kvantová reprezentace b. Předpokládá se, že existuje nějaký lineární operátor ${ displaystyle B}$ to může trvat libovolný kvantový stav ${ displaystyle | mathrm {počáteční} rangle}$ na ${ displaystyle | b rangle}$ efektivně nebo že tento algoritmus je podprogram ve větším algoritmu a je uveden ${ displaystyle | b rangle}$ jako vstup. Jakákoli chyba v přípravě stavu ${ displaystyle | b rangle}$ je ignorován.

Nakonec algoritmus předpokládá, že stav ${ displaystyle | psi _ {0} rangle}$ lze připravit efektivně. Kde

${ displaystyle | psi _ {0} rangle: = { sqrt {2 / T}} sum _ { tau mathop {=} 0} ^ {T-1} sin pi left ({ tfrac { tau + { tfrac {1} {2}}} {T}} vpravo) | tau rangle}$

pro některé velké ${ displaystyle T}$. Koeficienty ${ displaystyle | psi _ {0} rangle}$ jsou vybrány tak, aby se minimalizovala určitá kvadratická ztrátová funkce, která vyvolává chybu v ${ displaystyle U _ { mathrm {invertovat}}}$ níže popsaný podprogram.

Hamiltoniánská simulace

Hamiltoniánská simulace se používá k transformaci hermitovské matice ${ displaystyle A}$ do jednotného operátora, který lze poté libovolně použít. To je možné, pokud A je s-zřídka a efektivně vypočítatelný řádek, což znamená, že má nanejvýš s nenulové položky na řádek a vzhledem k indexu řádků lze tyto položky vypočítat v čase O (s). Za těchto předpokladů umožňuje kvantová hamiltoniánská simulace ${ displaystyle e ^ {iAt}}$ být simulován v čase ${ displaystyle O ( log (N) s ^ {2} t)}$.

${ displaystyle U _ { mathrm {invertovat}}}$ podprogram

Klíčový podprogram algoritmu, označený ${ displaystyle U _ { mathrm {invertovat}}}$, je definován následovně a zahrnuje a odhad fáze podprogram:

1. Připravte se ${ displaystyle | psi _ {0} rangle ^ {C}}$ v rejstříku C

2. Aplikujte podmíněný hamiltonovský vývoj (součet)

3. Aplikujte Fourierovu transformaci na registrC. Označte výsledné základní stavy pomocí ${ displaystyle | k rangle}$ pro k = 0, ..., T - 1. Definujte ${ displaystyle lambda _ {k}: = 2 pi k / t_ {0}}$.

4. Připojte se k trojrozměrnému registru S ve státě

${ displaystyle | h ( lambda _ {k}) rangle ^ {S}: = { sqrt {1-f ( lambda _ {k}) ^ {2} -g ( lambda _ {k}) ^ {2}}} | mathrm {nic} rangle ^ {S} + f ( lambda _ {k}) | mathrm {well} rangle ^ {S} + g ( lambda _ {k}) | mathrm {ill} rangle ^ {S},}$

5. Obraťte kroky 1–3 a zrušte výpočet veškerých odpadků vyprodukovaných podél cesty.

Postup fázového odhadu v krocích 1-3 umožňuje odhad vlastních čísel z A až do chyby ${ displaystyle epsilon}$.

Registr ancilla v kroku 4 je nezbytný pro konstrukci konečného stavu s obrácenými vlastními hodnotami odpovídajícími diagonalizované inverzní hodnotě A. V tomto registru jsou funkce F, G, se nazývají funkce filtru. Stavy „nic“, „dobře“ a „nemocný“ se používají k instruování těla smyčky, jak postupovat; „nic“ označuje, že k požadované inverzi matice dosud nedošlo, „dobře“ označuje, že k inverzi došlo a smyčka by se měla zastavit, a „špatně“ označuje tuto část ${ displaystyle | b rangle}$ je ve špatně podmíněném podprostoru A a algoritmus nebude schopen vytvořit požadovanou inverzi. Vytvoření stavu úměrného inverzní funkci k A vyžaduje měření „studny“, po které se celkový stav systému zhroutí do požadovaného stavu rozšířením Narozené pravidlo.

Hlavní smyčka

Tělo algoritmu sleduje amplitudová amplifikace postup: počínaje ${ displaystyle U _ { mathrm {invertovat}} B | mathrm {počáteční} rangle}$, je opakovaně použita následující operace:

${ displaystyle U _ { mathrm {invert}} BR _ { mathrm {init}} B ^ { dagger} U _ { mathrm {invert}} ^ { dagger} R _ { mathrm {succ}}}$

kde

${ displaystyle R _ { mathrm {succ}} = I-2 | mathrm {studna} rangle langle mathrm {studna} |,}$

a

${ displaystyle R _ { mathrm {init}} = I-2 | mathrm {počáteční} rangle langle mathrm {počáteční} |.}$

Po každém opakování ${ displaystyle S}$ se měří a bude produkovat hodnotu „nic“, „dobře“ nebo „špatně“, jak je popsáno výše. Tato smyčka se opakuje do ${ displaystyle | mathrm {dobře} rangle}$ se měří, což nastává s pravděpodobností ${ displaystyle p}$. Spíše než opakovat ${ displaystyle { frac {1} {p}}}$ krát, aby se minimalizovala chyba, se používá amplitudové zesílení k dosažení stejné odolnosti proti chybám pouze za použití ${ displaystyle O left ({ frac {1} { sqrt {p}}} right)}$ opakování.

Skalární měření

Po úspěšném měření „dobře“ zapnuto ${ displaystyle S}$ systém bude ve stavu úměrném:

${ displaystyle sum _ {i mathop {=} 1} ^ {N} beta _ {i} lambda _ {j} ^ {- 1} | u_ {j} rangle = A ^ {- 1} | b rangle = | x rangle.}$

Nakonec provedeme kvantově-mechanický operátor odpovídající M a získáme odhad hodnoty ${ displaystyle langle x | M | x rangle}$.

Analýza doby běhu

Klasická účinnost

Nejlepší klasický algoritmus, který vytváří skutečný vektor řešení ${ displaystyle { overrightarrow {x}}}$ je Gaussova eliminace, který běží dovnitř ${ displaystyle O (N ^ {3})}$ čas.

Li A je s-zřídké a pozitivní semi-definitivní, pak Metoda Conjugate Gradient lze použít k nalezení vektoru řešení ${ displaystyle { overrightarrow {x}}}$, kterou najdete v ${ displaystyle O (Ns kappa)}$ minimalizací kvadratické funkce ${ displaystyle | A { overrightarrow {x}} - { overrightarrow {b}} | ^ {2}}$.

Když pouze souhrnná statistika vektoru řešení ${ displaystyle { overrightarrow {x}}}$ je potřeba, stejně jako v případě kvantového algoritmu pro lineární systémy rovnic, může klasický počítač najít odhad ${ displaystyle { overrightarrow {x}} ^ { dagger} M { overrightarrow {x}}}$ v ${ displaystyle O (N { sqrt { kappa}})}$.

Kvantová účinnost

Runtime kvantového algoritmu pro řešení systémů lineárních rovnic původně navržený Harrowem a kol. bylo prokázáno, že je ${ displaystyle O ( kappa ^ {2} log N / varepsilon)}$, kde ${ displaystyle varepsilon> 0}$ je parametr chyby a ${ displaystyle kappa}$ je číslo podmínky z ${ displaystyle A}$. Toto bylo následně vylepšeno na ${ displaystyle O ( kappa log ^ {3} kappa log N / varepsilon ^ {3})}$ autor: Andris Ambainis^[7] a kvantový algoritmus s runtime polynomem v ${ displaystyle log (1 / varepsilon)}$ byl vyvinut Childs et al.^[8] Vzhledem k tomu, že algoritmus HHL udržuje své logaritmické škálování ${ displaystyle N}$ pouze pro řídké matice nebo matice s nízkým hodnocením, Wossnig et al.^[9] rozšířil algoritmus HHL na základě techniky odhadu kvantové singulární hodnoty a poskytl algoritmus lineárního systému pro husté matice, který běží v ${ displaystyle O ({ sqrt {N}} log N kappa ^ {2})}$ čas ve srovnání s ${ displaystyle O (N log N kappa ^ {2})}$ standardního HHL algoritmu.

Optimalita

Důležitým faktorem ve výkonu algoritmu inverze matice je číslo podmínky ${ displaystyle kappa}$, což představuje poměr ${ displaystyle A}$největší a nejmenší vlastní čísla. Jak se počet podmínek zvyšuje, je snadné najít vektor řešení pomocí metod gradientního sestupu, jako je například metoda sdruženého gradientu klesá, jak ${ displaystyle A}$ se blíží matici, kterou nelze převrátit, a vektor řešení se stává méně stabilním. Tento algoritmus předpokládá, že všechny singulární hodnoty matice ${ displaystyle A}$ lež mezi ${ displaystyle { frac {1} { kappa}}}$ a 1, v takovém případě je nárokovaná doba běhu úměrná ${ displaystyle kappa ^ {2}}$ bude dosaženo. Proto se zrychlení oproti klasickým algoritmům dále zvyšuje, když ${ displaystyle kappa}$ je ${ displaystyle mathrm {poly} ( log (N))}$.^[1]

Pokud byla doba běhu algoritmu změněna na polylogaritmickou ${ displaystyle kappa}$ pak problémy řešitelné n qubits lze vyřešit v poly (n) čas, což způsobí třídu složitosti BQP rovnat se PSPACE.^[1]

Analýza chyb

Provedení hamiltonovské simulace, která je dominantním zdrojem chyb, se provádí simulací ${ displaystyle e ^ {iAt}}$. Za předpokladu, že ${ displaystyle A}$ je s-řídký, lze to udělat s chybou ohraničenou konstantou ${ displaystyle varepsilon}$, což se promítne do aditivní chyby dosažené ve výstupním stavu ${ displaystyle | x rangle}$.

Krok odhadu fáze je chybný ${ displaystyle O left ({ frac {1} {t_ {0}}} right)}$ při odhadování ${ displaystyle lambda}$, což znamená relativní chybu ${ displaystyle O left ({ frac {1} { lambda t_ {0}}} right)}$ v ${ displaystyle lambda ^ {- 1}}$. Li ${ displaystyle lambda geq 1 / kappa}$, přičemž ${ displaystyle t_ {0} = O ( kappa varepsilon)}$ vyvolá konečnou chybu ${ displaystyle varepsilon}$. To vyžaduje, aby celková účinnost běhu byla úměrně zvýšena ${ displaystyle O left ({ frac {1} { varepsilon}} right)}$ minimalizovat chyby.

Experimentální realizace

I když dosud neexistuje kvantový počítač, který by mohl skutečně nabídnout zrychlení oproti klasickému počítači, implementace „důkazu koncepce“ zůstává důležitým milníkem ve vývoji nového kvantového algoritmu. Demonstrace kvantového algoritmu pro lineární systémy rovnic zůstávala výzvou i po letech od jeho návrhu až do roku 2013, kdy to prokázali Cai et al., Barz et al. a Pan et al. paralelně.

Cai a kol.

Publikováno v Physical Review Letters 110, 230501 (2013), Cai et al. uvedl experimentální demonstraci nejjednodušší smysluplné instance tohoto algoritmu, tedy řešení ${ displaystyle 2 krát 2}$ lineární rovnice pro různé vstupní vektory. Kvantový obvod je optimalizován a zkompilován do lineární optické sítě se čtyřmi fotonickými kvantovými bity (qubits) a čtyřmi řízenými logickými hradly, které se používají pro koherentní implementaci každého podprogramu pro tento algoritmus. Pro různé vstupní vektory poskytuje kvantový počítač řešení pro lineární rovnice s přiměřeně vysokou přesností, od věrnosti 0,825 do 0,993.^[10]

Barz a kol.

5. února 2013 Stefanie Barz a spolupracovníci demonstrovali kvantový algoritmus pro lineární systémy rovnic na fotonické kvantové výpočetní architektuře. Tato implementace používala dvě po sobě jdoucí zamotávací brány na stejné dvojici polarizací kódovaných qubitů. Byly realizovány dvě samostatně řízené brány NOT, kde byla úspěšná operace první ohlašována měřením dvou pomocných fotonů. Barz a kol. zjistili, že věrnost v získaném výstupním stavu se pohybovala od 64,7% do 98,1% kvůli vlivu emisí vyššího řádu ze spontánní parametrické down-konverze.^[3]

Pan a kol.

8. února 2013 Pan et al. uvedla experimentální demonstraci kvantového algoritmu pomocí konceptu kvantového informačního procesoru 4kbitové nukleární magnetické rezonance. Implementace byla testována pomocí jednoduchých lineárních systémů pouze se 2 proměnnými. Ve třech experimentech získali vektor řešení s přesností přes 96%.^[4]

Wen a kol.

Další experimentální demonstrace využívající NMR pro řešení systému 8 * 8 byla popsána Wen et al.^[11] v roce 2018 pomocí algoritmu vyvinutého Subaşı et al.^[12]

Aplikace

Kvantové počítače jsou zařízení, která využívají kvantovou mechaniku k provádění výpočtů způsoby, které klasické počítače neumí. Kvůli určitým problémům dodávají kvantové algoritmy exponenciální zrychlení oproti svým klasickým protějškům, nejznámějším příkladem je Shorův faktoringový algoritmus. Je známo jen málo takových exponenciálních zrychlení a ty, které jsou (například použití kvantových počítačů k simulaci jiných kvantových systémů) dosud našly omezené použití mimo oblast kvantové mechaniky. Tento algoritmus poskytuje exponenciálně rychlejší metodu odhadu vlastností řešení soustavy lineárních rovnic, což je problém všudypřítomný ve vědě a inženýrství, a to samostatně i jako podprogram u složitějších problémů.

Elektromagnetický rozptyl

Clader a kol. poskytl předem připravenou verzi algoritmu lineárních systémů, která poskytla dva pokroky. Nejprve předvedli, jak a kondicionér lze zahrnout do kvantového algoritmu. To rozšiřuje třídu problémů, kterými lze dosáhnout slíbeného exponenciálního zrychlení, protože škálování HHL a nejlepší klasické algoritmy jsou oba polynomy v číslo podmínky. Druhým pokrokem byla ukázka toho, jak použít HHL k řešení problému průřez radaru složitého tvaru. To byl jeden z prvních příkladů, jak pomocí HHL vyřešit konkrétní problém exponenciálně rychleji než nejznámější klasický algoritmus.^[13]

Řešení lineárních diferenciálních rovnic

Dominic Berry navrhl nový algoritmus pro řešení lineárních časově závislých diferenciálních rovnic jako rozšíření kvantového algoritmu pro řešení lineárních systémů rovnic. Berry poskytuje efektivní algoritmus pro řešení evoluce na plný úvazek pomocí řídkých lineárních diferenciálních rovnic na kvantovém počítači.^[14]

Metoda konečných prvků

The Metoda konečných prvků používá velké systémy lineárních rovnic k nalezení přibližného řešení různých fyzikálních a matematických modelů. Montanaro a Pallister demonstrují, že algoritmus HHL, pokud je aplikován na určité problémy MKP, může dosáhnout polynomického kvantového zrychlení. Navrhují, že exponenciální zrychlení není možné u problémů s pevnými rozměry a pro které řešení splňuje určité podmínky hladkosti.

Kvantová zrychlení pro metodu konečných prvků jsou vyšší u problémů, které zahrnují řešení s deriváty vyššího řádu a velkými prostorovými rozměry. Například problémy v dynamice mnoha těl vyžadují řešení rovnic obsahujících derivace v měřítku řádů s počtem těl a některé problémy v výpočetní finance, jako Black-Scholes modely vyžadují velké prostorové rozměry.^[15]

Kování nejmenších čtverců

Wiebe a kol. poskytnout nový kvantový algoritmus k určení kvality a nejmenší čtverce se hodí ve kterém se používá spojitá funkce k aproximaci množiny diskrétních bodů rozšířením kvantového algoritmu pro lineární systémy rovnic. Jak se zvyšuje počet diskrétních bodů, čas potřebný k vytvoření přizpůsobení metodou nejmenších čtverců pomocí i kvantového počítače s algoritmem tomografie kvantového stavu se stává velmi velkým. Wiebe a kol. zjistili, že v mnoha případech může jejich algoritmus efektivně najít stručnou aproximaci datových bodů, což eliminuje potřebu algoritmu tomografie s vyšší složitostí.^[16]

Strojové učení a analýza velkých dat

Strojové učení je studium systémů, které dokážou identifikovat trendy v datech. Úkoly ve strojovém učení často zahrnují manipulaci a klasifikaci velkého objemu dat ve vysokodimenzionálních vektorových prostorech. Runtime klasických algoritmů strojového učení je omezeno polynomiální závislostí jak na objemu dat, tak na rozměrech prostoru. Kvantové počítače jsou schopné manipulovat s vysokodimenzionálními vektory pomocí prostorů tenzorových produktů a jsou tak dokonalou platformou pro algoritmy strojového učení.^[17]

Kvantový algoritmus pro lineární systémy rovnic byl aplikován na podpůrný vektorový stroj, což je optimalizovaný lineární nebo nelineární binární klasifikátor. Podporovaný vektorový stroj lze použít pro supervizované strojové učení, ve kterém je k dispozici tréninková sada již klasifikovaných dat, nebo pro strojové učení bez dozoru, ve kterém jsou všechna data poskytnutá systému nezařazená. Rebentrost a kol. ukazují, že lze použít vektorový stroj kvantové podpory velká data klasifikace a dosáhnout exponenciálního zrychlení oproti klasickým počítačům.^[18]

V červnu 2018 Zhao et al. vyvinul algoritmus pro provádění Bayesiánského tréninku hlubokých neuronových sítí v kvantových počítačích s exponenciálním zrychlením oproti klasickému tréninku díky použití kvantového algoritmu pro lineární systémy rovnic,^[5] poskytující také první obecnou implementaci algoritmu, který má být spuštěn cloudové kvantové počítače.^[19]

Reference