Czy powszechne użycie „ignorowania stałych” w informatyce jest przydatne przy porównywaniu obliczeń klasycznych z obliczeniami kwantowymi?

Daniel Sank wspomniał w komentarzu , odpowiadając na (moją) opinię, że stałe przyspieszenie w przypadku problemu z dopuszczeniem algorytmu wielomianowego czasu jest skąpe, że$10^8$

Teoria złożoności ma zbyt dużą obsesję na punkcie nieskończonych granic skalowania wielkości. W rzeczywistości liczy się to, jak szybko uzyskasz odpowiedź na swój problem.

W informatyce powszechne jest ignorowanie stałych w algorytmach i ogólnie okazało się, że działa to całkiem dobrze. (Mam na myśli, że istnieją dobre i praktyczne algorytmy. Mam nadzieję, że udzielisz mi (teoretycznych) algorytmów, które badacze mieli w tym dość dużą rękę!)

Rozumiem jednak, że jest to nieco inna sytuacja niż obecnie:

1. Nie porównuje dwóch algorytmów działających na tym samym komputerze, ale dwa (nieco) różne algorytmy na dwóch bardzo różnych komputerach.
2. Pracujemy teraz z komputerami kwantowymi , dla których być może tradycyjne pomiary wydajności mogą być niewystarczające.

W szczególności metody analizy algorytmów są jedynie metodami . Myślę, że radykalnie nowe metody obliczeniowe wymagają krytycznego przeglądu naszych obecnych metod oceny wydajności!

Moje pytanie brzmi:

Porównując wydajność algorytmów na komputerze kwantowym z algorytmami na komputerze klasycznym, czy praktyka „ignorowania” stałych jest dobrą praktyką?

Powszechne użycie „ignorowania stałych” w informatyce jest użyteczne tylko wtedy, gdy różnice w wydajności różnych rodzajów architektury sprzętowej lub oprogramowania można zignorować przy odrobinie masowania. Ale nawet w klasycznych obliczeniach ważne jest, aby zdawać sobie sprawę z wpływu architektury (zachowanie w pamięci podręcznej, użycie dysku twardego), jeśli chcesz rozwiązać trudne problemy lub duże problemy.

Praktyka ignorowania stałych nie jest praktyką motywowaną (w sensie ciągłego potwierdzania) z punktu widzenia implementacji. Wynika to głównie z zainteresowania podejściem do badania algorytmów, który jest dobrze ułożony w składzie i przyjmuje proste charakterystyki, w sposób zbliżony do czystej matematyki. Twierdzenia o przyspieszeniu dla maszyn Turinga oznaczały, że żadna rozsądna definicja nie mogła próbować precyzyjnie określić złożoności problemów, aby dojść do sensownej teorii; a poza tym, w walce o znalezienie dobrych algorytmów dla trudnych problemów, stałe czynniki nie były interesującą matematycznie częścią ...

To bardziej abstrakcyjne podejście do badania algorytmów było i jest w dużej mierze owocne. Ale teraz mamy do czynienia z sytuacją, w której mamy dwa modele obliczeń, gdzie

• Jeden jest w zaawansowanym stanie dojrzałości technologicznej (klasyczne obliczenia); i
• Jeden jest w bardzo niedojrzałym stanie, ale próbuje zrealizować model teoretyczny, który może prowadzić do znacznych asymptotycznych ulepszeń (obliczeń kwantowych).

W takim przypadku możemy zapytać, czy rozważenie korzyści asymptotycznej ma sens, z dokładnym rozliczeniem stałych czynników. Ze względu na dodatkowy wysiłek, który może być wymagany do wykonania skalowalnego obliczenia kwantowego, nie tylko czynniki skalarne, ale również wielomianowe „przyspieszenia” wydajności teoretycznej mogą zostać zmyte po uwzględnieniu całego obciążenia związanego z realizacją algorytmu kwantowego.

We wczesnych dniach mogą występować znaczące różnice w wydajności różnych podejść do architektury kwantowej. Może to sprawić, że wybór architektury będzie równie ważny (jeśli nie ważniejszy) dla tego, jak dobrze działa algorytm niż analiza asymptotyczna - tak samo jak dla ciebie ważne będzie, czy wykonasz konwencjonalne obliczenia na maszynie von Neumanna, czy w wysoce rozproszonej sieci ze znacznymi opóźnieniami.

W rzeczywistości istotną rzeczą dla praktycznych obliczeń jest - i zawsze było - nie tylko algorytmy, ale implementacje algorytmów : algorytm zrealizowany w określony sposób, na określonej architekturze. Powszechna praktyka analizy asymptotycznej, która ignoruje stałe czynniki, pozwala nam zwracać uwagę na systematyczne, matematyczne przyczyny różnic w działaniu algorytmów i jest praktycznie motywowana w tych przypadkach, gdy różnice architektoniczne nie są tak duże, aby zdominować praktyczne działanie .

W odniesieniu do technologii kwantowych nie znajdujemy się w tak szczęśliwej sytuacji, w której możemy bezpiecznie przeglądać stałe czynniki w dowolnym praktycznym kontekście. Ale może kiedyś będziemy w stanie to zrobić. Jest to długa gra kwantowych technologii informacyjnych - do tej pory prawie jedyna gra, w którą kiedykolwiek grali informatycy akademiccy, jeśli chodzi o technologię informacji kwantowej. Przewidując dzień, w którym technologia kwantowa znajdzie swoje miejsce, dobrze będzie, abyśmy kontynuowali analizę asymptotyczną jako jedną z linii badań w zakresie wydajności algorytmów kwantowych.

$O\left(f\left[N\right]\right)$$N$

$10^{10}$

$\approx300$

Nie można zignorować stałych czynników przy porównywaniu obliczeń kwantowych z obliczeniami klasycznymi. Są za duże.

Na przykład oto zdjęcie z niektórych slajdów, które przedstawiłem w zeszłym roku:

Na dole są fabryki stanów magicznych. Mają ślad 150 kubitów fizycznych. Ponieważ bramka AND używa 150 tysięcy kubitów przez 0,6 milisekundy, przypuszczamy, że objętość czasoprzestrzenna kwantowej bramki AND jest rzędu 90 kubitów sekund.

Jednym z celów moich współpracowników jest użycie 1 procesora na 100 kubitów podczas korekcji błędów. Można więc powiedzieć, że 90 sekund kubitowych wymaga 0,9 sekundy procesora. Uczyniliśmy konstrukcje kwantowe kilka razy bardziej wydajne od czasu wykonania powyższego obrazu, więc nazwijmy to 0,1 cpu sekundy.

(Istnieje wiele założeń, które uwzględniają te szacunki. Jaki rodzaj architektury, poziomy błędów itp. Próbuję jedynie przekazać ideę rzędu wielkości).

Wykonanie dodawania 64-bitowego zajmuje 63 bramki. 63 * 0,1 cpu sekund ~ = 6 cpu sekund. Pod względem ilościowym 64-bitowe dodanie kosztuje więcej niż sekundę procesora. Zazwyczaj dodanie 64-bitowe kosztuje mniej niż nanosekunda procesora. Łatwo jest tutaj uzyskać stałą różnicę współczynników wynoszącą 10 miliardów. W porównaniu z równoległą klasyczną maszyną, taką jak GPU, liczby stają się jeszcze gorsze. Przy tak wielu cyfrach nie można ignorować stałych czynników.

Rozważmy na przykład algorytm Grovera, który pozwala nam szukać satysfakcjonujących danych wejściowych dla funkcji w ocenach sqrt (N) funkcji zamiast N ocen. Dodaj stały współczynnik 10 miliardów i rozwiąż problem, gdy komputer kwantowy zaczyna wymagać mniejszej liczby ocen:

Algorytm Grovera nie może zrównoleglać ocen, a oceny wymagają co najmniej jednej bramki AND, więc w zasadzie zaczniesz dostrzegać korzyści z czasu procesora, gdy wyszukiwanie zajmuje dziesiątki milionów lat.

O ile nie poprawimy stałych czynników o wiele lepiej, nikt nigdy nie będzie używał wyszukiwania Grovera do niczego przydatnego. W tej chwili sytuacja kwantowa kontra klasyczna jest wykładniczą przewagą lub popiersiem.

Podczas gdy inne odpowiedzi dostarczają dobrych argumentów, wydaje mi się, że nadal trochę się nie zgadzam. Podzielę się zatem własnymi przemyśleniami na ten temat.

Krótko mówiąc, myślę, że ciągłe „takie, jakie są” są w najlepszym razie zmarnowaną szansą. Być może jest to najlepsze, co możemy obecnie uzyskać, ale jest dalekie od ideału.

Ale najpierw myślę, że krótka wycieczka nie jest konieczna.

Kiedy mamy skuteczny algorytm?

$10^6$

1. $P$
2. $P^2$$P$
3. $P^2$

$P^2$$P$$P$$P^2$

Dlatego nie jest nieuzasadnione, że nasz algorytm śmieci może przypadkowo wydawać się mieć „cudowne” przyspieszenia. Oczywiście istnieje wiele technik projektowania eksperymentów, które mogą zmniejszyć ryzyko, ale być może bardziej sprytne „szybkie” algorytmy, które wciąż zawodzą w wielu, ale zbyt mało przykładów może nas oszukać! (zauważ również, że zakładam, że żaden badacz nie jest złośliwy , co jeszcze gorzej!)

Chciałbym teraz odpowiedzieć: „Obudź mnie, gdy będzie lepszy wskaźnik wydajności”.

Jak więc możemy zrobić lepiej?

Jeśli możemy sobie pozwolić na przetestowanie naszego algorytmu „czarnej skrzynki” we wszystkich przypadkach, nie możemy dać się zwieść powyższemu. Jest to jednak niemożliwe w praktycznych sytuacjach. ( Można to zrobić w modelach teoretycznych!)

Co nam może zamiast zrobić jest stworzenie statystycznego hipotezę jakiegoś sparametryzowanego czasu pracy (zwykle dla wielkości wejściowej) w celu zbadania tego, może dostosować naszą hipotezę i test ponownie, dopóki nie otrzymamy hipotezę lubimy i odrzucenia null wydaje się rozsądne. (Zauważ, że prawdopodobnie biorę pod uwagę inne czynniki, które ignoruję. Jestem praktycznie matematykiem. Projektowanie eksperymentów nie wchodzi w zakres mojej wiedzy)

$O(n^3)$

Co więc zrobić ze stałymi?

$10^9$

Myślę, że najbardziej użyteczne jest uznanie dziwnej stałej za anomalię , tzn. Jest to twierdzenie, które samo w sobie wymaga dalszych badań. Myślę, że tworzenie hipotez opartych na bardziej ogólnych modelach niż po prostu „nasz algorytm zajmuje X czasu” jest dobrym narzędziem do tego. Tak więc, chociaż nie sądzę, że możemy po prostu przejąć konwencje CS tutaj, całkowite pominięcie „pogardy” dla stałych jest również złym pomysłem.