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


14

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

1
Dane wejściowe to ciąg binarny o długości gdzie bitów to 1, a wynikiem jest dowolna z możliwych tego? Można to zrobić na klasycznym komputerze z 1 krokiem. Chcesz alll możliwych wyjść? nk(nk)1
user1271772,

Nie, należy wygenerować tylko jeden wynik, który jest losowo wybierany spośród wszystkich możliwych wyników.
JanVdA

Czy klasyczny algorytm byłby wystarczająco dobry? (Nadal możesz uruchomić go na komputerze kwantowym.) Czy też potrzebujesz czegoś. który przewyższa najlepszy klasyczny algorytm?
Norbert Schuch,

1
@JanVdA: Dlaczego po prostu nie wybierzesz żadnego 1 i dowolnego 0 i zamienisz je na klasycznym komputerze?
user1271772

1
Ponieważ nie określiłeś losowego rozkładu, który chcesz, zostawię to tutaj: Dilbert i XKCD ;)
Ali

Odpowiedzi:


4

Można to zrobić za pomocą dodatkowych wzdłuż tych linii:logn

  1. Przekształć dodatkowe kubity, aby kodowały liczbę wybraną równomiernie losowo.k{0,,n1}

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

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

1nk=0n1|kk|
k

Dziękuję za odpowiedź. Interesuje mnie rzeczywisty algorytm kwantowy dla problemu - jeśli mógłbyś zmapować powyżej klasycznego algorytmu do programu kwantowego, to też jest w porządku, ale nie mam pojęcia, jak to zrobić.
JanVdA

2
Myślę, że pytanie staje się coraz bardziej aktualne: tak naprawdę nie szukasz algorytmu, szukasz kodu. To, co opisałem, to algorytm, a pozostałym zadaniem jest wdrożenie tego algorytmu (lub innego) jako kodu w pewnym języku lub jako niskopoziomowego opisu obwodu kwantowego. Sugeruję, abyś poprawił pytanie, aby było bardziej jasne - ale pamiętaj, że prosisz kogoś o wykonanie żmudnej i nieciekawej koncepcyjnie pracy. Alternatywa samodzielnego uczenia się, jak to zrobić, może wydawać się zniechęcająca, ale w dłuższej perspektywie może okazać się lepszym rozwiązaniem.
John Watrous,

Dodałem notatkę do pytania. Myślę, że różnie interpretowaliśmy pojęcie algorytmu kwantowego . Dla mnie a_klasyczny algorytm_ nie jest algorytmem kwantowym, ale może być odwzorowany na algorytm kwantowy .
JanVdA

@JanVdA: Co rozumiesz przez algorytm kwantowy? Na przykład, czy wymagasz, aby obejmowała przynajmniej jedną bramkę ? Lub że wymaga co najmniej jednej bramki ? A może wymaga innego określonego zestawu bram? Jakiego zestawu bramek chcesz użyć dla tego algorytmu? HY
użytkownik1271772,

Algorytm kwantowy to algorytm, który można zmapować (na poziomie kroku) do programu dla uniwersalnego komputera kwantowego. Dane wejściowe i wyjściowe kroków algorytmu kwantowego są kubitami (lub mogą być odwzorowane na szereg kubitów). Ostatni krok algorytmu kwantowego = odczyt (obserwacja) wartości kubitów (więc kubity zostają zamapowane na rzeczywiste bity). Nie ma ograniczeń co do ustawienia bramki. Chodzi o to, że cały algorytm może działać na uniwersalnym komputerze kwantowym.
JanVdA

3

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 .13(|001+|010+|100)001010100

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|31=13(|001+|010+|100)|010|100

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ą”.|nknk

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 .|000114|41|0011|4216


Potrzebuję więcej badań, aby docenić twoją odpowiedź, ale nie do końca zgadzam się z twoim akapitem drugim dotyczącym ograniczenia odwracalności. Zauważ, że użyłeś jako rozwiązania dla ale istnieje wiele innych rozwiązań w trakcie pracy z liczbami zespolonymi (np. możliwe jest także rozwiązanie13(|001+|010+|100)|00113(|001|010+i.|100)
JanVdA

1
@JanVdA Prawidłowo, można użyć faz, aby ustawić różne wyjścia prostopadłe. Moje czytanie twojego pytania brzmiało: chciałeś mieć taki sam etap we wszystkich przypadkach.
Craig Gidney

0

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 . NO(N)nthO(N)


Dzięki, ale algorytm zamieniłby tylko 2 bity (więc nie wygeneruje wszystkich permutacji) i nadal jest klasycznym algorytmem, podczas gdy chciałbym zobaczyć algorytm kwantowy.
JanVdA
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.