Czy istnieje algorytm kwantowy NC do obliczania GCD?

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 .$\mathsf{NC}$$\mathsf{P}$$\mathsf{P}$$\mathsf{NP}$

Czy istnieje coś takiego jak „quantum algorytm” dla GCD jak jest kwantowa wielomian czas ( B Q P algorytm) dla Integer na czynniki?$\mathsf{NC}$$\mathsf{BQP}$

Powiązane pytanie: złożoność największego wspólnego dzielnika (gcd)

Przede wszystkim istnieje formalna definicja „kwantowego NC”, patrz QNC w zoo.

GCD jest rzeczywiście dobrym kandydatem do rozwiązania problemu, który może występować w QNC, ale nie jest znany w NC. Jednak znalezienie algorytmu QNC dla GCD jest nadal otwartym problemem.

Poczucie, w którym uważa się to za prawdę, wynika z faktu, że kwantową transformatę Fouriera można wykonać w QNC.

Odniesienie: Część końcowa „R. Cleve i J. Watrous, Szybkie równoległe obwody dla kwantowej transformaty Fouriera”, arXiv: quant-ph / 0006004