ПОИСК Статьи Рисунки Таблицы Определение квантового вычисления. Примеры из "Классические и квантовые вычисления" Пока мы описали работу квантового компьютера. Теперь пора определить, когда эта работа приводит к решению интересующей пас задачи. Определение будет похоже на определение вероятностного вычисления. [c.68] Нас интересует вероятность того, что компьютер закончит работу в состоянии вида (Р х), г), где г — любое. [c.68] Задача 8.1. Докажите, что приведенное рассуждение является корректным в квантовом случае функция MAJt реализована в виде обратимой схемы, иа вход которой подаются выходные q-биты га копий схемы и. [c.69] В квантовой постановке задача выглядит так. [c.69] Нужно вычислить значение Р(х) и найти ответ у (прн котором выполнен Л х, у)). [c.70] Результаты, о которых уже упоминалось, формулируются так (см. [31, 48]) существуют две константы С и 62 такие, что есть схема размера С гл/Х, решающая задачу для любого предиката А х,у) а для любой схемы размера 62 / существует предикат А х,у), при котором задача не решается на этой схеме [т.е. схема даёт неправильный ответ с вероятностью 1/3). [c.70] Мы разберём упрощённую постановку считаем, что ответ существует и единствен, обозначим его через уо нужно найти уо. Схема, которую мы для этого построим, будет примером прямого квантового вычисления она будет описана в терминах преобразований базисных векторов. [c.70] Построить оператор Ж, который переводит ( ) в 0 ), просто. Это = Я , где оператор Я — из стандартного базиса (см. с. 66). Действительно, 10 = ( 0) -Н 1)) , а Я ( 0) -Н 1)) 0). [c.70] реализующая оператор V, изображена иа рис. 4. Центральная часть, включающая в себя Z, и Z, реализует онератор У. В схеме используется онератор сг = К (К из стандартного базиса). [c.71] Пусть вас не смущает то, что действует только на управляемый q-бит, а меняется в результате весь вектор. Вообще, различие между чтением н записью в квантовом случае неабсолютно н зависит от выбора базиса. Приведём соответствующий пример. [c.71] Иапример, как будет выглядеть матрица оператора, схема которого изображе-рисунке Попробуйте также поме-нять базис в другом бите. [c.72] Что прп этом получается Геометрически оба оператора есть отражения относительно гиперплоскости. Подпространство С = С(Ю, Уо)) инвариантно относительно обоих операторов, а, значит, и относительно 1/. Поскольку вектор Ю принадлежит этому подпространству, достаточно рассмотреть действие УЯ на нём. [c.72] Если решается переборная задача в общей постановке (т. е. ответов может быть несколько, а может не быть вообще), требуются дополнительные технические ухищрения. Число шагов для поворота от исходного вектора к какому-нибудь вектору из нодиространства, порожденного векторами ответов, обратно пропорционально корню из числа решений. [c.73] Квантовые схемы имеют конструктивное описание, если указать точность, с которой известны матричные элементы операторов, входящих в схему. Пусть есть описание квантовой схемы Z, размера L и точности S. Элементами этой схемы могут быть любые унитарные операторы на г = 0 ogL) q-битах (так чтобы полная длина описания схемы не превышала poly(L, log(l/(5))). Обозначим оператор, реализуемый этой схемой, через Op Z). [c.73] Квантовый алгоритм для вычисления F — это однородная последовательность схем, вычисляющих F . Однородная означает, что по п можно построить описание соответствующей схемы на обычной полиномиально ограниченной машине Тьюринга. Будем говорить, что алгоритм работает за время Т(п), если размер схемы, вычисляющей F , равен Т п). [c.74] Замечание 8.1. Можно определить квантовую машину Тьюринга и неносредственно через сунериозиции различных состояний ленты МТ (первоначальное определение Д. Дойча было именно таким). Паше определение оказывается эквивалентным. [c.74] Определение 8.2. Функция F W — В принадлежит классу BQP, если есть квантовый алгоритм её вычисления, работающий за врем,я 0(п ) для некоторой константы d. [c.74] Вернуться к основной статье