Главная / Алгоритмы и дискретные структуры / Классические и квантовые вычисления

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

Правильные ответы выделены зелёным цветом.
Все ответы: Этот курс предназначен для первоначального знакомства с новой быстро развивающейся и популярной областью исследований - теорией квантовых вычислений.

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

(1) вычислительная задача

(2) алгоритм

(3) функция

Матрицу плотности чистого состояния math

унитарный оператор переводит в матрицу:

(1)

(2)

(3) нет верного ответа

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

(1)

(2)

(3)

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

(1) является единственным нетривиальным использованием квантовых свойств для вычислений

(2) дает следствия для теории сложности вычислений

(3) дает полиноминальное ускорение

Если требуется math

обращений к оракулу и каждый вопрос имеет длину math

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

(1)

(2)

(3)

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

(1) линейно

(2) экспоненциально

(3) квантовое вычисление не чувствительно к погрешностям

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

(1) недетерминированной

(2) детерминированной

(3) переходной

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

(1) вероятностной

(2) детерминированной

(3) недетерминированной

(4) переходной

Обозначение класса дополнений классу языков math

имеет вид:

(1)

(2)

(3)

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

(1) квантовой механикой

(2) классической механикой

(3) нет верного ответа

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

(1) перестановка

(2) обратимая функция

(3) следовая норма

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

(1) бесконечное множество унитарных операторов

(2) конечное множество унитарных операторов

(3) нет верного ответа

Чему равна вероятность получения базисного состояния, math

при измерении состояния math

(1)

(2)

(3)

Если система из math

q-битов находится в состоянии math

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

(1)

(2)

(3)

В наборе

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

(1)

(2)

- некоторый элемент math

(3)

- некоторая функция из math

Каким преобразованием задается отбрасывание второй системы, если есть math

(1)

(2)

(3)

Если есть пространство состояний math

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

, тогда всякий оператор вида math

будет называться:

(1) линейный

(2) измеряющим

(3) унитарный

Для любого классического вероятностного алгоритма, делающего не более math

обращений к оракулу ( math

), существует подгруппа math

и соответствующая функция math

, для которой вероятность ошибки алгоритма:

(1)

(2)

(3)

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

(1) детерминированная полиномиальная машина Тьюринга

(2) вероятностная полиномиальная машина Тьюринга

(3) недетерминированная полиномиальная машина Тьюринга

Код исправляет math

ошибок:

(1) если

(2) если

(3) если

Условие

для предиката math

, принадлежащего классу math

, означает, что:

(1) на любом пути вычисления ответа "да" не получается

(2) существует путь вычисления, дающий ответ "да" за время, не превосходящее math

(3) нет верного ответа

Условие существования вероятностной машины Тьюринга math

и полинома math

, причем машина math

заведомо остановится за время, не превосходящее math

, определяет, что:

(1) предикат math

принадлежит классу BPP

(2) предикат math

принадлежит классу PSPACE

(3) предикат math

принадлежит классу NP

Автором теоремы " math

" является:

(1) Лаутеман

(2) Кук, Левин

(3) Черч

Множество состояний math

классической системы:

(1) конечно

(2) имеет мощность math

(3) имеет мощность math

Последовательность перестановок math

, где

- множества битов, math

- некоторое множество перестановок вида math

является:

(1) обратимой квантовой схемой

(2) обратимой классической схемой

(3) квантовой схемой

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

(1)

(2)

(3)

Чему равна суммарная длина math

в формуле

, которой должна удовлетворять квантовая схема math

, вычисляющая math

(1)

(2)

(3)

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

(1) бра-вектору

(2) кет-вектору

(3) вектору единичной длины

Состояние машины Тьюринга задается тройкой math

, где бесконечное слово в алфавите math

- это:

(1)

(2)

(3)

Каким условиям эквивалентна физическая реализуемость линейного оператора math

, записанного в координатном виде math

(1)

(2)

(3)

- неотрицательная матрица (по парам индексов)

Если к состоянию, описываемому матрицей плотности math

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

(1)

(2)

(3)

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

(1) алгоритм нахождения скрытой группы

(2) алгоритм разложения числа на простые множители

(3) алгоритм вычисления дискретного логарифма

Какому условию должно удовлетворять math

в неравенстве math

, если

(1)

(2)

(3)

Следовая норма оператора math

равна:

(1)

(2)

(3)

Предикат

принадлежит классу math

, если он представим в форме:

(1)

(2)

(3)

Если установлена принадлежность предиката math

к классу BPP, существуют полином math

и предикат math

, то выражение math

означает, что:

(1) доля слов math

длины

, для которых выполнено math

, больше

(2) доля слов math

длины

, для которых выполнено math

, меньше

(3) доля слов math

длины

, для которых выполнено math

, больше

Утверждение о том, что для случайных независимых math

вероятность события math

больше 0, содержится в записи :

(1)

(2)

(3)

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

(1) это пространство над полем комплексных чисел

(2) конечномерное

(3) имеет размерность math

(4) имеет размерность math

Какой функцией является перестановка на двух битах math

(1) обратимой

(2) линейной

(3) нелинейной

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

(1) базис, содержащий все унитарные операторы, действующие на парах q-битов, позволяет реализовать любой унитарный оператор

(2) все операторы на одном q-бите в сочетании с оператором math

образуют полный базис

(3) количество существующих унитарных операторов бесконечно

Какое название имеет функция math

(1) функция базиса

(2) функция голосования

(3) обратимая функция

Проектор на подпространство, порожденное math

, обозначается, как:

(1)

(2)

(3)

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

(1) функция math

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

(2) любая машина Тьюринга вычисляет ровно одну функцию

(3) любая машина Тьюринга вычисляет заранее определенное количество функций

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

(1)

(2)

(3) нет верного ответа

Определите вид оператора math

, действующего на пространстве

(1) линейный

(2) измеряющим

(3) унитарный

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

(1) не меньше math

(2) не меньше math

(3) не больше math

Если

- множество троек вида math

описанием схемы - приближенная реализация в стандартном базисе, а math

(

- размер описания схемы). Тогда для math

выполняется:

(1) если существует вектор math

, при действии на который в первом бите получится 1 с вероятностью, большей math

(2) если существует вектор math

, при действии на который в первом бите получится 1 с вероятностью, меньшей math

(3) если для всех math

вероятность получить в первом бите 1 меньше math

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

(1) они используют math

(2) они используют math

(3) они используют math

Условием полиномиальной сводимости предиката math

к предикату math

является:

(1) существование функции math

, что

(2) существование функции math

, что

(3) существование функции math

, что

Утверждение "если math

- простое и math

, то

" является:

(1) малой теоремой Ферма

(2) китайской теоремой об остатках

(3) теоремой Кука, Левина

Чем объясняется то, что вероятность события math

не больше

, где

- некоторая группа, а math

- подмножество math

(1) вероятность объединения событий не меньше суммы вероятностей этих событий

(2) вероятность объединения событий не больше суммы вероятностей этих событий

(3) вероятность объединения событий не больше разности вероятностей этих событий

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

, в которых фиксированы базисы math

(1) это пространство с базисом из элементов math

(2) размерность равна произведению размерностей сомножителей

(3) размерность равная размерности первого сомножителя

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

(1) элемент Тоффоли math

(2) отрицание math

(3) конъюнкция (логическое И)

Какая пара операторов будет соответствовать соотношению math

(1)

(2)

(3)

За какое время квантовый компьютер вычислит значение предиката math

(

- количество шагов):

(1)

(2)

(3)

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

(1) функцией math

(2) вектором состояния math

(3) нет верного ответа

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

(1) характеристическая функция равна 0

(2) характеристическая функция вычислима

(3) характеристическая функция равна 1

По какой причине копирование произвольного квантового состояния math

физически нереализуемо:

(1) операция является линейной

(2) операция является нелинейной

(3) нет верного ответа

Если унитарный оператор math

разложить в сумму проекторов на собственные подпространства следующим образом: math

, то

. В этом случае условные вероятности будут равны:

(1)

(2)

(3) нет верного ответа

Если получено math

дробей вида math

то вероятность того, что наименьшее общее кратное их знаменателей отлично от math

(равномерно распределенное на множестве math

случайное число):

(1) больше math

(2) меньше math

(3) меньше math

Условие нормировки math

означает:

(1)

- отрицательно полуопределенные

(2)

- положительно полуопределенные

(3) нет верного ответа

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

(1)

(2)

(3) нет верного ответа

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

(1)

(2)

(3)

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

(1)

(2)

(3)

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

(1)

(2)

(3)

Выделенный базис для math

имеет вид:

(1)

(2)

(3)

Что означает символ math

(1) эрмитово сопряженный оператор

(2) обратимое копирование бита

(3) следовая норма

Каково действие унитарного оператора math

в трехмерном евклидовом пространстве:

(1)

(2)

(3)

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

(1)

(2)

(3) нет верного ответа

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

(1)

(2)

(3)

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

(1) каждая машина Тьюринга math

вычисляет частичную функцию math

из

(2) предикат от нескольких переменных разрешим, если его характеристическая функция вычислима

(3) любой алгоритм может быть реализован машиной Тьюринга

В случае одного q-бита обнуление внедиагональных элементов можно получить, если применить оператор math

с вероятностью:

(1)

(2)

(3)

Квантовые условные вероятности math

ведут себя как обычные, если...

(1) квантовые условные вероятности никогда не ведут себя как обычные

(2) рассматриваются произведения измеряющих операторов, построенных на разных ортогональных разложениях пространства состояний

(3) рассматриваются произведения измеряющих операторов, построенных на одном и том же ортогональном разложении пространства состояний

Условные вероятности для оператора math

определяются, как ( math

- значение в math

-ом бите):

(1)

(2)

(3)

В качестве первого сомножителя пространства math

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

(1) пространство, на котором действует схема

(2) пространство счетчика шагов

(3) нет верного ответа

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

(1)

(2)

(3)

Предикатом math

задается:

(1) выполнимость

(2) сложность

(3) сводимость

Условие

алгоритма проверки простоты числа, где math

- случайное среди чисел от 1 до math

(1) определяет, что math

- cоставное

(2) определяет, что math

- простое

(3) не является определяющим

Количество состояний системы, где math

- память,

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

(1)

(2)

(3)

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

(1)

(2)

(3)

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

(1) вопрос о необходимой энергии для квантовых вычислений

(2) вопрос о необходимой энергии для классических вычислений

(3) вопрос о необходимой времени для квантовых вычислений

Если унитарный оператор math

действует на трехмерном евклидовом пространстве ( math

), для матриц Паули math

соответствует повороту вокруг оси X на:

(1) 90 градусов

(2) 180 градусов

(3) 45 градусов

Оператор, переводящий math

(1)

(2)

(3)

Каким условиям удовлетворяют операторы вида math

(1)

(2)

(3)

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

(1) имеются ссылки на другие части формулы

(2) каждая вспомогательная переменная используется в правой части присваиваний только один раз

(3) результатом вычисления является math

Если подпространство math

ортогонально подпространству math

, то для любой матрицы плотности math

выполняется равенство:

(1)

(2)

(3)

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

(1) нет верного ответа

(2) складываются

(3) перемножаются

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

(1)

(2)

(3)

Чему равна левая часть формулы math

(1)

(2)

(3)

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

(1) отличия между этими кодами нет

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

(3) в классических линейных кодах кодовое расстояние определяется как наименьшая норма вектора из подпространства с выкинутым нулем, а у симплектических кодов нуль раздувается до подпространства

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

(1) если

, то

- NP-полная

(2) нет верного ответа

(3) если

- NP-полная, math

, то

- NP-полная

Вероятность получения ответа " math

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

(1)

(2)

(3)

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

(1) за один такт

(2) за два такта

(3) за три такта

Левая половина скалярного вектора math

называется:

(1) бра-вектором

(2) кет-вектором

(3) гиль-вектором

Если существует вычисление, требующее памяти math

, то реализовать его можно обратимым способом с использованием памяти:

(1)

(2)

(3)

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

(1)

(2)

(3)

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

(1) указанием точности, с которой известны матричные элементы операторов схемы

(2) указанием квантовой вероятности

(3) нет верного ответа

Состояние, заданное вектором ( math

), называется:

(1) чистым

(2) смешанным

(3) обобщенным

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

(1) дизъюнкция конъюнкций литералов

(2) конъюнкция дизъюнкций литералов

(3) отрицание дизъюнкций литералов

(4) нет верного ответа

Преобразование матриц плотности math

где

, называется:

(1) недетерминированным измерением

(2) детерминированным измерением

(3) детерминированным измерением

Как называется следующая формула: math

(1) формула полной вероятности

(2) формула условной вероятности

(3) эта формула не имеет специального названия

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

(1) Саймоном

(2) Шором

(3) Куком

Утверждение о том, что схема, на вход которой подан вектор math

, дает ответ 1 с вероятностью не меньше, чем math

описывается формулой:

(1)

(2)

(3)

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

(1) торические коды могут задаваться только вершинами

(2) торические коды могут задаваться только гранями

(3) торические коды могут задаваться и вершинами и гранями

(4) кодовое расстояние для симплектического кода math

равно

3-КНФ - это:

(1) конъюнкция отрицаний, каждая из которых содержит три литерала

(2) дизъюнкция конъюнкций, каждая из которых содержит три литерала

(3) конъюнкция дизъюнкций, каждая из которых содержит три литерала

Усиление оценки вероятностей с math

до

является основанием доказательства:

(1) китайской теоремы об остатках

(2) малой теоремы Ферма

(3) теоремы math

Задача

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

(1)

(2)

(3)

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

(1)

(2)

(3)

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

(1) все физические законы на микроуровне являются обратимыми

(2) избежать потерь энергии, связанных с необратимостью вычислений невозможно

(3) избежание потерь энергии, связанных с необратимостью вычислений возможно

Наибольшее собственное число оператора math

определяется как:

(1)

(2)

(3)

Если имеется последовательность булевых функций math

, то однородная последовательность схем, вычисляющих math

- это:

(1) классический алгоритм

(2) квантовый алгоритм

(3) специальная унитарная группа

Если на пространстве math

задана матрица плотности вида math

и имеется два подпространства math

, то справедливо равентство:

(1)

(2)

(3) нет верного ответа

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

(1) способа кодировки входных данных

(2) внешнего алфавита

(3) ни один из перечисленных

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

(1)

(2)

(3)

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

(1)

(2)

(3)

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

(1) Саймон

(2) Гровер

(3) Черч

Функция

принадлежит классу NP, если есть частично определенная функция math

от двух переменных, такая что:

(1)

(2)

(3)

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

(1) кодирование повышает устойчивость квантового состояния

(2) код

исправляет ошибки из множества math

, если для любых math

из

следует

(3) код

исправляет ошибки из множества math

, если для любых math

из

следует

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

(1) класс NP определен только для предикатов

(2) NP - класс предикатов, вычислимых за полиномиальное время недетерминированными машинами Тьюринга

(3) недетерминированные машины Тьюринга имеют несколько путей вычисления

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

(1) результатом некоторого случайного процесса

(2) заранее определенным состоянием

(3) предыдущим состоянием

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

(1)

(2)

(3)

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

(1) используют возможности, не доступные обычным компьютерам

(2) выполняют преобразования на конечных множествах состояний

(3) выполняют унитарные преобразования

Унитарный оператор, сопоставляемый перестановке math

, имеет вид:

(1)

(2)

(3)

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

(1) необходимостью содержания бесконечного множества элементов в полном базисе

(2) возможностью ослабления условия точной реализуемости оператора схемой

(3) необходимостью введения эрмитово совпряженного оператора

Какое условие должно выполняться, чтобы схема math

вычисляла

(1) для любого math

(2) для любого math

(3) для любого math

Каким образом будут распределены классические состояния квантовой системы, находящейся в состоянии math

(1)

(2)

(3)

В наборе

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

(1) множеством состояний управляющего устройства

(2) алфавитом

(3) внешним алфавитом

В случае изометрического вложение math

в пространство большей размерности, задаваемое формулой math

, матрица плотности math

преобразуется:

(1)

(2)

(3)

Если есть пространство состояний math

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

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

(1)

(2)

(3)

Если

- независимые случайные равномерно распределенные элементы абелевой группы math

, то вероятность, с которой они порождают всю группу math

, определяется:

(1)

(2)

(3)

Какому классу принадлежит функция math

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

размера, реализующих такие операторы math

, что

(1) NP

(2) BQNP

(3) BPP

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

(1) типа

(2) типа

(3) типа

Для существующей недетерминированной машины Тьюринга, полинома math

и предиката L условие math

означает:

(1) существует путь вычисления, дающий ответ "да" за время, не превосходящее math

(2) не существует пути вычисления, дающий ответ "да" за время, не превосходящее math

(3) на любом пути вычисления ответа "да" не получается

Если предикат math

принадлежит классу BPP, то выражение math

означает, что:

(1) вероятностная машина Тьюринга с вероятностью большей math

дает ответ "нет"

(2) вероятностная машина Тьюринга с вероятностью большей math

дает ответ "да"

(3) вероятностная машина Тьюринга с вероятностью меньшей math

дает ответ "да"

При доказательстве утверждения " math

" используется:

(1) тождественность класса BPP относительно дополнений

(2) замкнутость класса BPP относительно дополнений

(3) открытость класса BPP относительно дополнений

(4) нет верного ответа

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

(1) это элементарное состояние

(2) имеет два выделенных состояния

(3) имеет несколько выделенных состояний

Перестановка, реализуемая обратимой схемой, является ( math

- некоторое множество перестановок вида math

(1) последовательностью перестановок math

(2) произведением перестановок math

(3) обратимой классической схемой

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

(1)

(2)

(3)

Сколько экземпляров квантовой схемы math

необходимо взять, чтобы уменьшить вероятность неудачи в math

раз:

(1)

(2)

(3) нет верного ответа

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

(1)

(2)

(3)

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

(1) бесконечного слова в алфавите math

(2) неотрицательного целого числа

(3) состояния управляющего устройства math

(4) ничего из перечисленного

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

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

(1)

для любого math

(2)

для любого math

(3) нет верного ответа

Если на совместное состояние системы и прибора math

подействовать измеряющим оператором math

, то получим состояние:

(1)

(2)

(3)

Как называется порядок числа math

в мультипликативной группе вычетов math

(1) норма

(2) амплитуда

(3) период

Какому условию должно удовлетворять math

в неравенстве math

, если

(1)

(2)

(3)

Пусть

- разложение пространства math

в прямую сумму взаимно ортогональных подпространств. Тогда для любой пары матриц плотности math

(1)

(2)

(3)

Под размером входа для предиката math

в записи

понимают:

(1)

(2)

(3)

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

(1) P

(2) NP

(3) BPP

Чему равна вероятность того, что случайный сдвиг math

не покрывает (не содержит) некоторый фиксированный элемент, где math

- некоторая группа, а math

- подмножество math

(1)

(2)

(3)

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

(1) базисное состояние math

(2) преобразования - это функции из math

(3) преобразования - это унитарные операторы, то есть операторы, сохраняющие длину вектора math

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

(1) два

(2) четыре

(3) три

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

(1)

(2)

(3)

Какое значение принимает функция math

, если более половины ее аргументов равны 1:

(1)

(2)

(3)

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

(1)

|c_x|=|\langle \psi|x\rangle |^2=\langle \psi \overbrace{|x\rangle \langle x|}^{\vbox to2pt{\vss\hbox{$\scriptstyle\Pi_x$}}}\psi\rangle,

(2)

|c_x|^2=|\langle \psi|x\rangle |=\langle \psi \overbrace{|x\rangle \langle x|}^{\vbox to2pt{\vss\hbox{$\scriptstyle\Pi_x$}}}\psi\rangle,

(3)

|c_x|^2=|\langle \psi|x\rangle |^2=\langle \psi \overbrace{|x\rangle \langle x|}^{\vbox to2pt{\vss\hbox{$\scriptstyle\Pi_x$}}}\psi\rangle,

Частичная функция math

из

вычислима на машине Тьюринга :

(1) если существует машина Тьюринга math

, для которой math

(2) если существует машина Тьюринга math

, для которой math

(3) всегда

Для доказательства физической реализации преобразования вида math

на завершающем шаге необходимым является:

(1) взятие частичного следа по добавленным битам

(2) добавление нулевых битов

(3) обратимое копирование исходных битов

Почему

в операторе math

можно разложить в сумму проекторов на собственные подпространства следующим образом: math

(1) поскольку math

- унитарный оператор

(2) поскольку math

- измеряющий оператор

(3) поскольку math

- линейный оператор

Какова вероятность получить делитель числа math

в результате работы процедуры нахождения делителя ( math

- число различных простых делителей math

(1) не меньше, чем math

(2) не меньше, чем math

(3) не больше, чем math

Каждое слагаемое локального гамильтониана math

является:

(1) эрмитовым оператором, действующим на множестве q-битов math

(2) проектором, действующим на множестве q-битов math

(3) оператором с квантовым управлением

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

(1)

(2)

(3)

Сводимость по Карпу предиката math

к предикату math

обозначается:

(1)

(2)

(3)

"Если

- разложение числа на взаимно простые множители, то существует взаимно однозначное соответствие между остатками от деления на math

и парами остатков от деления на math

и на

" - утверждает:

(1) китайская теорема об остатках

(2) малая теорема Ферма

(3) теорема Черча

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

(1) сокращения времени вычисления функций из класса BPP менее math

(2) удержании времени вычисления функций из класса BPP на math

(3) сокращения времени вычисления функций из класса NP менее math

Записи пространства состояний системы из math

q-битов

соответствует:

(1)

(2)

(3)

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

(1)

(2)

(3)

Матрицы

, образующие ортонормированный базис, называются:

(1) матрицами Паули

(2) матрицами Черча

(3) тензорными матрицами

За какое количество шагов классический компьютер вычислит значение предиката math

(

- количество битов в записи y):

(1)

(2)

(3)

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

(1)

(2)

(3)

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

(1) максимальным (по всем входам) количеством тактов, которое проработает math

до остановки

(2) положением головки при вычислениях на входах

(3) нет верного ответа

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

(1)

(2)

(3)

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

(1) так как math

- линейный оператор, его можно разложить в сумму проекторов на собственные подпространства: math

(2) так как math

- унитарный оператор, его можно разложить в сумму проекторов на собственные подпространства: math

(3) так как math

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

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

(1) обозначение несократимой дроби, представляющей рациональное число math

, имеет вид math

(2) для умножения вычетов существует булева схема полиномиального размера math

(3) в контексте квантовых вычислений пределы орбиты числа math

- это цикл перестановки, которому принадлежит math

Если

- множество троек вида math

, где

, (

), то для

выполняются условия:

(1)

если у

есть собственное число, не меньшее math

(2)

если у

есть собственное число, не большее math

(3)

если все собственные числа math

больше

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

(1)

(2)

(3) нет верного ответа

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

(1) следствием сходимости предиката math

к предикату math

является

(2) сводимость по Карпу называют полиномиальной сводимостью

(3) если любой предикат из math

сводится к math

, то предикат math

называется math

-полным

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

(1) на каждом шаге

(2) остается неизменной

(3) за каждый два шага

Какому классу принадлежит math

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

Б имеет выигрышную стратегию math

(Б - игрок, имеющих имя "белые"):

(1)

(2)

(3)

Как называются коэффициенты math

разложения вектора math

по базису

(1) q-биты

(2) коэффициенты комплексного сопряжения

(3) амплитуды

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

(1)

(2) нет верного ответа

(3)

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

(1)

(2)

(3)

В контексте квантовой постановки нерешаемость задачи для любого предиката math

на квантовой схеме, означает, что:

(1) схема дает неправильный ответ с вероятностью math

(2) схема дает неправильный ответ с вероятностью math

(3) схема дает правильный ответ с вероятностью math

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

(1) если

то

(2) если

то

(3) если

то

Функция

является функцией полиномиального роста, если для некоторой константы math

при достаточно больших math

выполняется неравенство:

(1)

(2)

(3)

Если имеется физически реализуемое преобразование math

, причем для любого чистого состояния math

выполняется свойство: math

, то для любого оператора math

справедливым является равенство ( math

- некоторая фиксированная матрица плотности на пространстве math

(1)

(2)

(3)

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

(1) измеряющий оператор

(2) унитарный оператор

(3) линейный оператор

Зная, что

, где

- константа, за сколько испытаний можно добиться вероятности ошибки math

при фиксированном math

(1)

(2)

(3)

Из каких слагаемых состоит гамильтониан, сопоставляемый схеме, действующие на пространстве math

(1)

(2)

(3)

(4)

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

(1)

, где все

коммутируют

(2)

, где все

коммутируют

(3)

, где все

коммутируют

Авторами теоремы "Если math

, то

" являются:

(1) Черч

(2) Левин

(3) Кук

(4) Карп

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

(1) если

- нечетное и больше 2

(2) если из math

извлекается нацело корень math

- й степени при math

(3) если

- четное и больше 2

В формуле

для нахождения количества состояний системы, math

- это:

(1) используемая системой память

(2) алфавит рассматриваемой машины Тьюринга

(3) множество состояний управляющего устройства

Обозначением вектора math

является:

(1)

(2)

(3)

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

(1) конечна

(2) бесконечно мала

(3)

Если имеется действие math

, то :

(1) на подпространстве, порожденном векторами math

, действует оператор math

(2) на ортогональном дополнении к подпространству, порожденному векторами math

, действует тождественный оператор

(3) нет верного ответа

Если имеются операторы math

, то:

(1) подпространство math

инвариантно относительно обоих операторов

(2) оба оператора есть отражения относительно гиперплоскости подпространство math

инвариантно оператора math

(3) подпространство math

инвариантно оператора math

Любой оператор, обладающий свойствами math

(1) матрицей плотности

(2) матрицей Паули

(3) эрмитово сопряженный оператор

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

(1) исходными переменными

(2) числами, указывающими номера аргументов

(3) переменными, описывающими результат работы схемы

При отображении math

- квантовая часть и math

- классическая часть системы, результат является диагональным по отношению:

(1) ко второй компоненте

(2) к первой компоненте

(3) нет верного ответа

Если

, а

, тогда

(1)

(2)

(3)

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

(1) точность определения собственных чисел полиномиально зависит от размера схемы

(2) если полиномиальная схема есть для самого оператора math

, то ее можно получить для math

(3) определение собственных чисел произвольного оператора производится с высокой точностью

Какое слагаемое гамильтониана math

описывает эволюцию системы:

(1)

(2)

(3)

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

(1) задается гранями

(2) задается вершинами

(3) нет верного ответа

Проверка транзизитивности сводимости - если math

, то

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

(1) если

, то

(2) если

, то

(3) если

, то

- NP-полная

Алгоритм проверки простоты числа с вероятностью math

выдает ответ:

(1) "

- составное", если math

- простое

(2) "

- простое", если math

- простое

(3) "

- составное", если math

- составное

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

(1)

(2)

(3)

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

(1) скалярное произведение антилинейно по первому аргументу и линейно по второму

(2) бра- и кет-векторы находятся во взаимно однозначном соответствии

(3) унитарный оператор - это линейный оператор, сохраняющий скалярное произведение

Если

вычислима булевой схемой размера math

, то размер памяти, на которой можно вычислить функцию math

, равен:

(1)

(2)

(3)

Каким условиям должна удовлетворять норма math

на пространстве операторов:

(1)

(2)

(3)

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

(1)

(2)

(3)

Чему равна вероятность "события" math

для квантового состояния, задаваемого матрицей плотности math

и подпространства math

(1)

(2)

(3)

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

(1) количество присваиваний в схеме называется ее размером

(2) схемная сложность функции math

в базисе

- это максимальный размер схемы в базисе math

, вычисляющей функцию math

(3) переход от одного полного конечного базиса к другому полному конечному базису не меняет схемную сложность

В детерминированном измерении math

выступает в качестве:

(1) результата измерений

(2) состояния измеряемой системы до измерения

(3) состояния измеряемой системы после измерения и получения результата

Если применить измеряющий оператор к состоянию math

, где

, то вероятность наблюдения состояния math

можно записать в виде:

(1)

(2)

(3)

В задаче о скрытой подгруппе в math

имеется "скрытая подгруппа" math

, порядок которой math

не превосходит:

(1)

(2)

(3)

Если

- неотрицательные операторы, math

- их нулевые подпространства, причем math

, ненулевые собственные числа math

не меньше

, где

- угол между math

, то справедливым является равенство:

(1)

(2)

(3)

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

(1) возбужденными состояниями

(2) основными состояниями

(3) нет верного ответа

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

(1)

(2)

(3)

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

(1) повторение опытов за полиномиальное время экспоненциально уменьшает оценку вероятности ошибки

(2) повторение опытов за полиномиальное время не меняет размер входа math

(3) повторение опытов за полиномиальное время экспоненциально увеличивает оценку вероятности ошибки

В качестве math

в булевой формуле math

задаваемой задачей math

, где

- некоторая логическая формула, выступает:

(1)

(2)

(3) нет верного ответа

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

(1)

равный

(2)

равный

(3)

равный

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

(1) добавление квантора по булевой переменной уменьшает требуемую память не более чем на константу битов

(2) добавление квантора по булевой переменной увеличивает требуемую память не менее чем на константу битов

(3) добавление квантора по булевой переменной увеличивает требуемую память не более чем на константу битов

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

(1) матрицы ранга 1

(2) эквивалентность классическому распределению вероятностей

(3) задание с помощью матрицы плотности

Если существует квантовый алгоритм вычисления функции math

, работающий за время math

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

, то функция math

(1) принадлежит классу BPP

(2) принадлежит классу BPP и BQP

(3) принадлежит классу BQP

Если распределение вероятностей имеет вид math

, имеется совместное распределение на множестве math

и событие не зависит от исхода во втором множестве math

, то вероятность такого события выражается как:

(1)

, где

(2)

, где

(3)

, где

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

(1) разумны

(2) неразумны

(3) эквивалентны

Матрицу плотности чистого состояния math

в матрицу

переводит:

(1) унитарный оператор

(2) проектор

(3) оператор с квантовым управлением

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

(1)

(2)

(3)

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

(1) косвенным свидетельством превосходства по скорости квантовых вычислений над классическими является задача с оракулом

(2) доказано, что квантовые вычисления значительно превосходят по скорости классические вероятностные вычисления

(3) любой классический вероятностный алгоритм является экспоненциальным

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

(1) MA

(2) NP

(3) BPP

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

(1)

(2)

(3)

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

(1) наличие нескольких путей вычисления

(2) наличие функции переходов

(3) возможность выбора перехода на каждом такте работы

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

(1) вероятность того или иного ответа

(2) выдаваемый ответ

(3) нет верного ответа

Какое обозначает запись math

по отношению к классу А:

(1) класс дополнений

(2) эрмитово сопряженный оператор

(3) множество конечных слов в алфавите math

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

(1) увеличиваются

(2) уменьшаются

(3) не изменяются

(4) изменение в ту или иную сторону научно не доказано

В соответствии с каким оператором действует унитарный оператор math

в пространстве math

(1)

(2)

(3)

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

(1) предназначено для решения проблемы выбора базиса в квантовых схемах

(2) является заменой условия точной реализуемости

(3) нет верного ответа

В формуле

, которой должна удовлетворять квантовая схема math

, вычисляющая math

, значение math

(1)

(2)

(3)

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

(1) амплитуды

(2) перестановки

(3) нормы

Множество состояний управляющего устройства в наборе math

для задания машины Тьюринга - это:

(1)

(2)

(3)

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

(1) физически реализуемые преобразования матриц плотности - это композиции любого числа преобразований унитарным оператором и взятия частичного следа

(2) изометрическое вложение сохраняет скалярное произведение

(3) унитарный оператор переводит матрицу плотности чистого состояния math

в матрицу

Как называется оператор вида math

, если в пространстве состояний math

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

(1) линейный

(2) измеряющим

(3) унитарный

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

(1)

(2)

(3)

Каким условиям должны удовлетворять операторы math

, реализуемые однородной последовательностью квантовых схем полиномиального по math

размера, чтобы функция math

принадлежала классу BQNP:

(1)

(2)

(3)

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

(1) код Хэмминга - это код типа math

(2) код Хэмминга - это код типа math

(3) код исправляет math

ошибок если math

(4) код Хэмминга - это самая простая схема кодирования

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

(1) понятие недетерминированной машины Тьюринга

(2) понятие полиномиально вычислимого предиката от одной переменной

(3) понятие полиномиально вычислимого предиката от двух переменных

Если вероятность правильного ответа для каждого экземпляра из math

запущенных машин Тьюринга равна math

, то вероятность правильного ответа после голосования math

машин:

(1) не меньше math

, где

(2) не меньше math

, где

(3) не больше math

, где

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

(1)

(2)

(3)

Запись

, где

обозначает:

(1) линейная комбинация базисных состояний

(2) произвольное состояние системы

(3) базисные состояния системы

Какому условию должно удовлетворять произведение перестановок, определяющее перестановку math

в расширенном смысле:

(1)

(2)

(3)

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

(1) эрмитово сопряженного оператора

(2) оператора с квантовым управлением

(3) оператора проектирования

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

(1) в формуле math

, которой должна удовлетворять квантовая схема math

, вычисляющая вычисляющая выбор math

является существенным

(2) в формуле math

, которой должна удовлетворять квантовая схема math

, вычисляющая вычисляющая выбор math

не является существенным

(3) в формуле math

, которой должна удовлетворять квантовая схема math

, вычисляющая math

, в качестве N выступает количество битов, с которым работает схема

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

(1) преобразования физических состояний в квантовой механике унитарны

(2) модуль амплитуды - это вероятность наблюдения системы в состоянии math

(3) коэффициенты разложения по выделенному базису называются амплитудами

Условием остановки машины Тьюринга, находящейся в состоянии math

, является:

(1)

(2) функция переходов на паре math

не определена

(3)

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

(1) любое физически реализуемое преобразование матриц плотности имеет вид math

, где

- изометрическое вложение

(2) координатным видом линейный оператор math

является

(3) чтобы линейный оператор math

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

для любого math

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

(1) действие: "прибор становится классическим" означает, что матрица диагонализуется по второму сомножителю

(2) действие: "прибор становится классическим" означает, что матрица диагонализуется по первому сомножителю

(3) действие: "прибор становится классическим" не имеет никакого смысла

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

(1) нет верного ответа

(2)

(3)

В соответствии со свойствами квантовой механики формула math

равна:

(1)

(2)

(3)

При сравнении вероятностных распределений в math

- норме ,если math

- два распределения, то мерой их различия считаем

(1)

(2)

(3)

Для формы

справедливо:

(1)

- полином

(2)

(3)

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

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

(2) предикаты из класса BPP можно считать реально вычислимыми

(3) для определения простоты числа существует вероятностный алгоритм, работающий за полиномиальное время

Чему равна вероятность того, что что math

случайных сдвигов не покрывают фиксированный элемент, где math

- некоторая группа, а math

- подмножество math

(1)

(2)

(3)

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

(1) реальный квантовый компьютер - это часть большой системы, взаимодействующая с остальным миром

(2) состояние квантового компьютера - это вектор единичной длины, заданный с точностью до фазового множителя

(3) квантовый компьютер работает с состояниями из конечного числа битов

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

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

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

(3) обратимые схемы реализуют только перестановки

Если справедливо равенство math

, то

(1)

(2)

(3)

Какой размер имеет схема, которой в полном базисе реализуется функция math

(1)

(2)

(3)

Формулы

достаточно для определения:

(1) класса BQP

(2) квантового вычисления

(3) измеряющих операторов

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

(1) мощность множества машин Тьюринга

(2) мощность множества функций

(3) счетное множество

Выполнение каких действий необходимо для доказательства физической реализации преобразования вида math

(1) добавление нулевых битов

(2) обратимое копирование исходных битов в добавленные обратимое копирование добавленых битов в исходные

(3) взятие частичного следа по добавленным битам взятие частичного следа по исходным битам

Можно ли в операторе math

разложить

в сумму проекторов на собственные подпространства следующим образом: math

(1) рассматриваются произведения измеряющих операторов, построенных на разных ортогональных разложениях пространства состояний

(2) рассматриваются произведения измеряющих операторов, построенных на одном и том же ортогональном разложении пространства состояний

(3) квантовые условные вероятности никогда не ведут себя как обычные

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

(1)

(2)

(3)

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

(1) локальный гамильтониан является квантовым аналогом 3-кнф

(2) локальность является аналогом ограниченности числа переменных, входящих в одну дизъюнкцию

(3) в классе BQNP не существует полных задач относительно полиномиальной сводимости

Сколько будет базисных операторов для пространства math

, образованного матрицами Паули?

(1)

(2)

(3)

Если

, то:

(1)

(2)

(3)

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

(1) "если

- разложение числа на взаимно простые множители. Тогда math

(2) "если

- простое и math

, то

(3) нет верного ответа

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

(1)

(2)

(3)

Определение тензорного произведения двух пространств math

, в которых фиксированы базисы math

(1) инвариантно

(2) неинвариантно

(3) нет верного ответа

Из каких функций состоит базис math

(1) линейных

(2) обратимых

(3) нелинейных

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

(1) эрмитовы матрицы math

с нулевым следом образуют трехмерное евклидово пространство

(2) скалярное произведение задается формулой math

(3) ортонормированный базис образуют матрицы Черча

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

(1) понятие универсальной переборной задачи существует и в классической, и в квантовой постановке

(2) при вычислении предиката math

квантовые устройства дают полиномиальное ускорение по сравнению с классическими

(3) квантовый компьютер вычисляет значение предиката math

за время

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

(1) они не являются физически реализуемыми операторами

(2) они описывают переход от одного состояния системы к другому за определенный промежуток времени

(3) они выделяют часть состояний системы из всех возможных

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

(1) память math

(2) объем вычислений math

(3) время

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

(1) результатом работы квантовой схемы является вероятностная функция

(2) копирование произвольного квантового состояния math

является нелинейным оператором

(3) копирование произвольного квантового состояния math

является физически реализуемым

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

(1)

(2)

(3)

Порядок числа math

в мультипликативной группе вычетов math

обозначается как:

(1)

(2)

(3)

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

(1) PSPACE

(2) BQNP

(3) PP

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

(1)

(2)

(3)

Если

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

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

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

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

(1)

(2)

(3)

Размер схемы умножения чисел math

столбиком определяется, как:

(1)

(2)

(3)

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

(1) класс BPP содержит функции, могут быть вычислены на машине Тьюринга, использующей память, ограниченную полиномом от длины входного слова

(2) вычисление на памяти math

бессмысленно проводить дольше, чем время math

(3) псевдослучайные генераторы отсутствуют при math

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

(1)

(2)

(3)

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

(1) менять в записи биты местами можно, используя функцию math

(2) для перестановок битов достаточно иметь в базисе math

(3) для обратимых схем базис, состоящий из отрицания и элемента Тоффоли, является полным

Если унитарный оператор math

действует на трехмерном евклидовом пространстве ( math

), то задаваемый изоморфизм имеет вид:

(1)

(2)

(3)

Какой вид будет иметь запись оператора math

в матричной форме:

(1)

(2)

(3)

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

(1)

(2)

(3)

Если характеристическая функция предиката вычислима на машине Тьюринга math

, для которой math

, то

(1) предикат math

на множестве math

принадлежит классу math

(2) предикат math

на множестве math

принадлежит классу math

(3) предикат math

на множестве math

принадлежит классам math

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

(1) сбой фазы приводит к тому, что система ведет себя как классическая

(2) если постоянно наблюдать за системой (делать копии), то система будет вести себя как классическая

(3) в случае одного q-бита обнуление внедиагональных элементов можно получить, если применить оператор math

с вероятностью math

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

(1) произведение измеряющих операторов - линейный оператор

(2) произведение измеряющих операторов - измеряющий оператор

(3) произведение измеряющих операторов - унитарный оператор

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

(1)

(2)

(3)

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

(1)

(2)

(3)

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

(1)

(2)

(3)

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

(1) если

, то

(2) если

, то

(3) если

, то

Условием алгоритма проверки простоты числа math

, определяющим что math

- составное, где math

- случайное среди чисел от 1 до math

- нечетное, является:

(1) нахождение math

, для которого math

(2) нахождение math

, для которого math

(3) нахождение math

, для которого math

Если число ходов ограничено math

, а

, то время работы машины Тьюринга ограничено:

(1)

(2)

(3)

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

(1)

(2)

(3)

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

(1) обратимой операции

(2) необратимой операции

(3) они различны всегда

Запись

имеет следующий смысл:

(1) группа поворотов в трехмерном евклидовом пространстве

(2) группа ортогональных преобразований с детерминантом, равным math

(3) специальная ортогональная группа на трехмерном евклидовом пространстве

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

(1) композиция двух отражений относительно двух прямых есть поворот на удвоенный угол между этими прямыми

(2) Число шагов для поворота от исходного вектора к другому вектору из подпространства, порожденного векторами ответов, обратно пропорционально корню из числа решений

(3) композиция двух отражений относительно двух прямых есть поворот на угол между этими прямыми

Частичный след от оператора math

по пространству math

имеет вид:

(1)

(2)

(3)

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

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

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

(3) отрицание, дизъюнкция, конъюнкция

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

(1) основной механизм взаимодействия между квантовой и классической частями состоит в измерении квантовых регистров

(2) измерение (преобразование матриц плотности) состоит в том, что для состояний из подпространства math

измеряющий прибор помещает в классический регистр номер состояния math

(3) квантово-классическое состояние всегда разложимо на "условные"

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

(1)

(2)

(3)

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

(1)

(2)

(3)

Как определяется слагаемое гамильтониана math

, отвечающее начальному состоянию:

(1)

(2)

(3)

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

(1) каждый проверочный оператор действует на ограниченное константой число q-битов;

(2) каждый q-бит входит в ограниченное константой число проверочных операторов;

(3) кодовое расстояние неограниченно возрастает

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

(1) NP-полные предикаты существуют

(2) композиция двух полиномиально вычислимых функций полиномиально вычислима

(3) NP-полные предикаты не существуют

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

(1) меньше math

(2) меньше math

(3) меньше math

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

(1) по двум сложностным классам math

можно определить класс math

таких языков, которые распознаются машинами из класса math

с оракулами из math

(2) класс языков, распознаваемых недетерминированными машинами, работающими на памяти math

, содержится в классе языков, распознаваемых детерминированными машинами, работающими на памяти math

(3)

- класс языков, вычислимых за экспоненциальное время math

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

(1) тензорное произведение произвольного унитарного оператора, действующего на части сомножителей math

, где

мало (

), и тождественного оператора, действующего на остальных сомножителях

(2) функция из math

, которая зависит от небольшого числа битов и изменяет также небольшое число битов

(3) функция из math

, которая зависит от небольшого числа битов и изменяет также небольшое число битов

Если

вычислимы булевыми схемами размеров math

, то

реализуется обратимой схемой размера:

(1)

(2)

(3)

Выражение

определяет:

(1) норму оператора math

(2) следовую норму

(3) норму для преобразования матриц плотности

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

(1)

(2)

(3)

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

(1) обобщенные квантовые состояния и матрицы плотности являются аналогами

(2) состояние, задаваемое общей матрицей плотности, называется смешанным

(3) операторы вида math

- это эрмитовы неотрицательно определенные операторы со следом 1

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

(1) задает схемную сложность на math

-том такте

(2) задает состояние машины Тьюринга после math

тактов работы

(3) определяет размер схемы

Если имеется math

, а

, то детерминированное измерение будет иметь вид:

(1)

\rho= \begin{pmatrix} \rho_{00}&\rho_{01}\\ \rho_{10}&\rho_{11} 

\end{pmatrix} \mapsto (\rho_{00}\ket0\bra0,\,0)+(\rho_{11}\ket0\bra1,\,1)

(2)

\rho= \begin{pmatrix} \rho_{00}&\rho_{01}\\ \rho_{10}&\rho_{11} 

\end{pmatrix} \mapsto (\rho_{00}\ket0\bra0,\,0)+(\rho_{11}\ket1\bra0,\,0)

(3)

\rho= \begin{pmatrix} \rho_{00}&\rho_{01}\\ \rho_{10}&\rho_{11} 

\end{pmatrix} \mapsto (\rho_{00}\ket0\bra0,\,0)+(\rho_{11}\ket1\bra1,\,1)

Верно ли, что если применить измеряющий оператор к состоянию math

, где

, то вероятность наблюдения состояния math

можно записать в виде: math

(1) да, верно

(2) нет, не верно

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

(1) задача о вычислении периода является частным случаем задачи о скрытой подгруппе в math

(2) фурьеобраз от произведения равен свертке фурье-образов сомножителей

(3) распределением по множеству всех собственных чисел можно управлять

(4) определение группы характеров имеет обозначение math

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

(1)

(2)

(3)

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

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

(2) торический код исправляет math

ошибок

(3) векторы из ортогонального дополнения называются возбужденными состояниями

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

(1)

является NP-полной

(2)

(3) 3-КНФ задается предикатом math

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

(1) хотя бы один такой объект существует

(2) не существует ни одного подобного объекта

(3) нет верного ответа

Выберите верные тождества, где math

- язык,

(1)

(2)

(3)

Для квантовой схемы math

- последовательности math

выступает в роли:

(1) базисов

(2) амплитуд

(3) q-битов

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

, чтобы

реализовалась обратимой схемой размера math

(1)

(2)

(3)

Если имеется чистое состояние math

, то разложение Шмидта имеет вид ( math

- ортонормированные вектора):

(1)

(2)

(3)

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

(1)

(2)

(3)

Каким образом определяется частичный след оператора math

по пространству math

(

(1) нет верного ответа

(2)

(3)