Kürzeste Folge von universellen Quantentoren, die einer gegebenen Einheit entsprechen

Frage: Können wir bei einer einheitlichen Matrix, die auf Qubits einwirkt , die kürzeste Folge von Clifford + T-Gattern finden, die dieser einheitlichen Matrix entsprechen?$n$

Zum Hintergrund der Frage zwei wichtige Referenzen:

1. Schnelle und effiziente exakte Synthese von Einzel-Qubit- Einheiten, die von Clifford- und T-Gates von Kliuchnikov, Maslov und Mosca erzeugt wurden
2. Genaue Synthese von Multiqubit-Clifford + T-Schaltkreisen von Giles und Selinger.

Eine optimale Zersetzung ist definitiv ein offenes Problem. (Und natürlich ist die Zerlegung unlösbar, Gates für große .) Eine "einfachere" Frage, die Sie zuerst stellen könnten, ist, was die kürzeste Folge von cnots und einzelnen Qubit-Rotationen um einen beliebigen Winkel ist (was IBM , Rigetti und bald auch Google bieten derzeit an, dass diese universelle Basis von Toren in Form Ihrer Basis von Cliffords und T-Gates ausgedrückt werden kann. Diese "einfachere" Frage ist ebenfalls offen und hat eine nicht eindeutige Antwort. Eine verwandte Frage ist, was eine exakte optimale Zerlegung von Toren von einer universellen Basis ist, um vom Grundzustand in einen gegebenen Endzustand zu gelangen.$\exp(n)$$n$

Ich gehe davon aus, dass Sie sich auf genaue Zerlegungen beziehen. Wenn Sie eine ungefähre Zerlegung wünschen, gibt es dafür verschiedene Methoden, z. B. die Trotter-Suzuki-Zerlegung oder die Annäherung an eine genaue Zerlegung.

Der "Quanten-csd-Compiler" in Qubiter führt eine nicht optimierte Zerlegung von n-Qubit-Einheiten in cnots und einzelne Qubit-Rots unter Verwendung der berühmten csd-Subroutine (Cosine-Sine Decomposition) von LAPACK durch. Einige unternehmungslustige Personen könnten versuchen, Optimierungen für den Quantencompiler von Qubiter zu finden. Sie können zum Beispiel den Compiler von Qubiter verwenden (ich habe einen Artikel darüber geschrieben), um Ihren klassischen Computer die Quanten-Fourier-Transformations-Zerlegung von Coppersmith neu entdecken zu lassen!

Qubiter ist Open Source und bei github erhältlich (vollständige Offenlegung - ich habe es geschrieben).

Angenommen, eine exakte Synthese war für Ihre bereitgestellte Einheit möglich (die Anzahl der theoretischen Einschränkungen für die Einträge), und die in der Frage beschriebenen Algorithmen haben Ihnen eine Folge von Clifford + T-Gates gegeben, die diese Einheit implementiert haben. Wie im Giles-Selinger-Papier angegeben, erhalten Sie eine Sequenz, die alles andere als optimal ist. An diesem Punkt haben Sie sich also auf das Wortproblem in der Gruppe reduziert, die durch das Clifford + T-Gate-Set generiert wurde. Einige Gruppen haben Algorithmen, um ein bestimmtes Wort zu verkürzen und gleichzeitig dasselbe Element der Gruppe in eine normale Form zu bringen, die innerhalb dieser Klasse die kürzeste ist. Andere nicht.

Weitere Details zur Veranschaulichung des Prinzips: Nehmen wir an, es gibt Qubits. Bezeichne usw. für den Generator, der das Phasengatter auf Qubit , wobei für die Steuerung usw. ist. Jeder dieser Generatoren wird als Buchstabe behandelt. Der Algorithmus wird in diesen Generatoren ein Wort ausspucken. Die Gruppe ist die Gruppe mit diesen Generatoren und vielen Beziehungen wie und wenn$2$$S_1$$1$$CNOT_{12}$$1$$S_i^4=1$$X_i Y_j = Y_j X_i$$i \neq j$unter vielen anderen Beziehungen. Dies definiert also eine endlich erzeugte Gruppe. Da wir ein Wort aus den bereitgestellten Algorithmen haben, das jedoch nicht optimiert wurde, besteht die Aufgabe darin, eine bequeme, kürzestmögliche Normalform im Wortproblem für diese Gruppe bereitzustellen. Wenn also das Wort , könnte man die Beziehung zweimal und die Beziehung einmal verwenden, um als kürzeres Wort zu erhalten, das dasselbe Gruppenelement darstellt. Für eine gegebene Gruppenpräsentation möchte man einen Algorithmus, der ein beliebiges Wort nimmt und es reduziert. Im Allgemeinen ist dies nicht möglich.$S_1 S_1 S_2 S_1 S_1$$S_1 S_2 = S_2 S_1$$S_1^4=1$$S_2$

Haftungsausschluss für unten: Kommende Projekt- / Haskell-Implementierungsstelle mit Jon Aytac.

Ich weiß nichts über die Lösbarkeit des Wortproblems für die Clifford + T-Gate-Menge, aber man kann etwas Einfacheres nur mit den Involutionen (nenne sie ) in dieser Menge und nur mit den Beziehungen der Form tun . Dies ist eine Coxeter-Gruppe, die mit dem Clifford + T-Gate-Set verwandt ist, jedoch ein effizient lösbares Wortproblem aufweist. Man kann also das Ergebnis des Giles-Selinger-Algorithmus nehmen und es möglicherweise nur mit diesen sehr einfachen Beziehungen verkürzen (nachdem man Segmente mit nur diesen Involutionsbuchstaben betrachtet hat). Tatsächlich kann jeder Algorithmus, der eine bestimmte Einheit nimmt und sie in Clifford + T approximiert oder genau synthetisiert, in dieses Verfahren eingespeist werden, um sie möglicherweise geringfügig zu verkürzen. ( r i r j ) m i j = $r_i$$(r_i r_j)^{m_{ij}}=1$