Классические и квантовые вычисления - ответы
Количество вопросов - 336
Состояние машины Тьюринга задается тройкой
, где бесконечное слово в алфавите
- это:
Какому Выберите верное утверждение:
Выберите верное утверждение:
Чему равна вероятность "события"
для квантового состояния, задаваемого матрицей плотности
и подпространства
:
Выберите верное утверждение:
Конечному состоянию гамильтониана, сопоставляемого схеме, отвечает:
Условием строгой формулировки вычислительной задачи является наличие:
Усиление оценки вероятностей с
до
является основанием доказательства:
Перестановка, реализуемая обратимой схемой, является (
- некоторое множество перестановок вида
):
Любой оператор, обладающий свойствами 
Какое значение принимает функция
, если более половины ее аргументов равны 1:
Верным является тождество:
Какая из ниже перечисленных формул является справедливой:
Какие свойства характерны классической вероятности:
Для тензорного произведения пространств, на которых действуют сомножители, справедливо:
Частичная функция
из
в
вычислима на машине Тьюринга :
В широкий класс задач, связанных с абелевыми группами, входят задачи, открытые:
Чему равна вероятность того, что что
случайных сдвигов не покрывают фиксированный элемент, где
- некоторая группа, а
- подмножество
:
Величина энергии, требуемая для стирания одного бита:
Условие нормировки
означает:
Если характеристическая функция предиката вычислима на машине Тьюринга
, для которой
, то
Проверка простоты числа является классическим примером задачи класса:
Функция
принадлежит классу NP, если есть частично определенная функция
от двух переменных, такая что:
Условием выхода из алгоритма проверки простоты числа является:
"Если
- разложение числа на взаимно простые множители, то существует взаимно однозначное соответствие между остатками от деления на
и парами остатков от деления на
и на
" - утверждает:
Для вероятностной машины Тьюринга можно определить:
В формуле
для нахождения количества состояний системы,
- это:
Авторами теоремы "Если
, то
" являются:
Каким равенством выражается дуальность между классическими и фазовыми ошибками?
Если кодировки переводятся друг в друга при помощи полиномального алгоритма, то они:
В наборе
для задания машины Тьюринга выполняется условие:
Для задания состояния машины Тьюринга обязательным является указание:
Условием разрешимости предиката является:
Тезисом Черча является утверждение:
Вершины входной степени 0 ориентированного ациклического графа помечаются:
Дизъюнктивной нормальной форме (ДНФ) соответствует:
Машина Тьюринга, имеющая состояния, в которых она может выполнить одно из нескольких действий, называется:
Какое понятие используется для определения класса
:
Под размером входа для предиката
в записи
понимают:
Если
, то:
Если
-полный предикат можно вычислить за время
, то любой предикат из
для некоторого числа
можно вычислить за время:
Проверка транзизитивности сводимости - если
,
, то
является достаточным доказательством утверждения:
Если предикат
принадлежит классу BPP, то выражение
означает, что:
Утверждение "если
- простое и
, то
" является:
Размер схемы умножения чисел
,
столбиком определяется, как:
Условие
алгоритма проверки простоты числа, где
- случайное среди чисел от 1 до
:
Алгоритм проверки простоты числа с вероятностью
выдает ответ:
Обозначение класса дополнений классу языков
имеет вид:
Автором теоремы "
" является:
Чем объясняется то, что вероятность события
не больше
, где
- некоторая группа, а
- подмножество
:
Функции, которые могут быть вычислены на машине Тьюринга, использующей память, ограниченную полиномом от длины входного слова относятся к классу:
Если число ходов ограничено
, а
, то время работы машины Тьюринга ограничено:
Выберите верное утверждение:
Задача
является полной задачей класса:
Вычислительные возможности при переходе от преобразований конечных множеств к унитарным преобразованиям конечномерных пространств:
q-бит квантового компьютера:
Выберите верное утверждение:
Определение тензорного произведения двух пространств
и
, в которых фиксированы базисы
и
:
Выделенный базис для
имеет вид:
Обозначение скалярного произведения в гильбертовом пространстве является запись:
Элементарному преобразованию в квантовом случае соответствует определение:
Для квантовой схемы
- последовательности
,
выступает в роли:
В соответствии с каким оператором действует унитарный оператор
в пространстве
:
Какому условию должно удовлетворять произведение перестановок, определяющее перестановку
в расширенном смысле:
Какие две функции необходимо включить в базис, чтобы реализовать любую функцию:
Что означает символ
:
Два различных логических состояния становятся одинаковыми при выполнении:
Если существует вычисление, требующее памяти
, то реализовать его можно обратимым способом с использованием памяти:
Выберите верное утверждение:
В чем заключается проблема выбора базиса в квантовых схемах:
Оператор с квантовым управлением имеет обозначение:
Если справедливо равенство
, то
=:
Матрицы
, образующие ортонормированный базис, называются:
Если унитарный оператор
действует на трехмерном евклидовом пространстве (
), то задаваемый изоморфизм имеет вид:
Если унитарный оператор
действует на трехмерном евклидовом пространстве (
), для матриц Паули
,
соответствует повороту вокруг оси X на:
Какое обозначение имеет норма вектора:
Что из ниже перечисленного характерно для смешанного состояния:
Чему равна вероятность получения базисного состояния,
при измерении состояния
:
Какое название имеет функция
:
За какое время квантовый компьютер вычислит значение предиката
(
- количество шагов):
Какой вид будет иметь запись оператора
в матричной форме:
Если имеются операторы
и
, то:
Конструктивное описание квантовой схемы формируется:
Если система из
q-битов находится в состоянии
, то вероятность обнаружить систему в состоянии x определяется как:
Какая из ниже перечисленных формул является справедливой:
Проектор на подпространство, порожденное
, обозначается, как:
Что из ниже перечисленного является характерным для проекторов на подпространство
Каким условиям удовлетворяют операторы вида
:
Состояние, заданное вектором (
), называется:
Каким образом определяется частичный след оператора
по пространству
(
):
Матрицу плотности чистого состояния
унитарный оператор переводит в матрицу:
В случае изометрического вложение
в пространство большей размерности, задаваемое формулой
, матрица плотности
преобразуется:
Какие из ниже перечисленных условий являются обязательными для того, чтобы линейный оператор
являлся физически реализуемым преобразованием матриц плотности:
Выполнение каких действий необходимо для доказательства физической реализации преобразования вида
:
Преобразование, заключающееся в обнулении внедиагональных элементов, записывается в виде:
Если имеется физически реализуемое преобразование
, причем для любого чистого состояния
выполняется свойство:
, то для любого оператора
справедливым является равенство (
- некоторая фиксированная матрица плотности на пространстве
):
При отображении
в
,
- квантовая часть и
- классическая часть системы, результат является диагональным по отношению:
В детерминированном измерении
выступает в качестве:
Какой вид имеет оператор, реализуемый квантовой схемой?
Если есть пространство состояний
, причем первый сомножитель разложен в прямую сумму попарно ортогональных подпространств:
, тогда всякий оператор вида
будет называться:
Если к состоянию, описываемому матрицей плотности
, подсоединить прибор с выделенным базисом, то совместное состояние системы и прибора будет описываться матрицей плотности вида:
Почему
в операторе
можно разложить в сумму проекторов на собственные подпространства следующим образом:
,
?
Если унитарный оператор
разложить в сумму проекторов на собственные подпространства следующим образом:
,
, то
. В этом случае условные вероятности будут равны:
Квантовые условные вероятности
ведут себя как обычные, если...
Продолжите фразу: условные вероятности для произведения измеряющих "разными приборами" операторов...
Верно ли, что если применить измеряющий оператор к состоянию
, где
, то вероятность наблюдения состояния
можно записать в виде:
?
Автором "задачи о скрытой группе" является
Какую сложность имеет алгоритм нахождения скрытой группы
:
Как называется порядок числа
в мультипликативной группе вычетов 
С какой вероятностью должен вычисляться делитель составного числа в подпрограмме для нахождения факторизации числа:
Если получено
дробей вида
то вероятность того, что наименьшее общее кратное их знаменателей отлично от
(равномерно распределенное на множестве
случайное число):
Какое свойство характерно для оператора умножения на число 
Какое из ниже перечисленных равенств является справедливым (с учетом тождества
):
Если требуется
обращений к оракулу и каждый вопрос имеет длину
, то размер квантовой схемы определяется как:
Каким условиям должны удовлетворять операторы
, реализуемые однородной последовательностью квантовых схем полиномиального по
размера, чтобы функция
принадлежала классу BQNP:
Какому условию должно удовлетворять
в неравенстве
, если 
Каждое слагаемое локального гамильтониана
является:
Какому классу принадлежит локальный гамильтониан:
Из каких слагаемых состоит гамильтониан, сопоставляемый схеме, действующие на пространстве
:
Какое слагаемое гамильтониана
описывает эволюцию системы:
Утверждение о том, что схема, на вход которой подан вектор
, дает ответ 1 с вероятностью не меньше, чем
описывается формулой:
Кодовое расстояние - это:
Код исправляет
ошибок:
Пусть
- разложение пространства
в прямую сумму взаимно ортогональных подпространств. Тогда для любой пары матриц плотности
, 
Сколько будет базисных операторов для пространства
, образованного матрицами Паули?
Симплектический квантовый код задается условиями:
Какими способами задаются торические коды?
Выберете верные утверждения:
Что из ниже перечисленного называется классической ошибкой?
Если есть пространство состояний
, причем первый сомножитель разложен в прямую сумму попарно ортогональных подпространств:
, тогда измеряющим будет называться всяки оператор вида:
Чему эквивалентно условие
Сколько ошибок исправляет торический код?
Укажите верные утверждения:
Если на совместное состояние системы и прибора
подействовать измеряющим оператором
, то получим состояние:
Как определяется слагаемое гамильтониана
, отвечающее начальному состоянию:
Множество состояний управляющего устройства в наборе
для задания машины Тьюринга - это:
Если имеется действие
, то :
Предикат, задающий 3-КНФ:
Какая цепочка эквивалентностей является некорректной:
Выберите неверное утверждение:
Выберите неверное утверждение:
В качестве первого сомножителя пространства
, на котором действует гамильтониан, сопоставляемый схеме, выступает:
Преобразование матриц плотности
где
, называется:
Специальная ортогональная группа на трехмерном евклидовом пространстве обозначается записью:
Что послужило источником интереса к обратимым вычислениям:
Укажите верное утверждение:
Если существует квантовый алгоритм вычисления функции
, работающий за время
для некоторой константы
, то функция 
Пространство состояний квантовой системы:
Последовательность кодов называется кодами с локальными проверками, если выполнены следующие условия:
Записи пространства состояний системы из
q-битов
соответствует:
Какая пара операторов будет соответствовать соотношению
?
Условие
для предиката
, принадлежащего классу
, означает, что:
Формулировкой китайской теоремы об остатках является:
Если вероятность правильного ответа для каждого экземпляра из
запущенных машин Тьюринга равна
, то вероятность правильного ответа после голосования
машин:
Физически реализуемым является преобразование вида:
Выберите неверное утверждение:
Выберите верное утверждение:
Что из ниже перечисленного называется фазовой ошибкой?
Каким преобразованием задается отбрасывание второй системы, если есть
:
Какая из ниже перечисленных формул является верной:
Что из ниже перечисленного верно отражает свойство "множество содержит много элементов":
Выберите верное утверждение:
В наборе
для задания машины Тьюринга множество S является:
Время работы машины Тьюринга определяется:
Полный стандартный базис образуют булевы функции:
Выберите верное утверждение:
Выберите верное утверждение:
Предикат
принадлежит классу
, если он представим в форме:
Сводимость по Карпу предиката
к предикату
обозначается:
Теорема Кука, Левина утверждает, что:
Справедливым является утверждение:
Условие существования вероятностной машины Тьюринга
и полинома
, причем машина
заведомо остановится за время, не превосходящее
, определяет, что:
В соответствии с алгоритмом Евклида, если делить большее число на меньшее, то длина записи меньшего числа уменьшается на константу:
Вероятность получения ответа "
- составное" для алгоритма проверки простоты составного числа n равна:
Выберите верное утверждение:
Какое обозначает запись
по отношению к классу А:
Утверждение о том, что для случайных независимых
вероятность события
больше 0, содержится в записи :
Какому классу принадлежит
, если существует такая игра с полиномиальным от длины входного слова числом ходов и полиномиально вычислимым результатом, что
Б имеет выигрышную стратегию
(Б - игрок, имеющих имя "белые"):
За какое количество тактов машина Тьюринга с оракулом проверяет, принадлежит ли записанное на оракульной ленте слово языку
:
Выберите верные тождества, где
- язык,
:
Множество состояний
классической системы:
Что из перечисленного является характерным для квантового компьютера:
Обозначением вектора
является:
Левая половина скалярного вектора
называется:
Какой вид имеет оператор, реализуемый квантовой схемой:
Перестановок на каком количестве бит является достаточным для реализации функции, заданной булевой схемой в полном базисе:
Из каких функций состоит базис
:
Какие из ниже перечисленных формул являются верными:
Если
вычислима булевой схемой размера
, то размер памяти, на которой можно вычислить функцию
, равен:
Условие приближенной реализуемости:
Выберите верное утверждение
Запись
имеет следующий смысл:
Если имеется чистое состояние
, то разложение Шмидта имеет вид (
,
и
- ортонормированные вектора):
В формуле
, которой должна удовлетворять квантовая схема
, вычисляющая
, значение
:
Сколько экземпляров квантовой схемы
необходимо взять, чтобы уменьшить вероятность неудачи в
раз:
Выберите неверное утверждение
Формулы
достаточно для определения:
Какая из ниже перечисленных формул является определением квантовой вероятности:
Частичный след от оператора
по пространству
имеет вид:
Если на пространстве
задана матрица плотности вида
и имеется два подпространства
,
, то справедливо равентство:
Матрицу плотности чистого состояния
в матрицу
переводит:
Выберите неверное утверждение:
Выберите верное утверждение:
Выберите верное утверждение:
Какой вид имеет линейный оператор?
Определите вид оператора
, действующего на пространстве
Как называется следующая формула:
?
Решение универсальной переборной задачи алгоритмом Гровера -
Какова вероятность получить делитель числа
в результате работы процедуры нахождения делителя (
- число различных простых делителей
):
Условные вероятности для оператора
определяются, как (
- значение в
-ом бите):
Равномерное распределение на множестве всех собственных чисел можно получить, если взять в качестве начального состояние, задаваемое следующей диагональной матрицей плотности:
Выберите верное утверждение:
В соответствии со свойствами квантовой механики формула
равна:
Выберите верное утверждение:
Чему равна левая часть формулы 
Если
,
- неотрицательные операторы,
,
- их нулевые подпространства, причем
, ненулевые собственные числа
и
не меньше
, где
- угол между
и
, то справедливым является равенство:
Как накапливаются ошибки при квантовом вычислении?
Следовая норма оператора
равна:
В чем заключается отличие симплектического кода от классических линейных кодов?
Выберете верные утверждения:
Оператор, переводящий
в
:
Если
- множество троек вида
описанием схемы - приближенная реализация в стандартном базисе, а
(
,
- размер описания схемы). Тогда для
выполняется:
Выберите верное свойство скалярного произведения в гильбертовом пространстве:
Выберете верные утверждения:
Какой функцией является перестановка на двух битах
:
Выберите верное утверждение:
Если имеется последовательность булевых функций
, то однородная последовательность схем, вычисляющих
- это:
Действие унитарного оператора на произвольные матрицы плотности задается формулой:
Машина Тьюринга, переходящая в состояние, определяемое результатом некоторого случайного процесса, называется:
Отличием недетерминированной машины Тьюринга является:
В каком случае заведомо не существует псевдослучайных генераторов:
Порядок числа
в мультипликативной группе вычетов
обозначается как:
Сколько раз для нахождения факторизации числа необходимо применить подпрограмму, которая по любому составному числу вычисляет какой-то его делитель с вероятностью, не меньшей
:
По какому правилу в квантовой постановке действует оракул, задающий оператор
:
Каким образом будут распределены классические состояния квантовой системы, находящейся в состоянии
:
Выберите верное утверждение:
Условием остановки машины Тьюринга, находящейся в состоянии
, является:
Важнейшими ресурсами, требующимися машине Тьюринга для вычислений, является:
Схема является формулой, если:
Строка таблицы вычисления
:
Справедливым является утверждение (запись):
Если установлена принадлежность предиката
к классу BPP, существуют полином
и предикат
, то выражение
означает, что:
Из утверждения "вероятность того, что объекта с нужными свойствами не существует, меньше 1" следует, что:
Использование генераторов псевдослучайных чисел является основой идеи:
В качестве
в булевой формуле
задаваемой задачей
, где
,
- некоторая логическая формула, выступает:
Какой вид имеет элемент Тоффоли:
Выберите верное утверждение:
Возможность точной реализации оператора квантовой схемой связана с использованием:
Каким условиям должна удовлетворять норма
на пространстве операторов:
Какое условие должно выполняться, чтобы схема
вычисляла
:
Выберите верное утверждение:
Полная длина квантовой схемы Z, размера L и точности не должна превышать:
В контексте классической вероятности распределение вероятностей задается:
Каким условиям эквивалентна физическая реализуемость линейного оператора
, записанного в координатном виде
?
В случае одного q-бита обнуление внедиагональных элементов можно получить, если применить оператор
с вероятностью:
Как называется оператор вида
, если в пространстве состояний
, причем первый сомножитель разложен в прямую сумму попарно ортогональных подпространств:
?
Если применить измеряющий оператор к состоянию
, где
, то вероятность наблюдения состояния
можно записать в виде:
Какому классу принадлежит функция
, если существует однородная последовательность квантовых схем полиномиального по
размера, реализующих такие операторы
, что 
Какому условию должно удовлетворять
в неравенстве
, если 
Если
- множество троек вида
, где
,
,
, (
), то для
выполняются условия:
Как выглядят коммутационные соотношения между матрицами Паули?
Как называются векторы из кодового подпространства являющиеся собственными и обладающие наименьшей энергией?
Как называются коэффициенты
разложения вектора
по базису
:
Автором каких квантовых алгоритмов является П. Шор:
Последовательность перестановок
, где
- множества битов,
,
- некоторое множество перестановок вида
является:
Какая запись является верной:
Какой размер имеет схема, которой в полном базисе реализуется функция
:
Можно ли в операторе
разложить
в сумму проекторов на собственные подпространства следующим образом:
,
?
В играх Артура - Мерлина в качестве Артура выступает:
Какой из операторов можно считать аналогом полупрозрачного зеркала?
Запись
, где
обозначает:
Если распределение вероятностей имеет вид
, имеется совместное распределение на множестве
и событие не зависит от исхода во втором множестве
, то вероятность такого события выражается как:
Для формы
справедливо:
Выберите верное утверждение:
Какой вид имеет измеряющий оператор?
Для существующей недетерминированной машины Тьюринга, полинома
и предиката L условие
означает:
Условием полиномиальной сводимости предиката
к предикату
является:
Выберите верное утверждение:
При двойном проведении алгоритма проверки простоты числа вероятность ошибки оказывается:
Выберите верное утверждение:
Унитарный оператор, сопоставляемый перестановке
, имеет вид:
Решение проблемы выбора базиса в квантовых схемах связано с:
Чему соответствуют физическое состояние в квантовой механике:
Выберите верное утверждение:
Выберите верное утверждение:
Что будет являться произведением измеряющих операторов?
Если
- независимые случайные равномерно распределенные элементы абелевой группы
, то вероятность, с которой они порождают всю группу
, определяется:
Класс, входящий в иерархию классов, определяемых играми Артура - Мерлина, обозначается как:
В контексте квантовой постановки нерешаемость задачи для любого предиката
на квантовой схеме, означает, что:
Чему равна суммарная длина
и
в формуле
, которой должна удовлетворять квантовая схема
, вычисляющая
:
Выберите верное утверждение:
Что из перечисленного является характерным для тензорного произведения двух пространств
и
, в которых фиксированы базисы
и 
Выберите верное утверждение:
Какая из ниже перечисленных формул является верной:
Если подпространство
ортогонально подпространству
, то для любой матрицы плотности
выполняется равенство:
Однозначно определенная совокупность инструкций по преобразованию исходных данных в результат - это:
Функция
является функцией полиномиального роста, если для некоторой константы
при достаточно больших
выполняется неравенство:
Предикатом
задается:
Возможность действовать на бесконечном множестве описывается:
Классическим объектом, соответствующим унитарному оператору является:
Если
и
вычислимы булевыми схемами размеров
, то
реализуется обратимой схемой размера:
Каково действие унитарного оператора
в трехмерном евклидовом пространстве:
Наибольшее собственное число оператора
определяется как:
Обозначение оператора, реализуемого универсальной квантовой схемой, имеет вид:
Какая из ниже перечисленных формул для квантовой вероятности является верной:
Укажите верное утверждение:
Зная, что
, где
- константа, за сколько испытаний можно добиться вероятности ошибки
при фиксированном
:
Какого типа код Хэмминга
?
В задаче о скрытой подгруппе в
имеется "скрытая подгруппа"
, порядок которой
не превосходит:
За какое количество шагов классический компьютер вычислит значение предиката
(
- количество битов в записи y):
Сколько кодовых q-битов используют коды со сколь угодно большим кодовым расстоянием?
Состояние перехода вероятностной машины Тьюринга определяется:
Условием алгоритма проверки простоты числа
, определяющим что
- составное, где
- случайное среди чисел от 1 до
,
- нечетное, является:
Количество состояний системы, где
- память,
- соответственно множество состояний управляющего устройства и алфавит рассматриваемой машины Тьюринга, определяется по формуле:
Выражение
определяет:
Какой полиномиальный размер имеет булева функция для умножения вычетов:
Чему равно кодовое расстояние для симплектического кода
?
Как получить условные вероятности для произведения измеряющих "разными приборами" операторов?
Алгоритм Евклида основан на рекурсивном использовании равенства:
Чему равна вероятность того, что случайный сдвиг
не покрывает (не содержит) некоторый фиксированный элемент, где
- некоторая группа, а
- подмножество
:
Какому размеру должны удовлетворять булевы схемы, вычисляющие
и
, чтобы
реализовалась обратимой схемой размера
:
Коэффициенты разложения по выделенному базису классических состояний называются:
Если имеется
, а
, то детерминированное измерение будет иметь вид:
При сравнении вероятностных распределений в
- норме,если
,
- два распределения, то мерой их различия считаем
Для любого классического вероятностного алгоритма, делающего не более
обращений к оракулу (
), существует подгруппа
и соответствующая функция
, для которой вероятность ошибки алгоритма:
Выберите верное утверждение:
Для доказательства физической реализации преобразования вида
на завершающем шаге необходимым является:
При доказательстве утверждения "
" используется:
По какой причине копирование произвольного квантового состояния
физически нереализуемо:
Какая из ниже перечисленных формул является верной:
Вероятность обнаружить систему в конкретном базисном состоянии определяется, как: