Время и память квантовых и недетерминистических вычислений тема автореферата и диссертации по физике, 01.04.02 ВАК РФ

03 Введение

Об Глава 1. Квантовые компьютеры с последовательным доступом

06 1.1. Классические и квантовые вычисления

07 1.1.1. Введение в классические алгоритмы

08 1.1.2. История квантовых вычислений. Недетерминизм 10 1.2 Общие принципы квантовых вычислений

10 1.2.1 Гильбертово пространство состояний и наблюдения

11 1.2.2 Матрица плотности и проблема декогерентности 13 1.3 Формализация квантовых алгоритмов

13 1.3.1 Различные модели квантовых вычислений

13 1.3.2 Модель квантового компьютера. (неформальное описание)

16 1.3.3. Модель квантового компьютера.

18 1.3.4 Роль оракула в квантовом компьютере

20 1.4 Формулировка основных результатов

23 1.5 Вероятностная мера на оракулах

24 1.6. Моделирование эволюций на компьютере с оракулом 24 1.6.1. Классическое моделирование эволюций

26 1.6.2. Квантовое моделирование коротких эволюций

28 1.6.3. Нижняя граница времени квантовой имитации.

30 Глава 2. Квантовые алгоритмы, использующие поиск

30 2.1 Проверка формул логики предикатов

30 2.1.1 Формулировка результата

31 2.1.2 Унитарные алгоритмы

34 2.1.3 Элиминация кванторов

35 2.2 Нижняя оценка сложности квантового перебора 35 2.2.1 Формулировка основной теоремы.

37 2.2.2 Доказательство

40 2.2.3 Нижняя оценка времени квантового поиска

40 2.3 Квантовая база данных

40 2.3.1 Квантовые методы хранения и защиты информации

42 2.3.2 Основные свойства преобразования диффузии

42 2.3.3 Относительное преобразование диффузии

43 2.3.4 Реализация относительного преобразования диффузии.

46 2.3.5 Защита информации

47 2.3.6 Замечание о коррекции ошибок в базе данных

49 Глава 3. Вычисления на недетерминистических клеточных

49 3.1 Клеточный автомат как модель вычислений.

51 3.2 Основные определения и результаты

55 3.3 Метод прямого моделирования

62 3.4 Оптимизация автоматов.

65 3.5 Метод эвольвент

70 Некоторые проблемы

Цель работы

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

Полученные результаты

В диссертации установлены следующие новые научные результаты.

По квантовым компьютерам.

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

2. Доказано, что не слишком длинная эволюция классической системы, выбранной произвольно с вероятностью 1 не может быть предсказана на квантовом компьютере даже на один шаг вперед. Таким образом, большинство классических алгоритмов с оракулом нельзя ускорить на квантовом компьютере. Вот точная формулировка этого результата.

Теорема 1.1.

Если Т = 0(27+7), е > 0; то для черного ящика f выбранного случайно из ■равномерного распределения с вероятностью 1 всякое квантовое вычисление Т итераций f требует не меньше Т обращений к /.

3. Для эволюций произвольной длины классических систем, выбранных с вероятностью 1, получена нижняя оценка на время квантовой имитации как квадратный корень из длины эволюции. Точная формулировка результата такова.

Теорема 1.2. Для черного ящика f выбранного произвольно из равномерного распределения с вероятностью 1 всякий квантовый компьютер, вычисляющий результат Т итераций f использует Í2(\/T) обращений к /.

4. Получена новая нижняя оценка для квантового перебора: Теорема 2.2.

Пусть í(n) = o(y/N/b(n)), п —У оо, и некоторый квантовый компьютер с оракулом для ф находит за время t(n) решение уравнения ф(х) = 1 для некоторых ф с фиксированной верхней оценкой е для вероятности ошибки (Í) < е < 1). Пусть р(п) будет вероятностью того, что этот алгоритм дает правильный ответ для оракула ф, выбранного случайно из равномерного распределения на Sb■ Тогда р(п) —> 0 (п —у оо).

5. Построен квантовый алгоритм с параллельным доступом к оракулу, распознающий истинность формул логики предикатов за время порядка квадратного корня из длины формулы (уточнение и модернизация алгоритма Бурхама и др., полученное независимо).

Теорема 2.1 [36]. Существует квантовый алгоритм, проверяющий формулу логики предикатов вида (2.1) за время с ограниченной вероятностью ошибки с использованием (Сп)к одновременных обращений к оракулу, где константа С зависит от вероятности ошибки. 3

6. Предложена схема квантовой базы данных, реализующая степень защиты информации, принципиально недостижимую в классических базах данных. Система управления такой базой данных основана на введенном автором относительном преобразовании диффузии (см. Главу 2). Соотношение между вероятностями несанкционированного получения информации и обнаружения такой попытки устанавливает такая Теорема.

Теорема 2.4. Существует, функция a(g,N), такая что Ve > 0 Зд : a(g,N) > 1-е N = 1,2,. со следующим свойством. Для всякого выбора блоков, обозреваемых S и унитарных преобразований, которые S совершает, имеет место неравенство

Рех > рас.

По классическим недетерминистическим алгоритмам, реализуемым на клеточных автоматах.

7. Для самых быстрых недетерминистических клеточных автоматов установлена линейная связь памяти и времени.

Теорема 3.3. Пусть Л есть наибыстрейший недетерминистический клеточный автомат. Тогда

3.3) Тд(п) = 0(SA(n)).

8. Построен способ имитации r-мерных недетерминистических клеточных автоматов с временем Т и памятью S в г + 1-мерном пространстве за время <9(Т1-Г/(Г+1)2) или Tr+1 = 0(Т^2 + S).

Теорема 3.1.

NC(r, Т, S) С NC(r + 1, Vf + S, VT + S).

Теорема 3.2.

NC(r,T,5)CNC(r,T1,T1), где Ti = T^S^TT

Разработанные методы

В диссертации исследованы вычисления в моделях с двумя вариантами недетерминистичности: более сильной - классической и более слабой - квантовой. Предложена удобная для теоретических исследований модель квантового компьютера с разделением классической и квантовой частей. Для квантовых вычислений разработан метод получения нижних оценок, основанный на подсчете расстояний между состояниями квантового компьютера как точками в Гильбертовом пространстве состояний. На основе этого метода получены три первых результата о квантовых вычислениях. Введено понятие унитарных квантовых вычислений, и с использованием этого понятия построен квантовый алгоритм с параллельным доступом к оракулу для проверки истинности формул логики предикатов 1 порядка.

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

Структура диссертации

Заключение и выводы

Подытожим основные новые результаты, представленные в этой работе.

1. Возможность ускорения произвольных вычислений при расширении памяти установлена только для классических недетерминистических вычислительных устройств. Для таких устройств зависимость времени от памяти линейна при любой фиксированной размерности. При увеличении размерности на единицу скорость произвольных вычислений можно увеличить в соответствии с формулами

Тг+1,р = 0((ТГ)р)1г/(г+1)2) или Тг+1 = 0(Т^2 +5).

2. Большинство классических алгоритмов с оракулом и временем Т = О(Ж^) не допускает никакого квантового ускорения, где N - общее число конфигураций вычислительного устройства, е > 0. Эволюцию большинства классических систем такой длины нельзя предсказать на. квантовом компьютере даже на один шаг вперед. Для произвольного времени Т нижняя граница квантового моделирования для большинства классических систем установлена как л/ЛГ).

3. Для задачи квантового поиска решения уравнения /(ж) = 1 установлена сильная форма нижней оценки времени как 0(у/ЛгД), где I - число решений: любой более быстрый алгоритм даст неверный ответ для большинства функций /.

4. На квантовом компьютере с (Мп)к одновременными запросами к оракулу формулу логики предикатов можно проверить за время л/2", где п -длина формулы, к - число перемен кванторов, М - зависящая от допустимой вероятности ошибки константа.

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

Из этих результатов можно сделать такие общие выводы:

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

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

3. В некоторых более сложных случаях чем задача перебора, например, в задаче о проверке формул логики предикатов, наличие возможности параллельного доступа к оракулу дает возможность получить то же ускорение, что и для КР-задач.

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

Перспективы дальнейших исследований

Мы кратко наметим здесь возможные постановки дальнейших математических задач в теории сложности квантовых вычислений, которые представляются сейчас наиболее важными.

1. Выяснить, дает ли возможность Ь одновременных обращений к оракулу (X << 2та) ускорение произвольного вычисления для а) детерминистических клеточных автоматов, б) классических вероятностных клеточных автоматов, в) квантовых компьютеров, г) квантовых компьютеров по сравнению с классическими с той же возможностью.

2. Существует ли общий способ хоть какого-нибудь ускорения длинных классических вычислений с временем, превышающим на квантовом компьютере с последовательным доступом к оракулу.

3. Можно ли распознать истинность произвольной формулы логики предикатов на квантовом компьютере с последовательным доступом к оракулу за время л/К. Если нет, то доказать невозможность.

4. Существуют ли другие схемы существенных квантовых ускорений, отличные от метода Гровера и квантового преобразования Фурье, для алгоритмов: а) с малой памятью (порядка длины входного слова), б) с большой памятью. в) с малым временем сохранения когерентности.

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

Благодарности

Автор благодарит академика РАН В. П. Маслова за поддержку и внимание к этой работе, член.-корр. РАН, ректора МГТУ "Станкин" Ю. М. Соломенцева за создание благоприятных условий, профессоров МГУ О. А. Хрусталева и В. Л. Голо за полезные обсуждения, а также Л. К. Гровера и П. Хоера за дискуссии, приведшие к прояснению модели кван-того компьютера.

1. Доступ к электронному архиву через Интернет:http://xxx.lanl.gov/abs/uMsr архива/номер статьи, где имя архива есть quant-ph или comp-gas, номер статьи указан в списке литературы.

2. D.Aharonov , M.Ben-Or, Fault-Tolerant Quantum Computation With Constant Error, Proc. of the 29th Annual ACM Symposium on Theory of Computing (STOC) 1997, lanl e-print quant-ph/9611025.

3. T. Baker, J. Gill, R. Solovay, Relativixations of the P=?NP question, SIAM J. Comput. 4 (N 4), 431-442.

4. R.Beals, H.Buhrman, R.Cleve, M.Mosca, R.de Wolf, Tight Quantum Bounds by Polynomials, 19 Feb. 1998, lanl e-print quant-ph/9802049).

5. V.P. Belavkin, V.P. Maslov, Design of the optimal dynamics analysis: mathematical aspects of sound and visual pattern recognition, In: Mathematical aspects of computer, Mir, Moscow (1988).

6. P. Benoiff, Quantum mechanical Hamiltonian models of Turing machines, J. Stat. Phys. 22 (1982), 515-546.

7. C. Bennett, Logocal reversability of computation, IBM J. Res. Develop. 17 (1973), 525-532.

8. C. Bennett, J. Gill, Relative to a random oracle A, PA ф NPA ф NPA with probability 1, SIAM J. Comput. 10 (N 1) (1981), 96-113.

9. C.H.Bennett, E.Bernstein, G.Brassard, U.Vazirani, Strenths and Weakness of Quantum Computing, To appear in SIAM Journal on Computing, lanl e-print quant-ph/9701001.

10. C.H. Bennett, G. Brassard, C. Crepau, R. Jozsa, A. Peres, W.K. Wootters, teleportation an unknown quantum state via dual classical and Einstein-Podolsky-Rosen channels, Phys. Rev. Lett. 70 (1993), 1895-1898.

11. Б.Bernstein, U.Vazirani, Quantum complexity theory, preliminary version in Proceedings of the 25 Annual ACM Symposium On Theory of Computing, 1993, pp 11-20, SIAM J. Comput. 26 (5) (1997), 1411-1473.

12. A.Berthiaume, G.Brassard, Oracle quantum computing, Journal of modern optics 41 (N 12) (1994), 2521-2535.

13. Buhrman H., Cleve R., Wigderson A., Quantum vs. Classical Communication and Computation, Proc. 30th Ann. ACM Symp. on Theory of Computing (STOC 98), pp. 63-68.

14. A.W.Burks, Essays on Cellular Automata, Univ. of Illinois Press, 1970.

15. A.R.Calderbank, P.W.Shor, Good quantum error-correcting codes exist, Phys. Rev. 54 (1996), 1098-1105.

16. I.L. Chuang, L.M.K. Vandersypen, X. Zhou, D.W. Leung, S. Lloyd, Experimental realization of a quantum algorithm, Nature 393 (1998), 143-146.

17. S.Cook, The complexity of theorem-proving procedures, ACM, NY, Proceedings of the 3rd Annual Symposium on the theory of Computing (1971), 151-158.

18. K.Culik,Sheng Yu., Undecidebility of cellular automata. Classification schemes, Complex Systems 2(2) (1988), 177-190.

19. D.Deutsch, Quantum theary, the Church-Turing principle and the universal quantum computer, Proc.R.Soc.Lond. A 400 (1985), 97-117.

20. D.Deutsch, R.Jozsa, Rapid solution of problems by quantum computation, Proc. Roy. Soc. Lond. A 439 (1992), 553-558.

21. C. Durr, P. Hoyer, A Quantum Algorithm for Finding the Minimum, lanl e-print quant-ph/9607014.

22. E. Fahri, S. Gutmann, Quantum mechanical square root speedup in a structured search problem, lanl e-print, quant-ph/9711035.

23. E.Farhi, J.Goldstone, S.Gutmann, M.Sipser, Л Limit, on the Speed of Quantum Computation in Determining Parity, 16 Feb. 1998, lanl e-print quant-ph/9802045.

24. R.P. Feynman, Simulation physics with computers, Int. J. Phys. 21 (1982), 467-488.

25. L.K.Grover, A fast quantum mechanical algorithm for database search, Proceedings, STOC, Philadelphia PA USA (1996), 212-219.

26. A.Kitaev, Quantum measurements and the Abelian Stabilizer Problem, lanl e-print quant-ph/9511026.

27. L, Landau, . Lifshits, Quantum mechanics. Nonrelativistic theory Theoretical physics, volume 3, Moscow, 1963.

28. Levin, Axiom of choise in classical analysis, Vest. MSU 4 (1975), 59-65.

29. S.Molotkov, S.S.Nazin, Single Spin State Detection for the Kane Model of Silicon-based Quantum Computer, lanl e-print quant-ph/9906106.

30. J. von Neumann, Theory of Self-Reproducing Automata (A.Burks, ed.), Univ. of Illinois Press, 1966.

31. Y. Ozhigov, About quantum mechanical speeding up of classical algorithms, lanl e-print quant-ph/970'6003.

32. Y. Ozhigov, Quantum computer can not speed up iterated application of a black box, Lecture Notes in Computer Science 1509 (1999), 521-530.

33. Y. Ozhigov, Quantum computers speed up classical with probability zero, Chaos, Solitons and Fractals 10 (10) (1999), 1707-1714, lanl e-print quant-ph/9803064.

34. Y. Ozhigov, Protection of information in quantum databases, Complex Systems 11 (1997), 223-232,, lanl e-print quant-ph/9712016.

35. Y. Ozhigov, Lower bounds of quantum search for extreme point, Proc. Royal. Soc. (Math. Phys. Engineering Science) 455 (1999), 2165-2172, lanl e-print quant-ph/9806001.

36. Y.Ozhigov, Fast quantum verification for the formulas of predicate calculus, lanl e-print quant-ph/9809015.

37. Y.Ozhigov, Speedup of iterated quantum seach by a parallel performance, lanl e-print quant-ph/9904039.

38. Y. Ozhigov, Computations on nondeterministic cellular automata, Information and Computation 148 (1999), 181-201, lanl e-print comp-gas/9801001.

39. Y. Ozhigov, Lindenmayer systems as a model of computations, lanl e-print comp-gas/9801002.

40. Y.Ozhigov, Cellular automata and comtinuous functions: negative results, Complex Systems 10 (1996), 383-389.

41. P.W. Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on Quantxim Computer, Proceedings of the 35th Annual Symposium on Foundations of Computer Science, Santa Fe (1994), 124-134. IEEE Computer Society Press.

42. D. Simon, On the power of quantum computations., Proceedings of the 35th Annual Symposium on the Foundations of Computer Science. IEEE Computer Society Press, Los Alamos, CA (1994), 116.

43. A. Steane, Quantum computing, lanl e-print quant-ph/9708022.

44. K.Sutner, The computational complexity of cellular automata, Lecture Notes in Computer Science, Proceedings of Fundamentals of Computation Theory, vol. 380, Springer, Berlin, 1989, p. 451.

45. S. Ulam, Random Processes and Transformations, Proc. Int. Cong. Mathem. 2 (1952), 264275.

46. I.V.Volovich, Models of Quantum Computers and Decoherence Problem, lanl e-print quant-ph/9902055.

47. D. Ventura, T. Martinez, Quantum associative memory, lanl e-print quant-ph/9807053.

48. Wim van Dam, Quantum oracle interrogation: getting all information for almost half the price, lanl e-print quant-ph/9805006.

49. J. Watrous, On One-Dimensional Quantum Cellular Automata, Proceedings of the 36th Annual IEEE Symposium on Foundations of Computer Science (1995).

50. S.Wolfram, Computation theory of cellular automata, Comm.Math.Physics 96(1) (1984), 1557.

51. S.Wolfram, Cellular Automata and Complexity: Collected Papers, Addison-Wesley, 1994.

52. T.Yaku, The constructibility of a configuration in cellular automata, Journal of Computers and System Science 7 (1973), 481-496.

53. A.Yao, Quantum Circuit Complexity, Proceedings 34th Annual Symposium on Foundations of Computer Science (FOCS) (1993), 352-361.

54. Cellular Automata, Proc. of an Interdisciplinary workshop, Los Alamos, Ne mexico, USA, Mar. 7-11 1983, vol. 13, Amsterdam, North-Holland physics publ., 1984, p. 247.

55. Cellular automata.Theory and experiment, Proc. of a workshop, Los Alamos, Ne Mexico, USA, vol. 17, Amsterdam, North-Holland, 1990, pp. 483.

56. Ожигов Ю.И. Быстрое квантов о-механическое распознавание логических формул ДАН РФ, сер. "Информатика", в печати.

57. Ожигов Ю.И. Квантовые вычисления, монография, изд-во МГТУ "СТАНКИН", в печати.

58. Ожигов Ю.И. О квантовом моделировании классических эволюции, Работа депонирована в ВИНИТИ, 21.06.99, N 1976-В, 99.

59. Ожигов Ю.И. Возможности квантового поиска экстремумов, Работа депонирована в ВИНИТИ, 21.06.99, N 1977-В, 99.

60. Ожигов Ю.И. Квантовая проверка логических формул, Работа депонирована в ВИНИТИ, 21.06.99, N 1978-В, 99.

61. Ожигов Ю.И. Защита информации в квантовой базе данных, Работа депонирована в ВИНИТИ, 21.06.99, N 1979-В, 99.

62. Ожигов Ю.И. Методы получетья нижних оценок сложности квантовых алгоритмов, рукопись.