Séquence la plus courte de portes quantiques universelles qui correspondent à une unité donnée

Question: Étant donné une matrice unitaire agissant sur qubits, pouvons-nous trouver la séquence la plus courte de portes Clifford + T qui correspond à cette unité?$n$

Pour le contexte de la question, deux références importantes:

1. Synthèse exacte rapide et efficace des unitaires à qubit unique générés par les portes Clifford et T par Kliuchnikov, Maslov et Mosca
2. Synthèse exacte des circuits Clifford + T multibits de Giles et Selinger.

$\exp(n)$$n$

Je suppose que vous faites référence à des décompositions exactes. Si vous voulez des décompositions approximatives, il existe différentes méthodes pour cela, comme la décomposition Trotter-Suzuki, ou approximer une décomposition exacte.

Le "compilateur quantique csd" de Qubiter effectue une décomposition non optimisée de tout n qubit unitaire en cnots et en un seul qubit en utilisant le célèbre sous-programme csd (Cosine-Sine Decomposition) de LAPACK. Une personne entreprenante pourrait essayer de trouver des optimisations pour le compilateur quantique de Qubiter. Vous pouvez utiliser le compilateur de Qubiter, par exemple (j'ai écrit un article à ce sujet), pour laisser votre ordinateur classique redécouvrir la décomposition de la transformée de Fourier quantique de Coppersmith!

Qubiter est open source et disponible sur github (divulgation complète - je l'ai écrit).

Supposons qu'une synthèse exacte soit possible pour votre unité fournie (le nombre de restrictions théoriques sur les entrées) et que les algorithmes décrits dans la question vous donnent une séquence de portes Clifford + T qui implémentent cette unité. Comme indiqué dans l'article de Giles-Selinger, vous obtenez une séquence très loin d'être optimale. Donc, à ce stade, vous avez réduit le problème de mot dans le groupe généré par l'ensemble de portes Clifford + T. Certains groupes ont des algorithmes pour raccourcir un mot donné tout en représentant le même élément du groupe sous une forme normale qui est la plus courte de cette classe. D'autres ne le font pas.

$2$$S_1$$1$$CNOT_{12}$$1$$S_i^4=1$$X_i Y_j = Y_j X_i$$i \neq j$$S_1 S_1 S_2 S_1 S_1$$S_1 S_2 = S_2 S_1$$S_1^4=1$$S_2$comme un mot plus court qui représente le même élément de groupe. Pour une présentation de groupe donnée, on voudrait un algorithme qui prend un mot arbitraire et le réduit. En général, ce n'est pas possible.

Avertissement pour ci-dessous: Projet à venir / Joint de mise en œuvre Haskell avec Jon Aytac.

$r_i$$(r_i r_j)^{m_{ij}}=1$. Il s'agit d'un groupe Coxeter lié à l'ensemble de portes Clifford + T, mais avec un problème de mots efficacement résoluble. On peut donc prendre le résultat de l'algorithme de Giles-Selinger et potentiellement le raccourcir en utilisant uniquement ces relations très simples (après avoir regardé les segments avec uniquement ces lettres d'involution). En fait, tout algorithme qui prend un unitaire donné et le rapproche ou le synthétise exactement dans Clifford + T peut être introduit dans cette procédure pour le raccourcir légèrement.