Naukowcy z NTT twierdzą, że mają nowy sposób na sprawdzenie przewagi kwantowej

Sunnyvale, Kalifornia – 26 października 2022 – NTT Research ogłosiło, że naukowiec z jej Laboratorium Kryptografii i Bezpieczeństwa Informacji (CIS) i kolega z Laboratoria Informatyki Społecznej NTT (SIL) napisali przełomowy artykuł na temat przewagi kwantowej. Artykuł został wybrany do zaprezentowania na dorocznym sympozjum IEEE na temat podstaw informatyki (FOCS), które odbędzie się w dniach 31 października – listopada. 3 w Denver.

Współautorzy artykułu pt. „Weryfikowalna przewaga kwantowa bez struktury”, to dr Takashi Yamakawa, wybitny badacz w NTT SIL i dr Mark Zhandry, starszy naukowiec w Badania NTT Laboratorium CIS. Praca została wykonana częściowo na Uniwersytecie Princeton, gdzie dr Yamakawa był wizytującym naukowcem, a dr Zhandry służy również jako adiunkt informatyki. 

Temat przewagi kwantowej (lub przyspieszenia kwantowego) dotyczy rodzajów problemów, które komputery kwantowe mogą rozwiązywać szybciej niż komputery klasyczne lub niekwantowe oraz o ile są szybsze. Omawiane problemy są powszechnie określane jako niedeterministyczna klasa wielomianowa (NP). Ile korzyści może się różnić w ogromnym stopniu. Komputer kwantowy może być w stanie rozwiązać konkretny problem w ciągu minuty lub sekundy, co zajmuje klasycznemu komputerowi tydzień, a może nawet niewyobrażalnie wykładniczą ilość czasu. W niniejszym artykule autorzy podejmują wyzwanie weryfikacji tej wyższości i robienia tego skutecznie. Do tej pory demonstracje przewagi kwantowej obejmowały znaczącą „strukturę” lub komunikację w obie strony między dwiema lub większą liczbą stron. Przełomem artykułu Yamakawy i Zhandry'ego jest zademonstrowanie trudnego problemu NP, w którym możliwa jest weryfikacja bez struktury.

„Po raz pierwszy zaobserwowaliśmy wykładnicze przyspieszenie kwantowe dla problemu wyszukiwania NP, który wymaga jedynie losowej wyroczni”, powiedział University of Texas z Austin, profesor informatyki w Austin, dr Scott Aaronson, który skomentował wczesną wersję referatu podczas warsztatów 13 czerwca 2022 r. w Simons Institute for the Theory of Computing. Wymagając jedynie losowej wyroczni, tj. teoretycznej czarnej skrzynki, która generuje losowe odpowiedzi na każde zapytanie, Yamakawa i Zhandry zbudowali swój problem na nieustrukturyzowanych założeniach obliczeniowych. W związku z tym ich problem jest ściślej związany z funkcjami jednokierunkowymi zamiast ustrukturyzowanymi, takimi jak te występujące w kryptografii klucza publicznego. To jednokierunkowe wyrównanie ułatwia skuteczną weryfikację.

„To ekscytujące widzieć, jak kryptografowie zrzeszeni w NTT współpracują nad badaniami, które po raz kolejny zasługują na miano „przełomu”, zwłaszcza w artykule, który wzbogaca naszą wiedzę o obliczeniach kwantowych, kolejnym obszarze, na którym skupiamy się w NTT Research” – powiedział Kazuhiro Gomi , prezes i dyrektor generalny NTT Research. „Gratulacje i najlepsze życzenia dla wszystkich uczestników tej prestiżowej konferencji IEEE.” 

Problem wyszukiwania NP, który opracowali Yamakawa i Zhandry, był problemem „dwa w jednym”, który polegał na znalezieniu 1) ciągu n-symbolowego, który jest słowem kodowym danego kodu korekcji błędów, oraz 2) ciągu n-symbolowego, w którym każdy symbol jest przyporządkowany do zera pod losową wyrocznią. Każdy problem z osobna jest łatwy. Ale znalezienie pojedynczego ciągu symboli, który jest zarówno słowem kodowym, jak i odwzorowuje zero, jest znacznie trudniejsze, przynajmniej klasycznie. „Jeśli jesteś kwantem, możesz to rozwiązać w czasie wielomianowym”, powiedział dr Zhandry, „ale jeśli jesteś klasykiem, przynajmniej jeśli jesteś w tym modelu czarnoskrzynkowym, potrzebujesz czasu wykładniczego”. Z drugiej strony, mając dane potencjalne rozwiązanie, łatwo je zweryfikować, sprawdzając, czy oddzielnie rozwiązuje każdy z dwóch problemów. Zauważ, że jak przystało na artykuł dla FOCS, ta praca jest podstawowa lub fundamentalna. Jak wskazano w przemówieniu dr Aaronsona w Simons Institute (omówionym w niniejszym badaniu NTT Research artykuł na blogu), argument Yamakawy-Zhandry należy do klasy przyspieszeń, które można łatwo sprawdzić matematycznie, ale nie można ich w najbliższym czasie zademonstrować w praktyce za pomocą rzeczywistego komputera kwantowego. Jednak poza przełomowym schematem weryfikacji, artykuł wskazuje również na coś nowego w zakresie przyspieszenia kwantowego.

„Przed naszą pracą mieliśmy przykłady przewagi kwantowej w przypadku problemów NP, takich jak faktoryzacja lub, w warunkach czarnej skrzynki, znajdowanie okresów. Okazuje się jednak, że algorytm kwantowy leżący u podstaw wszystkich tych przykładów polegał w zasadzie na odnajdywaniu okresu – chociaż pokazanie, jak zastosować wyszukiwanie okresu do tych przykładów, często nie było trywialne” – powiedział dr Zhandry. „Z naszego artykułu wynika, że ​​istnieje co najmniej drugi przypadek. Można to optymistycznie zinterpretować jako stwierdzenie, że istnieje nadzieja, że ​​przewaga kwantowa jest bardziej rozpowszechniona, niż być może wcześniej sądziliśmy”.

Sponsorowana przez Komitet Techniczny IEEE Computer Society ds. Matematycznych Podstaw Informatyki (TCMF), FOCS jest wiodącą konferencją w dziedzinie informatyki teoretycznej. W zaproszeniu do składania referatów na FOCS 2022, 63. takie doroczne zgromadzenie, obliczenia kwantowe wymieniono jako jeden z 17 ogólnych obszarów zainteresowania. Artykuł Yamakawy-Zhandry ma zostać zaprezentowany 31 października 2022 r. o godz. 10:15 MT. Aby dowiedzieć się więcej i zarejestrować się na to wydarzenie, odwiedź FOCS 2022 stronie internetowej.