Decydowalność / algorytm sprawdzania uniwersalności zbioru bramek kwantowych

Biorąc pod uwagę skończony zestaw bram kwantowych , czy jest rozstrzygalne (w sensie teoretycznym obliczeń), czy jest uniwersalnym zestawem bramek? Z jednej strony „prawie wszystkie” zestawy bram są uniwersalne, z drugiej strony nie-uniwersalne zestawy bram wciąż nie są dobrze zrozumiane (w szczególności oczywiście nie wiadomo, czy każdy nie-uniwersalny zestaw bram jest klasycznie symulowany), więc wyobrażam sobie, że podanie jawnego algorytmu sprawdzania uniwersalności może być nieprofesjonalne. $\mathcal{G} = \{G_1, \dots, G_n\}$ $\mathcal{G}$

quantum-computing

— Marcin Kotowski
źródło

Czy możesz wyjaśnić pytanie? Odpowiedź Joe zakłada, że masz ustaloną liczbę kubitów i wszystkie bramki działają na nich, ale dla uniwersalności często zakładamy, że bramki mogą działać na dowolny podzbiór kubitów. Np. CNOT + wszystkie bramki jednokubitowe nie są uniwersalne, jeśli bramki jednokubitowe mogą działać tylko na pierwszy kubit, a CNOT jest tylko od qubit 1 do qubit 2. W tym drugim przypadku możemy chcieć ekstrapolować na wiele kubitów uzyskać uniwersalność. W takim przypadku myślę, że odpowiedź może być nieznana.

@DanielGottesman: Zgadzam się z ograniczeniami mojej odpowiedzi. Rzeczywiście, uważam, że jest to nierozstrzygalne w tym drugim przypadku w następujący sposób: Weź automaty komórkowe na nieskończonej sieci kubitów i użyj go do zakodowania problemu zatrzymania (nazwij tę aktualizację jednostkowym

). Następnie weź drugą siatkę z uniwersalnym QCA (z aktualizacją jednostkową

). Możemy zdefiniować nowy jednolity

, gdzie indeks dolny

U_{1}

$U_1$

U_{2}

$U_2$

C U_{2} = | 0 ⟩ ⟨ 0 |_{H} \otimes I + | 1 ⟩ ⟨ 1 | \otimes U_{2}

$CU_2 = |0\rangle\langle0|_H\otimes I + |1\rangle\langle1|\otimes U_2$

H

$H$ oznacza kubit, który jest ustawiony na

przypadku zatrzymania pierwszych automatów komórkowych.

| 1 ⟩

$|1\rangle$

— Joe Fitzsimons,

Zatem bramka

jest uniwersalna wtedy i tylko wtedy, gdy pierwsza maszyna Turinga zatrzyma się, a zatem jest nierozstrzygalna.

C U_{2} \times U_{1}

$CU_2 \times U_1$

— Joe Fitzsimons,

W przypadku Hamiltonianów zamiast bram odpowiedź brzmi trywialnie: po prostu wyliczasz niezależne elementy algebry Lie. Ponieważ algebra Lie jest przestrzenią wektorową z dodatkiem operatora nawiasu Lie. Ponieważ przestrzeń jest skończona, ma skończoną podstawę i można ją łatwo sprawdzić, czy jest zamknięta, czy otwarta w operacji klamry Lie. Po prostu sprawdzenie nawiasów Lie wszystkich par operatorów ortogonalnych można wykonać wielomianem czasowym w wymiarach przestrzeni, a odpowiednią podstawę operatora można znaleźć metodą Grama-Schmidta.

W przypadku bramek tak naprawdę nie masz takiej samej możliwości natychmiastowego skorzystania z nieskończenie małych i musisz zbudować bramki z irracjonalnymi wartościami własnymi, abyś mógł dowolnie dobrze przybliżać wymagane nieskończenie małe generatory. Myślę, że jest to stosunkowo prosty sposób, ale nie jest to od razu oczywiste.

W każdym razie pobranie dziennika bramek w celu uzyskania zestawu operatorów, które generują je po potęgowaniu, i sprawdzenie, czy wygenerowały one pełną algebrę Lie, zapewniłoby proste niezbędne, ale niewystarczające kryteria dla uniwersalności.

— Joe Fitzsimons
źródło

Dlaczego powinniśmy sprawdzać tylko pary?

— Alex „qubeat”

@AlexV: Ponieważ nawias klamrowy zajmuje działa na 2 wejściach. Za każdym razem, gdy produkujesz nowego liniowo niezależnego operatora, produkujesz ortogonalnego i powtarzasz aż do zamknięcia.

— Joe Fitzsimons,

[\dots [H_{k}, H_{j}], H_{l}], \dots]

$[\ldots[H_k,H_j],H_l],\ldots]$

@AlexV: Nie musisz. Jest to przestrzeń wektorowa, więc wektor jest ortogonalny dla danej podprzestrzeni wtedy i tylko wtedy, gdy jest ortogonalny względem dowolnej podstawy dla tej podprzestrzeni.

— Joe Fitzsimons,

Prawdopodobnie mówimy o różnych rzeczach - o jakiej przestrzeni wektorowej mówisz? Nie znasz od samego początku subalgebry generowanej przez twoje bramy - musisz ją zbudować na podstawie danych Hamiltonianów, aby sprawdzić, czy to cała algebra Lie.

— Alex „qubeat”