Оракул

Оператор и нам задан (это оракул). Построим квантовую схему, вычисляющую Г. Действовать будем так переведем ) в 0") некоторым оператором , затем применим оператор У = / —2 0")(0" , после чего применим [c.70]

Утверждение 12.1. Пусть п к. Для любого классического вероятностного алгоритма, делающего не более 2 обращений к оракулу, существует подгруппа О С (22з) и соответствующая функция / —> П ", для которой алгоритм ошибается с вероятностью [c.91]

Подведём итог для нахождения скрытой подгруппы В требуется 0 к] обращений к квантовому оракулу. В целом алгоритм имеет сложность 0 к ). [c.93]

В другой регистр поместим 0"). Применим квантовый оракул (12.2) и выбросим второй регистр. Получится смешанное состояние [c.104]

Первый ход белых в этой игре состоит в объявлении последовательности нар (/j,Sj)j i. Белые утверждают, что эта последовательность есть протокол обращений к оракулу в процессе работы алгоритма с оракулом вычисляющего Р(х). Более точно это означает, что алгоритм обращается к оракулу q раз, j-й запрос делается о слове Xj, оракул отвечает иа это запрос /j, и окончательный результат Р[х) = 1. Следующим ходом чёрные объявляют индекс j и, если fj = О, то дополнительно первый ход белых в игре Q xj). Далее, если fj = 1, то разыгрывается игра G(xj), а если fj = О, то разыгрывается игра Q(xj) со сдвигом иа темп (г - - 1)-й ход белых в F x) в этом случае соответствует i-y ходу чёрных в Q[xj), а (г + 1)-й ход чёрных — (г + 1)-у ходу белых в Q xj), к 1)-й ход чёрных на результат влияния ие оказывает. [c.165]

С похожей задачей столкнулся еще Александр Македонский, но он, по существу, уклонился от ее решения. Правда, фракийский оракул тоже хорош — подсовывать человеку гордиев узел, чтобы тот его распутывал. [c.107]

Тэйт оказался мудрее того фракийского оракула. Он ке стал впутывать в дело посторонних, а заинтересовал проблемой узлов знакомых математиков. Повозившись с узлами лет шестьдесят, математики довольно здорово наловчились распутывать сложные узлы. В 1928 г. они придумали инвариант узла. [c.109]

То, что карты иногда играли очень существенную роль в судьбе человека, нашло свое отражение во многих художественных произведениях. Достаточно вспомнить хотя бы знаменитую Пиковую даму Карты часто выступали в роли таинственной силы, обогащавшей одного и разорявшей другого. Карты представали и в виде оракула, предсказывающего судьбу и помогавшего как-то определить правильную линию поведения. Вот еще один пример, где карты решают судьбу человека [c.20]

Перефразировав изречение дельфийского оракула Познай самого себя , можно посоветовать каждому, кому предстоит выбрать вид или штамм бактерии для изучения конкретного аспекта метаболизма Познай свою бактерию . [c.413]

То, что сказано в священном тексте (или оракулом), истинно [c.96]

Задача 4.2. Машина Тьюринга с оракулом А — это МТ с дополнительной оракульной лентой, куда она (машина) может записывать слова, а затем за один такт работы проверять, принадлежит ли записанное [c.48]

Вернёмся к построению схемы для универсальной переборной задачи. Оракул и = I — 2 уо) уо иам задан, п мы реализовали онератор [c.72]

Задача о скрытой подгруппе. Пусть G — конечная группа, причём задано некоторое представление элементов G двоичными словами. Пмеется устройство (оракул), вычисляющее функцию / G —> Ш" со следующим свойством [c.90]

Следует иметь в виду, что сложность задач с оракулом часто отличается от СЛОЖНОСТИ обычных вычислительных задач. Классический пример — теорема о том, что IP = PSPA E [36, 37]. Оракульный аналог этого утверждения неверен [30] [c.90]

Доказательство. Для одной и той же подгруппы О существует несколько различных оракулов /. Мы будем считать, что один пз пих выбирается случайно и равновероятно. (Если алгоритм ошибается с вероятностью > 1/.3 при случайном оракуле, то ои также будет ошибаться с вероятностью > 1/3 при каком-нибудь конкретном оракуле.) Случайный оракул обладает следующим свойством если очередной ответ ад не совпадает ни с одним из предыдущих ответов г/1,. . ., ад 1, то ои равномерно распределён иа множестве Е г/1,. . ., щ 1 . Таким образом, случайный оракул эквивалентен устройству с памятью, которое на вопрос Xj выдает наименьшее число Sj j, такое что Xj - х е О. Классическую машину можно изменить таким образом, что она сама будет производить случайный выбор ад е Е ад,..., ад-1 , когда 8 = [c.91]

Пусть число вопросов к оракулу равно I 2 . Без уменьшения общности все вопросы различны. В случае О — 0 все ответы также различны, то есть. 5 = j для всех j. Теперь рассмотрим случай О = О, г , где г выбирается случайно с равномерным распределением на множестве всех ненулевых элементов группы (Жз). Тогда, независимо от используемого алгоритма,. 5 = j с вероятностью 1 — ( — 1)/(2 — 1). С вероятностью 1 — 1 1 — 1)/(2(2 — 1)) > 1/2 это имеет место для всех j = I,. . . , 1. Папомним, что у нас есть два случайных параметра г и г. Мы можем зафиксировать г таким образом, чтобы вероятность иолучення ответов Sj = j (для всех по-прежнему была больше 1/2. Посмотрим, что будет делать классическая машина в этом случае. Если оиа выдает ответ О = 0 с вероятностью 2/3, положим О = О, г — тогда выдаваемый ответ будет неверным с вероятностью > (2/3) (1/2) = 1/3. Если же вероятность ответа О = 0 меньше 2/3, положим О — 0 . [c.91]

Теперь определим квантовый аналог оппсанного выше устройства. Соответствующий квантовый оракул — это унитарный оператор [c.92]

Легко сообразить, как имитировать оракул F из Е/., имея возможность заказывать оракул из П. Пужно заказать оракул, а дальше брать отрицание от каждого результата его работы. [c.165]

Пусть есть предикат F Е, а вычисляюгций его полиномиальный алгоритм использует оракул G S. Игру, которая задаёт G[x), обозначим Q(x). Опишем теперь игру выигрыш белых в которой [c.165]

Белые выигрывают в этой игре, если (xj)j i — правильная последовательность аргументов прн обращениях к оракулу, результат нгры 6(xj) совпадает с fj, а. результат работы алгоритма для вычисления F на входе х с ответами оракула (/j) i равен 1. [c.165]

Дельфы — древнегреч. город в юго-зап. Фокиде, обще-греч. культовый центр с храмом и оракулом Апполона. [c.209]

В области химии лекарственных веществ разработана система СТРАК для анализа связей между структурой химического соединения и его биологической активностью. Экспертная система ОРАКУЛ используется для конструирования лекарств. [c.140]

Но кто же будет заниматься собственно анализом До сего времени обслуживание аппаратуры для физических методов приходилось поручать физикам. Однако практически подобная аппаратура достигла такого совершенства, что она может обслуживаться и пе специалистами. В этом заложена возможность постепенного углубленного изучения химиками физичесюзх методов анализа. Наконец, я хочу отметить последний вопрос. Наблюдается тенденция рассматривать эти физические приборы как своего рода универсальные оракулы. Эту тенденцию необходимо преодолеть. Несомненно, что физические методы обладают исключительными возможностями, но их всегда следует использовать в разумном сочетании с химическими методами анализа. [c.322]

Составители программы поставили доклад Митчела непосредственно перед моим. В тот день я очень опасался, что, сосредоточившись на предстоящем мне выступлении, упущу что-нибудь существенное из речи Митчела, всегда отличавшегося стремлением сказать за полчаса то, на что не хватило бы и целого часа. Однако тревоги оказались напрасными. За какие-то восемь месяцев, прошедших со встречи в Дрездене, Митчел изменился сильней, чем за двенадцать предшествующих лет нашего с ним знакомства. Слава, всемирное признание сделали то, чего не смогло совершить время. Куда исчез торопливый докладчик, стремящийся выплеснуть на слушателей избыток новых идей и гипотез С трибуны вещал почтенный метр, оракул из Бодмина . [c.94]

Справочник химика 21

Химия и химическая технология