О ПРИМЕНЕНИИ КВАНТОВЫХ ВЫЧИСЛЕНИЙ К ИНФОРМАЦИОННЫМ СИСТЕМАМ
Берзин Д.В.
Кандидат физико-математических наук, доцент, Финансовый университет при Правительстве Российской Федерации, Москва
О ПРИМЕНЕНИИ КВАНТОВЫХ ВЫЧИСЛЕНИЙ К ИНФОРМАЦИОННЫМ СИСТЕМАМ
Аннотация
В этой работе показывается, что если квантовые вычисления будут применены в информационных системах, то это может значительно улучшить их производительность.
Ключевые слова: ИТ, информационная система, прикладная информатика, кубит, алгоритмы поиска, Z-буфер.
Berzin D.V.
PhD in Physics and Mathematics, Associate Professor, Financial University under the Government of the Russian Federation, Moscow
ON APPLYING QUANTUM COMPUTATIONS TO CAD
Abstract
In the work, we demonstrate that quantum computations can improve performance of information systems.
Keywords: IT, information system, applied informatics, qubit, search algorithms, Z-buffer.
В [1] был дан краткий обзор существующих работ по квантовым вычислениям, а также было рассказано о принципе суперпозиции.
В классической физике возможные состояния системы, состоящие из n частиц, чьи отдельные состояния могут быть описаны вектором в двумерном линейном пространстве, составляют линейное пространство размерности 2n. Тем не менее, в квантовой системе результирующее пространство состояний намного объемнее: системе из n кубитов (см. [1]) соответствует пространство состояний размерности 2 . Таким образом, с ростом количества частиц мы наблюдаем экспоненциальный рост размерности пространства состояний. Что, в свою очередь, предполагает возможное экспоненциальное увеличение скорости вычислений на квантовых компьютерах (по сравнению с классическими компьютерами).
В классическом случае пространства состояний n частиц составляются посредством декартового произведения. Квантовые состояния, тем не менее, комбинируются через тензорное произведение. Давайте взглянем на разницу между декартовым произведением и тензорным произведением. Эта разница очень важна для понимания квантовых вычислений.
Допустим, что V и W - два двумерных комплексных линейных пространства с базисами {v ,v } и {w ,w } соответственно. Декартово произведение этих двух пространств может иметь в качестве базиса объединение базисов его пространств-компонент: {v ,v , w ,w }. Таким образом, размерность классического пространства состояний множественных частиц растет линейно с числом этих частиц, так как dim(X×Y)=dim(X)+dim(Y). Тензорное произведение V W простанств V и W имеет базис { v w , v w , v w , v w }. Таким образом, пространство состояний двух кубитов, у каждого из которых базис {|0>,|1>}, имеет базис {|0> |0>, |0> |1>, |1> |0>, |1> |1>}, который может быть записан более компактно как {|00>,|01>,|10>,|11>}. Обобщая, напишем |a>, что означает |a a …a >, где a - бинарные цифры числа a. Базис для системы из трех кубитов - это
{|000>,|001>, |010>, |011>,|100>,|101>,|110>,|111>}
и в общем, система из n кубитов имеет 2 базисных вектора. Мы теперь можем наблюдать экспоненциальный рост размерности пространства состояний с ростом числа квантовых частиц. Тензорное произведение X Y имеет размерность dim(X)×dim(Y).
Измерение единичного кубита проецирует квантовое состояние на одно из базовых состояний, ассоциированных с измерительным устройством. Результат измерения - вероятностный, и процесс измерения изменяет состояние к измеренному. Измерениями мы вторгаемся в систему. Согласно принципам квантовой механики, действие сопровождается проецированием пространства состояния системы, или ее коллапсом, который является необратимым процессом, так что измерение - это последний шаг, после которого система разрушается и уже не годится для практических целей. В таком смысле измерение может дать только частичную информацию.
Можно перечислить по меньшей мере два вида прикладных проблем, для которых использование квантовых компьютеров принесет однозначные преимущества.
- Алгоритмы поиска.
Следующая проблема хорошо известна. Нам дан неупорядоченный набор элементов a , a ,…, a. Требуется найти определенный элемент a . Например, ищется определенный номер в телефонной книге, принадлежащий человеку, имя которого неизвестно. Классический алгоритм требует N /2 шагов для списка из N номеров. Квантовый алгоритм Гровера [2] требует только количества состояний порядка .
- Разложение целых чисел на множители.
Рассмотрим классическую задачу разложения заданного целого числа N в произведение его простых делителей. На данный момент лучший алгоритм требует количество вычислений порядка exp[2L (log L) ], где L= log N. Квантовый алгоритм Шора [3] требует только O(L ) шагов. Таким образом, использование квантовых вычислений позволит относительно решить задачи, трудные для классических вычислений.
Естественно ожидать, что квантовые алгоритмы были бы весьма эффективны не только в задачах поиска и в арифметике. Например, алгоритм Гровера может быть очень полезным в информационных системах. Рассмотрим в качестве частного случая хорошо известную в CAD процедуру, называемую Z-буфер. Рассмотрим неупорядоченное множество, состоящее из N точек в R . Проблема заключается в их сортировке вдоль оси z. Предположим, например, что N=1000. На основании вышесказанного, используя квантовые вычисления, мы выполним процедуру сортировки приблизительно в 16 раз быстрее, чем используя обычный компьютер. Без сомнения, мы можем решать подобные проблемы намного эффективней, используя квантовые вычисления вместо классических алгоритмов. Безусловно, квантовые вычисления требуют специальных устройств (т.е. квантовых компьютеров), чтобы стать рабочим инструментом для науки и бизнеса. Научные исследования в этом направлении очень перспективны, и можно ожидать, что квантовые компьютеры станут повседневной реальностью в обозримом будущем.
Литература
- Д.В.Берзин "Квантовые вычисления и автоматизированные системы проектирования" // Международный научно-исследовательский журнал = Research Journal of International Studies, №8 (27), август 2014, с.9
- L.K.Grover. “Quantum mechanics helps in searching for a needle in a haystack.” // Phys.Rev.Lett. 79 (1997), 325-328.
- P.W.Shor “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer.” // SIAM J. Comput., 26:5 (1997), 1484-1509.
References
- D.V.Berzin "Kvantovye vychislenija i avtomatizirovannye sistemy proektirovanija" // Mezhdunarodnyj nauchno-issledovatel'skij zhurnal = Research Journal of International Studies, №8 (27), avgust 2014, s.9
- L.K.Grover. “Quantum mechanics helps in searching for a needle in a haystack.” // Phys.Rev.Lett. 79 (1997), 325-328.
- P.W.Shor “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer.” // SIAM J. Comput., 26:5 (1997), 1484-1509.