Квантовые компьютеры и квантовые алгоритмы: потенциальные возможности и математические



Скачать 107.95 Kb.
Pdf просмотр
Дата13.02.2017
Размер107.95 Kb.
Просмотров89
Скачиваний0

Квантовые компьютеры и квантовые алгоритмы:
потенциальные возможности и математические модели к.т.н. О.О.Васильев
ИПУ РАН, 2012 22 мая 2012 г.
к.т.н. О.О.Васильев
Квантовые компьютеры и квантовые алгоритмы: потенциальные

Постановка задачи
Проблема.
Для множества практических задач доказана их вычислительная сложность, однако решать их все равно нужно.
Варианты решения.
Применять различные эвристические приемы снижающие сложность,
на наиболее часто встречающих вариантах , снижать “среднюю”
сложность.
Использовать различные вероятностные алгоритмы.
Найти физические процессы отличные от лежащих в основе существующих компьютеров, которые позволят производить нетривиальные вычислительные действия “автоматически”.
к.т.н. О.О.Васильев
Квантовые компьютеры и квантовые алгоритмы: потенциальные

Постановка задачи
Проблема.
Для множества практических задач доказана их вычислительная сложность, однако решать их все равно нужно.
Варианты решения.
Применять различные эвристические приемы снижающие сложность,
на наиболее часто встречающих вариантах , снижать “среднюю”
сложность.
Использовать различные вероятностные алгоритмы.
Найти физические процессы отличные от лежащих в основе существующих компьютеров, которые позволят производить нетривиальные вычислительные действия “автоматически”.
Наводящее соображение
Сложность моделирования квантовой физической системы на классическом компьютере экспоненциальна. Однако в природе квантовые системы существуют – и, значит, “моделируют” сами себя.
к.т.н. О.О.Васильев
Квантовые компьютеры и квантовые алгоритмы: потенциальные

Сложность алгоритмов: некоторые замечания
В теории сложности(в отличие от обычного понимания “оценки сложности задачи” чаще всего рассматривается сложность “задач разрешимости”, то есть имеющих ответ “да” или “нет”.
Исследование классов сложности “функциональных задач”(вычисление значения некоторой функции) или “задач подсчета”(сколько существует значений удовл.заданному свойству)
также производится, но реже и результатов в этой области существенно меньше.
Сложность задач принято оценивать в терминах длины входа, то есть, задача разрешимая за экспоненциальное время от длины входа,
если на вход подается число N, есть задача разрешимая за время экспоненциальное от log N или, что то же линейное от самого числа
N.
к.т.н. О.О.Васильев
Квантовые компьютеры и квантовые алгоритмы: потенциальные

Классы сложности.
Некоторые классы сложности
P
- класс задач разрешимых за полиномиальное время.
NP
- класс задач, решение которых может быть проверено за полиномиальное время от длины входа.
NP
− complete - задачи, к которым может быть за полиномиальное время сведена любая задача из класса NP.
BPP
- класс задач разрешимых за полиномиальное время при помощи вероятностного алгоритма с вероятностью ошибки не более
1 3
BQP
- класс задач разрешимых за полиномиальное время при помощи квантового алгоритма с вероятностью ошибки не более
1 3
PSPACE
- класс задач для решения которых требуется полиномиальная память.
к.т.н. О.О.Васильев
Квантовые компьютеры и квантовые алгоритмы: потенциальные

Предполагаемое соотношение между классами сложности.
Рис.:
Предполагаемое соотношение между классами сложности к.т.н. О.О.Васильев
Квантовые компьютеры и квантовые алгоритмы: потенциальные

Примеры сложных задач. Общая ситуация.
SAT: имеется ли хотя бы один набор значений на котором заданная булева функция истинна(NP-полна, S.Cook, Л.Левин, начало 1970-х)
Целочисленное программирование: заданы целочисленная матрица A
и вектор b, существует ли (0, 1) вектор x такой, что
Ax
= b.(NP-полна, R.M.Karp, 1972).
Разложение числа на множители. Заданы числа N и M, 1 ≤ M ≤ N.
Существует ли простой делитель числа N меньший M?
Наилучший известный алгоритм для разложения чисел на множители(GNFS, J.M. Pollard конец 1980-х-начало 1990-х)имеет сложность порядка:
O
(exp((
64 9
log N)
1 3
(log log N)
2 3
).
Этот факт не доказан. Проблема, по-видимому, лежит в классе
NP-промежуточных. При этом, проверить является ли число простым или нет можно за полиномиальное время(M. Agrawal, N.
Kayal, N. Saxena 2002).
к.т.н. О.О.Васильев
Квантовые компьютеры и квантовые алгоритмы: потенциальные

Примеры доказуемо сложных задач. Теория управления.
Интервальная неособость: существует ли особая матрица в заданном аффинном семействе вещественных матриц (NP-трудна, S.Poljak,
J.Rohn, начало 1990-х)
Интервальная устойчивость, спектральная норма, положительная определенность семейств матриц (NP-трудны, А. Немировский,
1993).
Существование стабилизирующей обратной связи по выходу при интервальных ограничениях (NP-трудна V.Blondel, J. Tsitsiklis, 1995)
Существование стабилизирующей обратной связи по выходу с фиксированным множеством полюсов(NP-трудна, M.Fu, 2004).
Существование стабилизирующей обратной связи по выходу без ограничений(возможно NP-трудна, открытая проблема).
Очень много и других проблем. См., например, (довольно старый уже)
обзор V. Blondel, J.Tsitsiklis A survey of computational complexity results in systems and control. Automatica Vol.36(2000) P. 1249-1274
к.т.н. О.О.Васильев
Квантовые компьютеры и квантовые алгоритмы: потенциальные

Квантовая информатика. Хронология
1970-е: S.Wiesner- понятие кубита, А.С. Холево - передача квантовой информации; Р.П. Поплавский - сложность моделирования квантовых систем; R.S. Ingarden - квантовая теория информации.
1980-е: Ю.И. Манин и Р.Фейнман - идея квантового компьютера,
P.Benioff, D.Deutsch - первые мат.модели квантового компьютера,
1990-е: D.Simon, P.Shor, L.Grover, A.Steane, А. Китаев и мн.другие- разложение числа на множители, поиск в базе данных - базовые квантовые алгоритмы.
2000-е/2010-е: Множество конкретных квантовых алгоритмов(линейная алгебра, обработка символьных данных,
алгоритмы алгебры и геометрии, моделирование, статистика итп).
к.т.н. О.О.Васильев
Квантовые компьютеры и квантовые алгоритмы: потенциальные

Физика квантовых компьютеров. Хронология
1995. Первая экспериментальная реализация квантового гейта(ионные ловушки).
1997. Идея ЯМР-квантового компьютера и компьютеров на принципе
“квантовых точек”. Экспериментальная передача квантовой информации(“квантовая телепортация”).
1998. 2- и 3- кубитные компьютеры. Первая эксперимент.реализация квантовых алгоритмов
2000. 5- и 7- кубитные компьютеры. Разложение числа на множители.
2001-2003. Разложение числа 15. Оптические квантовые компьютеры(идея и реализ. гейта).
2005. Кубайт; квантовая память.
2006. 12 кубит
2007-2011 ...
2011-2012 Квантовый компьютер с фон-неймановской архитектурой;
операции с достаточной с практической т.з. частотой ошибок;
D-Wave претендует на создание коммерч.квантового компьютера(мнения специалистов крайне противоречивы);
к.т.н. О.О.Васильев
Квантовые компьютеры и квантовые алгоритмы: потенциальные

Квантовые компьютеры: что возможно, а что нет.
Квантовые вычисления НЕ расширяют класс вычислимых функций(эти проблемы рассматриваются в другой области деятельности - hypercomputation,
Квантовые алгоритмы имеют вероятностный характер.
Квантовые вычисления НЕ дают экспоненциального ускорения на всех задачах и НЕ дают решения NP-полных задач за полиномиальное время.
Существует ряд задач для которых существуют квантовые алгоритмы дающие экспоненциальное или суперполиномиальное ускорение. Для еще большего числа задач имеет место полиномиальное ускорение.
к.т.н. О.О.Васильев
Квантовые компьютеры и квантовые алгоритмы: потенциальные

Задачи на которых достигается экспоненциальное(суперполиномиальное) ускорение.
Разложение числа на множители. Если N - натуральное число, то алгоритм P.Shor(1994) разложения на простые множители имеет сложность O((log N)
3
). Экспериментально с его помощью на данный момент разложены числа 15 и 21.
Алгоритмы алгебры и теории чисел: дискретное логарифмирование(P. Shor, 1995); уравнения Пелля(S. Hallgren,
2002); проверка главности идеала(S. Hallgren, 2002, A. Schmidt,
2009); группа единиц, группа классов идеалов числового поля(S.
Hallgren, 2005, A.Schmidt, U.Vollmer, 2005); гауссовы суммы(W. van
Dam, G. Seroussi, 2002); вычисление неприводимых представлений групп(S. Jordan, 2008) и др.
Все алгоритмы выше имеют одну и ту же природу и связаны с т.н.
алгоритмом поиска скрытой подгруппы: выяснение образующих конечной факторгруппы по структуре отображения факторизации.
В абелевом случае алгоритм в полной общности сформулирован D.Boneh и R.Lipton в 1995. В неабелевом общая проблема построения полиномиального квантового алгоритма открыта(изучены частные случаи).
к.т.н. О.О.Васильев
Квантовые компьютеры и квантовые алгоритмы: потенциальные

Задачи на которых достигается экспоненциальное(суперполиномиальное) ускорение.
Часть 2.
Решение’ систем линейных уравнений. (A.Harrow, A.Hassidim, S.Lloyd.
2009; A. Ambainis, 2011) зв время O(k log
3
k log N), где N - размер матрицы, а k - число обусловленности. Вычисление степеней разреженных симметрических матриц(D. Janzing, P. Wocjan, 2007)
Поиск “Cкрытого сдвига”(W. van Dam, S. Hallgren, L. Ip, 2006 и мн.др. позже), поиск пути в графе(A.Childs R. Cleve, E.Deotto,
E.Farhi, S.Gutmann, D. Spielman, 2003).
Алгоритмы геометрии и топологии: инварианты узлов(M.Freedman,
M.Larsen, Z.Wang, 2002 и мн.др.), инварианты трехмерных многообразий(S.Garnerone, A.Marzuoli, M. Rasetti, 2007; G.Alajic,
S.Jordan, R.Koenig, B. Reichart 2010)
Tермодинамические модели(D. Aharonov, I. Arad, E. Eban, Z. Landau
2007 и др.),
Алгебраическая геометрия над конечными полями(K.Kedlaya, 2006;
W. van Dam, 2004)
Теория кодирования(E.Knill, R.Laflamme, 2001 и др.)
Переписывающие системы(D.Jantsing, P.Wocjan, 2006).
к.т.н. О.О.Васильев
Квантовые компьютеры и квантовые алгоритмы: потенциальные

Квантовые вычисления. Математические модели.
Существует несколько моделей квантовых вычислений. Часть из них чисто математическая, часть может иметь реализуемые аналоги.
Квантовая машина Тьюринга (D.Deutsch, 1985).
Квантовые схемы (D.Deutsch, 1989).
Топологический квантовый компьютер(А. Китаев, 1997).
One-Way Quantum Computer(R. Raussendorf, H.Briegel, 2000).
Адиабатические квантовые вычисления(E.Farhi, J. Goldstone, S.
Gutmann, M.Sipser 2000).
Существует не менее полутора десятков возможных физических моделей,
реализующих квантовый компьютер.
к.т.н. О.О.Васильев
Квантовые компьютеры и квантовые алгоритмы: потенциальные

Квантовые схемы: что такое кубит?
Бра-кет нотация
Вектор |x понимается как элемент векторного пространства. Вектор y|
как линейный функционал. x|y - скалярное произведение.
Кубит- аналог бита.
Кубит - вектор в пространстве C
2
= B с нормой 1 определенный с точностью до множителя e i
ϕ
Аналогами значений бита 0 и 1 являются базисные состояния |0 и |1
Аналог булевых векторов
Аналогом пространства B
n булевых векторов является множество векторов пространства B
N
= (C
2
)
⊗N
= C
2
N
с нормой единица, определенных с точностью до множителя e i
ϕ
Иначе говоря, это линейные комбинации вида x
=(x
1
...x
N
)∈B
n c
x
|x
1
. . . x
N
,
причем x ∈B
n
|c x
|
2
= 1.
к.т.н. О.О.Васильев
Квантовые компьютеры и квантовые алгоритмы: потенциальные

Квантовые схемы: принцип вычислений.
Вычисление есть последовательность унитарных операторов между в пространстве B
N
Измерение есть проектор на подпространство.
Произвольные унитарные операторы аппроксимируются некоторыми фиксированными с заданной точностью.
Все вычисления(кроме измерений) обратимы - то есть память резервируется в начале вычисления и остается занятой до конца.
Окончательный вектор должен быть разложим, то есть иметь вид
|ξ ⊗ |η , где ξ результат, а |η - произвольно.
В контексте моделей квантовых вычислений доклад опирается, в основном, на монографию А.Китаев, А.Шень, М.Вялый Классические и квантовые вычисления. М.: МЦНМО, 1999.
к.т.н. О.О.Васильев
Квантовые компьютеры и квантовые алгоритмы: потенциальные

Квантовые схемы: определение
Квантовая схема
Пусть A- некоторое множество унитарных операторов. Тогда квантовая схема в базисе A - это последовательность U
1
[A
1
], . . . U
l
[A
l
], где U
i
∈ A, а
A
i
- некоторые множества кубитов.
U
i
[A
i
] - оператор действующий как U
i на кубитах из A
i и тождественно на остальных кубитах.
Оператор U = U
l
[A
l
] · . . . U
1
[A
1
] есть оператор реализумый квантовой схемой.
Оператор реализуемый квантовой схемой в расширенном смысле
Оператор U : B
⊗n
→ B
⊗n реализуемый схемой в расширенном смысле это такой оператор, что произведение W = U
l
[A
l
] · . . . U
1
[A
1
], действующее на
N
кубитов N ≥ n, для любого |ξ ∈ B
⊗n удовлетворяет условию
W
|ξ ⊗ |0
N−1
= (U|ξ ) ⊗ |0
N−n к.т.н. О.О.Васильев
Квантовые компьютеры и квантовые алгоритмы: потенциальные

Базисные операторы: явный вид матриц.
Унарные операторы
H
=
1

2 1
1 1
−1
K
=
1 0
0
i
Controlled-NOT
CNOT
=




1 0
0 0
0 1
0 0
0 0
0 1
0 0
1 0




к.т.н. О.О.Васильев
Квантовые компьютеры и квантовые алгоритмы: потенциальные

Базисные операторы: явный вид матриц.
Рис.:
Гейт Тоффоли: таблица истинности и матрица.
к.т.н. О.О.Васильев
Квантовые компьютеры и квантовые алгоритмы: потенциальные

Управляющие кубиты: конструкция Controlled-NOT и гейта Тоффоли.
Оператор с управляющим кубитом.
Пусть задан оператор U : B
⊗n
→ B
⊗n
Оператор Λ
k
(U) : B ⊗ B
⊗n
→ B ⊗ B
⊗n с квантовым управляющим кубитом определяется следующими соотношениями:
Λ(U)|x
1
. . . x k
⊗ |ξ = |0 ⊗ |ξ , если x
1
& . . . x k
= 0
Λ(U)|x
1
. . . x l
⊗ |ξ = |1 ⊗ U|ξ если x
1
& . . . x k
= 1
Замечание
Какой кубит считать управляющим - зависит от выбора базиса.
Конструкция операторов
Определим оператор σ
x
=
0 1
1 0
Это квантовая версия отрицания.
Оператор Controlled-NOT в этом случае будет Λ(σ
x
). Оператор Тоффоли:
Λ
2

x
).
к.т.н. О.О.Васильев
Квантовые компьютеры и квантовые алгоритмы: потенциальные

Квантовые вычисления
Теорема об аппроксимации
Всякий унитарный оператор можно аппроксимировать с точностью δ
квантовой схемой из операторов H, K , Controlled Not и оператора
Тоффоли размера не более exp(O(n))poly (log(
1
δ
)).
к.т.н. О.О.Васильев
Квантовые компьютеры и квантовые алгоритмы: потенциальные

Квантовые вычисления
Теорема об аппроксимации
Всякий унитарный оператор можно аппроксимировать с точностью δ
квантовой схемой из операторов H, K , Controlled Not и оператора
Тоффоли размера не более exp(O(n))poly (log(
1
δ
)).
Измерение
Вероятность получения базисного состояния x при измерении состояния
|ψ =
c x
|x равна |c x
|
2
к.т.н. О.О.Васильев
Квантовые компьютеры и квантовые алгоритмы: потенциальные

Квантовые вычисления
Теорема об аппроксимации
Всякий унитарный оператор можно аппроксимировать с точностью δ
квантовой схемой из операторов H, K , Controlled Not и оператора
Тоффоли размера не более exp(O(n))poly (log(
1
δ
)).
Измерение
Вероятность получения базисного состояния x при измерении состояния
|ψ =
c x
|x равна |c x
|
2
Квантовое вычисление
Схема U = U
L
· . . . · U
2
· U
1
вычисляет F , если для некоторого фиксированного ǫ <
1 2
z
| F (x), z|U|x, 0
N−n
|
2
≥ 1 − ǫ.
При этом уменьшение вероятности неверного ответа в k раз можно реализовать классической булевой схемой размера O(k log k log log k).
к.т.н. О.О.Васильев
Квантовые компьютеры и квантовые алгоритмы: потенциальные

Пример квантового алгоритма: алгоритм Гровера.
Об алгоритме
Алгоритм Гровера(L. Grover, 1996) позволяет производить поиск в неупорядоченной базе данных размера N за время O(

N
).
То есть, в квантовом случае оказывается возможным достичь квадратичное ускорение на задаче полного перебора.
При этом, более чем квадратичного ускорения достичь невозможно(C.Zalka, 1997).
Рис.:
Схема используемого оракула
Постановка задачи.
Пусть дано устройство, которое по входам x, y определяет некое булево значение A(x, y ). Необходимо вычислить функцию F (x) = ∃xA(x, y) и, по возможности, найти соответствующее y .
к.т.н. О.О.Васильев
Квантовые компьютеры и квантовые алгоритмы: потенциальные

Алгоритм Гровера
Упрощение
Будем предполагать, что для каждого x существует единственное y
0
такое,
что A(x, y
0
) = 1.
к.т.н. О.О.Васильев
Квантовые компьютеры и квантовые алгоритмы: потенциальные

Алгоритм Гровера
Упрощение
Будем предполагать, что для каждого x существует единственное y
0
такое,
что A(x, y
0
) = 1.
Алгоритм.
Рассмотрим операторы: U = I − 2|y
0
y
0
|, V = I − 2|ξ ξ|, где
|ξ =
1

N
y
|y .
Оператор U здесь- это квантовая “база данных”. Оператор V можно аппроксимировать базисными.
Тогда (VU)
s
|ξ при s ≈
π
4

N,
будет близко к вектору y
0
,
а, значит,
система с высокой вероятностью будет находиться в состоянии |y
0
к.т.н. О.О.Васильев
Квантовые компьютеры и квантовые алгоритмы: потенциальные

Алгоритм Гровера
Упрощение
Будем предполагать, что для каждого x существует единственное y
0
такое,
что A(x, y
0
) = 1.
Алгоритм.
Рассмотрим операторы: U = I − 2|y
0
y
0
|, V = I − 2|ξ ξ|, где
|ξ =
1

N
y
|y .
Оператор U здесь- это квантовая “база данных”. Оператор V можно аппроксимировать базисными.
Тогда (VU)
s
|ξ при s ≈
π
4

N,
будет близко к вектору y
0
,
а, значит,
система с высокой вероятностью будет находиться в состоянии |y
0
Пояснение.
Оператор VU- поворот на некоторый угол ϕ. При этом ξ|y
0
=
1

N
= sin
ϕ
2
,
то есть этот угол мал. Значит, при больших N ϕ ≈
2

N
,
значит, за s

π
4

N
итераций вектор повернется приблизительно на
π
2
к.т.н. О.О.Васильев
Квантовые компьютеры и квантовые алгоритмы: потенциальные

Некоторые, быть может, интересные алгоритмы.
Оценка градиента гладкой функции R
d
→ R за одну итерацию: S.P.
Jordan Fast Quantum Algorithm for Numerical Gradient Estimation.
arXiv:quant-ph/0405146v2
Квантовые алгоритмы оптимизации: W. Baritompa, D. Bulger, G.
Wood Grover’s quantum algorithm applied for global optimization//SIAM
J. of Optimisation Vol.15(2005) pp.1170-1184(и др. работы D.Bulger);
S.P. Jordan Quantum Computation Beyond the Circuit
Model//arXiv:0809.2307v1, PhD Thesis(MIT).
Решение систем линейных уравнений за время O(k log
3
k log N), где
N
- размер матрицы, а k - число обусловленности.A.Harrow, A.
Hassidim, S. Lloyd Quantum algorithm for solving linear systems of equations//Phys. Rev. Lett. 103, 150502 (2009), arXiv:0811.3171v3;
A.Ambainis Variable time amplitude amplifcation and a faster quantum algorithm for solving systems of linear equations//arXiv:1010.4458v2
к.т.н. О.О.Васильев
Квантовые компьютеры и квантовые алгоритмы: потенциальные


Поделитесь с Вашими друзьями:


База данных защищена авторским правом ©nethash.ru 2017
обратиться к администрации

войти | регистрация
    Главная страница


загрузить материал