Вопросы с тегом «black-box»

27
Приблизительный подсчет проблем с захватом BQP

В модели черного ящика проблема определения выходного сигнала машины BPP на входе является приближенной задачей подсчета определения с аддитивной ошибкой 1/3 (скажем).M(x,r)M(x,r)M(x,r)xxxErM(x,r)ErM(x,r)E_r M(x,r) Есть ли похожая проблема для BQP? Этот комментарий Кена Ригана наводит на мысль о...

20
Тестирование недвижимости в других метриках?

Существует большое количество литературы по «тестированию свойств» - проблеме создания небольшого числа запросов черного ящика к функции чтобы различать два случая:f:{0,1}n→Rf:{0,1}n→Rf\colon\{0,1\}^n \to R является членом некоторого класса функций CfffCC\mathcal{C} является ε -far из каждой...

16
Построение Oracle для алгоритма Гровера

В «Квантовых вычислениях и квантовой информации» Майка и Айка алгоритм Гровера объясняется очень подробно. Тем не менее, в книге и во всех объяснениях, которые я нашел в Интернете для алгоритма Гровера, кажется, нет упоминания о том, как устроен Оракул Гровера, если только мы уже не знаем, какое...

13
Исчерпывающий симулятор протоколов нулевого знания в модели случайного Oracle

В статье под названием «Об отрицании в общей эталонной строке и случайной модели Oracle» Рафаэль Пасс пишет: Мы отмечаем, что при проверке безопасности в соответствии со стандартным определением нулевого знания в модели RO [Random Oracle], симулятор имеет два преимущества по сравнению с симулятором...