Dlaczego kubit wyroczni jest potrzebny w algorytmie Grovera?

10

Jestem trochę zdezorientowany co do konieczności kubitu wyroczni w algorytmie Grovera.

Moje pytanie brzmi: czy to zależy od tego, jak wdrażasz swoją wyrocznię, czy potrzebujesz kubitowej wyroczni, czy nie? A może jest jakiś powód, dla którego kubit wyroczni? (np. istnieją pewne problemy, których nie można rozwiązać bez kubitu wyroczni, lub łatwiej jest pomyśleć o problemie z kubitem wyroczni lub jest to konwencja itp.)

Wiele zasobów przedstawia algorytm Grovera z kubitem wyroczni, ale znalazłem kilka przypadków, w których nie potrzebujesz kubitu wyroczni.

Na przykład oto dwie implementacje algorytmu Grovera w symulatorze IBM Q. Jeden używa kubitu wyroczni, a drugi nie. W obu przypadkach chciałbym znaleźć | 11> z przestrzeni | 00>, | 01>, | 10> i | 11>. W obu przypadkach wyrocznia pomyślnie odwraca | 11> do - | 11>.

・ Z kubitem oracle ( Link do symulatora IBM Q ) wprowadź opis zdjęcia tutaj

・ Bez kubatury Oracle ( łącze do symulatora IBM Q ) wprowadź opis zdjęcia tutaj

Bick
źródło

Odpowiedzi:

5

Z punktu widzenia zdefiniowania obwodu kwantowego kubit wyroczni nie jest absolutnie konieczny. Na przykład w wyszukiwaniu Grovera normalnie możesz zdefiniować działanie wyroczni jako gdzie zwraca 1, jeśli oznacza zaznaczony element. Jednak zawsze używamy tego w określony sposób, wprowadzając w kubicie Oracle. Ma to efekt netto po prostu wdrożenie fazy na zaznaczonym elemencie. Innymi słowy, jest to całkowicie równoważne z implementacją nowego jednolitego

U|x|y=|x|yf(x),
f(x)x(|0|1)/2
U~|x=(1)f(x)|x

Jednak ma to znaczenie w praktyce. Szukając przedmiotu, potrzebujemy pewnego rodzaju obwodu, który rozpoznaje zaznaczony element, na podstawie danych wejściowych . W tym momencie znacznie łatwiej jest myśleć o wypisaniu odpowiedzi na bit wyroczni, niż w jakiś sposób bezpośrednio budować jednostkę, która daje fazę bez użycia kubidu wyroczni. Rzeczywiście, podejrzewam, że gdybym poprosił cię o zaprojektowanie wersji ogólnej , wymyśliłbyś z dodatkowym kubitem jako rozwiązaniem.xU~U

DaftWullie
źródło
W rzeczywistości bardzo łatwo jest uniknąć dodatkowego kubitu, zakładając, że nie jest on używany jako obszar roboczy podczas obliczania wyroczni. Znajdź dowolne CNOT na dodatkowym kubicie i zamień je bramką Z na sterowanie CNOT. Podobnie zamień CCNOT na dodatkowy kubit na CZ pomiędzy dwoma kontrolami CCNOT. Itd.
Craig Gidney,
@CraigGidney To słuszna kwestia, chociaż myślę, że w twoim oświadczeniu jest więcej założeń (co sprawia, że ​​nie są ogólne, nawet jeśli większość przypadków, o których wiemy, że je spełniają): (1) nie powinno się stosować żadnych pośrednich pomocników podczas ocena funkcji; (2) obwód wyroczni musi zostać rozłożony na zestaw bramek, w którym jedynymi bramkami wieloczubitowymi działającymi na kubit ustny są (nie) kontrolowane-notki skierowane na kubit wyroczni; (3) żadne inne bramki nie mogą oddziaływać na kubit wyroczni (tj. Nie można po prostu odwrócić c-not działających w niewłaściwy sposób, używając Hadamardów na wejściach i wyjściach).
DaftWullie
To jest poprawne.
Craig Gidney