Budowanie komputera kwantowego w symulacji

Jeśli ktoś chce zacząć budować komputer kwantowy od zera w symulacji (np. Jak ludzie budują klasyczny komputer od zera podczas kursu Nand2Tetris ), czy jest to możliwe?

Jeśli tak, jakie byłyby możliwe podejścia?

Jakie będą granice takiej symulowanej maszyny, biorąc pod uwagę określoną klasyczną moc obliczeniową? Na przykład, gdybyśmy wybrali przeciętnego komputera stacjonarnego / laptopa, jaki będzie limit? Jeśli weźmiemy superkomputer (taki jak Titan), jaki byłby limit?

Pierwsza część twojego pytania wydaje się być duplikatem istniejącego postu QC SE: Czy są emulatory dla komputerów kwantowych? .

Nie jestem do końca pewien, co masz na myśli, mówiąc, że budując komputer kwantowy od zera w symulacjach . Jednak tak, możesz wykonywać symulacje oprogramowania komputera kwantowego przy użyciu przeciętnego laptopa / komputera stacjonarnego. Dokładny „limit” będzie zależeć od specyfikacji komputera.

Ponieważ komputer kwantowy nie narusza tezy Church-Turinga , teoretycznie możliwe jest symulowanie komputera kwantowego za pomocą idealnej maszyny Turinga. Oczywiste podejście do symulacji takiego układu wymaga czasu wykładniczego na klasycznym komputerze, a złożoność przestrzeni jest wykładniczą funkcją liczby symulowanych bitów kwantowych. Powiedzmy, że symulujesz bitowy komputer kwantowy, musisz przechowywać około 2 n bitów informacji w klasycznym komputerze w każdej chwili. Ponadto wdrożenie bram kwantowych ponownie zajmie ogromną ilość zasobów pod względem złożoności czasu i przestrzeni. Implementacja bramki kwantowej działającej na $n$$2^{n}$$n$ kubitach musiałaby przechowywać (ponieważ można przedstawić wszystkie operacje bramek kwantowych jako macierz wielkości 2 n × 2 n ) bitów informacji.$4^{n}$$2^{n}\times2^{n}$

Możesz niejako oszacować „limit” w zależności od specyfikacji klasycznego komputera. Na przykład, jeśli (dostępna) wielkość pamięci twojego klasycznego komputera wynosi około TB, spodziewam się, że możesz symulować log 4 ( 8 × 10 12 ) ≈ 21- bitowy komputer kwantowy (dla pewności, powiedzmy 20 ). Należy jednak pamiętać, że klasyczne komputery zajęłyby znacznie więcej czasu, aby uzyskać dostęp do wszystkich pojedynczych bitów informacji, w porównaniu do rzeczywistego komputera kwantowego (w zależności od sprzętu komputera kwantowego). Więc będzie wolniej$1$$\log_4(8\times 10^{12})\approx 21$$20$niż rzeczywisty komputer kwantowy! Niektóre inne ograniczenia są takie, że po każdym działaniu bramy qitit należy śledzić, które kubity wyjściowe są splątane, co jest trudnym problemem dla NP . Ponadto pomiaru nie można dokładnie zasymulować na klasycznym komputerze, ponieważ klasycznie nie ma naprawdę generatora liczb losowych.$n$

Cóż, obecnie pracuję nad symulatorem komputera kwantowego. Podstawową ideą obliczeń kwantowych są oczywiście bramki reprezentowane przez macierze stosowane do kubitów reprezentowanych przez wektory. Korzystanie z pakietu numpy Pythona nie jest trudne do zaprogramowania w najbardziej podstawowym tego słowa znaczeniu.

Stamtąd można oczywiście rozszerzyć interfejs. Można również rozważyć próbę uczynienia z niego symulatora nieidealnego komputera kwantowego, to znaczy biorąc pod uwagę czasy dekoherencji i korekcję błędów.

Następnie dostaniesz się na nieznane terytorium. Jak budujesz zestaw instrukcji dla komputera kwantowego? Kto wie. Musisz się dowiedzieć. Będziesz także musiał znaleźć swoją wersję asemblera, a nawet wersję języków programowania wyższego poziomu.

A więc ograniczenia klasycznego komputera? Cóż, to naprawdę skomplikowane pytanie (które warto zadać osobno, imho), ale oto krótkie podsumowanie:

• nie wiemy, czy komputery kwantowe są rzeczywiście lepsze niż komputery klasyczne; algorytmy dla klasycznych komputerów nie mogą być jeszcze wystarczająco dobre (supremacja kwantowa)
• powiedzmy, co wydaje się całkiem prawdopodobne, że komputery kwantowe są lepsze niż komputery klasyczne. ta poprawa będzie w dużej mierze zależeć od problemu - komputery kwantowe mogą na przykład zauważyć znacznie wyższą poprawę prędkości w znajdowaniu głównych faktoryzacji niż w sprawdzaniu wiadomości e-mail. (patrz także to P.SE Q /).
• aby podać jakąś wartość liczbową, jeśli weźmiemy pod uwagę obecny najszybszy algorytm do znalezienia klasycznego podziału na czynniki pierwsze, tj. ogólne sito liczbowe, mamy czas O $O\Big(e^{\sqrt{\frac{64}{9}}(\log N)^{\frac 13}(\log\log N)^{\frac 23}}\Big)$co jest wyraźnie raczej obrzydliwe. Z drugiej strony algorytm Shora działa $O((\log N)^2(\log \log N)(\log \log \log N))$ co jest oczywiście znacznie szybsze.
• Mogę uruchamiać kilka kubitów na komputerze, o ile przechowuję je w $|0\rangle$ lub $|1\rangle$stany - tzn. skutecznie klasyczne. Więc w pewnym sensie twoje pytanie jest znów źle zdefiniowane.

Wydaje mi się, że ta odpowiedź opiera się głównie na niezrozumieniu, co to znaczy „symulować” coś.

Mówiąc ogólnie, „symulacja” złożonego systemu oznacza odtworzenie niektórych funkcji takiego systemu za pomocą platformy, którą łatwiej kontrolować (często, ale nie zawsze, klasyczny komputer).

Dlatego pytanie, czy „można symulować komputer kwantowy w komputerze klasycznym” jest nieco niejednoznaczne. Jeśli masz na myśli, że chcesz odtworzyć każdy możliwy aspekt „komputera kwantowego”, to nigdy tak się nie stanie, tak jak nigdy nie będziesz w stanie zasymulować każdego aspektu dowolnego klasycznego systemu (chyba że użyjesz tego samego identycznego system oczywiście).

Z drugiej strony z pewnością można symulować wiele aspektów złożonego urządzenia, takiego jak „komputer kwantowy”. Na przykład można chcieć symulować ewolucję stanu w obwodzie kwantowym. W rzeczywistości może to być niezwykle łatwe! Na przykład, jeśli masz python na swoim komputerze, po prostu uruchom następujące

import numpy as np
identity_2d = np.diag([1, 1])
pauliX_gate = np.array([[0, 1], [1, 0]])
hadamard_gate = np.array([[1, 1], [1, -1]]) / np.sqrt(2)

cnot_gate = np.kron(identity_2d, pauliX_gate)
H1_gate = np.kron(hadamard_gate, identity_2d)

awesome_entangling_gate = np.dot(cnot_gate, H1_gate)

initial_state = np.array([1, 0, 0, 0])
final_state = np.dot(awesome_entangling_gate, initial_state)
print(final_state)

Gratulacje, właśnie „zasymulowałeś” ewolucję separowalnego stanu dwóch kubitów w stan Bell!

Jeśli jednak spróbujesz zrobić to samo z, powiedzmy, 40 kubitami i nietrywialną bramą, nie będziesz w stanie wyciągnąć tego łatwo. Naiwnym powodem jest to, że nawet po prostu zapisuję stan$n$-qubit (nie rzadki) stan, musisz podać ~$2^n$liczby zespolone, a to bardzo szybko zaczyna zajmować dużo pamięci. Mówię tutaj „naiwnie”, ponieważ w wielu przypadkach mogą istnieć sztuczki, które pozwalają uniknąć tego problemu$^{(1)}$. Dlatego wiele osób pracuje nad próbą znalezienia sprytnych sztuczek do symulacji obwodów kwantowych (i innych rodzajów układów kwantowych) za pomocą klasycznych komputerów i dlatego nie jest to wcale takie proste$^{(2)}$.

Inne odpowiedzi już dotyczyły różnych aspektów tej twardości, a odpowiedzi na inne pytanie już wspominają o wielu dostępnych platformach do symulacji / emulacji różnych aspektów algorytmów kwantowych, więc nie pójdę tam.

(1) Ciekawym tego przykładem jest problem symulacji urządzenia do pobierania próbek bozonów (nie jest to algorytm kwantowy w sensie stanu ewoluującego przez szereg bramek, ale mimo to jest przykładem nietrywialnego urządzenia kwantowego). BosonSampling to problem z próbkowaniem , w którym zadanie polega na próbkowaniuz określonego rozkładu prawdopodobieństwa, co zostało wykazane (przy prawdopodobnych założeniach), że nie można skutecznie zrobić z klasycznym urządzeniem. Chociaż nigdy nie wykazano, że jest to podstawowy aspekt tej twardości, niewątpliwie nietrudnym problemem związanym z symulacją urządzenia do pobierania próbek bozonów była konieczność obliczenia wykładniczo dużej liczby prawdopodobieństw, z których należy próbkować. Jednak ostatnio wykazano, że rzeczywiście nie trzeba obliczać całego zestawu prawdopodobieństw, aby pobrać z nich próbki ( 1705.00686 i 1706.01260). W zasadzie nie jest to dalekie od symulacji ewolucji wielu kubitów w obwodzie kwantowym bez konieczności przechowywania całego stanu układu w dowolnym punkcie. Jeśli chodzi o bardziej bezpośrednio obwody kwantowe, przykłady niedawnego przełomu w możliwościach symulacji to 1704.01127 i 1710.05867 (również najnowszy, jeszcze nieopublikowany, to 1802.06952 ).

(2) W rzeczywistości wykazano (a raczej dostarczono mocnych dowodów na to), że nie można skutecznie symulować większości obwodów kwantowych, patrz 1504.07999 .