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.
- algorytm
- blockchain
- pomysłowość
- kryptografia
- szyfr
- Technologia przyszłości
- Sprzęt HPC
- ibm kwant
- Wewnątrz HPC
- aktualności
- Badania NTT
- plato
- Platon Ai
- Analiza danych Platona
- Gra Platona
- PlatoDane
- platogaming
- Kwant
- przewaga kwantowa
- komputery kwantowe
- informatyka kwantowa
- fizyka kwantowa
- wyższość kwantowa
- Artykuły z cotygodniowych biuletynów
- zefirnet