Jak obliczenia kwantowe zmienią programowanie? [Zamknięte]

Czym różni się programowanie algorytmu kwantowego? Jak wyglądałby język C, gdyby był zaprojektowany dla kubitów? Czy typy się zmieniły?

Kiedy spojrzałem na to jakiś czas temu, było jasne, że algorytmy kwantowe, choć nie są szczególnie szybkie, pozwalają na wykładniczo masywną równoległość. Będą więc świecić w przypadkach, w których wyszukiwanie w przestrzeniach jest niepraktyczne w przypadku sprzętu sekwencyjnego, a nawet masowo równoległego sprzętu sekwencyjnego.

Jedną z właściwości algorytmów kwantowych jest to, że muszą być odwracalne . Dany algorytm można przetłumaczyć na odwracalny, dodając do niego wystarczającą liczbę rejestrów, aby można go było uruchomić wstecz.

Inną właściwością jest to, że uzyskanie odpowiedzi z algorytmu kwantowego jest sprawą trafienia i nieudanej próby, ponieważ na końcu obliczeń otrzymujesz wiele odpowiedzi, każda z własnym prawdopodobieństwem. Należy go uruchomić w taki sposób, aby oczekiwana odpowiedź miała duże prawdopodobieństwo. Może to obejmować wielokrotne uruchomienie algorytmu do przodu i do tyłu.

Sprawdź algorytm wyszukiwania Grovera .

WSTAWIONO, aby pokazać podstawowe działanie algorytmu Grovera. Załóżmy, że występuje problem z wyszukiwaniem. Możliwe odpowiedzi to 0, 1, 2 i 3, ale prawidłowa odpowiedź to 2. Tak więc komputer kwantowy jest nakładany na superpozycję wszystkich czterech stanów i przechodzi przez sekwencję kroków, aby sprawdzić, który z nich jest poprawny, i odwraca swoją amplitudę, jak czarne kropki i strzałki poniżej:

Widać, że strzałka 2 została odwrócona wewnątrz maszyny, ale nie ma sposobu, aby powiedzieć, że na zewnątrz, ponieważ na zewnątrz widoczne są tylko prawdopodobieństwa, które są amplitudami do kwadratu , a gdy są do kwadratu, wszystkie są równe.

Jednak amplitudy mają średnią, oznaczoną czerwoną linią, a komputer może przejść przez sekwencję kroków, która odwraca każdą amplitudę względem średniej . Kiedy to się stanie, amplitudy i prawdopodobieństwa zostaną przeniesione do stanu 2, właściwa odpowiedź ! Więc jeśli maszyna zostanie zaobserwowana, stan 2 świeci.

To nie jest takie proste. Zasadniczo potrzeba wielu cykli maszyny, do przodu i do tyłu, odwracając na końcu każdego cyklu, aby zmaksymalizować prawdopodobieństwo właściwej odpowiedzi. Ponadto należy uważać, aby nie robić tego więcej niż tyle razy, ponieważ może on równie łatwo się odwrócić.

Dlaczego więc mówią, że komputery kwantowe są tak szybkie ? Ponieważ za każdym razem, gdy podwoisz liczbę kubitów, wyrównasz równoległość, ale nie wyrównasz długości czasu, więc ostatecznie wygrywa.

Czy to nie jest zabawne?

Byłem osobiście zainteresowany, w jaki sposób można to zastosować do weryfikacji poprawności oprogramowania. Teraz testujemy oprogramowanie, rzucając na niego wiązkę testowych danych wejściowych i (aby być zbyt prostym) sprawdzając, czy trafi ono w Assert. W komputerze kwantowym może być możliwe równoległe uruchomienie go na znacznie gęstszym zestawie danych wejściowych i sprawdzenie, czy którykolwiek z tych przypadków nie trafi w Assert.

Tak jakby wejściowy algorytm miał 128 bajtów lub 1024 bity, istnieją 2 ^ 1024 lub 10 ^ 308 możliwych różnych danych wejściowych. Nie ma sposobu na przetestowanie tylu wejść na konwencjonalnym komputerze, ale komputer kwantowy mógłby wypróbować je wszystkie równolegle.

Jak wyglądałby język C, gdyby był zaprojektowany dla kubitów? Czy typy się zmieniły?

Byłoby tak drastycznie inne, że byłoby niezrozumiałe jak C.

Główną kwestią (jak rozumiem) jest to, że obliczenia kwantowe nie działają w miły, imperatywny sposób „zrób to, potem to, a potem jeszcze jedno”. Próba zmuszenia C do zrobienia tego w „procesorze” komputera kwantowego będzie, jeśli nie niemożliwa, bardzo nieefektywna.

Algorytmy programowania dla komputerów kwantowych (znowu, jak rozumiem), wydają się być bliższe funkcjonalnemu mapowaniu / zmniejszaniu stylu programowania, ponieważ obliczenia kwantowe pozwalają na jednoczesne istnienie wszystkich kandydatów w części „redukującej” i „wypadnięcie” z komputera kiedy zaobserwowano.

Zauważ, że istnieją pewne algorytmy dla komputerów kwantowych, nawet jeśli nie istnieją urządzenia do ich uruchomienia. Na przykład algorytm Simona .

Aby jak najbardziej efektywnie wykorzystać komputer kwantowy, trzeba umieć radzić sobie z wejściami i wyjściami, które są stanami rejestru kwantowego, dla których tak naprawdę nie ma klasycznego analogu. Mówiąc z kilku lat doświadczenia w dziedzinie informacji kwantowej, muszę cię ostrzec, że nikt tak naprawdę nie ma dobrej intuicji poza abstrakcyjną matematyką algebr C *, i powiedziano mi, że nawet ta intuicja okazuje się nieodpowiednia jeśli zaczniecie się zastanawiać nad teorią względności.

Klasa problemów, które można skutecznie rozwiązać na komputerze kwantowym, jest znana jako BQP, dla Bounded Quantum Polynomial. To jest kwantowa wersja BPP i więcej informacji można znaleźć w tym artykule: http://www.scottaaronson.com/papers/bqpph.pdf

Wczoraj wieczorem badacz algorytmów kwantowych powiedział mi, że istnieje bardzo ważny problem, który jest kompletny w BQP: rozwiązanie liniowego układu N równań. Klasycznie jest to możliwe do rozwiązania w krokach O (N) z eliminacją Gaussa. Algorytm Harrow-Hassidim-Lloyd ( http://arxiv.org/abs/0811.3171 ) rozwiązuje go w polylog (N), pod warunkiem, że jesteś gotów zaakceptować odpowiedź, która ma rozwiązanie zakodowane jako stan kwantowy. Jeśli chcesz w pełni wykorzystać komputer kwantowy, wydaje się konieczne, abyś miał typ odpowiadający stanowi rejestru kwantowego.

Chociaż obecnie jestem trochę poza moją szczególną wiedzą, zaryzykuję przypuszczenie, że będziesz w stanie zaprogramować komputer kwantowy, o ile masz dostęp do typu odpowiadającego stanom magicznym. Jest to jednak trudna koncepcja, która wymaga dogłębnego przestudiowania tematu.

Ostrzegamy, że mamy bardzo dużo czasu od posiadania kwantowego języka programowania, ponieważ jesteśmy na bardzo prymitywnym etapie badań w dziedzinie obliczeń kwantowych. Pytanie o kwantowe C w tej chwili byłoby jak pójście do Alana Turinga i poproszenie go o zaprojektowanie Pythona. Nie mamy jeszcze kwantowej wersji lampy próżniowej!