W przypadku problemu faktoryzacji liczb całkowitych algorytm Shora zapewnia znaczne przyspieszenie (wykładnicze?) W porównaniu z algorytmami klasycznymi. Czy istnieją podobne wyniki dotyczące bardziej podstawowych matematyki, takich jak ocena funkcji transcendentalnych?
Powiedzmy, że chcę obliczyć , lub . W klasycznym świecie mogę użyć rozszerzenia takiego jak seria Taylora lub jakiś algorytm iteracyjny. Czy istnieją algorytmy kwantowe, które mogą być szybsze niż to, co potrafi klasyczny komputer, czy to asymptotycznie lepsze, mniej iteracji z tą samą precyzją, czy też szybciej według zegara ściennego?
Istnieją już klasyczne algorytmy, które potrafią ocenić je z rozsądną (np. 80-bitową) precyzją w kilku cyklach zegara (i są one faktycznie zaimplementowane w procesorach); wydaje się mało prawdopodobne, aby QC działała znacznie szybciej niż to. Czy pytasz o bardzo wysoką precyzję (np. 1 milion bitów)?
—
ponczo
@poncho To ma sens, że podstawowe rzeczy takie jak ten zostały zoptymalizowane do niemal perfekcji, ale zastanawiam się, czy jest coś w tych funkcjach, co można wykorzystać, by być jeszcze szybszym na QC. Nawet jeśli efekt można zobaczyć tylko przy ekstremalnych wymaganiach dotyczących precyzji.
—
Norrius
@poncho „wydaje się mało prawdopodobne, aby QC działała znacznie szybciej niż to”. Ludzie myśleli, że mało prawdopodobne jest ulepszenie naiwnego algorytmu mnożenia, ale teraz mamy Karatsubę. Możesz się zastanawiać, czy nie chcielibyśmy mieć lepszego algorytmu (tak, np. Dla precyzji, jak powiedziałeś), ale tak naprawdę nie jest tak dziwne oczekiwać jakiejś poprawy.
—
Dyskretna jaszczurka