Quantum Information Processing, vol. 5, no. 1, pp. 1-4, 2006.

Zusammenfassung:

Wie Peter Shor gezeigt hat, können die Probleme des Faktorisierens ganzer Zahlen und des diskreten Logarithmus in der Einheitengruppe eines endlichen Körpers in polynomialer Zeit auf einem Quantenrechner gelöst werden. Beide Probleme sind von kryptographischer Relevanz und es sind keine effizienten klassischen Algorithmen zu ihrer Lösung bekannt; die besten Verfahren haben subexponentielle Laufzeit. Diese Quantenalgorithmen von Shor verwenden Reduktionen der ursprünglichen Probleme auf die Bestimmung der Periodenlänge von Funktionen, also auf Probleme, die mit Methoden der Fourieranalyse angegangen werden können.

Ein wesentlicher Punkt ist hierbei die Tatsache, daß die diskrete Fouriertransformation der Länge N auf einem Quantenrechner in O(log^2 N) elementaren Operationen ausgeführt werden kann, was im Vergleich zu klassischen Verfahren zur schnellen Fouriertransformation, die Realisierungen in O(N log N) Operationen liefern, eine exponentielle Beschleunigung bedeutet. In der Arbeit werden Möglichkeiten vorgestellt, wie eine weitere Beschleunigung der Berechnung einer diskreten Fouriertransformation auf einem Quantenrechner erzielt werden kann. Diese ergeben sich, wenn man nicht an exakten, sondern nur an approximativen Realisierungen interessiert ist.

Die Zielsetzung, weitere Klassen von Signaltransformationen auf einem Quantenrechner effizient zu realisieren, wurde erfolgreich bearbeitet; ein Ergebnis der Arbeit sind effiziente Quantenschaltkreise zur Realisierung einer Reihe von Transformationen. Die verwendeten Verfahren beruhen auf der allgemeinen Zerlegungstheorie linearer Systeme mit Symmetrie in modulare Subsysteme. Hierbei wird die inhärente Symmetrie der Transformationen mit Methoden der Gruppentheorie modelliert und ausgenutzt. Die resultierenden Quantenschaltkreise sind aus elementaren Gattern aufgebaut, die einer universellen Familie unitärer Schaltfunktionen angehören.

Die bereits erwähnten Quantenalgorithmen sind spezielle Instanzen eines allgemeineren Konzeptes: Es handelt sich in beiden Fällen um das Problem, in einer gegebenen algebraischen Struktur eine Unterstruktur zu bestimmen, die implizit durch eine leicht zu berechnende Funktion gegeben ist. Es sind Instanzen dieses sogenannten Problems der verborgenen Untergruppen bekannt, die mit einem polynomialen Quantenalgorithmus gelöst werden können, während sie auf einem klassischen probabilistischen Rechner nur in exponentieller Zeit lösbar sind. Ein Ergebnis der Arbeit ist, daß für gewisse Klassen nichtabelscher Gruppen das Problem der verborgenen Untergruppen ebenfalls effizient gelöst werden kann.

While the first chapter mainly deals with finite groups (by the way: always in the non-modular case) the further objects of interest are invariant rings under compact groups acting in various ways. In the case of the direct sum of the standard representation of SU(2) a closed form of the Molien series is found. Starting from a combinatorial interpretation of the coefficients of this closed form a correspondence between secondary invariants and binary trees is given.

Finally the theory of invariants under local unitary tranformations is applied to the very new topic of quantum error correcting codes. As in the case of classical codes an Mac-Williams duality between weight-enumerator polynomials exists [2] which can be interpreted by means of invariant theory.

[1] B. Sturmfels, Algorithms in Invariant Theory, Springer, 1993.
[2] P. Shor, R. Laflamme, Phys. Rev. Letters, vol. 78, no. 8, 1997.