Najkrótsza sekwencja uniwersalnych bram kwantowych, które odpowiadają danej jednostce

Pytanie: Biorąc pod uwagę jednolitą macierz działającą na $n$ kubity, czy możemy znaleźć najkrótszą sekwencję bramek Clifford + T, która odpowiada tej jednostce?

Dla tła pytania dwa ważne odniesienia:

1. Szybka i wydajna dokładna synteza pojedynczych kubitowych jednostek unitarnych generowanych przez Clifforda i T-bramki przez Kliuchnikova, Maslova i Mosca
2. Dokładna synteza wielotubowych obwodów Clifford + T autorstwa Gilesa i Selingera.

Uzyskanie optymalnego rozkładu jest zdecydowanie otwartym problemem. (I oczywiście rozkład jest trudny do rozwiązania,$\exp(n)$ bramy dla dużych $n$.) „Prostszym” pytaniem, które możesz zadać najpierw, jest najkrótsza sekwencja węzłów i pojedynczych obrotów kubitów pod dowolnym kątem (co obecnie oferują IBM, Rigetti i wkrótce Google), tę uniwersalną podstawę bram można wyrazić w kategoriach twoja podstawa Cliffords i T-gates). To „prostsze” pytanie jest również otwarte i zawiera niejednoznaczną odpowiedź. Powiązanym pytaniem jest, jaki jest dokładny optymalny rozkład bramek z uniwersalnej podstawy, aby przejść ze stanu podstawowego do danego stanu końcowego.

Zakładam, że odnosisz się do dokładnego rozkładu. Jeśli chcesz uzyskać przybliżony rozkład, istnieją na to różne metody, takie jak rozkład Trottera-Suzuki lub przybliżenie dokładnego rozkładu.

„Kwantowy kompilator csd” w programie Qubiter dokonuje niezoptymalizowanego rozkładu dowolnego n-kubitowego unitu na węzły i pojedyncze zgniłe qubity za pomocą słynnego podprogramu csd (Cosine-Sine Decomposition) z LAPACK. Pewna przedsiębiorcza osoba mogłaby spróbować znaleźć optymalizacje dla kompilatora kwantowego Qubitera. Możesz na przykład użyć kompilatora Qubitera (napisałem o tym artykuł), aby Twój klasyczny komputer ponownie odkrył kwantowy rozkład Transformaty Fouriera Coppersmitha!

Qubiter jest oprogramowaniem typu open source i jest dostępny na github (pełne ujawnienie - napisałem to).

Załóżmy, że dokładna synteza była możliwa dla podanego unitarnego (liczba teoretycznych ograniczeń wpisów), a więc algorytmy opisane w pytaniu dały ci sekwencję bramek Clifford + T, które zaimplementowały to unitary. Jak stwierdzono w pracy Gilesa-Selingera, sekwencja jest bardzo daleka od optymalnej. W tym momencie ograniczyłeś się do problemu słów w grupie generowanej przez zestaw bramek Clifford + T. Niektóre grupy mają algorytmy do skracania danego słowa, a jednocześnie reprezentują ten sam element grupy w normalnej formie, która jest najkrótsza w tej klasie. Inni nie.

Więcej szczegółów ilustrujących zasadę: powiedzmy, że istnieją $2$kubity. Oznaczać$S_1$ itp. dla generatora wykonującego bramkę fazową w qubit $1$, $CNOT_{12}$ dla $1$będący kontrolą itp. Każdy z nich traktowany jest jak litera. Algorytm wypluje jakieś słowo z tych generatorów. Grupa jest grupą z tymi generatorami i wieloma podobnymi relacjami$S_i^4=1$ i $X_i Y_j = Y_j X_i$ kiedy $i \neq j$wśród wielu innych relacji. Definiuje to pewnie skończoną grupę. Ponieważ mamy słowo z dostarczonych algorytmów, ale nie zostało zoptymalizowane, zadaniem jest zapewnienie dogodnej najkrótszej możliwej postaci normalnej w zadaniu tekstowym dla tej grupy. Więc jeśli dane słowo$S_1 S_1 S_2 S_1 S_1$ można użyć tej relacji $S_1 S_2 = S_2 S_1$ dwa razy i $S_1^4=1$ związek raz, aby uzyskać $S_2$jako krótsze słowo reprezentujące ten sam element grupy. Dla danej prezentacji grupowej potrzebny jest algorytm, który pobiera dowolne słowo i redukuje je. Zasadniczo nie jest to możliwe.

Zastrzeżenie dla poniżej: Nadchodzący projekt / wspólne wdrożenie Haskell w / Jon Aytac.

Nie wiem na temat możliwości rozwiązania problemu słownego dla zestawu bram Clifford + T, ale można zrobić coś prostszego za pomocą tylko zaangażowania (nazwij je $r_i$) w tym zbiorze i tylko relacje formularza $(r_i r_j)^{m_{ij}}=1$. Jest to grupa Coxeter związana z zestawem bramki Clifford + T, ale z efektywnie rozwiązanym problemem słownym. Można więc wziąć wynik algorytmu Gilesa-Selingera i potencjalnie skrócić go, używając tylko tych bardzo prostych relacji (po spojrzeniu na segmenty zawierające tylko te litery inwolucji). W rzeczywistości każdy algorytm, który przyjmuje daną jednostkę i przybliża ją lub dokładnie syntetyzuje do Clifford + T, może zostać wprowadzony do tej procedury, aby potencjalnie ją nieco skrócić.