W modelu czarnej skrzynki problem określania wydajności maszyny BPP na wejściu x jest przybliżonym problemem zliczania określania E r M ( x , r ) z błędem addytywnym 1/3 (powiedzmy) .M(x,r)M(x,r)M(x,r)xxxErM(x,r)ErM(x,r)E_r M(x,r) Czy istnieje podobny problem dla BQP? Ten komentarz Kena Regana...
Istnieje duża literatura na temat „testowania właściwości” - problemu polegającego na utworzeniu niewielkiej liczby zapytań do czarnej skrzynki do funkcji celu rozróżnienia dwóch przypadków:f:{0,1}n→Rf:{0,1}n→Rf\colon\{0,1\}^n \to R fff jest członkiem pewnej klasy funkcjiCC\mathcal{C} fff jest...
Niech f:{0,1}n→(2−n,1]f:{0,1}n→(2−n,1]f \colon \lbrace 0,1 \rbrace ^ n \to (2^{-n},1] będzie funkcją. Chcemy oszacować średnią fff ; to znaczy: E[f(n)]=2−n∑x∈{0,1}nf(x)E[f(n)]=2−n∑x∈{0,1}nf(x)\mathbb{E}[f(n)]=2^{-n}\sum_{x\in \lbrace 0,1 \rbrace ^ n}f(x) . NOTE: In the OP, the range of f was...
W „Obliczeniach kwantowych i informacjach kwantowych” Mike'a i Ike'a algorytm Grovera został szczegółowo wyjaśniony. Jednak w książce i we wszystkich wyjaśnieniach, które znalazłem w Internecie dla algorytmu Grovera, wydaje się, że nie ma wzmianki o tym, jak zbudowana jest Wyrocznia Grovera, chyba...
W artykule zatytułowanym „On Deniability in Common Reference String and Random Oracle Model” Rafael Pass pisze: Zauważamy, że udowadniając bezpieczeństwo zgodnie ze standardową definicją zerowej wiedzy w modelu RO [Random Oracle], symulator ma dwie zalety w stosunku do zwykłego symulatora...