Dlaczego kubit wyroczni jest potrzebny w algorytmie Grovera?

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 )

・ Bez kubatury Oracle ( łącze do symulatora IBM Q )

algorithm grovers-algorithm

— Bick
źródło

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 ⟩ | y \oplus f (x) ⟩,

$U|x\rangle|y\rangle=|x\rangle|y\oplus f(x)\rangle,$

f (x)

$f(x)$

x

$x$

(| 0 ⟩ - | 1 ⟩) / \sqrt{2}

$(|0\rangle-|1\rangle)/\sqrt{2}$

\tilde{U} | x ⟩ = (- 1)^{f (x)} | x ⟩

$\tilde U|x\rangle=(-1)^{f(x)}|x\rangle$

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. $x$ $\tilde U$ $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