Классические и квантовые вычисления

<<- Назад к вопросам

Полный стандартный базис образуют булевы функции:

(Отметьте один правильный вариант ответа.)

Варианты ответа

отрицание, дизъюнкция, эквивалентность

отрицание, дизъюнкция, конъюнкция(Верный ответ)

отрицание, конъюнкция

Похожие вопросы

Какие две функции необходимо включить в базис, чтобы реализовать любую функцию:

Выделенный базис для $\left(\CC^2\right)^{\otimes n}$ имеет вид:

Из каких функций состоит базис $\calA_\oplus$ :

Какому размеру должны удовлетворять булевы схемы, вычисляющие

и $F^{-1}$ , чтобы

реализовалась обратимой схемой размера O(L+n)

Матрицы $\sx=\begin{pmatrix}0&1\\1&0\end{pmatrix},\; \sy=\leftp\begin{array}{rr}0&-i\\ i&0\end{array}\rightp,\; \sz=\leftp\begin{array}{rr}1&0\\0&-1\end{array}\rightp.$ , образующие ортонормированный базис, называются:

Если

-полный предикат можно вычислить за время T(n)

, то любой предикат из

для некоторого числа

можно вычислить за время:

Перестановок на каком количестве бит является достаточным для реализации функции, заданной булевой схемой в полном базисе:

Функции, которые могут быть вычислены на машине Тьюринга, использующей память, ограниченную полиномом от длины входного слова относятся к классу:

Если существует квантовый алгоритм вычисления функции $F\colon\cb^*\to\cb^*$ , работающий за время O(n^d)

для некоторой константы

, то функция $F\colon\cb^*\to\cb^*$