Czym dokładnie jest wyrocznia?

Czym dokładnie jest „ wyrocznia ”? Wikipedia mówi, że wyrocznia to „ czarna skrzynka ”, ale nie jestem pewien, co to znaczy.

Na przykład, w algorytmie Deutsch – Jozsa , , czy wyrocznia jest po prostu polem oznaczonym czy też wszystko między pomiarem a danymi wejściowymi (w tym bramkami Hadamarda)?
$\hspace{85px}$
$`` U_f " ,$

I żeby dać wyrocznię, czy muszę napisać $U_f$ w postaci macierzowej czy skondensowanej: $U_f$ daje $y \rightarrow y \oplus f(x)$ i $x \rightarrow x$ wystarczy w odniesieniu do definicji wyroczni?

quantum-information terminology oracles

— StarBucK
źródło

Microsoft ma niezłą dokumentację dotyczącą wyroczni kwantowych .

— Sanchayan Dutta

Wyrocznia (przynajmniej w tym kontekście) jest po prostu operacją, która ma pewną właściwość, której nie znasz i próbuje się dowiedzieć. Termin „czarna skrzynka” jest używany w sposób równoważny, aby przekazać, że jest to po prostu pudełko, którego nie widać w środku, a zatem nie wiesz, co robi. Wszystko, co wiesz, to że możesz dostarczać wejścia i odbierać wyjścia. Na schemacie, który przedstawiasz, jest to tylko pole . Wszystko inne to rzeczy, które dodajesz, aby pomóc przesłuchać wyrocznię i odkryć jej właściwości. $U_f$

Aby dać wyrocznię, możesz napisać ją w dowolnej poprawnej formie, która definiuje mapę od wszystkich możliwych danych wejściowych do wyników. Może to być macierz (prawdopodobnie z nieznanym parametrem) lub mapa (ściśle, ), ponieważ na podstawie dowolnego opisu możesz wypracować drugi. $U:(x,y)\mapsto (x,y\oplus f(x))$ $\forall x,y\in\{0,1\}$

— DaftWullie
źródło

Czy możesz wyjaśnić, co miałeś na myśli ściśle w ostatnim zdaniu?

— Aritra Das

@tparker nie bardzo - celem takich form wyroczni jest często to, że pozwala opisać nie tylko algorytm, ale także optymalizację algorytmu. Mierzy się to po prostu jako liczbę zastosowań wyroczni. Nie ma znaczenia, jak długo wyrocznia trwa. Tak więc w przypadku hodowców wymaga to pierwiastka kwadratowego z liczby wywołań wyroczni, tak jak w przypadku klasycznego.

— DaftWullie

Masz rację; mój komentarz był źle sformułowany. Chciałem powiedzieć, że jeśli chcesz, aby wynik wyroczni dał jakikolwiek wgląd w środowisko uruchomieniowe „w świecie rzeczywistym”, musisz założyć (oprócz założenia czarnej skrzynki), że niezależnie od podprogramu, który uruchomisz, aby faktycznie zaimplementować Wywołanie wyroczni dominuje w środowisku uruchomieniowym algorytmu, dzięki czemu liczba wywołań wyroczni jest rzeczywiście proporcjonalna do rzeczywistego środowiska wykonawczego. Jest to jednak dodatkowe założenie dotyczące istotności w „świecie rzeczywistym”, a nie niezbędna część definicji wyroczni.

— tparker