Pomysły na projekty obliczeń kwantowych

15

Jestem studentem informatyki i obecnie planuję projekt dyplomowy. Potrzebuję pomysłów w dziedzinie obliczeń kwantowych. jakaś pomoc?

quantum-computing soft-question Deyaa
źródło
Byłoby pomocne, gdybyś mógł podać przykład rodzaju projektu, który uważasz za odpowiedni, biorąc pod uwagę czas na ten projekt i zamierzoną trudność. Czy szczegółowe czytanie artykułu jest dopuszczalne jako projekt?
Robin Kothari,
Przykład: połączenie (lub wynalezienie nowych) technik uczenia maszynowego z obliczeniami kwantowymi w celu rozwiązania trudnego problemu Google użył algorytmów uczenia maszynowego i komputera kwantowego z falą D, aby wykonać znacznie szybsze wyszukiwanie obrazów. Czas, mam: 11 miesięcy trudność: średnia (licencjackie)
Deyaa
3
Myślę, że powinna to być wiki społeczności, zakładając, że ma ona w ogóle zasięg.
Lew Reyzin
2
@ Ross: Głosowałem za tym, po prostu dlatego, że pytanie było niejasne, bardzo otwarte, subiektywne, a na pewno nie coś z jasną „poprawną odpowiedzią” (patrz także cstheory.stackexchange.com/faq ). Przy bardziej dokładnych wyjaśnieniach i w trybie „społeczności wiki” najprawdopodobniej uniknąłbym mojego negatywnego wyniku. Przepraszam, jeśli wydaje się to niepotrzebnie surowe, ale myślę, że ludzie powinni zwracać większą uwagę na formułowanie swoich pytań (i używać flagi CW poprawnie, zwłaszcza, że ​​nikt inny nie może tego obecnie naprawić).
Jukka Suomela,
3
@Deyaa, myślę, że próba odpowiedzi na pytania Joe Fitzsimmonsa i Jukki Suomeli pomoże ci w sformułowaniu lepszego pytania.
Suresh Venkat

Odpowiedzi:

27

Kilka pomysłów na teorię złożoności kwantowej zamieściłem na stronie http://scottaaronson.com/blog/?p=471

(Ale uwaga, większość z nich to problemy otwarte od lat! Moją propozycją dla projektu licencjackiego byłoby zerwanie części jednego z problemów).

Scott Aaronson
źródło
17

Jeden projekt, który zasugerowałem, jest następujący: Spróbuj opracować algorytm kwantowy oparty na losowym chodzie kwantowym do programowania liniowego. W ramach projektu należy najpierw nauczyć się kilku podstawowych faktów na temat losowych spacerów kwantowych i ich przydatności algorytmicznej, po drugie na temat algorytmów typu simpleks, a po trzecie próbować połączyć te dwa. Część 3 jest bardzo ambitna i nie wiem, czy można w ogóle powiedzieć coś owocnego, ale część 1 i 2 są już dobre dla projektu licencjackiego.

Gil Kalai
źródło
1
To naprawdę miła sugestia. W rzeczywistości istnieje duża liczba algorytmów, które mogą skorzystać ze specjalistycznych losowych spacerów. Kody korekcji błędów LT / Raptor oparte są na przykład na losowym marszu. Do góry głosuj ode mnie. I miło cię tu widzieć, Gil. :-)
Ross Snider
Nie wiedziałem, że istnieją takie przypadkowe spacery kwantowe! dobry pomysł !
Suresh Venkat
2
Suresh: Tak, są. Okazuje się, że są dość ważnym podejściem do algorytmów kwantowych. Rzecz w projektach algorytmów polega na tym, że przyspieszenie pierwiastka kwadratowego jest trywialne, a uzyskanie czegoś lepszego jest bardzo trudne. Być może innym pomysłem byłoby przyjrzenie się próbom sprowadzenia algorytmów wielomianu do czasu logowania, tak jak w najnowszym algorytmie rozwiązywania liniowych układów równań.
Joe Fitzsimons,
11

Wyniki DWaves z wyszukiwaniem obrazów są trochę dziwne. Obecnie nie ma mocnych dowodów na to, że urządzenia DWave nie mogą być skutecznie symulowane. Zostało to szczegółowo omówione na wielu blogach (zarówno Scott Aaronson, jak i Dave Bacon wielokrotnie opisywali DWave).

Pomijając tę ​​kwestię, istnieje ogromna liczba potencjalnych projektów, w zależności od interesującego cię aspektu obliczeń kwantowych. Zależy to również od poziomu twojej wiedzy na temat mechaniki kwantowej i fizyki. Pytania typu architektury często stają się dość fizyką, ponieważ ograniczenia eksperymentalne odgrywają dużą rolę w określaniu, na jakie problemy warto zwrócić uwagę. Algorytmy i złożoność komunikacji są znacznie bardziej zorientowane na CS.

Istnieje wiele różnych modeli obliczeń kwantowych, a dla niektórych istnieją bardziej strome bariery wejścia. Adiabatyczne i topologiczne obliczenia kwantowe są zwykle trudniejsze do uzyskania niż model obwodowy i model obliczeniowy oparty na pomiarach.

Jednym z problemów, na których miałem sukces podczas pracy z letnim studentem, było przybliżenie progów tolerancji błędów dla różnych kodów korekcji błędów przez symulację. Jest to coś, co ma stosunkowo niską barierę wejścia. Innym pomysłem jest przyjrzenie się kwantowym automatom komórkowym do zadań specjalnych (kodowanie, pomiary, przygotowanie stanu).

Wspomniałeś o uczeniu maszynowym, więc być może warto przyjrzeć się programowaniu ewolucyjnemu do ewolucji obwodów kwantowych pod kątem różnych prostych problemów. Bawiłem się tym kilka razy i wydaje się, że możesz uzyskać całkiem niezłe zachowanie (na przykład zmieniające się reguły wyszukiwania).

Mógłbym wymieniać losowe pomysły, które mogłyby stworzyć odpowiedni projekt, ale jeśli możesz podać więcej pomysłów na temat tego, czym jesteś zainteresowany, myślę, że uzyskasz lepsze odpowiedzi. Zasadniczym pytaniem może być po prostu: czy interesuje Cię projekt kodowania, jeden dotyczący projektowania sprzętu, drugi dotyczący czystej teorii itp.? W zależności od drogi, którą chcesz iść, będzie wiele różnych możliwości.

Joe Fitzsimons
źródło
4

Sugeruję coś w rodzaju dostarczenia obecnych narzędzi programistycznych do obliczeń kwantowych (takich jak libquantum) z możliwością wykorzystania procesorów graficznych z obsługą CUDA w celu przyspieszenia symulacji. Obliczenia kwantowe w mniejszym lub większym stopniu dotyczą algebry liniowej, tj. Operacji macierzowych i wektorowych, do czego przede wszystkim zostały zaprojektowane GPU.

M. Alaggan
źródło
symulacje jak co?
Deyaa,
Narzędzia programistyczne do obliczeń kwantowych umożliwiają symulację algorytmów i protokołów kwantowych, w tym algorytmu Shora, wyszukiwania Grovera, teleportacji kwantowej, kodów korekcji błędów oraz algorytmów, które sam stworzyłeś i chcesz przetestować.
M. Alaggan
3

Języki tematyczne związane z obliczeniami kwantowymi, takie jak QCL, zostały stworzone dla projektów dyplomowych. W rzeczywistości wszystkie języki oparte na obliczeniach kwantowych, które widziałem zaimplementowane w Internecie, zostały wykonane dla projektów dyplomowych. Możesz także spróbować zakodować emulator kwantowy. W książce „Obliczenia kwantowe dla informatyków” udostępniają ćwiczenia programistyczne, które łącznie składają się na taki emulator.

Vincent Russo
źródło
2

Nie wiem, jak to będzie pomocne, ale może da jakieś wskazówki.

Wiosną 2009 roku Sasha Razborov prowadziła kurs z zakresu obliczeń kwantowych. Strona internetowa kursu zawiera kilka pomysłów „projektowych”, a także odniesienia do kilku przełomowych prac kwantowych.

„Projekty” na stronie są tak naprawdę „bardziej zaangażowanymi problemami w odrabianiu prac domowych”, więc prawdopodobnie nie nadają się same do pracy magisterskiej i nie potrwają 11 miesięcy. Jednak te problemy i / lub niektóre odniesienia mogą wywołać dla Ciebie kilka dobrych pomysłów.

Joshua Grochow
źródło