Jak śledzić splątania podczas emulacji obliczeń kwantowych?

Próbuję zbudować bibliotekę obliczeń kwantowych jako mój projekt uniwersytecki. Wciąż uczę się wszystkich aspektów dziedziny obliczeń kwantowych. Wiem, że istnieją już wydajne biblioteki do emulacji kwantowej. Chcę tylko stworzyć własną, która pomoże mi zrozumieć niektóre podstawowe koncepcje obliczeń kwantowych.

wiem to $n$ kubity można przechowywać za pomocą $2^n$tablica złożona z elementów. Również$n$ qubit gate to $2^n \times 2^n$Tablica 2D. Oto moje wątpliwości (związane głównie z splątaniem):

1. Kiedy muszę znaleźć iloczyn tensorowy bram (np $I \otimes H \otimes I$, dla $3$system qubit)? Czy zawsze konieczne jest obliczenie iloczynu tensorowego rzędu?$2^n \times 2^n$, nawet jeśli kubity nie są splątane?

2. Z tylko $2^n$tablicy elementów (w której przechowuję współczynniki), czy rzeczywiście mogę w jakiś sposób obliczyć, które kubity są splątane? Czy też muszę utworzyć inną strukturę danych do przechowywania moich informacji o splątaniu$n$ kubity (o które kubity są splątane)?

3. Czy moje drugie pytanie jest rzeczywiście istotne? Czy w ogóle muszę śledzić informacje o splątaniu? To znaczy, nie wiem, czy wystarczy pomnożyć bramki przez współczynniki (nawet jeśli system jest splątany). Może ma to znaczenie tylko w momencie pomiaru.

Z pewnością wystarczy zawsze obliczyć pełny $2^n\times 2^n$ macierz jednolitą, a następnie zastosuj ją do $2^n$wektor stanu wejścia. Jeśli to właśnie wybierzesz, to wszystko co musisz zrobić, ponieważ wszystkie informacje o splątaniu są zawarte w tym wektorze. Szybkim i łatwym sposobem sprawdzenia, czy dany kubit jest zaplątany, jest pobranie częściowego śladu (czystego) wektora stanu nad wszystkimi innymi kubitami. Jeśli wynikowa macierz ma rangę 1, to kubit jest w stanie do rozdzielenia, w przeciwnym razie jest splątany.

Zakładam, że sedno twojego pytania brzmi: „Jak można uniknąć tak ogromnych kosztów obliczeniowych?”. Zasadniczo tak nie jest - jeśli wykorzystujesz pełną moc komputera kwantowego, zawsze będziesz go potrzebować$2^n$wektor stanu wejścia. Istnieją jednak różne sztuczki, które zmniejszają koszty obliczeniowe, takie jak opóźnianie zapotrzebowania na tak duży wektor stanu poprzez śledzenie splątania.

Poprawa wydajności

Największą oszczędnością, jaką możesz zrobić w porównaniu do naiwnej implementacji powyżej, jest uniknięcie $2^n\times 2^n$macierze jednolite. Na przykład, jeśli używasz tylko bramek 1- lub 2-kubitowych, po prostu użycie rzadkości matryc oznacza, że ​​potrzebujesz tylko$O(2^n)$ miejsce do przechowywania zamiast $O(2^{2n})$.

Są też inne taktyki, które możesz zastosować. Na przykład wyobraź sobie, że chcesz zastosować jednolitą bramę o dwóch kubitach$U$ na kubitach $i$ i $j$. Z wektora stanu możesz pobrać zestawy 4 elementów ($|x\rangle_{1,2,\ldots n\setminus i,j}|y\rangle_{i,j}$ dla ustalonych $x\in\{0,1\}^{n-2}$ biorąc wszystko inne $y\in\{0,1\}^2$) i po prostu stosując $4\times 4$ jednolity $U$na tym 4-elementowym wektorze. Powtarzam to dla każdego$x$ wróci $U$ uchwalone na oryginalnym wektorze stanu.

Wyobrażam sobie, że istnieją inne strategie, które można wymyślić. Tym, co zasugerowało pierwotne pytanie, było śledzenie splątania. Daje to poprawę pamięci i szybkości na początku obliczeń, ale ostatecznie jest równoważne, ponieważ (prawdopodobnie) wszystko w komputerze kwantowym zostanie splątane.

Śledzenie uwikłania

Załóżmy, że twoje obliczenia składają się tylko z jednolitej ewolucji i pomiaru na zbiorze$n$ kubity, tj. nie ma dekoherencji, map probabilistycznych itp. Załóżmy dalej, że zaczynasz od stanu całkowicie oddzielnego, takiego jak $|0\rangle^{\otimes n}$. W tym momencie każdy kubit można oddzielić i wystarczy go zachować$n$różne rejestry, z których każdy przekazuje stan oddzielnego kubitu. Jeśli twoja pierwsza bramka to tylko operacja na pojedynczy kubit$U$ na qubit $i$, po prostu aktualizujesz stan zapisany w qubit $i$ tak jak $|\psi_i\rangle\mapsto U|\psi_i\rangle$i nie musisz dotykać niczego innego.

Jeśli chcesz zrobić bramę z dwoma kubitami $V$ między kubitami $i$ i $j$powiedzmy, że musisz połączyć stany w obu witrynach. Tak więc zamieniasz dwa rejestry, każdy o wymiarze 2, na jeden rejestr o wymiarze 4, zawierający stan$V|\psi_i\rangle|\psi_j\rangle$. Problem polega na tym, że nie możesz teraz ponownie podzielić tego stanu, więc musisz zachować te dwa kubity w rejestrze na zawsze. Oczywiście, jeśli kiedykolwiek masz bramę 1-kubitową$U$ aplikować na qubit $i$, musisz teraz złożyć wniosek $|\psi_{i,j}\rangle\mapsto U\otimes\mathbb{I}|\psi_{i,j}\rangle$. Then, the next time you want a 2-qubit gate between, say, $j$ and $k$, you'll have to combine the spaces for $(i,j)$ and $k$. Those spaces will keep growing, but if a gate is localised on just one space, you only have to apply it there (using $\mathbb{I}$ operators to pad it on the rest of the qubits), and you don't have to do anything to the other spaces.

If you're doing things like this, you will not have (at least for the first few steps of your algorithm) a single $2^n$rejestr elementów. Będziesz musiał mieć kilka różnych rejestrów i śledzić, które kubity są opisane przez który rejestr w osobnej tablicy. Za każdym razem, gdy połączysz spacje niektórych kubitów, zaktualizujesz tę dodatkową tablicę.

Oto bardzo prymitywny pseudo-kod, który może pomóc przekazać moje znaczenie:

#initialise variables
entangled_blocks={{1},{2},{3},...,{n}}
quantum_states={{1,0},{1,0},...,{1,0}}

#apply action of each gate
for each gate
   for each gate_target
       target_block=entangled_blocks entry containing gate_target
   next gate_target
   if all target_blocks equal then
      apply gate on target_block (pad with identity on other qubits)
   else
      new_entangled_block=union(target_blocks)
      new_state_vec=tensor_product(quantum_states for each target block)
      apply gate on new_state_vec (pad with identity on other qubits)
      replace all target_blocks in entangled_blocks with new_entangled_block
      replace all quantum_states(all target blocks) with new_state_vec
   end if
next gate

Inne opcje

(W żadnym wypadku nie wyczerpujący)

Być może zainteresuje Cię przeczytanie o stanach produktów Matrix, które są dobrym sposobem na enkapsulację informacji o niezbyt splątanych stanach, i które mogą stanowić dla ciebie alternatywną trasę, w zależności od tego, co chcesz osiągnąć.