Algorytm Deutsch-Jozsa, algorytm, który pokazał obietnicę przewagi kwantowej, autorstwa współodkrywcy Davida Deutscha

[ad_1]

Być może jednym z najlepszych sposobów na zilustrowanie mocy obliczeń kwantowych jest przykładowy algorytm obliczeniowy, który pokazuje moc kwantowej równoległości. Przyjrzymy się podstawom obliczeń kwantowych, a następnie algorytmowi Deutscha.

Obliczenia kwantowe

Jedną ze znaczących zalet korzystania z komputera kwantowego w porównaniu z klasycznym komputerem jest wydajność obliczeniowa wykonywania obliczeń. Osoby zaznajomione z tworzeniem lub budowaniem algorytmów wiedzą, że zwykle korzystne jest, aby działały one tak szybko, jak to możliwe, przy ustalonych zasobach. Niezależnie od tego, czy jest to wyszukiwanie w ciągu mikrosekund, czy symulacja w celu znalezienia cennych leków, wykonywanie obliczeń tak efektywnie, jak to możliwe, ma fundamentalne znaczenie dla naszego życia. Obliczenia kwantowe to sposób na uzyskanie jak największej „bang for the buck” z konkretnymi problemami.

Oczywiście, jak można się spodziewać, nie jest to takie proste i nie każdy problem można sformułować w sposób kwantowy, a tym samym być bardziej wydajnym. Wyzwaniem dla informatyki jest znalezienie odpowiednich sposobów zastosowania technik kwantowych do rozwiązywania niektórych światowych wyzwań. Jeśli można wykonywać obliczenia szybciej, można argumentować, że ludzkość staje się lepsza, ponieważ wiele problemów można powiązać ze zdolnością do szybkiego wykonywania obliczeń. Zadania inteligencji maszynowej, odkrywanie leków. Wyobraźmy sobie przykłady takie jak autonomiczna jazda, która, jak wielu może twierdzić, jest związana ze zdolnością do obliczania ogromnych ilości danych w rzeczywistych warunkach.

Kim jest David Deutsch?

David Deutsch jest jednym z najwybitniejszych naukowców w dziedzinie obliczeń kwantowych. Niektórzy mogą go nawet nazwać przodkiem obliczeń kwantowych. Deutsch jest brytyjskim fizykiem pracującym na Uniwersytecie Oksfordzkim – profesorem i członkiem Royal Society (FRS). Jeśli chcesz dowiedzieć się więcej o Davidzie Deutschu i jego naukowych innowacjach, odwiedź nasz artykuł na temat przodka obliczeń kwantowych lub odwiedź jego stronę internetową tutaj.

Deutsch jest brytyjskim fizykiem pracującym na Uniwersytecie Oksfordzkim, profesorem i członkiem Royal Society (FRS). — Deutsch jest brytyjskim fizykiem pracującym na Uniwersytecie Oksfordzkim – profesorem i członkiem Royal Society (FRS).

Równoległość kwantowa wyjaśniona

W skrócie, pozwala nam to na jednoczesną ocenę wielu funkcji. Mówiąc bardziej szczegółowo, biorąc pod uwagę funkcję f(x), wersja kwantowa w jakiś sposób (magicznie) pozwala nam obliczyć funkcję dla wielu wartości x – tak zwany większy zwrot z inwestycji. Chciałbym wyjaśnić, jakie to szalone. Wyobraźmy sobie, że mamy funkcję, którą za cenę jednokrotnego obliczenia możemy obliczyć dwa razy. Tak, wydaje się to dziwne, ale jak wszyscy wiemy, mechanika kwantowa jest dziwna, więc zbadajmy mechanizmy stojące za tym dziwnym twierdzeniem.

Jak dzieje się magia w algorytmie Deutscha Jozsy?

Wprowadzenie

Po pierwsze, powinieneś wiedzieć, że Algorytm Deutscha Jozsy jest rozszerzeniem Algorytmu Deutscha, a ponieważ jesteśmy prostymi istotami, powinniśmy opanować go najpierw, stąd część I. Aby zapoznać się z podstawowymi informacjami na temat Qubitów, przejdź na stronę tutaj.

Konfiguracja i terminologia

Ponieważ staramy się zakładać niewielką lub żadną wcześniejszą wiedzę, oznacza to, że musimy omówić niektóre z podstawowych maszyn, z których często korzysta Mechanika Kwantowa. Oto niektóre z podstaw (nie kompletne podstawy dla początkujących), których potrzebujesz.

Funkcja / operator Hadamarda

Jest to jeden z najciekawszych operatorów w fizyce kwantowej. Zmienia stan pojedynczego kubitu w superpozycję stanów. Niesamowite. Ma kilka fajnych właściwości, ponieważ może działać na kubitach w stanach 0 i 1. Aby uzyskać szczegółowe informacje na temat kubitów, postępuj zgodnie z artykułem tutaj, który zawiera łatwy przewodnik po świecie kubitów. Być może esencja jest następująca:

Jeśli qubit znajduje się w stanie 0, operator Hadamarda przekształca go w następujący stan superpozycyjny:

$\Frac{1}{\Sqrt{2}}|0\Rangle + \Frac{1}{\Sqrt{2}}|1\Rangle$ $\Frac{1}{\Sqrt{2}}|0\Rangle + \Frac{1}{\Sqrt{2}}|1\Rangle$

Jeśli Qubit jest w stanie 1, operator przekształca go w następujący stan superpozycyjny:

$\Frac{1}{\Sqrt{2}}|0\Rangle - \Frac{1}{\Sqrt{2}}|1\Rangle$ $\Frac{1}{\Sqrt{2}}|0\Rangle - \Frac{1}{\Sqrt{2}}|1\Rangle$

Voila, to wszystko. Pominę formę macierzy, ale jeśli chcesz, możesz to sprawdzić tutaj. Ale podstawowy sposób myślenia o tym jest fundamentalny dla obliczeń kwantowych i zapewnia wiele „sztuczek”, które można wykonać, więc warto go zrozumieć dogłębnie.

XOR (dodawanie bitów)

Czy kiedykolwiek widzieliśmy tablicę prawdy dla funkcji XOR? Cóż, przedstawię ją poniżej, ale prosty „sposób” myślenia o niej jest następujący: Jeśli bity wejściowe (a i b) sumują się do 2, to należy sprawić, by suma ta ponownie przewróciła się do 0. Funkcja XOR daje zatem 0 w połowie przypadków i 1 w drugiej połowie przypadków. Ma ona mnóstwo naprawdę przydatnych funkcji, takich jak to, że jeśli bity wejściowe są takie same, to zawsze otrzymujemy 0, a jeśli są różne, to otrzymujemy 1. Co za wspaniała funkcja, i to nie tylko w przestrzeni klasycznej, ale i kwantowej.

Czasami funkcja ta jest najlepiej rozumiana jako dodawanie „modulo 2”. Często ze względu na jej użyteczność można użyć prostego symbolu: $X \ Oplus Y = Z$ $X \Oplus Y = Z$

Dane wejściowe (x)	Wejście (y)	XOR (z)
0	0	0
0	1	1
1	0	1
1	1	0

Funkcje jednostkowe

Możemy teraz skonstruować funkcję o nazwie $U_F$ $U_F$ to jest to samo, co praca nad naszą funkcją $F(X)$ $F(X)$ który przyjmuje wartości i przekształca dane wejściowe w dane wyjściowe. Zbadajmy teraz, co się stanie, gdy weźmiemy tę dowolną funkcję (nie ma znaczenia, co robi) i zastosujemy ją w prostym obwodzie kwantowym. Szczególną cechą funkcji unitarnych jest to, że jeśli ponownie wykonamy tę samą operację lub funkcję, możemy osiągnąć pierwotny stan – jest to ważna i istotna koncepcja w obliczeniach kwantowych.

Prosty obwód kwantowy

Będziemy mieć 2 wejścia (podobnie jak w naszej funkcji XOR) i sprawdzimy wyjście. Jednak zamiast zwykłych klasycznych bitów, użyjemy bitów kwantowych lub Qubitów jako naszych wejść i naszej funkcji $U_F$ $U_F$ będzie działać na stanach kwantowych.

Wprowadzamy $X$ $X$ , $Y$ $Y$ i uzyskać nowe dane wyjściowe $X$ $X$ oraz $Y \Oplus F(X)$ $Y \Oplus F(X)$ . W bardziej kwantowym żargonie możemy powiedzieć

$|X, Y\Rangle &Nbsp;\Rightarrow | X, Y \Oplus F(X) \Rangle$ $|X, Y\Rangle &Nbsp;\Rightarrow | X, Y \Oplus F(X) \Rangle$

Tworzenie niektórych wejść kwantowych do naszego obwodu

Dla naszego wejścia $X$ $X$ oraz $Y$ $Y$ , użyjmy odpowiednio kolejno $X$ $X$ w superpozycję $Algorytm Deutsch-Jozsa, algorytm, który pokazał obietnicę przewagi kwantowej przez współodkrywcę Davida Deutscha$ $Algorytm Deutsch-Jozsa, algorytm, który pokazał obietnicę przewagi kwantowej przez współodkrywcę Davida Deutscha$ oraz $1$ $1$ stany wykorzystujące bramkę Hadamarda $H(0)$ $H(0)$ co daje:

$X = \Frac{1}{\Sqrt{2}}(|0\Rangle + |1\Rangle)$ $X = \Frac{1}{\Sqrt{2}}(|0\Rangle + |1\Rangle)$

Miejmy $Y$ $Y$ jako stan kwantowy „0”, co daje nam następujące dane wejściowe

$Y = |0\Rangle$ $Y = |0\Rangle$

Spójrzmy teraz na wyjście z naszego obwodu po zastosowaniu funkcji jednostkowej:

$\Frac{1}{\Sqrt{2}}( |0, F(0)\Rangle + |1, F(1)\Rangle )$ $\Frac{1}{\Sqrt{2}}( |0, F(0)\Rangle + |1, F(1)\Rangle )$

Oznacza to, że nasz stan wyjściowy po zastosowaniu funkcji jest stanem superpozycji dwóch ocen funkcji. W skrócie, wykonaliśmy dwie oceny funkcji dla jednej oceny funkcji. Szaleństwo, co? Pomyśl o tym: wprowadzając stan superpozycji, obwód kwantowy może efektywnie ocenić naszą funkcję dwa razy! $F(0)$ $F(0)$ oraz $F(1)$ $F(1)$ , dając nam korzyści, o których mówiliśmy.

Multiverse – to już jest szalone

Dla tych, którzy pytają, zadajcie sobie pytanie, gdzie wykonywane są obliczenia. Czy może to być Multiwersum? Dla tych, którzy chcą bardziej zagłębić się w filozofię stojącą za obliczeniami kwantowymi, prosimy o bardziej szczegółowe zapoznanie się z Davidem Deutschem.

[ad_2]