Czy konieczna jest korekcja błędów?

20

Dlaczego potrzebujesz korekcji błędów? Rozumiem, że korekcja błędów usuwa błędy z szumu, ale hałas powinien się uśrednić. Aby wyjaśnić, o co pytam, dlaczego nie możesz zamiast korekcji błędów po prostu uruchomić operacje, powiedzmy sto razy, i wybrać średnią / najczęstszą odpowiedź?

error-correction noise

— wrzos
źródło

18

To nie jest dobrze skalowane. Po umiarkowanie długim obliczeniu zasadniczo pozostajesz w stanie maksymalnego zmieszania lub w jakimkolwiek punkcie stałym, jaki ma Twój hałas. Aby skalować do dowolnych długich obliczeń, musisz poprawić błędy, zanim staną się zbyt duże.

Oto kilka krótkich obliczeń dla podanej powyżej intuicji. Rozważ prosty model białego szumu (hałas depolaryzujący), gdzie jest stanem idealnym ( obowiązuje standardowa notacja ). Jeśli połączysz takich hałaśliwych procesów, nowym parametrem hałasu jest , który wykładniczo zwiększa liczbę bramek (lub innych źródeł błędów). Jeśli powtórzysz eksperyment razy i przyjmiesz, że standardowy błąd skaluje się do , zobaczysz, że liczba uruchomień

ρ^{'} (ε) = (1 - ε) ρ + ε \frac{ja}{tr ja},

$\rho'(\varepsilon)= (1-\varepsilon)\rho + \varepsilon \frac{\mathbb{I}}{\operatorname{tr} \mathbb{I}},$

ρ

$\rho$

n

$n$

ε^{'} = 1 - (1 - ε)^{n}

$\varepsilon'=1-(1-\varepsilon)^n$

m

$m$

\frac{1}{\sqrt{m}}

$\frac{1}{\sqrt{m}}$

m

$m$ będzie wykładniczo w długości obliczeń!

— M. Sterna
źródło

11

Gdyby poziom błędu był wystarczająco niski, można by wykonać obliczenia sto razy i przyjąć najczęstszą odpowiedź. Na przykład działałoby to, gdyby poziom błędów był na tyle niski, że oczekiwana liczba błędów na obliczenie była bardzo niewielka - co oznacza, że skuteczność tej strategii zależy od tego, jak długo i jak skomplikowane będzie obliczenie.

Gdy poziom błędu lub długość obliczeń osiągną wystarczająco wysoką wartość, nie można już mieć żadnej pewności, że najbardziej prawdopodobnym wynikiem jest to, że wystąpiły błędy zerowe: w pewnym momencie staje się bardziej prawdopodobne, że masz jeden lub dwa lub więcej błędów, niż że masz zero. W takim przypadku nic nie stoi na przeszkodzie, aby większość przypadków udzieliła nieprawidłowej odpowiedzi. Co wtedy?

Te kwestie nie są szczególne w obliczeniach kwantowych: dotyczą one również obliczeń klasycznych - zdarza się, że prawie cała nasza technologia jest na wystarczająco zaawansowanym etapie dojrzałości, że problemy te nie dotyczą nas w praktyce; że może istnieć większa szansa, że komputer zostanie uderzony przez meteoryt w trakcie obliczeń (lub skończy mu się bateria, albo zdecydujesz się go wyłączyć) niż błąd sprzętowy. Tym, co jest (tymczasowo) szczególne w obliczeniach kwantowych, jest to, że technologia nie jest jeszcze wystarczająco dojrzała, abyśmy byli tak zrelaksowani w kwestii możliwości wystąpienia błędu.

W czasach, gdy obliczenia klasyczne mająbyliśmy na etapie, gdy korekcja błędów była zarówno praktyczna, jak i konieczna, mogliśmy skorzystać z niektórych technik matematycznych - korekcji błędów - które pozwoliły zlikwidować efektywny poziom błędu i zasadniczo obniżyć go tak, jak nam się podobało. Te same techniki można zaskakująco zastosować do kwantowej korekcji błędów - z odrobiną rozszerzenia, aby uwzględnić różnicę między informacją kwantową a klasyczną. Początkowo, przed połową lat dziewięćdziesiątych, uważano, że korekcja błędu kwantowego jest niemożliwa ze względu na ciągłość przestrzeni stanów kwantowych. Ale jak się okazuje, poprzez zastosowanie klasycznych technik korekcji błędów we właściwy sposób do różnych sposobów pomiaru kubitów (zwykle określanych jako „bit” i „faza”), w zasadzie możesz tłumić wiele rodzajów szumów również w układach kwantowych. Techniki te również nie są specjalne dla kubitów: ten sam pomysł można zastosować w systemach kwantowych o dowolnym skończonym wymiarze (chociaż w przypadku modeli takich jak obliczenia adiabatyczne może to utrudnić faktyczne wykonanie obliczeń, które chcesz wykonać).

W chwili, gdy to piszę, poszczególne kubity są tak trudne do zbudowania i wprowadzenia, że ludzie mają nadzieję, że uda im się wykonać obliczenia oparte na zasadzie zasady bez żadnej korekty błędów. To dobrze, ale ograniczy to, jak długo mogą trwać ich obliczenia, dopóki liczba skumulowanych błędów nie będzie na tyle duża, że obliczenia przestaną mieć znaczenie. Istnieją dwa rozwiązania: poprawa tłumienia hałasu lub zastosowanie korekcji błędów. Oba są dobrymi pomysłami, ale możliwe jest, że korekcja błędów jest łatwiejsza do wykonania w perspektywie średnio- i długoterminowej niż tłumienie źródeł hałasu.

— Niel de Beaudrap
źródło

Szybką korektą jest to, że współczesny sprzęt cierpi z powodu nieistotnych poziomów błędów i stosowane są metody korekcji błędów. To powiedziawszy, oczywiście, że masz rację, że problemy są znacznie gorsze w obecnych komputerach kwantowych.

— Nat

@Nat: ciekawe. Mam niejasną świadomość, że obecnie może tak być w przypadku układów GPU i (w kontekście nieobejmującym aktywnego obliczania) macierze RAID są również oczywistym przykładem. Ale czy mógłbyś opisać inne platformy sprzętowe, dla których klasyczne obliczenia muszą polegać na korekcji błędów podczas obliczeń?

— Niel de Beaudrap

Wygląda na to, że błędy występują najczęściej w kontekstach sieciowych, następnie miejsce na dysku, a następnie pamięć RAM. Protokoły sieciowe i dyski rutynowo wdrażają sztuczki korekcji błędów. RAM to mieszana torba; pamięć RAM serwera / stacji roboczej zwykle korzysta z kodu korygującego błędy (ECC), chociaż pamięć RAM często nie. W procesorach wyobrażam sobie, że mają więcej taktyk specyficznych dla implementacji, ale prawdopodobnie byłyby to tajemnice producenta. Współczynniki błędów w procesorach i procesorach graficznych stają się istotne na możliwym do zaobserwowania poziomie w kilku przypadkach, np. W przypadku podkręcania i decyzji producenta o blokowaniu rdzenia.

— Nat

Właściwie trochę ciekawi mnie teraz korekcja błędów typu procesora. Mam na myśli, że pamięć podręczna wydaje się być podatna na te same problemy, co normalna pamięć RAM (chyba, że jest buforowana z większą mocą czy coś takiego?), Które prawdopodobnie byłyby nie do zaakceptowania na serwerze / konteksty stacji roboczych. Ale na poziomie rejestru? To byłoby coś miłego do przeczytania; nie zobaczyłem niczego od razu w Google, ale przypuszczam, że takie informacje prawdopodobnie byłyby tajemnicą handlową.

— Nat

8

Teraz, dodając do odpowiedzi M. Sterna :

Głównym powodem, dla którego korekcja błędów jest potrzebna komputerom kwantowym, jest to, że kubity mają kontinuum stanów (rozważam obecnie komputery kwantowe oparte tylko na kubitach).

W komputerach kwantowych, w przeciwieństwie do komputerów klasycznych, każdy bit nie istnieje tylko w dwóch możliwych stanach. Na przykład prawdopodobnym źródłem błędu jest nadmierna rotacja: może być powinien stać ale rzeczywiście staje $\alpha|0\rangle+\beta|1\rangle$ $\alpha|0\rangle + \beta e^{i\phi}|1\rangle$ $\alpha|0\rangle+\beta e^{i(\phi+\delta)}|1\rangle$ . Rzeczywisty stan jest zbliżony do poprawnego, ale nadal zły. Jeśli nic z tym nie zrobimy, z biegiem czasu pojawią się małe błędy i ostatecznie staną się dużym błędem.

W klasycznym komputerze powiedzmy, że wartość bitu jest replikowana n-razy w następujący sposób:

0 \to 00000 ... n razy

$0 \to 00000...\text{n times}$

1 \to 11111... n times

$1 \to 11111...\text{n times}$

$0001000100$ $0000000000$ $0's$ $0$ $10$

$|\psi\rangle = \alpha |0\rangle +\beta |1\rangle$ $(\alpha|0\rangle + \beta |1\rangle)\otimes (\alpha e^{i\epsilon}|0\rangle + \beta e^{i\epsilon'}|1\rangle)\otimes (\alpha e^{i\epsilon_2}|0\rangle + \beta e^{i\epsilon_2'}|1\rangle)\otimes ...$ $0$ $0$ $10$ $10$

Tak więc potrzebujesz innego rodzaju technik korekcji błędów, aby radzić sobie z błędami występującymi podczas działania komputera kwantowego, które mogą radzić sobie nie tylko z błędami odwracania bitów, ale także błędami przesunięcia fazowego. Ponadto musi być odporny na niezamierzone odkażanie. Należy pamiętać, że większość bram kwantowych nie będzie „idealna”, mimo że przy odpowiedniej liczbie „uniwersalnych bram kwantowych” można dowolnie zbliżyć się do zbudowania dowolnej bramy kwantowej, która dokonuje (teoretycznie) transformacji jednostkowej.

Niel de Beaudrap wspomina, że istnieją sprytne sposoby zastosowania klasycznych technik korekcji błędów w taki sposób, że mogą one poprawić wiele błędów pojawiających się podczas operacji kwantowych, co jest rzeczywiście poprawne i jest dokładnie tym, co robią dzisiejsze kody korekcji błędów kwantowych. Chciałbym dodać następujące informacje z Wikipedii , ponieważ mogą one wyjaśnić, w jaki sposób kody korygujące błędy kwantowe radzą sobie z problemem opisanym powyżej:

Klasyczne kody korygujące błędy wykorzystują pomiar syndromu do diagnozowania, który błąd powoduje uszkodzenie kodowanego stanu. Następnie odwracamy błąd, stosując operację naprawczą opartą na zespole. Kwantowa korekcja błędów wykorzystuje również pomiary syndromu. Wykonujemy pomiar wielu kubitów, który nie zakłóca informacji kwantowej w stanie zakodowanym, ale pobiera informacje o błędzie. Pomiar syndromu może ustalić, czy kubit został uszkodzony, a jeśli tak, to który. Co więcej, wynik tej operacji (syndrom) mówi nam nie tylko, który fizyczny kubit został dotknięty, ale także, w jaki sposób na kilka możliwych sposobów został on dotknięty. Ta ostatnia jest na pierwszy rzut oka sprzeczna z intuicją: skoro hałas jest arbitralny, w jaki sposób efekt hałasu może być jedną z niewielu wyraźnych możliwości? W większości kodów efekt jest albo odwrócony, albo odwrócony znak (fazy), lub oba (odpowiadające macierzom Pauliego X, Z i Y). Powodem jest to, że pomiar syndromu ma projekcyjny efekt pomiaru kwantowego. Tak więc nawet jeśli błąd spowodowany hałasem był arbitralny, można go wyrazić jako superpozycję operacji bazowych - podstawa błędu (podana tutaj przez macierze Pauliego i tożsamość). Pomiar syndromu „zmusza” kubit do „podjęcia decyzji” o wystąpieniu określonego „błędu Pauliego”, a syndrom mówi nam, który z nich pozwala nam na powrót tego samego operatora Pauli na uszkodzony qubit efekt błędu.

Pomiar syndromu mówi nam tyle, ile to możliwe, o występującym błędzie, ale nic o wartości zapisanej w logicznym kubicie - w przeciwnym razie pomiar zniszczyłby wszelką superpozycję kwantową tego logicznego kubitu z innymi kubitami w kwantie komputer.

Uwaga : Nie podałem żadnego przykładu rzeczywistych technik korekcji błędów kwantowych. Istnieje wiele dobrych podręczników, które omawiają ten temat. Mam jednak nadzieję, że ta odpowiedź da czytelnikom podstawowe pojęcie o tym, dlaczego potrzebujemy kodów korygujących błędy w obliczeniach kwantowych.

Zalecane dalsze odczyty:

Zalecany wykład wideo:

Kurs Mini Crash: Kwantowa korekcja błędów przeprowadzona przez Bena Reichardta z University of Southern California

— Sanchayan Dutta
źródło

3

Nie jestem pewien, czy kontinuum stanów odgrywa jakąkolwiek rolę. Klasyczne obliczenia za pomocą bitów również miałyby takie same problemy, gdyby nasza technologia była mniej dojrzała, i rzeczywiście w znacznym stopniu cierpiała z powodu hałasu w różnych momentach rozwoju. Zarówno w przypadku klasycznym, jak i kwantowym, hałas nie odbiega zwykle w normalnych okolicznościach

— Niel de Beaudrap

5

$5$

1

$1$

0

$0$

0

$0$

0.5

$0.5$

0

$0$

0

$0$

5

$5$

Oczywiście nie pomylisz się, mówiąc, że nawet klasyczne obliczenia cierpią z powodu problemu hałasu. Istnieje również ugruntowana teoria klasycznych kodów korygujących błędy! Jednak sytuacja jest znacznie bardziej tragiczna w przypadku obliczeń kwantowych ze względu na możliwość nieskończonej liczby stanów istnienia pojedynczego kubita.

— Sanchayan Dutta

1

Techniki stosowane do kwantowej korekcji błędów nie obejmują faktu, że przestrzeń stanu jest w jakikolwiek sposób nieskończona. Przedstawione przez ciebie argumenty wydają się wyciągać analogię między obliczeniami kwantowymi a obliczeniami analogowymi - chociaż istnieje podobieństwo, sugerowałoby to, że korekcja błędu kwantowego byłaby niemożliwa, gdyby była analogią dźwiękową. W przeciwieństwie do tego, przestrzeń stanu wielu kubitów jest również jak rozkład prawdopodobieństwa na ciągach bitów, których jest również kontinuum; a jednak sama korekcja błędów na określonych ciągach bitowych wystarcza, aby stłumić błąd.

— Niel de Beaudrap

1

@glS Usunąłem pierwsze zdanie. Masz rację. Interpretowałem obliczenia w niepowiązany sposób.

— Sanchayan Dutta

2

Dlaczego potrzebujesz korekcji błędów? Rozumiem, że korekcja błędów usuwa błędy z szumu, ale hałas powinien się uśrednić.

Jeśli zbudowałeś dom lub drogę, a hałas był wariantem, różnicą w odniesieniu do prostoty, kierunku, to nie tylko / tylko: „Jak by to wyglądało”, ale „Jak by to było?” - superpozycja zarówno skuteczności, jak i poprawności.

Gdyby dwie osoby obliczyły obwód piłki golfowej na podstawie średnicy, każda otrzymałaby podobną odpowiedź, z zastrzeżeniem dokładności ich obliczeń; jeśli każde użyje kilku miejsc po przecinku, byłoby to „wystarczająco dobre”.

Gdyby dwie osoby otrzymały identyczny sprzęt i składniki i otrzymały ten sam przepis na ciasto, czy powinniśmy oczekiwać identycznych rezultatów?

Aby wyjaśnić, o co pytam, dlaczego nie możesz zamiast korekcji błędów po prostu uruchomić operacje, powiedzmy sto razy, i wybrać średnią / najczęstszą odpowiedź?

Zniszczasz ważenie, stukając palcem w wagę.

Jeśli jesteś na głośnym koncercie i próbujesz komunikować się z osobą obok, czy ona rozumie cię za pierwszym razem, za każdym razem?

Jeśli opowiesz historię lub rozpowszechnisz pogłoskę, (a niektórzy komunikują się dosłownie, niektórzy dodają swój własny obrót, a inni zapominają o częściach), to kiedy wraca do ciebie, ocenia się samo i staje się zasadniczo (ale nie identycznie) to samo co powiedziałeś? - mało prawdopodobne.

To jak marszczenie kawałka papieru, a następnie spłaszczanie go.

Wszystkie te analogie miały na celu zaoferowanie prostoty w stosunku do dokładności, możesz je ponownie odczytać kilka razy, uśrednić i uzyskać dokładną odpowiedź lub nie. ;)

Bardziej techniczne wyjaśnienie, dlaczego kwantowa korekcja błędów jest trudna, ale konieczna, wyjaśniono na stronie Wikipedii: „ Kwantowa korekcja błędów ”:

„Kwantowa korekcja błędów (QEC) jest wykorzystywana w obliczeniach kwantowych do ochrony informacji kwantowej przed błędami wynikającymi z dekoherencji i innych szumów kwantowych . Kwantowa korekcja błędów jest niezbędna, jeśli chce się uzyskać odporne na błędy obliczenia kwantowe, które poradzą sobie nie tylko z szumem na przechowywanym informacje kwantowe, ale także z wadliwymi bramkami kwantowymi, wadliwym przygotowaniem kwantowym i błędnymi pomiarami. ”.

„Klasyczna korekcja błędów wykorzystuje redundancję .” ...

„Kopiowanie informacji kwantowej nie jest możliwe z powodu twierdzenia o braku klonowania . Twierdzenie to wydaje się stanowić przeszkodę w sformułowaniu teorii kwantowej korekcji błędów. Możliwe jest jednak rozprzestrzenienie informacji o jednym kubicie na wysoce splątany stan kilku ( fizyczne) kubity. Peter Shor po raz pierwszy odkrył tę metodę formułowania kodu korygującego błąd kwantowy, przechowując informacje o jednym kubicie w wysoce splątanym stanie dziewięciu kubitów. Kod korygujący błąd kwantowy chroni informacje kwantowe przed błędami o ograniczonej formie. ”.

— Obrabować
źródło

2

hałas powinien się uśrednić.

Hałas sam się nie uśrednia. To jest błąd Hazardzisty. Mimo że hałas ma tendencję do meandrowania w przód i w tył, wciąż się kumuluje.

$N/2$ $O(\sqrt N)$ $O(N)$

$Q$ $2Q$ $2^Q$ $O(N)$

uruchomić operacje, powiedzmy, sto razy i wybrać średnią / najczęstszą odpowiedź?

Gdy obliczenia stają się coraz większe i dłuższe, szansa na brak szumu lub jego doskonałe tłumienie szybko staje się tak bliska 0%, że nie można oczekiwać, że zobaczy prawidłową odpowiedź nawet raz, nawet jeśli powtórzysz obliczenia bilion razy.

— Craig Gidney
źródło