Jak permutować (przetasować) wejście n-bitowe?

Interesuje mnie algorytm kwantowy, który pobiera jako dane wejściowe sekwencję n-bitową i który wytwarza jako dane wyjściowe przetasowaną (permutowaną) wersję tej sekwencji n-bitowej.

Np. Jeśli dane wejściowe wynoszą 0,0,1,1 (więc n = 4 w tym przypadku), możliwe odpowiedzi to:

• 0,0,1,1
• 0,1,0,1
• 0,1,1,0
• 1,0,0,1
• 1,0,1,0
• 1,1,0,0

Należy zauważyć, że należy wygenerować tylko jedno wyjście, które jest losowo wybierane spośród wszystkich możliwych prawidłowych wyników.

Jak można to najlepiej wdrożyć w algorytmie kwantowym ?

Rozwiązanie tego problemu zostało już zaproponowane w ramach jednej z odpowiedzi na pytanie: Jak stworzyć algorytm kwantowy, który wytwarza 2 sekwencje n-bitowe o równej liczbie 1-bitów? . Problem w tym rozwiązaniu polega na tym, że wymaga to około $\binom{n}2$ pomocy, które szybko stają się ogromne, jeśli n jest duże.

Uwaga:

• Proszę nie dostarczać klasycznego algorytmu bez wyjaśnienia, w jaki sposób kroki klasycznego algorytmu mogą być odwzorowane na uniwersalny komputer kwantowy.
• dla mnie istnieją 2 dobre sposoby interpretacji „losowo wybranych spośród wszystkich możliwych dobrych wyników” : (1) każdy możliwy dobry wynik ma równe szanse na wybranie. (2) każda możliwa dobra wydajność ma szansę wyboru> 0.

Można to zrobić za pomocą dodatkowych wzdłuż tych linii:$\lceil\log n\rceil$

1. Przekształć dodatkowe kubity, aby kodowały liczbę wybraną równomiernie losowo.$k\in\{0,\ldots,n-1\}$

2. Cyklicznie przesuwaj kubity wejściowe razy.$k$

3. Niech ostatni z pierwotnych kubitów wejściowych zostanie ustalony jako wyjście i powtórzy się na pozostałych z nich.$n-1$

Jest to klasyczny algorytm, ale oczywiście można go uruchomić na komputerze kwantowym, jak zasugerował Norbert w komentarzu. (Aspekt nieugiętego pytania, że ​​algorytm jest kwantowy, wciąż nie jest dla mnie jasny, więc jeśli uruchomienie klasycznego algorytmu, takiego jak ten, który zasugerowałem na komputerze kwantowym, nie jest wystarczające, pomocne byłoby pytanie wyjaśnić.)

Zauważ, że ponieważ pytanie wymaga losowego wyniku, algorytm będzie musiał w pewnym momencie wygenerować entropię, prawdopodobnie poprzez pomiary lub wykonywanie innych niejednolitych operacji na kubitach (takich jak ich inicjalizacja). W powyższym algorytmie jest to pierwszy krok, który generuje entropię: niezależnie od stanu dodatkowych kubitów przed wykonaniem operacji w kroku 1, powinny one mieć stan po wykonaniu kroku 1 ( powiedzmy z zakodowanym binarnie).

Uwaga: ta odpowiedź zakłada, że ​​chcesz, aby permutacja była spójna , tzn. Chcesz zamiast 1/3 szansa , 1/3 szansa i 1/3 szansa .$\frac{1}{\sqrt{3}} ( |001\rangle + |010\rangle + |100\rangle)$$001$$010$$100$

Uważaj, jak określisz to zadanie, ponieważ może być bardzo łatwo niemożliwe z powodu ograniczeń odwracalności. Na przykład dla wejściowego chcesz wyprowadzić stan GHZ . Ale jeśli chcesz również wyprowadzić stan GHZ dla wejściowego i , to nie zadziała. Nie można wysłać wielu stanów wejściowych do tego samego stanu wyjściowego (bez dekoherencji). Tak długo, jak powiesz: „Dbam tylko o posortowane rosnąco, takie jak 0000111, ale nie 1110000 lub 0010110; możesz zrobić z nimi co chcesz”, to będzie w porządku.$|001\rangle$$\left| {3 \atop 1} \right\rangle = \frac{1}{\sqrt{3}} (|001\rangle + |010\rangle + |100\rangle)$$|010\rangle$$|100\rangle$

Jedną sztuczką w tworzeniu kwantowej permutacji posortowanego wejścia jest najpierw przygotowanie „stanu permutacji” poprzez zastosowanie sieci sortującej do listy wartości początkowych, z których każda znajduje się w jednolitej superpozycji. Sieć sortująca wysyła kubity zawierające posortowane nasiona, ale także kubity zawierające porównania sieci sortującej. Stan permutacji to tylko kubity porównawcze. Aby zastosować go do danych wejściowych, wystarczy uruchomić dane wejściowe przez sieć sortującą w odwrotnej kolejności. Zauważ, że są tu pewne trudne szczegóły; patrz artykuł „ Udoskonalone techniki przygotowania stanów własnych fermionowych hamiltonianów ”. Trzeba by uogólnić tę technikę, aby pracować z danymi wejściowymi z powtarzanymi wartościami, a nie tylko wartościami unikatowymi.

Możesz także przyjrzeć się „ kompresji kwantowej ”, która jest bardzo ściśle związana z stany (jednolite superpozycje wszystkich bitowych stanów z zestawem bitów), które chcesz utworzyć. Główna różnica polega na tym, że obwód kompresji kwantowej działałby w odwrotnej kolejności i oczekuje liczby kodującej „ile jest tych?” zamiast „daj mi stan z poprawną liczbą”.$\left| {n \atop k} \right\rangle$$n$$k$

Myślę, że mówię, że tworzenie tego rodzaju stanów jest bardziej skomplikowane, niż można się było spodziewać. Myślę, że powodem tego jest skomplikowanie, ponieważ amplituda amplitud wyjściowych zależy od obliczeniowego stanu wejściowego. Na przykład, dla chcesz wyjście, które jest superpozycją stanów czterech klasycznych, więc masz prefactor z ukryte wewnątrz . Ale dla pożądany wynik ma sześć klasycznych stanów, więc ukrywa prefiks .$|0001\rangle$$\frac{1}{\sqrt{4}}$$\left| {4 \atop 1} \right\rangle$$|0011\rangle$$\left| {4 \atop 2} \right\rangle$$\frac{1}{\sqrt{6}}$

Komputer kwantowy może wykonywać klasyczne obliczenia. Optymalnym algorytmem byłoby:

1. Wybierz dowolną (najszybszą, do której możesz uzyskać dostęp).
2. Znajdź bit o przeciwnej wartości (jeśli w kroku 1 masz 0, znajdź 1)
3. Przełącz je (0 staje się 1, a 1 staje się 0).

Krok 2 obejmuje przeszukanie ciągu bitów, który przy użyciu klasycznych operacji wymaga operacji , ale jeśli można uzyskać wartość bitu , oceniając funkcję, być może użyć algorytmu kwantowego Grovera do znalezienia przeciwnego bitu za pomocą operacji . $N$$\mathcal{O}(N)$$n^{\textrm{th}}$$\mathcal{O}\left(\sqrt{N}\right)$