База ответов ИНТУИТ

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

Количество вопросов - 336

Состояние машины Тьюринга задается тройкой (\sigma,p,q) , где бесконечное слово в алфавите \calS - это:

Какому Выберите верное утверждение:

Выберите верное утверждение:

Чему равна вероятность "события" \calM для квантового состояния, задаваемого матрицей плотности \rho и подпространства \calM:

Выберите верное утверждение:

Конечному состоянию гамильтониана, сопоставляемого схеме, отвечает:

Условием строгой формулировки вычислительной задачи является наличие:

Усиление оценки вероятностей с (1/2,2/3) до (\varepsilon,1-\varepsilon) является основанием доказательства:

Перестановка, реализуемая обратимой схемой, является (\calA - некоторое множество перестановок вида G\colon\cb^k \to \cb^k):

Любой оператор, обладающий свойствами 1)\; \rho=\rho^\dagger;\qquad 2)\; \forall\,\ket{\eta}\ \langle\eta|\rho|\eta\rangle \geq0; \qquad 3)\; Tr\rho=1

Какое значение принимает функция \MAJ(x_1,\dots,x_n), если более половины ее аргументов равны 1:

Верным является тождество:

Какая из ниже перечисленных формул является справедливой:

Какие свойства характерны классической вероятности:

Для тензорного произведения пространств, на которых действуют сомножители, справедливо:

Частичная функция f из \calA^* в \calA^* вычислима на машине Тьюринга :

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

Чему равна вероятность того, что что k случайных сдвигов не покрывают фиксированный элемент, где G - некоторая группа, а X - подмножество G:

Величина энергии, требуемая для стирания одного бита:

Условие нормировки 0\leq H_j\leq 1 означает:

Если характеристическая функция предиката вычислима на машине Тьюринга М, для которой S_М(n)=\poly(n), то

Проверка простоты числа является классическим примером задачи класса:

Функция F\colon \cb^n\to \{0,\,1,\, \langle \text{не определено}\rangle}\} принадлежит классу NP, если есть частично определенная функция R\in\P от двух переменных, такая что:

3-КНФ - это:

Условием выхода из алгоритма проверки простоты числа является:

"Если n=uv - разложение числа на взаимно простые множители, то существует взаимно однозначное соответствие между остатками от деления на n и парами остатков от деления на u и на v " - утверждает:

Для вероятностной машины Тьюринга можно определить:

В формуле |\calA|^S\cdot|\calQ|\cdot S для нахождения количества состояний системы, \calQ - это:

Авторами теоремы "Если SAT\in\P, то \P=\NP" являются:

Каким равенством выражается дуальность между классическими и фазовыми ошибками?

Если кодировки переводятся друг в друга при помощи полиномального алгоритма, то они:

В наборе \calS,\emptycell,\calA,\calQ,q_0,\delta для задания машины Тьюринга выполняется условие:

Для задания состояния машины Тьюринга обязательным является указание:

Условием разрешимости предиката является:

Тезисом Черча является утверждение:

Вершины входной степени 0 ориентированного ациклического графа помечаются:

Дизъюнктивной нормальной форме (ДНФ) соответствует:

Машина Тьюринга, имеющая состояния, в которых она может выполнить одно из нескольких действий, называется:

Какое понятие используется для определения класса NP:

Под размером входа для предиката R(x,y) в записи L(x)=\exists\, y\:\big( (|y|<q(|x|))\:\wedge\: R(x,y)\big) понимают:

Если L_1\propto L_2, то:

Если NP-полный предикат можно вычислить за время T(n), то любой предикат из NP для некоторого числа c можно вычислить за время:

Проверка транзизитивности сводимости - если L_1\propto L_2, L_2\propto L_3, то L_1\propto L_3 является достаточным доказательством утверждения:

Если предикат L принадлежит классу BPP, то выражение L(x)=1 означает, что:

Утверждение "если n- простое и n\nmid a, то a^{n-1}\equiv1\pmod n" является:

Размер схемы умножения чисел n, m столбиком определяется, как:

Условие a^{n-1}\not\equiv1\pmod n алгоритма проверки простоты числа, где a - случайное среди чисел от 1 до n:

Алгоритм проверки простоты числа с вероятностью \geq 1/2 выдает ответ:

Обозначение класса дополнений классу языков \mathrm A имеет вид:

Автором теоремы "\BPP\subset\Sigma_2\cap\Pi_2" является:

Чем объясняется то, что вероятность события \Prob[G\setminus\big( \bigcup_i g_iX\big)\ne\emptyset] не больше |G|\left(1-|X|/|G|\right)^k, где G - некоторая группа, а X - подмножество G:

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

Если число ходов ограничено p(|x|), а q=O(p(|x|)), то время работы машины Тьюринга ограничено:

Выберите верное утверждение:

Задача TQBF является полной задачей класса:

Вычислительные возможности при переходе от преобразований конечных множеств к унитарным преобразованиям конечномерных пространств:

q-бит квантового компьютера:

Выберите верное утверждение:

Определение тензорного произведения двух пространств L и M, в которых фиксированы базисы \{e_1,\dots,e_l\} и \{f_1,\dots,f_l\}:

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

Обозначение скалярного произведения в гильбертовом пространстве является запись:

Элементарному преобразованию в квантовом случае соответствует определение:

Для квантовой схемы \calA - последовательности U_l[A_l]\cdot\ldots\cdot U_1[A_1], A_j выступает в роли:

В соответствии с каким оператором действует унитарный оператор \ha{G} в пространстве \BB^{\otimes k}:

Какому условию должно удовлетворять произведение перестановок, определяющее перестановку W=U_l[A_l]\cdot\ldots\cdot U_1[A_1] в расширенном смысле:

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

Что означает символ \qxor:

Два различных логических состояния становятся одинаковыми при выполнении:

Если существует вычисление, требующее памяти L, то реализовать его можно обратимым способом с использованием памяти:

Выберите верное утверждение:

В чем заключается проблема выбора базиса в квантовых схемах:

Оператор с квантовым управлением имеет обозначение:

Если справедливо равенство \sx\bydef{\widehat\neg}=\begin{pmatrix}0&1\\1&0\end{pmatrix}, то \Lambda(\sx)=:

Матрицы \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., образующие ортонормированный базис, называются:

Если унитарный оператор U\in U(2) действует на трехмерном евклидовом пространстве (U\colon{} E\mapsto UEU^{-1}), то задаваемый изоморфизм имеет вид:

Если унитарный оператор U\in U(2) действует на трехмерном евклидовом пространстве (U\colon{} E\mapsto UEU^{-1}), для матриц Паули \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., \sx соответствует повороту вокруг оси X на:

Какое обозначение имеет норма вектора:

Что из ниже перечисленного характерно для смешанного состояния:

Чему равна вероятность получения базисного состояния, x при измерении состояния \ket\psi=\sum_x c_x\ket{x}:

Какое название имеет функция \MAJ(x_1,\dots,x_n):

За какое время квантовый компьютер вычислит значение предиката F(x)\double=\exists\, y\:\calA(x,y) (N - количество шагов):

Какой вид будет иметь запись оператора &V=I-2\ket{\xi}\bra{\xi} в матричной форме:

Если имеются операторы U=I-2\ket{y_0}\bra{y_0} и U=I-2\ket{\xi}\bra{\xi}, то:

Конструктивное описание квантовой схемы формируется:

Выберите верную формулу:

Если система из n q-битов находится в состоянии \ket\psi=\sum_{x}^{}c_x\ket{x}, то вероятность обнаружить систему в состоянии x определяется как:

Какая из ниже перечисленных формул является справедливой:

Проектор на подпространство, порожденное \ket{x}, обозначается, как:

Что из ниже перечисленного является характерным для проекторов на подпространство

Каким условиям удовлетворяют операторы вида \rho=\sum_{k}^{}p_k\ket{\xi_k}\bra{\xi_k}:

Состояние, заданное вектором (\rho=\ket{\xi}\bra{\xi}), называется:

Каким образом определяется частичный след оператора X по пространству \calN_2 (X=\sum_{m}^{} A_m\otimes B_m):

Матрицу плотности чистого состояния \rho=\ket\xi\bra\xi унитарный оператор переводит в матрицу:

В случае изометрического вложение V\colon \BB^{\otimes n} \double\to \BB^{\otimes N} в пространство большей размерности, задаваемое формулой \ket\xi\stackrel{\scriptscriptstyle V}{\mapsto} \ket\xi\otimes\ket{0^{N-n}}, матрица плотности \rho преобразуется:

Какие из ниже перечисленных условий являются обязательными для того, чтобы линейный оператор T\colon\LL(\calN)\to\LL(\calM) являлся физически реализуемым преобразованием матриц плотности:

Выполнение каких действий необходимо для доказательства физической реализации преобразования вида \rho=\sum_{j,k}^{}\rho_{jk}\ket{j}\bra{k} \stackrel{\scriptscriptstyle D}{\mapsto}\sum_{k}^{}\rho_{kk}\ket{k}\bra{k}:

Преобразование, заключающееся в обнулении внедиагональных элементов, записывается в виде:

Если имеется физически реализуемое преобразование T\colon\LL(\calN)\to\LL(\calM), причем для любого чистого состояния \rho выполняется свойство: Tr_{\calF}(T\rho)=\rho, то для любого оператора X справедливым является равенство (\gamma - некоторая фиксированная матрица плотности на пространстве \calF):

При отображении \LL(\calN) в \LL(\calN\otimes\calK), \calN - квантовая часть и \calK - классическая часть системы, результат является диагональным по отношению:

В детерминированном измерении \begin{equation}\rho\ \mapsto\ \sum_{j}^{}\PP(\rho,\calL_j)\left(\gamma^{(j)},j\right), \end{equation} \gamma^{(j)} выступает в качестве:

Какой вид имеет оператор, реализуемый квантовой схемой?

Если есть пространство состояний \calN\otimes\calK, причем первый сомножитель разложен в прямую сумму попарно ортогональных подпространств: \calN\double=\bigoplus\limits_j \calL_j, тогда всякий оператор вида W=\sum\limits_{j}^{} \Pi_{\calL_j}\otimes U_j будет называться:

Если к состоянию, описываемому матрицей плотности \rho\in\LL(\calN), подсоединить прибор с выделенным базисом, то совместное состояние системы и прибора будет описываться матрицей плотности вида:

Почему U в операторе \Lambda(U)=\Pi_0\otimes I + \Pi_1\otimes U можно разложить в сумму проекторов на собственные подпространства следующим образом: U=\sum_{j} \lambda_j\Pi_{\calL_j} , |\lambda_j|=1?

Если унитарный оператор U разложить в сумму проекторов на собственные подпространства следующим образом: U=\sum_{j} \lambda_j\Pi_{\calL_j} , |\lambda_j|=1, то \Lambda(U)=\sum_{j} (\Pi_0+\lambda_j\Pi_1)\otimes\Pi_{\calL_j}= \sum_{j}^{} \begin{pmatrix} 1&0\\ 0&\lambda_j \end{pmatrix} \otimes\Pi_{\calL_j}. В этом случае условные вероятности будут равны:

Квантовые условные вероятности \PP(k\big|j) = \left|\langle k|U_j|0\rangle \right|^2 ведут себя как обычные, если...

Продолжите фразу: условные вероятности для произведения измеряющих "разными приборами" операторов...

Верно ли, что если применить измеряющий оператор к состоянию \ket0\bra0\otimes\rho , где \rho\double\in\LL(\calN) , то вероятность наблюдения состояния k можно записать в виде:\PP\Bigl(W(\ket0\bra0\otimes\rho)W^\dagger,\,\CC(\ket{k})\otimes\calN\Bigr) \,=\, \prod\limits_{j} \PP(k\big| j) \PP(\rho, \calL_j)?

Автором "задачи о скрытой группе" является

Какую сложность имеет алгоритм нахождения скрытой группы (\ZZ_2)^k:

Как называется порядок числа a в мультипликативной группе вычетов (\ZZ/q\ZZ)^*

С какой вероятностью должен вычисляться делитель составного числа в подпрограмме для нахождения факторизации числа:

Если получено l дробей вида k_1'/t_1',\,k_2'/t_2',\dots,k_l'/t_l' то вероятность того, что наименьшее общее кратное их знаменателей отлично от t (равномерно распределенное на множестве \{0,\dots,t-1\} случайное число):

Какое свойство характерно для оператора умножения на число U_a

Какое из ниже перечисленных равенств является справедливым (с учетом тождества b\equiv a^{2^j}\pmod q):

Если требуется O(n) обращений к оракулу и каждый вопрос имеет длину O(k(n+\log k)), то размер квантовой схемы определяется как:

Каким условиям должны удовлетворять операторы U_n\colon \BB^{\otimes N_n}\to \BB^{\otimes N_n}, реализуемые однородной последовательностью квантовых схем полиномиального по n размера, чтобы функция F\colon \cb^n\to \{0,\,1,\,\} принадлежала классу BQNP:

Какому условию должно удовлетворять \eps в неравенстве F_n(x)=1 & \Longrightarrow & \exists\, \ket\xi\: \PP\Bigl(U_n\ket\xi\otimes\ket{x}\otimes\ket{0^{N_n-n-m_n}},\calM\Bigr) \geq p_1,\\ F_n(x)=0 & \Longrightarrow & \forall\, \ket\xi\: \PP\Bigl(U_n\ket\xi\otimes\ket{x}\otimes\ket{0^{N_n-n-m_n}},\calM\Bigr) \leq p_0, если F\in\BQNP

Каждое слагаемое локального гамильтониана H=\sum_{j}^{} H_j[S_j] является:

Какому классу принадлежит локальный гамильтониан:

Из каких слагаемых состоит гамильтониан, сопоставляемый схеме, действующие на пространстве \calL=\BB^{\otimes N}\otimes \CC^{L+1}:

Какое слагаемое гамильтониана H=H_{\rm in}+H_{\rm prop}+H_{\rm out} описывает эволюцию системы:

Утверждение о том, что схема, на вход которой подан вектор \ket\xi, дает ответ 1 с вероятностью не меньше, чем 1-\eps описывается формулой:

Кодовое расстояние - это:

Код исправляет kошибок:

Пусть \calN=\bigoplus_{j}\calN_j - разложение пространства \calN в прямую сумму взаимно ортогональных подпространств. Тогда для любой пары матриц плотности \rho, \gamma

Сколько будет базисных операторов для пространства \BB^{\otimes n}, образованного матрицами Паули?

Симплектический квантовый код задается условиями:

Какими способами задаются торические коды?

Выберете верные утверждения:

Что из ниже перечисленного называется классической ошибкой?

Если есть пространство состояний \calN\otimes\calK, причем первый сомножитель разложен в прямую сумму попарно ортогональных подпространств: \calN\double=\bigoplus\limits_j \calL_j, тогда измеряющим будет называться всяки оператор вида:

Чему эквивалентно условие

Сколько ошибок исправляет торический код?

Укажите верные утверждения:

Если на совместное состояние системы и прибора \rho\otimes\ket{0^m}\bra{0^m} подействовать измеряющим оператором W, то получим состояние:

Как определяется слагаемое гамильтониана H=H_{\rm in}+H_{\rm prop}+H_{\rm out}, отвечающее начальному состоянию:

Множество состояний управляющего устройства в наборе \calS,\emptycell,\calA,\calQ,q_0,\delta для задания машины Тьюринга - это:

Если имеется действие \Lambda^k(U), то :

Предикат, задающий 3-КНФ:

Какая цепочка эквивалентностей является некорректной:

Выберите неверное утверждение:

Выберите неверное утверждение:

В качестве первого сомножителя пространства \calL=\BB^{\otimes N}\otimes \CC^{L+1}, на котором действует гамильтониан, сопоставляемый схеме, выступает:

Преобразование матриц плотности \begin{equation}\rho\ \mapsto\ \sum_{j}^{}\PP(\rho,\calL_j)\left(\gamma^{(j)},j\right), \end{equation} где \gamma^{(j)}=\PP(\rho,\calL_j)^{-1}\times\Pi_{\calL_j} \rho\Pi_{\calL_j}, называется:

Специальная ортогональная группа на трехмерном евклидовом пространстве обозначается записью:

Что послужило источником интереса к обратимым вычислениям:

Укажите верное утверждение:

Континуум - это:

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

Пространство состояний квантовой системы:

Последовательность кодов называется кодами с локальными проверками, если выполнены следующие условия:

Записи пространства состояний системы из n q-битов \CC^{2^n} соответствует:

Какая пара операторов будет соответствовать соотношению XYX^{-1}Y^{-1}=\ii\sx?

Условие L(x)=0 для предиката L, принадлежащего классу NP, означает, что:

Формулировкой китайской теоремы об остатках является:

Если вероятность правильного ответа для каждого экземпляра из n запущенных машин Тьюринга равна c>1/2, то вероятность правильного ответа после голосования n машин:

Физически реализуемым является преобразование вида:

Выберите неверное утверждение:

Выберите верное утверждение:

Что из ниже перечисленного называется фазовой ошибкой?

Каким преобразованием задается отбрасывание второй системы, если есть \rho\in\LL(\calN\otimes\calF):

Какая из ниже перечисленных формул является верной:

Что из ниже перечисленного верно отражает свойство "множество содержит много элементов":

Выберите верное утверждение:

В наборе \calS,\emptycell,\calA,\calQ,q_0,\delta для задания машины Тьюринга множество S является:

Время работы машины Тьюринга определяется:

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

Выберите верное утверждение:

Выберите верное утверждение:

Предикат L принадлежит классу NP, если он представим в форме:

Сводимость по Карпу предиката L_1 к предикату L_2 обозначается:

Теорема Кука, Левина утверждает, что:

Справедливым является утверждение:

Условие существования вероятностной машины Тьюринга М и полинома p(n), причем машина М заведомо остановится за время, не превосходящее p(|x|), определяет, что:

В соответствии с алгоритмом Евклида, если делить большее число на меньшее, то длина записи меньшего числа уменьшается на константу:

Вероятность получения ответа "n - составное" для алгоритма проверки простоты составного числа n равна:

Выберите верное утверждение:

Какое обозначает запись \text{co-}\mathrm A по отношению к классу А:

Утверждение о том, что для случайных независимых g_1,\dots, g_k вероятность события \bigcup_i g_iX\double=G больше 0, содержится в записи :

Какому классу принадлежит L, если существует такая игра с полиномиальным от длины входного слова числом ходов и полиномиально вычислимым результатом, что L=\{x\:\big| Б имеет выигрышную стратегию \}(Б - игрок, имеющих имя "белые"):

За какое количество тактов машина Тьюринга с оракулом проверяет, принадлежит ли записанное на оракульной ленте слово языку \calA:

Выберите верные тождества, где \calA - язык, y_i\in\cb:

Множество состояний \cb^n=\{0,1\}^n классической системы:

Что из перечисленного является характерным для квантового компьютера:

Обозначением вектора \xi_1+\xi_2 является:

Левая половина скалярного вектора \langle\xi|\eta\rangle называется:

Какой вид имеет оператор, реализуемый квантовой схемой:

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

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

Какие из ниже перечисленных формул являются верными:

Если f(\cdot) вычислима булевой схемой размера L, то размер памяти, на которой можно вычислить функцию \exists\, x_1\:\forall\, y_1\:\dots\:\exists\, x_M\:\forall\, y_M\: f(x_1,y_1,\dots,x_M,y_M,z), равен:

Условие приближенной реализуемости:

Выберите верное утверждение

Запись SO(3) имеет следующий смысл:

Если имеется чистое состояние \ket{\psi}\in\calN\otimes\calF, то разложение Шмидта имеет вид (0<\lambda_j\le 1, \{\ket{\xi_j}\}\subset\calN и \{\ket{\eta_j}\}\subset\calF - ортонормированные вектора):

В формуле \sum_{z}^{} \bigl| \langle F(x),z|\,U\,|x,0^{N-n}\rangle\bigr|^2 \geq \varepsilon, которой должна удовлетворять квантовая схема U=U_L\cdot\ldots\cdot U_2U_1, вычисляющая F, значение \varepsilon:

Сколько экземпляров квантовой схемы U необходимо взять, чтобы уменьшить вероятность неудачи в N раз:

Выберите неверное утверждение

Формулы \PP(\ket\psi, x)=|c_x|^2 достаточно для определения:

Какая из ниже перечисленных формул является определением квантовой вероятности:

Частичный след от оператора \calA по пространству \calF имеет вид:

Если на пространстве \calN=\calN_1\otimes\calN_2 задана матрица плотности вида \rho_1\otimes\rho_2 и имеется два подпространства \calM_1\subseteq \calN_1, \calM_2\subseteq \calN_2, то справедливо равентство:

Матрицу плотности чистого состояния \rho=\ket\xi\bra\xi в матрицу \rho'=U\ket\xi\bra\xi U^\dagger переводит:

Выберите неверное утверждение:

Выберите верное утверждение:

Выберите верное утверждение:

Какой вид имеет линейный оператор?

Определите вид оператора \Lambda(U)=\Pi_0\otimes I + \Pi_1\otimes U, действующего на пространстве

Если R^{(1)}\double={\widetilde R}^{1}\otimes I, а R^{(2)}= I\otimes{\widetilde R}^{2}, тогда \PP(k_1,k_2\,\big|\,j)\double=?

Как называется следующая формула: \PP\Bigl(W(\ket0\bra0\otimes\rho)W^\dagger,\,\CC(\ket{k})\otimes\calN\Bigr) \,=\, \sum\limits_{j} \PP(k\big| j) \PP(\rho, \calL_j)?

Решение универсальной переборной задачи алгоритмом Гровера -

Какова вероятность получить делитель числа y в результате работы процедуры нахождения делителя (k - число различных простых делителей y):

Условные вероятности для оператора \prod\limits_{r=1}^s \Xi(U_a)[r,A] определяются, как (y_r- значение в r-ом бите):

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

Выберите верное утверждение:

В соответствии со свойствами квантовой механики формула \PP(z_1,\dots,z_k|\,\rho)= \Tr(X^{(z_1)}\otimes\ldots\otimes X^{(z_k)}\rho) равна:

Выберите верное утверждение:

Чему равна левая часть формулы ?=\Pi^{(0)}_1\otimes\ket{L}\bra{L}

Если A_1, A_2 - неотрицательные операторы, \calL_1, \calL_2 - их нулевые подпространства, причем \calL_1\cap \calL_2=0, ненулевые собственные числа A_1 и A_2 не меньше v, где \vt=\vt(\calL_1,\calL_2) - угол между \calL_1 и \calL_2, то справедливым является равенство:

Как накапливаются ошибки при квантовом вычислении?

Следовая норма оператора A\in\LL(\calN) равна:

В чем заключается отличие симплектического кода от классических линейных кодов?

Выберете верные утверждения:

Оператор, переводящий \ket{\xi} в \ket{0^n}:

Если Z - множество троек вида \langle\text{описание квантовой схемы } W\rangle, p_0, p_1) описанием схемы - приближенная реализация в стандартном базисе, а p_1-p_0=\Omega(n^{-\alpha}) (a>0, n - размер описания схемы). Тогда для z\in\Z F(z)=1 выполняется:

Выберите верное свойство скалярного произведения в гильбертовом пространстве:

Выберете верные утверждения:

Какой функцией является перестановка на двух битах g\colon{} \cb^2\to \cb^2:

Выберите верное утверждение:

Если имеется последовательность булевых функций F_n\colon{} \cb^n\to \cb^{m(n)}, то однородная последовательность схем, вычисляющих F_n - это:

Действие унитарного оператора на произвольные матрицы плотности задается формулой:

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

Отличием недетерминированной машины Тьюринга является:

В каком случае заведомо не существует псевдослучайных генераторов:

Порядок числа a в мультипликативной группе вычетов (\ZZ/q\ZZ)^*(a) обозначается как:

Сколько раз для нахождения факторизации числа необходимо применить подпрограмму, которая по любому составному числу вычисляет какой-то его делитель с вероятностью, не меньшей 1/2:

По какому правилу в квантовой постановке действует оракул, задающий оператор U_x:

Каким образом будут распределены классические состояния квантовой системы, находящейся в состоянии \ket\psi=\sum_{x}^{}c_x\ket{x}:

Выберите верное утверждение:

Условием остановки машины Тьюринга, находящейся в состоянии (\sigma,p,q), является:

Важнейшими ресурсами, требующимися машине Тьюринга для вычислений, является:

Схема является формулой, если:

Строка таблицы вычисления j:

Справедливым является утверждение (запись):

Если установлена принадлежность предиката L к классу BPP, существуют полином q(\cdot) и предикат R(\cdot,\cdot)\in\P, то выражение L(x)=0 означает, что:

Из утверждения "вероятность того, что объекта с нужными свойствами не существует, меньше 1" следует, что:

Использование генераторов псевдослучайных чисел является основой идеи:

В качестве \mathsf{Q}_j в булевой формуле \mathsf{Q}_1\, y_1\dots\mathsf{Q}_n\, y_n F(y_1,\dots,y_n), задаваемой задачей TQBF, где y_i\in\cb,F - некоторая логическая формула, выступает:

Какой вид имеет элемент Тоффоли:

Выберите верное утверждение:

Возможность точной реализации оператора квантовой схемой связана с использованием:

Каким условиям должна удовлетворять норма \big\| |\xi\rangle \big\| = \sqrt{\langle \xi|\xi\rangle } на пространстве операторов:

Какое условие должно выполняться, чтобы схема U=U_L\cdot\ldots\cdot U_2U_1 вычисляла F:

Выберите верное утверждение:

Полная длина квантовой схемы Z, размера L и точности не должна превышать:

В контексте классической вероятности распределение вероятностей задается:

Каким условиям эквивалентна физическая реализуемость линейного оператора T\colon\LL(\calN)\to\LL(\calM) , записанного в координатном виде T(\ket{j}\bra{k})=\sum_{j',k'} T_{(j'j)(k'k)} \ket{j'}\bra{k'}?

В случае одного q-бита обнуление внедиагональных элементов можно получить, если применить оператор \sigma^z с вероятностью:

Как называется оператор вида W=\sum\limits_{j}^{} \Pi_{\calL_j}\otimes U_j, если в пространстве состояний \calN\otimes\calK, причем первый сомножитель разложен в прямую сумму попарно ортогональных подпространств: \calN\double=\bigoplus\limits_j \calL_j?

Если применить измеряющий оператор к состоянию \ket0\bra0\otimes\rho , где \rho\double\in\LL(\calN) , то вероятность наблюдения состояния k можно записать в виде:

Какому классу принадлежит функция F\colon \cb^n\to \{0,\,1,\,\}, если существует однородная последовательность квантовых схем полиномиального по n размера, реализующих такие операторы U_n\colon \BB^{\otimes N_n}\to \BB^{\otimes N_n}, что F_n(x)=1 & \Longrightarrow & \exists\, \ket\xi\: \PP\Bigl(U_n\ket\xi\otimes\ket{x}\otimes\ket{0^{N_n-n-m_n}},\calM\Bigr) \geq p_1,\\ F_n(x)=0 & \Longrightarrow & \forall\, \ket\xi\: \PP\Bigl(U_n\ket\xi\otimes\ket{x}\otimes\ket{0^{N_n-n-m_n}},\calM\Bigr) \leq p_0.

Какому условию должно удовлетворять p_1 в неравенстве F_n(x)=1 & \Longrightarrow & \exists\, \ket\xi\: \PP\Bigl(U_n\ket\xi\otimes\ket{x}\otimes\ket{0^{N_n-n-m_n}},\calM\Bigr) \geq p_1,\\ F_n(x)=0 & \Longrightarrow & \forall\, \ket\xi\: \PP\Bigl(U_n\ket\xi\otimes\ket{x}\otimes\ket{0^{N_n-n-m_n}},\calM\Bigr) \leq p_0, если F\in\BQNP

Если Z - множество троек вида (\langle\text{описание k-локального гамильтониана } H\rangle, a, b), где k=O(1), 0\leq a<b, b-a=\Omega(n^{-\alpha}), (a>0), то для z\in Z выполняются условия:

Как выглядят коммутационные соотношения между матрицами Паули?

Как называются векторы из кодового подпространства являющиеся собственными и обладающие наименьшей энергией?

Как называются коэффициенты c_{x_1,\dots,x_n} разложения вектора \ket{\psi} по базису \{\ket{x_1,\dots,x_n}\}, \ x_j\in\cb:

Автором каких квантовых алгоритмов является П. Шор:

Последовательность перестановок U_1[A_1],\dots, U_l[A_l], где A_j - множества битов, U_j\in\calA, \calA - некоторое множество перестановок вида G\colon\cb^k \to \cb^k является:

Квантовые компьютеры:

Какая запись является верной:

Какой размер имеет схема, которой в полном базисе реализуется функция \MAJ(x_1,\dots,x_n):

Можно ли в операторе \Lambda(U)=\Pi_0\otimes I + \Pi_1\otimes U разложить U в сумму проекторов на собственные подпространства следующим образом: U=\sum_{j} \lambda_j\Pi_{\calL_j} , |\lambda_j|=1?

В играх Артура - Мерлина в качестве Артура выступает:

Какой из операторов можно считать аналогом полупрозрачного зеркала?

Запись \ket{x_1,\dots,x_n}, где x_j\in\cb обозначает:

Если распределение вероятностей имеет вид w_{jk}\double= w^{(1)}_jw^{(2)}_k, имеется совместное распределение на множестве N_1\times\N_2 и событие не зависит от исхода во втором множестве M=M_1\times\N_2, то вероятность такого события выражается как:

Для формы L(x)=\exists\, y\:\big( (|y|<q(|x|))\:\wedge\: R(x,y)\big) справедливо:

Выберите верное утверждение:

Какой вид имеет измеряющий оператор?

Для существующей недетерминированной машины Тьюринга, полинома p(n) и предиката L условие L(x)=0 означает:

Условием полиномиальной сводимости предиката L_1 к предикату L_2 является:

Выберите верное утверждение:

При двойном проведении алгоритма проверки простоты числа вероятность ошибки оказывается:

Выберите верное утверждение:

Унитарный оператор, сопоставляемый перестановке G\colon\cb^k \to \cb^k, имеет вид:

Решение проблемы выбора базиса в квантовых схемах связано с:

Чему соответствуют физическое состояние в квантовой механике:

Выберите верное утверждение:

Выберите верное утверждение:

Что будет являться произведением измеряющих операторов?

Если h_1,\dots,h_l - независимые случайные равномерно распределенные элементы абелевой группы X, то вероятность, с которой они порождают всю группу X, определяется:

Класс, входящий в иерархию классов, определяемых играми Артура - Мерлина, обозначается как:

В контексте квантовой постановки нерешаемость задачи для любого предиката \calA(x,y) на квантовой схеме, означает, что:

Чему равна суммарная длина (F(x),z) и (x,O^{N-n}) в формуле \sum_{z}^{} \bigl| \langle F(x),z|\,U\,|x,0^{N-n}\rangle\bigr|^2 \geq \varepsilon, которой должна удовлетворять квантовая схема U=U_L\cdot\ldots\cdot U_2U_1, вычисляющая F:

Выберите верное утверждение:

Что из перечисленного является характерным для тензорного произведения двух пространств L и M, в которых фиксированы базисы \{e_1,\dots,e_l\} и \{f_1,\dots,f_l\}

Выберите верное утверждение:

Какая из ниже перечисленных формул является верной:

Если подпространство \calL_1 ортогонально подпространству \calL_2, то для любой матрицы плотности \rho\in\DD(\calL_1) выполняется равенство:

Однозначно определенная совокупность инструкций по преобразованию исходных данных в результат - это:

Функция f(n) является функцией полиномиального роста, если для некоторой константы d при достаточно больших n выполняется неравенство:

Предикатом SAT(c) \Longleftrightarrow x задается:

Возможность действовать на бесконечном множестве описывается:

Классическим объектом, соответствующим унитарному оператору является:

Если F и F^{-1} вычислимы булевыми схемами размеров \leq L, то F реализуется обратимой схемой размера:

Каково действие унитарного оператора U\in U(2) в трехмерном евклидовом пространстве:

Наибольшее собственное число оператора X^\dagger X определяется как:

Обозначение оператора, реализуемого универсальной квантовой схемой, имеет вид:

Какая из ниже перечисленных формул для квантовой вероятности является верной:

Укажите верное утверждение:

Зная, что \Prob\left[\left|\frac{\sum\nolimits_{r=1}^{s}y_r}{s}-\PP(1\big|k)\right| >\delta\right]<2e^{-c\delta^{2}s}, где c>0 - константа, за сколько испытаний можно добиться вероятности ошибки \eps при фиксированном \delta:

Какого типа код Хэмминга H_r?

В задаче о скрытой подгруппе в \ZZ_k имеется "скрытая подгруппа" D\subseteq\ZZ^k, порядок которой E=\ZZ^k/D не превосходит:

За какое количество шагов классический компьютер вычислит значение предиката F(x)\double=\exists\, y\:\calA(x,y) (n - количество битов в записи y):

Сколько кодовых q-битов используют коды со сколь угодно большим кодовым расстоянием?

Состояние перехода вероятностной машины Тьюринга определяется:

Условием алгоритма проверки простоты числа n, определяющим что n - составное, где a - случайное среди чисел от 1 до n, l - нечетное, является:

Количество состояний системы, где S - память, \callQ,\calA - соответственно множество состояний управляющего устройства и алфавит рассматриваемой машины Тьюринга, определяется по формуле:

Выражение \sup_{|\xi\rangle\not=0} \frac{\big\|X |\xi\rangle\big\|}{\big\| |\xi\rangle\big\|} определяет:

Какой полиномиальный размер имеет булева функция для умножения вычетов:

Чему равно кодовое расстояние для симплектического кода \calM ?

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

Алгоритм Евклида основан на рекурсивном использовании равенства:

Чему равна вероятность того, что случайный сдвиг X не покрывает (не содержит) некоторый фиксированный элемент, где G - некоторая группа, а X - подмножество G:

Какому размеру должны удовлетворять булевы схемы, вычисляющие F и F^{-1}, чтобы F реализовалась обратимой схемой размера O(L+n):

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

Если имеется \Pi_{\calL_0}=\ket0\bra0, а \Pi_{\calL_0}=\ket1\bra1, то детерминированное измерение будет иметь вид:

При сравнении вероятностных распределений в \ell^1 - норме,если \boldsymbol p=(p_1,\dots,p_n) , \boldsymbol q=(q_1,\dots,q_n) - два распределения, то мерой их различия считаем

Для любого классического вероятностного алгоритма, делающего не более 2^{k/2} обращений к оракулу (n\geq k), существует подгруппа D\subseteq(\ZZ_2)^k и соответствующая функция f\colon (\ZZ_2)^k\to\cb^n, для которой вероятность ошибки алгоритма:

Выберите верное утверждение:

Для доказательства физической реализации преобразования вида \rho=\sum_{j,k}^{}\rho_{jk}\ket{j}\bra{k} \stackrel{\scriptscriptstyle D}{\mapsto}\sum_{k}^{}\rho_{kk}\ket{k}\bra{k} на завершающем шаге необходимым является:

При доказательстве утверждения "\BPP\subset\Sigma_2\cap\Pi_2" используется:

По какой причине копирование произвольного квантового состояния \ket{\xi}\mapsto\ket{\xi}\otimes\ket{\xi} физически нереализуемо:

Какая из ниже перечисленных формул является верной:

Вероятность обнаружить систему в конкретном базисном состоянии определяется, как: