Z uwagi na jedno z moich pytań dotyczących MathOverflow mam wrażenie, że kwestia dotycząca GCD będąc w vs. P jest zbliżona do kwestii dotyczącej Integer faktoryzacji Będąc w P vs. N P .
Czy istnieje coś takiego jak „quantum algorytm” dla GCD jak jest kwantowa wielomian czas ( B Q P algorytm) dla Integer na czynniki?
Powiązane pytanie: złożoność największego wspólnego dzielnika (gcd)