Naukowcy ze Stanów Zjednoczonych wymyślili, jak testować problemy, które nie są jeszcze dostępne dla ludzi. Naukowcy używają tej samej metody, co śledczy policyjni w rozmowach z komputerami rozwiązującymi te problemy. „Mylą” przesłuchiwanych, przesłuchują dwa samochody osobno itp. Wykorzystywana jest nawet mechanika kwantowa.
Wyobraź sobie: przychodzi do ciebie człowiek i mówi, że ma wróżbitę i że może on wyjawić niezrozumiałe tajemnice wszechświata. Jesteś zaintrygowany, ale prawie mu nie wierzysz. Na pewno będziesz chciał się upewnić, że wróżbita mówi prawdę, a do tego będziesz potrzebować jakiegoś sposobu lub metody.
To jest istota jednego z głównych problemów informatyki. Niektóre zadania są zbyt trudne do wykonania w rozsądnych ramach czasowych. Ale ich rozwiązanie jest łatwe do zweryfikowania. Z tego powodu informatycy chcą wiedzieć: jak złożony może być problem, który ma weryfikowalne rozwiązanie?
Okazuje się, że odpowiedź brzmi: może być niesamowicie złożona.
W kwietniu dwóch informatyków opublikowało artykuł badawczy, w którym zwielokrotniono liczbę problemów trudnych do rozwiązania, ale łatwych do zweryfikowania. Opisali metodę testowania rozwiązań problemów o niemal niewiarygodnej złożoności. „To brzmi jak szalone” - powiedział Thomas Vidick, informatyk z California Institute of Technology, który nie brał udziału w tej nowej pracy.
Badania dotyczą komputerów kwantowych wykonujących obliczenia według sprzecznych reguł mechaniki kwantowej. Komputery kwantowe dopiero zaczynają się pojawiać, ale w przyszłości mogą zrewolucjonizować obliczenia i obliczenia.
W rzeczywistości nowe przeprowadzone badania naukowe dają nam możliwość wpłynięcia na wróżbitę opisanego na początku artykułu. Nawet jeśli obiecuje dać nam odpowiedzi na te problemy, których sami nie jesteśmy w stanie rozwiązać, więc nawet w tej pozornie beznadziejnej sytuacji nadal będziemy mieli sposób, aby przetestować wróżbitę i upewnić się, że mówi prawdę (lub oszukuje).
Film promocyjny:
NA ŚMIERĆ WSZECHŚWIATA
Gdy problem jest trudny do rozwiązania, ale łatwy do zweryfikowania, znalezienie rozwiązania zajmuje dużo czasu, ale sprawdzenie poprawności danego rozwiązania już nie.
Oto przykład. Wyobraź sobie, że dostałeś rysunek. Jest to zbiór punktów (wierzchołków) połączonych liniami (krawędziami). Zostaniesz zapytany, czy możliwe jest pomalowanie tych punktów w kształcie tylko trzema kolorami, tak aby punkty połączone liniami miały różne kolory.
Ten „trójkolorowy” problem jest trudny do rozwiązania. Ogólnie rzecz biorąc, czas potrzebny na skomponowanie trójkolorowej figury (lub stwierdzenie, że nie może ona istnieć) rośnie wykładniczo wraz ze wzrostem wielkości figury. Na przykład, jeśli figura ma 20 punktów połączenia linii, to rozwiązanie problemu zajmuje od 3 do dwudziestej potęgi nanosekund, czyli kilka sekund w jednostkach czasu, do których jesteśmy przyzwyczajeni. Ale jeśli liczba wynosi 60 punktów, to poszukiwanie rozwiązania zajmie 100 razy dłużej niż szacowany wiek Wszechświata.
Ale wyobraźmy sobie: ktoś twierdzi, że zrobił taką trójkolorową figurę. Zajmie nam trochę czasu, zanim sprawdzimy prawdziwość jego oświadczenia. Po prostu zaczniemy sprawdzać punkty połączeń linii jeden po drugim. Wraz ze wzrostem liczby czas sprawdzania również powoli się wydłuża. To jest tak zwany czas wielomianowy. W rezultacie okazuje się, że komputerowi nie zajmuje dużo więcej czasu sprawdzenie trójkolorowej figury z 60 wierzchołkami niż sprawdzenie figury z 20 punktami połączeń.
„Łatwo jest sprawdzić, czy ten obwód działa, pod warunkiem, że jest to prawdziwa trójkolorowa figura” - mówi fizyk z MIT John Wright, który pisze nową pracę z Anandem Natarajanem z Caltech. …
W latach 70. programiści zidentyfikowali klasę problemów, które są łatwe do przetestowania, choć czasami trudne do rozwiązania. Nadali tej klasie nazwę NPT - niedeterministyczny czas wielomianowy. Od tamtej pory wielu informatyków bardzo intensywnie bada te problemy. W szczególności naukowcy chcą wiedzieć, jak zmienia się ta klasa problemów, gdy inspektor ma nowe sposoby sprawdzenia poprawności rozwiązania.
PYTANIA PRAWIDŁOWE
Przed pracami Natarajana i Wrighta dokonano dwóch ważnych odkryć podczas weryfikacji poprawności rozwiązania. Znacznie zwiększyły naszą zdolność do testowania bardzo trudnych problemów.
Aby zrozumieć istotę odkrycia pierwszego przełomu, wyobraź sobie, że jesteś daltonistą. Na stole przed tobą kładzie się dwie kostki i pojawia się pytanie, czy są tego samego koloru, czy innego. To zadanie jest dla Ciebie niemożliwe. Ponadto nie jesteś w stanie sprawdzić decyzji innej osoby.
Ale możesz zadawać pytania tej osobie, którą nazwiemy przysłowiowym. Powiedzmy, że przysłowie mówi, że para kostek ma różne kolory. Pierwszą kostkę oznaczymy literą „A”, a drugą literą „B”. Bierzesz kostki, chowasz je za plecami i kilkakrotnie przenosisz z rąk do rąk. Następnie pokazujesz kostki i prosisz komisarza, aby pokazał kostkę A.
Jeśli kostki są w różnych kolorach, wszystko jest niezwykle proste. Dowódca wie, że sześcian A jest, powiedzmy, czerwony i za każdym razem wskaże go poprawnie.
Ale jeśli kostki są tego samego koloru, to znaczy przysłowie powiedział kłamstwo, mówiąc, że ich kolor jest inny, może tylko zgadywać, gdzie jest sześcian. Z tego powodu będzie poprawnie wskazywał śmierć A tylko w 50% przypadków. Oznacza to, że kilkakrotnie pytając weryfikatora o rozwiązanie, można zweryfikować jego poprawność.
„Egzaminator może zadawać przysłowie pytania” - powiedział Wright. „A może pod koniec rozmowy zaufanie weryfikatora wzrośnie”.
W 1985 roku trójka programistów udowodniła, że takie interaktywne dowody można wykorzystać do testowania rozwiązań problemów bardziej złożonych niż klasa NIP. W wyniku ich pracy pojawiła się nowa klasa problemów zwana IPT - interaktywny czas wielomianowy. Metodę zastosowaną do przetestowania koloru dwóch kostek można wykorzystać do testowania rozwiązań bardziej złożonych problemów i pytań.
Drugi ważny krok został podjęty w tej samej dekadzie. Wszystko tutaj jest zgodne z logiką policyjnego śledztwa. Jeśli masz dwóch podejrzanych, o których myślisz, że popełnili przestępstwo, nie będziesz ich przesłuchiwać razem. Będziesz przesłuchiwał ich w różnych pokojach, a następnie porównywał udzielone przez nich odpowiedzi. Przesłuchując te osoby oddzielnie, możesz dowiedzieć się więcej prawdy, niż gdybyś miał tylko jednego podejrzanego.
„Dwóch podejrzanych nie będzie w stanie wymyślić jakiejś wiarygodnej i spójnej wersji, ponieważ po prostu nie znają swoich odpowiedzi” - powiedział Wright.
W 1988 roku grupa czterech informatyków udowodniła, że gdyby dwa komputery zostały poproszone o rozwiązanie tego samego problemu osobno, a następnie osobno zapytałyby o odpowiedzi, to można by przetestować jeszcze szerszą klasę problemów niż IPV. Ta klasa nazywa się IDMD - interaktywny dowód z wieloma dowodami.
Stosując to podejście, można na przykład testować problemy „trójkolorowe” w odniesieniu do sekwencji kształtów, które rosną znacznie szybciej niż kształty w niedeterministycznym czasie wielomianowym. W niedeterministycznym czasie wielomianu rozmiar kształtów rośnie liniowo - liczba punktów połączeń linii może wzrosnąć z 1 do 2, potem do 3, potem do 4 i tak dalej. W związku z tym nigdy nie będzie ogromnej dysproporcji między wielkością figury a czasem potrzebnym do przetestowania jej trójkolorowej. Ale jeśli mówimy o interaktywnym dowodzie z wieloma dowodami, to tutaj liczba punktów na rysunku rośnie wykładniczo.
W rezultacie cyfry te stają się zbyt duże i nie mieszczą się w pamięci komputera sprawdzającego, przez co nie może on sprawdzić ich trójkoloru, przeglądając listę punktów połączeń. Ale nadal można sprawdzić tricolor, zadając dwóm dowódcom oddzielne, ale powiązane pytania.
W klasie problemów IDMD egzaminator ma wystarczającą ilość pamięci, aby uruchomić program w celu określenia, czy dwa punkty w kształcie są połączone linią. Dowódca może następnie poprosić każdego z nich o nazwanie jednej z dwóch kropek połączonych linią, po czym może łatwo porównać odpowiedzi dowódców, aby upewnić się, że trójkolorowa figura jest poprawna.
Zwiększenie poziomu zadań trudnych do rozwiązania, ale łatwych do zweryfikowania, od NPV do IPV, a następnie do IDMD, można osiągnąć za pomocą klasycznych komputerów. Komputery kwantowe działają inaczej. Przez dziesięciolecia nie było jasne, jak zmieniają obraz, czyli czy trudniej czy łatwiej jest sprawdzić rozwiązanie z ich pomocą.
Nowa praca Natarajana i Wrighta dostarcza odpowiedzi na to pytanie.
Kwantowe oszustwo
Komputery kwantowe wykonują obliczenia, manipulując bitami kwantowymi (kubitami). Mają dziwną właściwość, której istotą jest to, że mogą się ze sobą pomylić. Kiedy dwa kubity, a nawet duże układy kubitów, zaplątują się ze sobą, oznacza to, że ich właściwości fizyczne odgrywają je w określony sposób.
W swojej nowej pracy Natarajan i Wright rozważają scenariusz z dwoma oddzielnymi komputerami kwantowymi, które mają wspólne splątane kubity.
Wydawałoby się, że tego rodzaju schemat działa przeciwko walidacji. Przekonalność interaktywnego dowodu z wieloma dowodami tłumaczy się właśnie tym, że można osobno przesłuchać dwóch dowódców, a następnie porównać ich odpowiedzi. Jeśli te odpowiedzi są zgodne, najprawdopodobniej są poprawne. Ale jeśli dwóch dowódców jest zdezorientowanych, to mają więcej okazji do konsekwentnego i konsekwentnego udzielania błędnych odpowiedzi.
Rzeczywiście, kiedy w 2003 roku po raz pierwszy zaproponowano scenariusz z dwoma splątanymi komputerami kwantowymi, naukowcy zasugerowali, że splątanie osłabi zdolności weryfikacyjne. „Wszyscy, łącznie ze mną, zareagowali bardzo wyraźnie: teraz testerzy będą mieli więcej siły i perswazji” - powiedział Vidik. „Mogą używać splątania do koordynowania swoich odpowiedzi”.
Pomimo tego początkowego pesymizmu, Vidic przez kilka lat próbował udowodnić, że jest inaczej. W 2012 roku wraz z Tsuyoshi Ito udowodnił, że nadal można przetestować wszystkie problemy w klasie IDMD przy pomocy splątanych komputerów kwantowych.
Teraz Natarajan i Wright udowodnili, że sytuacja jest jeszcze lepsza. Szerszą klasę problemów można przetestować ze splątaniem niż bez niego. Połączenia między splątanymi komputerami kwantowymi można wykorzystać na korzyść egzaminatora.
Aby zrozumieć, jak to zrobić, przypomnijmy sobie procedurę testowania trójkolorowych figur, których rozmiar zwiększa się wykładniczo, jeśli użyty zostanie dowód interaktywny z wieloma dowodami. Weryfikator nie ma wystarczającej ilości pamięci, aby zapisać całą figurę, ale wystarczy, aby zidentyfikować dwa powiązane punkty i zapytać weryfikatorów, jakiego są koloru.
Jeśli mówimy o problemach, które rozważają Natarajan i Wright - a należą one do klasy zwanej niedeterministycznym podwójnym czasem wykładniczym (NDEW) - to rozmiar postaci w nich rośnie jeszcze szybciej niż w przypadku klasy IDMD. Liczba w NDEV rośnie w „podwójnie wykładniczym” tempie. Oznacza to, że jest to podwójny postęp geometryczny. Liczba ta rośnie nie wraz z prędkością 21, 22, 23 stopnia, ale „w stopniach”. Z tego powodu kształty rosną tak szybko, że egzaminator nie może znaleźć jednej pary połączonych punktów.
„Potrzeba 2n bitów, aby oznaczyć punkt, który jest wykładniczo większy niż pamięć robocza weryfikatora” - mówi Natarajan.
Ale Natarajan i Wright twierdzą, że możliwe jest przetestowanie trójkolorowego zabarwienia podwójnie wykładniczej figury bez możliwości określenia punktów, o które należy zapytać dowódców. Chodzi o to, że sami dowodzący zadają pytania.
Zdaniem naukowców pomysł poproszenia komputerów o sprawdzenie własnych decyzji metodą sondażu jest tak samo rozsądny, jak pomysł poproszenia podejrzanych o popełnienie przestępstwa o przesłuchanie samych siebie. Oznacza to, że jest to kompletny nonsens. To prawda, Natarajan i Wright twierdzą, że tak nie jest. Powodem jest zamieszanie.
„Stan splątania to wspólny zasób” - mówi Wright. „Cały nasz protokół ma na celu zrozumienie, jak używać tego wspólnego zasobu do przygotowywania powiązanych pytań”.
Jeśli komputery kwantowe są zdezorientowane, ich wybór punktów zostanie wzajemnie połączony i zadadzą odpowiedni zestaw pytań do przetestowania trójkoloru.
Jednocześnie egzaminator nie potrzebuje zbyt ścisłego połączenia dwóch komputerów kwantowych, ponieważ ich odpowiedzi na te pytania będą spójne (jest to równoznaczne z tym, że dwóch podejrzanych zgadza się między sobą co do fałszywego alibi). Kolejna dziwna funkcja kwantowa rozwiązuje ten problem. W mechanice kwantowej zasada nieoznaczoności uniemożliwia nam jednoczesne poznanie położenia cząstki i pędu jej siły. Jeśli zmierzysz jeden, zniszcz informacje o drugim. Zasada nieoznaczoności poważnie ogranicza twoją wiedzę o dwóch „uzupełniających się” właściwościach układu kwantowego.
Natarajan i Wright wykorzystali to w swojej pracy. Aby obliczyć kolor wierzchołka, używają dwóch komputerów kwantowych, które uzupełniają się pomiarami. Każdy komputer oblicza kolor swoich punktów iw ten sposób niszczy wszystkie informacje o punktach drugiego komputera. Innymi słowy, splątanie umożliwia komputerom formułowanie powiązanych ze sobą pytań, ale zasada nieoznaczoności uniemożliwia im spiskowanie w odpowiadaniu na nie.
„Musimy sprawić, by przysłowia zapomniała [o fałszywej wersji wydarzeń] i to jest główna rzecz, którą [Natarajan i Wright] zrobili w swojej pracy” - powiedział Vidik. „Zmuszają dowódcę do usunięcia informacji podczas wykonywania pomiarów”.
Ich praca ma ogromne i bardzo ważne konsekwencje. Przed pojawieniem się tej pracy limit ilości wiedzy, którą mogliśmy mieć z całkowitą pewnością, był znacznie niższy. Gdybyśmy otrzymali odpowiedź na problem IDMD, musielibyśmy przyjąć ją na wiarę, ponieważ nie mamy innego wyjścia. Ale Natarajan i Wright usunęli to ograniczenie i umożliwili sprawdzenie odpowiedzi na wiele innych problemów obliczeniowych.
Ale teraz, kiedy to zrobili, nie jest jasne, gdzie jest granica walidacji.
„To mogłoby posunąć się znacznie dalej” - powiedział Lance Fortnow, informatyk z Georgia Institute of Technology. "Zostawiają miejsce na jeszcze jeden krok."
Kevin Hartnett