Czy istnieje algorytm kwantowy NC do obliczania GCD?


14

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 .NCPPNP

Czy istnieje coś takiego jak „quantum algorytm” dla GCD jak jest kwantowa wielomian czas ( B Q P algorytm) dla Integer na czynniki?NCBQP

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


5
kiedy przesyłasz post, lepiej ponownie napisać pytanie.
Alessandro Cosentino,

Odpowiedzi:


14

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


6
Byłoby miło, gdybyś mógł wyjaśnić związek między kwantową transformacją Fouriera i GCD.
Kaveh

Zgadzam się z Kavehem. Byłoby miło podać relację.
T ....

2
Nie sądzę, żeby istniał bezpośredni związek. Chciałem powiedzieć, że podejrzewamy, że QNC ma większą moc niż NC, ponieważ możemy wykonywać QFT w QNC. Pytamy więc, czy jest jakiś bardziej naturalny problem, który występuje również w QNC, a jednym z najprostszych naturalnych problemów, których nie wiemy, jak zrobić w NC, jest GCD. W pewnym momencie podejrzewałem, że istnieje związek między tymi dwoma problemami wynikającymi z faktu, że QFT i GCD są używane jako podprogramy w algorytmie ustalania okresu, ale nie byłem w stanie uczynić tego formalnym. Może inni użytkownicy mogą nas bardziej oświecić.
Alessandro Cosentino

Cześć Alessandro: Czy wiesz, czy wielomian GCD jest w NC?
T ....

1
@Arul: tak, jest. Patrz von zur Gathen, Algorytmy równoległe dla problemów algebraicznych. dx.doi.org/10.1145/800061.808728
Alessandro Cosentino
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.