ПОИСК Статьи Рисунки Таблицы Классические и квантовые коды из "Классические и квантовые вычисления" Можно строить квантовые аналоги не только для класса Р, но и для других классических сложностных классов. Мы разберём пример квантового аналога класса NP. [c.105] Частично опреде.ленная бу.лева функция — это функция F. W — О, 1, (не определено) . [c.105] И ещё одно замечание по поводу обозначений мы использовали обозначение Р и для класса полиномиально вычислимых функций, и для класса полиномиально разрешимых предикатов теперь поступим апа-логичио, используя обозиачепия Р, NP и т.п. для классов частично определённых функций. [c.106] естественно, обозначает класс полипомиальпо вычислимых частично определённых функций. Приведём модифицированное определение класса NP. [c.106] Как и раньше, q ] — полином. [c.106] Вектор Ю выполняет роль подсказки у) нз предыдущего определения. Нам удобнее считать его первым аргументом оператора (чтобы можно было в любой момент положить X константой п исключить из обозначений). [c.107] Замечание 13.1. В определении 1.3.2 кванторы по Ю включают в себя только векторы единичной длины. Аналогичное соглашение будем использовать и далее в этом разделе, выпося нормировочные множители за знак ). [c.107] Еслп вместо чистых состояний Ю рассматривать смешанные, то получается эквивалентное оиределенне максимум вероятности всё равно достигается на чистом состоянии. [c.107] Обсудим теперь соотношения между пороговыми вероятностями. Пз приведённого в онределенин 13.2 соотношения следует гораздо более сильное условие иа ро и pi. [c.107] если F x) = 0. Оценим величину р ах в этих случаях, соответственно, снизу н сверху. [c.109] Рассмотрим более интересные примеры. Для начала дадим определение квантового аналога 3-КНФ — локального гамильтониана (локальность является аналогом ограниченности числа переменных, входящих в одну дизъюнкцию). [c.110] Утверждение 13.3. -Задача ЛОКАЛЬНЫЙ ГАМИЛЬТОНИАН полна в к.лассе BQNP относите.льно по.лино.миа.льной своди.мости. [c.111] Пдея доказательства восходит к Фейнману [29] замена унитарной эволюции ие зависящим от времени гамильтонианом (т. е. переход от схемы к локальному гамильтониану). [c.111] Вернуться к основной статье