Gibt es einen Quanten-NC-Algorithmus zur Berechnung der GCD?

14

Aus den Kommentaren zu einer meiner Fragen zu MathOverflow habe ich das Gefühl, dass die Frage, ob GCD in vs. P ist, mit der Frage verwandt ist, ob Integer Factorization in P vs. N P ist .NCPPNP

Gibt es so etwas wie einen "Quantum " -Algorithmus für GCD, da es einen Quantenpolynomzeit- Algorithmus ( B Q P ) für die Ganzzahlfaktorisierung gibt?NCBQ.P

Verwandte Frage: Komplexität des größten gemeinsamen Divisors (gcd)

cc.complexity-theory quantum-computing dc.parallel-comp nt.number-theory comp-number-theory T ....
quelle
5
Wenn Sie einen Cross-Post schreiben, ist es besser, die Frage erneut zu schreiben.
Alessandro Cosentino

Antworten:

14

Zunächst gibt es eine formale Definition von "Quanten-NC", siehe QNC im Zoo.

GCD ist in der Tat ein guter Kandidat für ein Problem, von dem gezeigt werden könnte, dass es in QNC vorliegt, aber es ist nicht bekannt, dass es in NC vorliegt. Es ist jedoch immer noch ein offenes Problem, einen QNC-Algorithmus für GCD zu finden.

Das Gefühl, für das dies angenommen wird, beruht auf der Tatsache, dass die Quanten-Fourier-Transformation in QNC durchgeführt werden kann.

Literatur: Fazit von "R. Cleve und J. Watrous, Schnelle Parallelschaltungen für die Quanten-Fourier-Transformation", arXiv: quant-ph / 0006004

Alessandro Cosentino
quelle
6
Es wäre schön, wenn Sie die Beziehung zwischen der Quanten-Fourier-Transformation und der GCD erklären könnten.
Kaveh
Ich stimme Kaveh zu. Es wäre schön, die Beziehung zur Verfügung zu stellen.
T ....
2
Ich glaube nicht, dass es eine direkte Beziehung gibt. Was ich damit sagen wollte ist, dass wir vermuten, dass QNC leistungsfähiger ist als NC, weil wir QFT in QNC ausführen können. Wir fragen also, ob es noch ein weiteres natürliches Problem in QNC gibt, und eines der einfachsten natürlichen Probleme, die wir in NC nicht kennen, ist GCD. Irgendwann hatte ich vermutet, dass es eine Beziehung zwischen den beiden Problemen gibt, die darauf zurückzuführen ist, dass QFT und GCD beide als Unterroutinen im Periodenfindungsalgorithmus verwendet werden, aber ich konnte dies nicht formalisieren. Vielleicht können uns andere Benutzer mehr aufklären.
Alessandro Cosentino
Hallo Alessandro: Weißt du, ob Polynom GCD in NC ist?
T ...
1
@Arul: Ja, das ist es. Siehe von zur Gathen, Parallele Algorithmen für algebraische Probleme. dx.doi.org/10.1145/800061.808728
Alessandro Cosentino