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

9

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.
użytkownik120404
źródło
3
Witamy! Do kontekstu dodałem dwa odniesienia na ten temat. Cofnij lub popraw, jeśli nie są odpowiednie. Dodatkowo, gdyby do pytania można było dodać więcej szczegółów, byłoby świetnie :)
agaitaarino

Odpowiedzi:

9

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).

rrtucci
źródło
Czy rozkład jest również trudny do rozwiązania dla jednostek unitarnych, które składają się wyłącznie z pomnożenia bram Clifforda? Chcę zbudować generator z układem losowym i chciałbym wstawić warstwę inwersyjną po losowych bramkach, aby uzyskać stan deterministyczny (w tym przypadku równy początkowy). Jednak zamiast po prostu odwzorować obwód, zastanawiałem się, czy można skutecznie obliczyć warstwę inwersyjną, jeśli obwód wejściowy składa się wyłącznie z Cliffords?
Kelthar
4

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ą 2kubity. OznaczaćS1 itp. dla generatora wykonującego bramkę fazową w qubit 1, CNOT12 dla 1bę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 relacjamiSi4=1 i XiYj=YjXi kiedy ijwś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łowoS1S1S2S1S1 można użyć tej relacji S1S2=S2S1 dwa razy i S14=1 związek raz, aby uzyskać S2jako 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 ri) w tym zbiorze i tylko relacje formularza (rirj)mij=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ć.

AHusain
źródło