Efektywne pamięciowo kodowanie problemów kombinatorycznych do kwantowych obliczeń wariacyjnych

Obliczenia kwantowe są nowym paradygmatem przetwarzania informacji, który umożliwia rozwiązywanie szczególnych problemów szybciej niż konwencjonalne (klasyczne) komputery. Najpowszechniej znanym przykładem jest algorytm Shora, który rozwiązuje problem faktoryzacji liczb w czasie wielomianowym. Najlepszy znany algorytm klasyczny wymaga eksponencjalnie dużo zasobów z długością liczby. Jednakże, choć algorytm Shora wymaga jedynie wielomianowo wiele kubitów i kwantowych bramek, te wymagania ciągle wykraczają poza możliwości obecnych komputerów kwantowych. Są dwie główne przyczyny. Po pierwsze, obliczenia na kwantowym komputerach nie są wykonywane idealnie. Po drugie, obecne komputery operują na małej liczbie kubitów. Uważa się, że następne komputery kwantowe w~najbliższej przyszłości również będą ograniczone przez te dwa czynniki. Tego typu urządzenia określa się mianem zaszumionych, średnich rozmiarów kwantowych komputerów (ang. Noisy Intermediate-Scale Quantum (NISQ) computers). Aby ominąć te ograniczenia obecnych technologii, badacze wkładają znaczny wysiłek do formułowania problemów obliczeniowych w formie odpowiedniej dla obecnych urządzeń kwantowych.

Główą klasą algorytmów dostępną dla dzisiejszych komputerów są kwantowe obliczenia wariacyjne (ang. variational quantum computing). W tym modelu wpierw kodujemy klasyczny problem w kwantowym Hamiltonianie, a następnie optymalizowanie kwantowego stany używając klasycznych technik optymalizacyjnych aby znaleźć optimum oryginalnego problemu. Panuje przekonanie, że metody okażą się skuteczne do znajdowania stanu fizycznego o najniższej energii dla chemicznych systemów, co ma swoje zastosowanie z punktu widzenia chemii i materiałoznawstwa. Choć metody są skuteczne dla typowo kwantowych problemów, nie jest oczywiste czy znajdą one zastosowanie dla problemów pojawiających się w klasycznej informatyce.

Przyczyna jest podobna jak w przypadku algorytmu Shora. Choć kwantowy rachunek wariacyjny ma o wiele mniejsze wymagania odnośnie kwantowych zasobów, ciągle jedynie małe instancje problemów mogą być rozważane. Rozważmy problem komiwojażera, który dotyczy znajdowania optymalnej, z reguły najkrótszej ścieżki przechodzącej przez wszystkie miasta. Obecne algorytmy klasyczne potrafią znaleźć takie rozwiązanie nawet dla tysięcy miast. Niestety, najlepsze obecnie algorytmy bazujące na kwantowym rachunku wariacyjnym mogą rozważać instancje dla co najwyżej 8 miast dla obecnie największego 53-kubitowego komputera kwantowego. Instancje takich rozmiarów mogą być znajdowane klasycznie poprzez sprawdzenie każdej możliwości i wybranie najlepszej z nich.

Uważamy, że przyczyną jest marnotrawstwo zasobów kwantowych. Dlatego w ramach projektu skupimy się na projektowaniu efektywniejszych reprezentacji problemów, które umożliwią kwantowym komputerom rozpatrywanie znacznie większych instancji. Dzięki temu, zrobimy kolejny krok w stronę pokazania przewagi obliczeń kwantowych (ang. quantum computational advantage).

Numer projektu: 

2020/37/N/ST6/02220

Termin: 

od 03/02/2021 do 02/02/2024

Typ projektu: 

Projekt własny badawczy

Kierownik projektu: 

Wykonawcy projektu: 

Publikacje: 

Historia zmian

Data aktualizacji: 20/02/2024 - 18:27; autor zmian: Adam Glos (aglos@iitis.pl)

Obliczenia kwantowe są nowym paradygmatem przetwarzania informacji, który umożliwia rozwiązywanie szczególnych problemów szybciej niż konwencjonalne (klasyczne) komputery. Najpowszechniej znanym przykładem jest algorytm Shora, który rozwiązuje problem faktoryzacji liczb w czasie wielomianowym. Najlepszy znany algorytm klasyczny wymaga eksponencjalnie dużo zasobów z długością liczby. Jednakże, choć algorytm Shora wymaga jedynie wielomianowo wiele kubitów i kwantowych bramek, te wymagania ciągle wykraczają poza możliwości obecnych komputerów kwantowych. Są dwie główne przyczyny. Po pierwsze, obliczenia na kwantowym komputerach nie są wykonywane idealnie. Po drugie, obecne komputery operują na małej liczbie kubitów. Uważa się, że następne komputery kwantowe w~najbliższej przyszłości również będą ograniczone przez te dwa czynniki. Tego typu urządzenia określa się mianem zaszumionych, średnich rozmiarów kwantowych komputerów (ang. Noisy Intermediate-Scale Quantum (NISQ) computers). Aby ominąć te ograniczenia obecnych technologii, badacze wkładają znaczny wysiłek do formułowania problemów obliczeniowych w formie odpowiedniej dla obecnych urządzeń kwantowych.

Główą klasą algorytmów dostępną dla dzisiejszych komputerów są kwantowe obliczenia wariacyjne (ang. variational quantum computing). W tym modelu wpierw kodujemy klasyczny problem w kwantowym Hamiltonianie, a następnie optymalizowanie kwantowego stany używając klasycznych technik optymalizacyjnych aby znaleźć optimum oryginalnego problemu. Panuje przekonanie, że metody okażą się skuteczne do znajdowania stanu fizycznego o najniższej energii dla chemicznych systemów, co ma swoje zastosowanie z punktu widzenia chemii i materiałoznawstwa. Choć metody są skuteczne dla typowo kwantowych problemów, nie jest oczywiste czy znajdą one zastosowanie dla problemów pojawiających się w klasycznej informatyce.

Przyczyna jest podobna jak w przypadku algorytmu Shora. Choć kwantowy rachunek wariacyjny ma o wiele mniejsze wymagania odnośnie kwantowych zasobów, ciągle jedynie małe instancje problemów mogą być rozważane. Rozważmy problem komiwojażera, który dotyczy znajdowania optymalnej, z reguły najkrótszej ścieżki przechodzącej przez wszystkie miasta. Obecne algorytmy klasyczne potrafią znaleźć takie rozwiązanie nawet dla tysięcy miast. Niestety, najlepsze obecnie algorytmy bazujące na kwantowym rachunku wariacyjnym mogą rozważać instancje dla co najwyżej 8 miast dla obecnie największego 53-kubitowego komputera kwantowego. Instancje takich rozmiarów mogą być znajdowane klasycznie poprzez sprawdzenie każdej możliwości i wybranie najlepszej z nich.

Uważamy, że przyczyną jest marnotrawstwo zasobów kwantowych. Dlatego w ramach projektu skupimy się na projektowaniu efektywniejszych reprezentacji problemów, które umożliwią kwantowym komputerom rozpatrywanie znacznie większych instancji. Dzięki temu, zrobimy kolejny krok w stronę pokazania przewagi obliczeń kwantowych (ang. quantum computational advantage).