http://neerc.ifmo.ru/wiki/api.php?action=feedcontributions&feedformat=atom&user=%D0%A8%D0%B5%D0%B2%D1%87%D0%B5%D0%BD%D0%BA%D0%BE+%D0%90%D1%80%D1%82%D0%B5%D0%BCВикиконспекты - Вклад участника [ru]2026-05-05T12:32:53ZВклад участникаMediaWiki 1.30.0http://neerc.ifmo.ru/wiki/index.php?title=%D0%9A%D1%83%D0%B1%D0%B8%D1%82&diff=1191Кубит2010-05-23T07:51:41Z<p>Шевченко Артем: Новая страница: «==Кубит== Кубит -- это объект, который может находиться в одном из возможных состояний (кото…»</p>
<hr />
<div>==Кубит==<br />
<br />
Кубит -- это объект, который может находиться в одном из возможных состояний (которые будут описаны далее). Причем, каждое состояние при наблюдении реализуется в конкретное бинарное значение -- 0 или 1.<br />
<br />
Запись <math>\alpha_0|0> + \alpha_1|1> </math> представляет собой состояние кубита и означает, что в данном состоянии кубит может принять значение 0 с вероятностью <math>\alpha_0^2</math> и значение 1 с вероятностью <math>\alpha_1^2</math>. Отсюда естественным образом следует ограничение, которое накладывается на возможные состояния кубита: <math>\alpha_0^2 + \alpha_1^2 = 1</math>. Причем, в общем случае <math>\alpha_0</math> и <math>\alpha_1</math> могут быть и комплексными. Хотя в дальнейшем мы в основном будем иметь дело только с вещественными <math>\alpha_0</math> и <math>\alpha_1</math>.<br />
<br />
==<math>n</math>-кубит==<br />
<br />
Данные выше определения естественным образом обобщаются на случай системы из <math>n</math> кубитов. Состояние <math>n</math>-кубита описывается аналогичным образом: <math> \sum_{i \in {\{0,1\}}^n} \alpha_i|i></math>. Значение <math>i</math> реализуется в результате измерения с вероятностью <math>\alpha_i</math>, причем, аналогично случаю 1-кубита, <math>\sum\alpha_i^2 = 1</math>. Поскольку выполняется это условие, в дальнейшем мы будем опускать нормировочные множители, полагая, что при необходимости мы всегда можем привести результат к нормализованному виду.<br />
<br />
Приведем пример состояния 2-кубита: <math>|00> + |11></math>. Нормировочные множители <math>\frac{\sqrt{2}}{2}</math> были опущены. Данная запись обозначает, что при измерении система из двух кубитов равновероятно примет либо значение <math>\{0, 0\}</math>, либо <math>\{1, 1\}</math>.<br />
<br />
==Измерение <math>n</math>-кубита==<br />
<br />
Как уже было сказано, если измерить кубит, в результате будет получено конкретное значение. И при многократном измерении, на первый взгляд, мы как-будто просто узнаем в ходе исследования значения <math>\alpha_i^2</math>. В дальнейшем будет показано, что все не так просто.<br />
<br />
Кроме полного измерения <math>n</math>-кубита, возможно его частичное измерение. Измерив <math>m</math> компонент <math>n</math>-кубита, мы получим их конкретные реализации. Таким образом новое состояние системы может быть получено занулением <math>\alpha_i</math> для всех <math>i</math>, в которых не все из <math>m</math> измеренных компонент соответствуют полученной реализации (другими словами, не соответствуют реальности). После этой операции, в общем случае, подразумеваемые нормировочные множители изменятся.</div>Шевченко Артемhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D1%81%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8_(%D1%81%D1%82%D0%B0%D1%80%D0%B0%D1%8F_%D1%82%D1%80%D0%B5%D1%88%D0%BE%D0%B2%D0%B0%D1%8F_%D0%B2%D0%B5%D1%80%D1%81%D0%B8%D1%8F)&diff=1190Теория сложности (старая трешовая версия)2010-05-23T06:54:14Z<p>Шевченко Артем: </p>
<hr />
<div>== Лекция 1 ==<br />
*[[Класс DSPACE]]<br />
*[[Класс DTIME]]<br />
*[[Теорема о емкостной иерархии]]<br />
*[[Теорема о временной иерархии]]<br />
*[[Сведение по Карпу]]<br />
*[[Сведение по Куку]]<br />
*[[Класс P]]<br />
*[[Класс NP]]<br />
*[[Класс coNP]]<br />
<br />
== Практика 1 ==<br />
*[[Сведение по Куку задачи факторизации к языку из NP]]<br />
<br />
== Лекция 2 ==<br />
*[[Теорема Кука]]<br />
<br />
== Практика 2 ==<br />
*[[Понятие NP-трудной и NP-полной задачи]]<br />
*[[NP-полнота задачи BH1N]]<br />
*[[NP-полнота задачи о выполнимости булевой формулы в форме КНФ]]<br />
*[[NP-полнота задачи о выполнимости булевой формулы в форме 3-КНФ]]<br />
*[[NP-полнота задачи о клике]]<br />
*[[NP-полнота задачи о независимом множестве]]<br />
*[[NP-полнота задачи о вершинном покрытии]]<br />
<br />
== Лекция 3 ==<br />
*[[Теорема Ладнера]]<br />
*[[Теорема Левина]]<br />
*[[Теорема Бейкера-Гилла-Соловэя]]<br />
<br />
== Практика 3 ==<br />
*[[NP-полнота задач о гамильтоновом цикле и пути в графах]]<br />
*[[NP-полнота задачи о сумме подмножества]]<br />
*[[NP-полнота задачи о рюкзаке]]<br />
<br />
== Практика, которой на самом деле не было ==<br />
*[[NP-полнота задачи о раскраске графа]]<br />
<br />
== Лекция 4 ==<br />
*[[Класс PS]]<br />
*[[Теорема Сэвича]]<br />
*[[PS-полнота задачи Generalized geography]]<br />
<br />
== Лекция 6 ==<br />
*Классы [[L]], [[NL]], [[NL-полнота|NLC]]<br />
*[[NL-полнота задачи о достижимости в графе]]<br />
*[[Классы EXP, NEXP. Полнота языков EXP и NEXP]]<br />
*[[Теорема о связи вопросов EXP=NEXP и P=NP]]<br />
*[[Теорема Иммермана]]<br />
<br />
== Практика 6 ==<br />
*[[Классы Sigma_i и Pi_i]]<br />
*[[Класс PH]]<br />
*[[Полиномиальная иерархия]]<br />
*[[Теоремы о коллапсе полиномиальной иерархии]]<br />
<br />
== Лекция 7 ==<br />
*[[Теорема Карпа-Липтона]]<br />
<br />
== Практика 7 ==<br />
*[[Вероятностная машина Тьюринга]]<br />
*[[Класс ZPP]]<br />
*[[Сложностные классы RP и coRP]]<br />
*[[Сложностный класс PP]]<br />
*[[Сложностный класс BPP]]<br />
*[[Уменьшение ошибки в классе RP, сильное и слабое определение]]<br />
<br />
== Лекция 8 ==<br />
*[[Теорема о включении BPP в P/poly]]<br />
*[[Теорема Лаутемана]]<br />
*[[Теорема Валианта-Вазирани]]<br />
<br />
== Практика 8 ==<br />
*[[Лемма Шварца-Зиппеля]]<br />
<br />
== Лекция 9 ==<br />
*[[Класс IP|Класс IP]]<br />
*[[GNI|Принадлежность проблемы GNI классу IP]]<br />
*[[Sharp SAT|#SAT]]<br />
<br />
== Лекция 10 ==<br />
*[[Теорема Шамира]]<br />
*[[Семейство универсальных попарно независимых хеш-функций|Семейство универсальных попарно независимых хеш-функций]]<br />
*[[Теорема Голдвассера, Сипсера]]<br />
<br />
== Лекция 11 ==<br />
*[[Абсолютная секретность]]<br />
<br />
== Лекция 12 ==<br />
*[[Кубит]]</div>Шевченко Артем