Bernstein-Waziraniho algoritmus

Bernstein-Vaziraniho algoritmus je kvantový algoritmus , který řeší problém nalezení -bitového čísla (v zahraniční literatuře se také používá termín skrytý řetězec [1] ) skrytého v černé skříňce . Navrhli Ethan Bernstein a Umesh Wazirani v roce 1993 . Tento algoritmus řeší problém mnohem rychleji, než je možné v nekvantové formulaci . Algoritmus lze použít v databázích , útoky na blokové šifry , testy výkonu pro kvantové počítače $n$ , byl implementován na 5- a 16-qubitových kvantových počítačíchIBM .

Historie

Algoritmus navrhl profesor Berkeley Vazirani a jeho student Ethan Bernstein Moderní zdroje se při popisu algoritmu zpravidla odvolávají na projev Bernsteina a Vaziraniho [2] na sympoziu o teorii počítání v roce 1993 [3] . Algoritmus Bernstein-Vazirani je rozšířenou verzí Deutsch-Yozhiho algoritmu , protože místo určení, zda funkce patří do určité třídy - vyvážené nebo konstantní (to znamená, že pro všechny argumenty nabývá hodnotu 0 nebo 1) - Algoritmus najde "skrytý" vektor, který vám umožní jednoznačně určit hodnotové funkce v libovolném bodě [4] .

Bernstein-Vaziraniho algoritmus v problému demonstruje, že řeší mezeru mezi klasickými a kvantovými algoritmy z hlediska co nejmenšího požadovaného počtu požadavků na orákulum (černá skříňka). I když povolíte použití pravděpodobnostních algoritmů (s předem omezenou pravděpodobností chyby), řešení klasického problému bude vyžadovat volání orákula, zatímco v kvantovém algoritmu stačí zavolat [5] . $Na)$ $O(1)$

Prohlášení o problému Bernstein-Vazirani

Klasický problém

Uvažujme orákulum, které převádí -bitové číslo na jeden bit, tj . $n$ $f:\{0,1\}^{n}\rightarrow \{0,1\}$

Navíc , kde je skalární součin tvaru: . Uvažujeme, že jedno volání funkce se provádí v konstantním čase. $f(x)=a\cdot x$ $\cdot$ ${\displaystyle x\cdot y=x_{1}y_{1}\oplus x_{2}y_{2}\oplus ...\oplus x_{n}y_{n))$ $F$

Je potřeba najít [1] . $A$

Kvantový problém

Příkaz problému v kvantovém modelu je podobný, ale přístup k orákulu v něm není prováděn přímo prostřednictvím funkce , ale prostřednictvím lineárního operátora působícího na systém qubitů : $F$ $U_{f}$ $n+1$

U_{f}=\sum _{x\in \{0,1\}^{n},y\in \{0,1\}}|x\rangle \langle x|\otimes |y \oplus f(x)\rangle \langle y|

kde je ket vektor odpovídající kvantovému stavu , je vektor podprsenky odpovídající kvantovému stavu , je Kroneckerův produkt a je modulo 2 sčítání . $|x\rangle$ $X$ $\langle x|$ $X$ $\otimes$ $\oplus$

Kvantové stavy a odpovídají vektorům a . Vektor pro stav kloubu lze reprezentovat jako součin [6] . $0$ $jeden$ ${\textstyle |0\rangle ={\binom {1}{0))}$ ${\textstyle |1\rangle ={\binom {0}{1))}$ ${\displaystyle x_{1}x_{2}\tečky x_{n))$ $|x_{1}x_{2}\tečky x_{n}\rangle =|x_{1}\rangle \otimes |x_{2}\rangle \otimes \dots \otimes |x_{n}\rangle$

Podobně jako v klasickém případě se předpokládá, že volání do orákula, které vypočítává výsledek aplikace operátora na vstupní systém z qubit , probíhá v konstantním čase. $U_{f}$ $n+1$

V kvantovém případě, stejně jako v klasickém případě, se předpokládá, že , a je třeba najít [1] . $f(x)=a\cdot x$ $A$

Algoritmus

Klasický problém

V klasickém případě každé volání věštce vrací jeden bit čísla , takže k nalezení -bitového čísla musíte volat věštecké časy. Níže je uvedena varianta volání orákula, která vám umožní úplné obnovení [1] : $A$ $n$ $A$ $n$ $n$ $A$

$f(1000...0_{n})=a_{1}$

$f(0100...0_{n})=a_{2}$

$\vtečky$

$f(0000...1_{n})=a_{n}$

Počet volání do orákula v klasickém případě je , kde je počet bitů čísla . Jednoduchá informačně-teoretická úvaha může ukázat, že tuto hranici nelze zlepšit ani v rámci třídy BPP [1] . $Na)$ $n$ $A$

Kvantový algoritmus

Algoritmus je založen na n-qubit Hadamardově operátoru :

{\textstyle H^{\otimes n}={\frac {1}{\sqrt {2^{n))))\sum \limits _{x,y\in \{0,1\}^{n }}{{(-1)}^{x\cdot y}|y\rangle \langle x|}}

A také to, že aplikace operátoru na stav formuláře , kde výsledkem je hodnota [1] . ${\textstyle U_{f))$ ${\textstyle |x\rangle |-\rangle =|x\rangle \otimes |-\rangle }$ ${\textstyle |-\rangle ={\frac {|0\rangle -|1\rangle }{\sqrt {2))))$ ${\textstyle U_{f}(|x\rangle |-\rangle )=(-1)^{f(x)}|x\rangle |-\rangle }$

Krok za krokem lze činnost algoritmu znázornit následovně [1] :

V prvním kroku je Hadamardův operátor aplikován na stav -qubit sestávající ze základního stavu a pomocného bitu : $H^{\otimes {(n+1)))$ $(n+1)$ $|0\rangle ^{n}|1\rangle$ $|0\rangle ^{n}$ $|1\rozsah$ ${\textstyle |0\rangle ^{n}|1\rangle {\xrightarrow {H^{\otimes {(n+1))))}{\frac {1}{\sqrt {2^{n)) }}\součet \limits _{x\in \{0,1\}^{n}}|x\rangle |-\rangle }$ ;
Poté se operátor použije na výsledek předchozího kroku : $U_{f}$ ${\textstyle {\frac {1}{\sqrt {2^{n))))\sum \limits _{x\in \{0,1\}^{n}}|x\rangle |-\rangle {\xrightarrow {~U_{f}~}}{\frac {1}{\sqrt {2^{n))))\sum \limits _{x\in \{0,1\}^{n} }{(-1)}^{f(x)}|x\rangle |-\rangle }$ ;
Poté se použije na první qubity výsledku , což, vezmeme-li v úvahu, že , dává [4] : $n$ ${\displaystyle H^{\otimes (n)))$ $f(x)=a\cdot x$ ${\textstyle {\frac {1}{\sqrt {2^{n))))\sum \limits _{x\in \{0,1\}^{n}}{(-1)}^{ a\cdot x}|x\rangle |-\rangle {\xšipka doprava {~H^{\otimes (n)}~}}{\frac {1}{2^{n}}}\sum \limits _{ x,y\in \{0,1\}^{n}}{(-1)}^{(a\cdot x)\oplus (x\cdot y)}|y\rangle |-\rangle \sim |a\rangle |-\rangle }$ .

Výsledkem měření vstupního registru bude hodnota [1] . V kvantové formulaci problému tedy stačí odkázat na orákulum. Obecně platí, že konstrukce a použití orákula vyžaduje logické prvky , ale to se při analýze algoritmu v tomto modelu nebere v úvahu, protože pro něj je významný pouze počet volání do orákula [1] . Algoritmus v této podobě byl implementován na 5- a 16-qubitových počítačích IBM [1] , je možné sestavit i optický systém , který algoritmus implementuje [7] . $|a\rangle$ $O(1)$ $O(4^{n})$

Implementace algoritmu na počítačích IBM

V jakékoli praktické implementaci Bernstein-Vaziraniho algoritmu je hlavním problémem vytvoření věštce, protože konstrukce a použití věštce vyžaduje logický prvek . [jeden] $O(4^{n})$

Kromě složitosti stavby orákula provázejí praktickou realizaci problémy s přesností. Systém byl testován na 1-, 2- a 3-bitových řetězcích, na kterých simulátor IBM-Qiskit správnou se 100% přesností Poté bylo provedeno testování 1- a 2-bitových řetězců na 5-qubitovém stroji ibmqx4 a 16-qubitovém stroji ibmqx5, kde byly zaznamenány chyby ve výpočtu a velká odchylka od očekávaného výsledku [1] .

Praktická aplikace

Algoritmus Bernstein-Wazirani lze použít:

V databázích [8] . Pomocí algoritmu lze teoreticky získat přístup k potřebným datům mnohem rychleji než v klasickém případě.
V útoku na blokovou šifru [9] . Algoritmus Bernstein-Wazirani poskytuje několik nových, pokročilejších způsobů, jak napadnout blokovou šifru, než v klasickém případě.
V testu výkonu pro kvantové počítače [10] . Algoritmus se používá jako test výkonu pro 11-qubitový kvantový počítač.

Poznámky

↑ 1 2 3 4 5 6 7 8 9 10 11 12 Coles et al, 2018 , str. 10-13.
↑ Ethan Bernstein, Umesh Vazirani. Teorie kvantové složitosti // Sborník příspěvků z 25. výročního sympozia ACM o teorii výpočetní techniky. - New York, NY, USA: ACM, 1993. - S. 11-20 . — ISBN 978-0-89791-591-5 . - doi : 10.1145/167088.167097 .
↑ Hidary, 2019 , str. 104-107.
↑ 1 2 Sevag Gharibian. Přednáška 7: Algoritmy Deutsch-Josza a Berstein-Vazirani // Úvod do kvantového počítání léto 2018, Univerzita v Paderbornu. - str. 1-10 .
↑ Hidary, 2019 , str. 12-13.
↑ Coles et al, 2018 , str. čtyři.
↑ P. Londero, K. Banaszek, I. A. Walmsley, C. Dorrer, M. Anderson. Efektivní optická implementace Bernstein-Vaziraniho algoritmu (anglicky) // Physical Review A. - 2004. - V. 69 , no. 1 . — S. 010302–010302.4 . — ISSN 1050-2947 . - doi : 10.1103/PhysRevA.69.010302 .
↑ A.A. Ježov. Některé problémy kvantové neurotechnologie (ruština) // Vědecká sekce MEPhI–2003. V Celoruská vědecká a technická konference "Neuroinformatika-2003": přednášky z neuroinformatiky. Část 2. - 2003. - S. 44-45 . Archivováno z originálu 21. ledna 2022.
↑ Huiqin Xie, Li Yang. Použití Bernstein-Vaziraniho algoritmu k útoku na blokové šifry // Designs, Codes and Cryptography. — 2019-05-01. — Sv. 87 , iss. 5 . — S. 1161–1182 . — ISSN 1573-7586 . - doi : 10.1007/s10623-018-0510-5 .
↑ K. Wright, K. M. Beck, S. Debnath, J. M. Amini, Y. Nam, N. Grzesiak, J.-S. Chen, NC Pisenti, M. Chmielewski, C. Collins, KM Hudek, J. Mizrahi, JD Wong-Campos, S. Allen, J. Apisdorf, P. Solomon, M. Williams, AM Ducore, A. Blinov, SM Kreikemeier , V. Chaplin, M. Keesan, C. Monroe & J. Kim. Srovnávání 11-qubitového kvantového počítače // Nature Communications. - 2019. - Sv. 10. - S. 5464. - doi : 10.1038/s41467-019-13534-2 .

Odkazy

Patrick J. Coles, Stephan Eidenbenz, Scott Pakin, Adetokunbo Adedoyin, John Ambrosiano. Implementace kvantových algoritmů pro začátečníky // arXiv:1804.03719 [quant-ph]. — 2018.
David Deutsch, Roger Penrose. Kvantová teorie, Churchův-Turingův princip a univerzální kvantový počítač (anglicky) // Proceedings of the Royal Society of London. A. Matematické a fyzikální vědy. - 1985. - 8. července ( sv. 400 , vyd. 1818 ). — S. 97–117 . - doi : 10.1098/rspa.1985.0070 .
Charles H. Bennett, Ethan Bernstein, Gilles Brassard, Umesh Vazirani. Strengths and Weaknesses of Quantum Computing (anglicky) // SIAM J. Computing .. - 1997. - Vol. 26. - S. 1510-1523. - doi : 10.1137/S0097539796300933 . — arXiv : quant-ph/9701001 .
Jack D. Hidary. Quantum Computing: Aplikovaný přístup . - Springer International Publishing, 2019. - S. 104-107. — ISBN 978-3030239213 . - doi : 10.1007/978-3-030-23922-0 .

kvantová informatika

Obecné pojmy

kvantové komunikace

kvantový kanál
- kvantová síť
kvantová kryptografie
- Kvantová distribuce klíčů
Teleportace kvantové energie
kvantová teleportace
Kvantové ultra-husté kódování
LOCC
kvantová destilace

Kvantové algoritmy

kvantový simulátor
Deutsch-Yozhi algoritmus
Bernstein-Waziraniho algoritmus
Groverův algoritmus
Kvantová Fourierova transformace
Shorův algoritmus
Simonův problém
Algoritmus kvantového odhadu fáze
Kvantový výpočetní algoritmus
kvantové žíhání
Algoritmické chlazení
Kvantový algoritmus pro řešení soustavy lineárních rovnic
Amplitudový zisk

Kvantová teorie složitosti

Kvantové výpočetní modely

kvantový obvod
- kvantová brána
Jednostranný kvantový počítač
- shluk
Adiabatické kvantové výpočty
Topologický kvantový počítač

Prevence dekoherence

Oprava kvantových chyb
Stabilizační kódy
Stabilizační formalismus
Kvantový konvoluční kód

Fyzické implementace

kvantová optika	Kavitační kvantová elektrodynamika Konturová kvantová elektrodynamika Kvantové výpočty založené na lineární optice protokol KLM Bosonické vzorkování
superchladné atomy	Kvantový počítač s absorbovanými ionty Optická mřížka
zpět založené	Kvantový počítač založený na nukleární magnetické rezonanci Kaneův kvantový počítač Ztrátový kvantový počítač - DiVincenzo NV centrum
Supravodivé kvantové počítače	nabít qubit streamovací qubit Fázový qubit Transmon