Сравнительная сложность квантовых и классических моделей вычислений

Какие проблемы являются вычислимыми и как эффективно они могут быть вычислены? В основе теории вычислимости лежит Тезис Черча-Тьюринга: все разумные модели вычислений могут быть смоделированы машиной Тьюринга. Для вычислимых проблем встает вопрос о сложности вычисления, а именно, какие физические ресурсы требуются для того, чтобы решить проблему — такие, как память, время, энергия, и т. д. Основными сложностными характеристиками, изучаемыми в теории сложности, являются время вычисления и память, затрачиваемая в процессе вычисления.

Фундаментальный вопрос теории сложности — как ведет себя функция сложности, если ее рассматривать как функцию от размера входа — п, и, в частности, является ли она полиномиальной или экснонен-циональной от п. При этом принято считать, что некоторая проблема решается просто, если сложность является полиномиальной от размера входаи является трудно разрешимой, если функция сложности является экспоненциальной от размера входа.

Не менее актульный вопрос — что значит решить проблему? Решить точно или допустить некоторую вероятность ошибочного результата? Теория вероятностных алгоритмов отменяет требование к результату всегда быть точным и разрешает некоторую вероятность ошибки. Это позволяет получить заметное. уменьшение сложности решения ряда известных проблем. В связи с этим была выдвинута современная версия тезиса Черча: Все разумные модели вычислений могут быть эффективно (с полиномиальной сложностью) смоделированы вероятностной машиной Тьюринга.

В 80-х годах было предложено рассматривать вычислительные модели, которые делают возможным использование квантово-механических эффектов. Впервые эти идеи были высказаны Benioff [33], Feynman [40], и Маниным [16]. Фейнман в 1982 высказал идею, что квантовая физическая система из R частиц не может быть смоделирована на обычном компьютере без эксноненционального замедления в эффективности моделирования. Фейнман также заметил, что этого замедления можно избежать, если использовать вычислительные устройства, работающие, опираясь на законы квантовой физики.

Впоследствии эти идеи были формализованы Deutsh [38], который впервые определил квантовую вычислительную модель, основанную на использовании квантовой суперпозиции — квантовый аналог вероятностной машины Тьюринга. Deusth предположил, что эта модель может быть эффективнее, чем классическая, для некоторых задач. Он также показал существование универсальной квантовой машины Тьюринга (а также модели квантовых сетей — квантовый аналог классических схем). Однако его модель универсальной квантовой машины Тьюринга имела один недостаток — моделирование других квантовых машин Тьюринга (QMT) могло иметь экспоненциальную сложность. Эта проблема была решена Bernstein и Vazirani (1993) [34]. Они показали существование универсальной QMT, способной моделировать другие QMT в полиномиальное время.

Могут ли квантовые вычисления быть эффективнее классических? Прежде всего, отметим, что квантовые вычислители не могут решать проблемы, не разрешимые на классической машине Тьюринга. Это следует из того, что все вычислимое в квантовой модели может быть смоделировано на классической машине просто вычислением амплитуд суперпозиции и записи их на рабочую ленту. Это моделирование может быть экеионенционально, но времени, но в конце концов мы сможем решить все, что мы можем решить квантово. Таким образом, различие между классическими и квантовыми вычислениями лежит только в вопросе их сложности. Тривиальное моделирование квантовых вычислений классическим экспоненциально, но времени и памяти. Bernstein и Vazirani [34] показали, что моделирование может быть полиномиально ио памяти, хотя все еще экеионенционально ио времени.

Теорема 0.1 [34] BQP С PSPACE.

Это включение впоследствие было уточнено: BQP С РР [30]. Соотношение между классами BQP и NP неизвестно.

В 1992 Deutsch, Josza [39] показали, что существует проблема (в настоящий момент неизвестно, лежит ли она в классе Р), которая может быть решена точно, в полиномиальное время на квантовом компьютере.

В 1994 Simon [54] получил важный результат — он предложил квантовый алгоритм решения задачи (состоящей в нахождении периода булевской функции), не имеющей классических эффективных решений даже при использовании вероятностных методов.

Позже Shor [53] предложил квантовый полиномиальный алгоритм разложения числа на простые множители (и вычисления дискретного логарифма) — проблемы, имеющей существенную важность для криптографии. На сегодня это наиболее известный и эффектный из пока еще небольшого числа существующих квантовых алгоритмов. На данный момент не известно классического полиномиального алгоритма решения данной задачи, не известно также, лежит ли данная проблема в классе ВРР и является ли она iVP-иолной. После этого результата, а также нескольких других, таких, как алгоритм Гровера [41] поиска в неупорядоченной базе данных и алгоритма Китаева [44] нахождения стабилизатора Абелевой группы, возрос интерес математического сообщества к теории квантовых вычислений.

За счет чего квантовые вычисления могут быть мощнее классических?

• Прежде всего это так называемый квантовый параллелизм. Размер квантового вычислительного пространства состояний экспоненциален по сравнению с физическим размером системы. Квантовая система может находиться одновременно в суперпозиции экспоненциального числа устойчивых базисных состояний, и параллельно выполнять операции над экионенциальным количеством аргументов.

• Следующее — параллельные вычисления могут создавать интерференцию, за счет чего вычислительные пути, накладываясь друг на друга, могут как гасить, так и усиливать друг друга.

• И наконец, это возможность устраивать скрещенные состояния, которые позволяют удаленным частям системы быть сильно связанными друг с другом.

Данная работа иосвящеиа сравнительному анализу квантовых, детерминированных, вероятностных моделей вычислеиий, а именно, бинарных программ и конечных автоматов. Диссертация состоит из 4 глав и устроена следующим образом. В главе 1 представлены необходимые определения, понятия и сведения, лежащие в основе теории квантовых вычислений. Главы 2,3 посвящены бинарным программам, глава 4 — конечным автоматам. Основные результаты диссертации представлены в главах 2−4.

В главах 2−4 рассматривается известная модель для вычисления булевых функций — бинарные ирограмы (BP). В главе 2 приведены необходимые определения и предварительные сведения, касающиеся соотношений между детерминированными и вероятностными BP с ограничениями. Основные результаты диссертации, касающиеся бинарных программ, приведены в главах 2,3.

Вычисления на BP можно трактовать как вычисления на одиночном процессоре, который на каждом такте работы может считывать не более одного бита входного слова.

Введение

в модель BP случайных вершин, в которых, в зависимости от датчика случайных чисёл, выбирается тот или иной путь дальнейшего вычисления, приводит к модели вероятностных бинарных программ. Впервые модель вероятностной бинарной программы была определена в работе [26]. Известно, что вероятностные бинарные программы с определенными ограничениями могут быть экспоненциально экономнее соответствующих детерминированных BP.

В главе 1 рассматриваются дополнительные ограничения бинарных программ, такие, как уровневость и забываемость. Известно, что бинарные программы общего вида могут быть преобразованы в уровневые забывающие не более чем с полиномиальным увеличением сложности. В работе мы определяем модель’квантовой бинарной программы как обобщение соответствующей вероятностной уровневой забывающей модели. Известная модель перестановочных детерминированных бинарных программ является частным случаем квантовых бинарных программ, где преобразования, применяемые на каждом шаге вычисления — это перестановки. Известно, что класс функций, вычислимых перестановочными бинарными программами ограниченной ширины совпадает с классом NC1 функций, вычислимых схемами из функциональных элементов логарифмической глубины [8].

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

• Доказываются соотношения классов сложности РР-ВР, PrQP-ВР, BQP-BP, определенных для модели бинарных программ. При этом используется техника моделирования:

Моделирование классического вероятностного процесса вычисления квантовым использует известный прием моделирования вероятности ½ при помощи квантовой частицы. Имея вероятностную бинарную программу, вычисляющую функцию / на наборе, а с вероятностью правильного результата а-сг, мы строим квантовую бинарную программу, использующую измерения на каждом шаге вычисления, которая вычисляет функцию / на наборе, а с той же вероятностью (метод «квантового моделирования «вероятностной бинарной программы — Теорема 2.3).

Для моделирования квантового процесса вычисления классическим вероятностным (Теорема 2.2) используется разработанный нами метод «линейного моделирования», который частично является обобщением метода моделирования линейных конечных автоматов вероятностными.

• Мы доказываем нижнюю оценку сложности один раз читающей квантовой бинарной программы, вычисляющей произвольную булеву функцию / с ограниченной ошибкой (Теорема 3.1). Полу.

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

• На примере известной симметрической функции MODp мы доказываем, что один раз читающая квантовая BP может быть экспоненциально экономнее один раз читающей как детерминированной, так и вероятностной BP. Для данной функции доказываются нижние оценки сложности детерминированной BP и вероятностной BP, дающей правильный результат с большой вероятностью. Строится квантовая BP, вычисляющая MODp с ограниченной ошибкой.

Глава 4 посвящена исследованию конечных автоматов. Модель вероятностного конечного автомата, определяемая как обобщение детерминированного конечного автомата стала являться обьектом пристального исследования с 60-х годов. Известно, что конечные вероятностные автоматы с ограниченной ошибкой распознают только регулярные языки (Теорема редукции Рабина [19]). Известны примеры языков, для которых вероятностный автомат является более экономным, чем детерминированный, и примеры языков, для которых вероятностный автомат не дает приемущества перед детерминированным. Важным является результат П. Туракайнена [56] о тождественности класса стохастических языков и языков, представимых в конечных линейных автоматах. В диссертации рассматривается модель одностороннего квантового конечного автомата. Впервые эта модель была определена в [45, 48]. Известно, что квантовые конечные автоматы с ограниченной ошибкой распознают собственное подмножество регулярных языков. Кроме того, известен пример регулярного языка, не распознаваемого квантовым конечным автоматом с ограниченной ошибкой [45]. В работе мы рассматриваем две модели квантового конечного автомата — один раз измеряемый квантовый конечный автомат, в котором измерение («снятие результата вычисления») производится один раз по окончании процесса вычисления и много раз измеряемый квантовый конечный автомат, в котором измерение производится после каждого шага вычисления. Основными результатами главы 4 являются:

• Доказывается Теорема 4.1 о сложности классического моделирования квантовых конечных автоматов.

• Мы оцениваем сложность моделирования вероятностного конечного автомата, распознающего произвольный язык L, квантовым конечным автоматом, допускающим измерение текущей конфигурации после каждого шага вычисления (Теорема 4.2). Для этого предлагается метод «квантового моделирования «вероятностного конечного автомата, который является развитием разработанного нами метода «квантового моделирования «вероятностной бинарной программы.

• Мы доказываем нижнюю оценку сложности квантового конечного автомата, распознающего произвольный язык с ограниченной ошибкой (Теорема 4.3). При этом доказанная оценка формулируется в терминах сложности минимального детерминированного автомата, распознающего тот же самый язык. Полученная нижняя оценка является почти точной: пример языка, приведенного в работе [31], демонстрирует экспоненциальное ириемущество квантовых конечных автоматов перед детерминированными и вероятностными автоматами, распознающими языки с ограниченной ошибкой.

Основные результаты, относящиеся к предмету диссертации, изложены в работах [2, 3, 4, 5, 11, 12, 21, 22, 23, 24, 6, 25] и были доложены на 25 Международной конференции FCT'2000 (Братислава, Словения), международной конференции «Optimal Discrete Structures and Algorithms» (Росток, Германия, 2000 г.), IV Международной конференции «Дискретные модели в теории управляющих систем «(мехмат,.

МГУ, 2000 г., 2003 г.), 13 Международной конференции FCT'2001 (Рига,. Латвия), XII, XIII, XLV Международных школах-семинарах по теоретической и математической физике (Казань, 2001 г., 2002 г., 2003 г.), VII Международном семинаре «Дискретная математика и ее приложения» (мехмат, МГУ, 2001 г.), XIII Международной конференции «Проблемы теоретической кибернетики «(Казань, 2002 г.), 14 Международной конференции FCT'2003 (Malmo, Sweden), на семинарах мехмата Московского госуниверситета (руководитель — академик РАН, д.ф.-м.н., профессор Лупанов О.В.), на семинарах математического института им. В. А. Стеклова (руководитель — член кор. РАН. профессор Разборов А.А.), на семинарах физико-технического института РАН (руководитель — академик РАН, Валиев К.А.), на семинаре Латвийского госуниверситета (руководитель — академик Латвийской АН, д.ф.-м.н., проф. Фрейвалд Р.В.), на итоговых научных конференциях Казанского государственного университета, на семинарах ио квантовым вычислениям Казанского госуниверситета (руководитель — д.ф.-м.н., нроф. Аблаев Ф.М.).

1. Аблаев Ф. М. Влияние степени изолированности точки сечения на число состояний вероятностного автомата / Ф. М. Аблаев // Математические заметки. — М.:Изд-во «Наука», Главная редакция физико-математической литературы, 1988. — Т. 4, N 3. — С. 289−297.

2. Александров П. С.

Введение

а теорию множеств и общую топологию / П. С. Александров. М.: Главная редакция физико-математической литературы издательства «Наука», 1977. — 3G8 с.

3. Баррингтон Д. Ветвящиеся программы ограниченной ширины, имеющие полиномиальную сложность, распознают в точности языки из NC1 / Д. Баррингтон // Кибернетический сборник. М.: Мир, 1991. — вып. 28. — С. 94−113.

4. Бухараев Р. Г. Основы теории вероятностных автоматов / Р.Г. Бу-хараев. М.: Наука. Главная редакция физико-математической литературы, 1985. — 288 с.

5. Валиев В. А. Квантовые компьютеры: надежды и реальность / В. А. Валиев, А. А. Кокин. Ижевск: НИС «Регулярная и хаотическая динамика», 2001. — 352 с.

6. Гайнутдинова А. Ф. О сравнительной сложности квантовых и классических бинарных программ / А. Ф. Гайнутдинова // Дискретная математика. Москва: изд-во РАН, 2002. — Т. 14, вып. 3. — С. 109 121.

7. Кемени Д. Конечные цепи Маркова / Д. Кемени, Д. Снелл. М.: Главная редакция физико-математической литературы изд-ва «Наука», 1970. 271 с.

8. Китаев А. Классические и квантовые вычисления / А. Китаев, А. Шень, М. Вялый. М.: МЦНМО, ЧеРО, 1999. — 192 с.

9. Кострикин А. И. Линейная алгебра и геометрия / А. И. Кострикин, Ю. А. Манин. М.:Изд-во Моск. ун-та, 1980. — 320 е., 10 ил.1G. Манин Ю. И. Вычислимое и невычислимое / Ю. И. Манин. М.: Сов. радио, 1980. — 128 с.

10. Покровская И. А. Некоторые оценки числа состояний вероятностных автоматов, представляющих регулярные события / И. А. Покровская // Проблемы кибернетики. М.: Изд-во физ.-мат литературы, 1979. — вып. 36. — С. 181−194.

11. Рабин М. Вероятностные автоматы / М. Рабии // Кибернетический сборник. М.: Изд-во Мир, 1964. — вып.9. — С. 123−141.

12. Фрейвалд Р. В. Об увеличении числа состояний при детерминиза-ции конечных вероятностных автоматов / Р. В. Фрейвалд // Автоматика и вычислительная техника, 1982. N 3. — С. 39−42.

13. Ablayev F. On the Lower Bounds for One-Way Quantum Automata / F. Ablayev, A. Gainutdinova // Proc. of the 25th International Symposium, Mathematical Foundations of Computer Science (MFCS'2000, Bratislava) Springer-Verlag, 2000. — V. 1893. P. 132−140.

14. Ablayev F. On the Lower Bounds for One-Way Quantum Automata / F. Ablayev, A. Gainutdinova // Optimal Discrete Structures and Algorithms, (Rostok, Germany, September 11−13, 2000), Schedule and abstracts. University Rostok, 2000. — P. 13.

15. Ablayev F. On Computational Power of Quantum Branching Programs / F. Ablayev, A. Gainutdinova, M. Karpinski // Preprint. -Mathematical Sciences Research Institute, MSRI, 2002. N 2002;028. 20 p.

16. Ablayev F. Classical Simulation Complexity of Quantum Machines / F. Ablayev, A. Gainutdinova // Proc. 14th International Symposium FCT 2003, Mahno, Sweden, August 12−15, 2003. Lecture Notes in Computer Science, 2003. — V. 2751. — P. 296−302.

17. Ablayev F. On the power of randomized branching programs / F. Ablayev, M. Karpinski // Proc. 28th ICALP (1996). LNCS, Springer, 1996.-V. 1099.-P. 348−356.

18. Ablayev F. A Lower Bound for Integer Multiplication on Randomized Read-Once Branching Programs / F. Ablayev, M. Karpinski // Information and Computation. Elsevier, 2003. — V. 186, N 1. — P. 78−89.

19. Ablayev F. On BPP versus NP U coNP for ordered read-once branching programs / F. Ablayev, M. Karpinski, R. Mubarakzjanov // Theoretical Computer Science. Elsevier, 2001. — V. 264. — P. 127 137.

20. Ablayev F. Quantum and Stochastic Branching Programs of Bounded Width / F. Ablayev, C. Moore, C. Pollett // Proc. of the ICALP'2002, Lecture Notes in Computer Science. Springer-Verlag, 2002. — P. 343 354.

21. Adleman L. Quantum computability / L. Adleman, J. Demarrais, M. Huang // SIAM Л. on Computing, 1997. V. 26, N 5. — P. 1524−1540.

22. Ainbainis A. 1-way quantum finite automata: strengths, weaknesses and generalization //A. Ambainis, R. Freivalds // Proc. of the 39th IEEE Conference on Foundation of Computer Science. Computer Society Press, 1998. — P. 332−342.

23. Bennett C.H. Logical reversibility of computations / C.H. Bennett // IBM Jounal of Res. Develop, 1973. V. 17. — P. 525−532.

24. Benioff P.A. Quantum mechanical hamiltonian models of turing machines / P.A. BeniofF // Journal of Statistical Physics, 1982. V. 29, N 3. — P. 515−546.

25. Bernstein E., Vazirani U. Quantum complexity theory / E. Bernstein, U. Vazirani.// SIAM J. Comput, 1997. V. 26, N 5. — P. 1411−1473.

26. Cobham A. The recognition problem for the set of perfect squares / A. Cobham // Proc. of the 7th Symposium on Switching an Automata Theory (SWAT), 1996. P. 78−87.

27. Deutsch D. Quantum theory, the Church-Turing principle and the universal quantum computer / D. Deutsch // Proceedings of the Royal Society. London, 1985. — A400. — P. 97−117.

28. Deutsch D. Rapid solution of problems by quantum computation / D. Deutsch, R. Lozsa // Proc. of the Royal Society. London, 1992. -A439. — P. 553−558.

29. Feynman R. Simulating physics with computers / R. Feynman // International Journal of Theoretical Physics, 1982. V. 21, N 6,7. -P. 4G7−488.

30. Grover L. A fast quantum mechanical algorithm for database search / L. Grover // Proc. of 28th STOC, 1996. P. Philadelphia PA USA, 2996. — P. 212−219.

31. Gruska J. Quantum computing / J. Gruska. McGraw-Hill Publishing Company, 1999. — 419 p.

32. Green F. On the Complexity of Quantum ACC / F. Green, S. Homer, C. Pollet // Proc. of the 15th IEEE Conf. on Computational Complexity. Computer Society Press, 2000. — P. 250−262.

33. Kitaev Л. Yu., Quantum measurements and the Abelian Stabilizer Problem / A. Yu. Kitaev // http://xxx.lanl.gov/archive/quant-ph, 1995. quant-ph/9 511 026.

34. Kondacs A. On the power of quantum finite state automata / A. Kondacs, J. Watrous // Proc. of the 38th Annual Symposium on Foundations of Computer Science, 1997. P. 66−75.

35. Lecerf Y. Machines de Turing reversibles. Recursive insolubilite en n 6 N de l’equation и = 0n ou в est un isomorphisme de codes / Y. Lecerf // Comptes rendus de l’Academie francaise des sciences, 1963. V. 257. — P. 2597−2600.

36. Moore C. Some Notes on Parallel Quantum Computing / C. Moore, M. Nilson // http://xxx.lanl.gov/archive/quant-ph. quant ph/9 804 034.

37. Moore C. Quantum automata and quantum grammars / C. Moore, J. Crutchfield // http://xxx.lanl.gov/archive/quant-ph. quant-ph/9 707 031.

38. Motwani R. Randomized Algorithms / R. Motwani, P. Raghavan. -Cambridge University Press, 1995. 492 p.

39. Nayak A. Optimal lower bounds for quantum automata and random access codes / A. Nayak // Proc. of the 40th IEEE Conference on Foundation of Computer Science, 1999. P. 369−376.

40. Pudlak P. Space complexity of computations / P. Pudlak, S. Zak // Technical report, Univ. Prague, 1983.

41. Shor P. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer / P. Shor // SI AM J. on Computing, 1997. V. 26, N 5. — P. 1484−1509.

42. Simon D. On the power of quantum computation / D. Simon // SIAM Journal of Computing, 1997. V. 26, N 5. — P. 1474−1483.

43. Travaglione B.C. ROM-based computation: quantum versus classical / B.C. Travaglione, M.A. Nielsen, H.M. Wiseman, A. Ambainis // http://xxx.lanl.gov/archive/quant-ph. quant-ph/109 016.

44. Turakainen P. Generalized automata and stochastic languages / P. Turakainen // Proc. Amer. Math. Soc., 1969. V. 21. — P. 303−309.

45. Wegener I. Branching Programs and Binary Decision Diagrams / I.Wegener. Siam Monographs on Discrete Mathematics and Applications, 2000. — 408 p.

46. Yao A. Quantum circuit complexity / A. Yao // Proc. 34th IEEE Symposium on Foundation of Computer Science, 1993. P. 352−361.