О применении квантовых вычислений к информационным системам
Характеристика классической задачи разложения целого числа в произведение его простых делителей. Исследование экспоненциального роста размерности пространства состояний с ростом числа квантовых частиц. Преимущества использования квантовых компьютеров.
| Рубрика | Математика |
| Вид | статья |
| Язык | русский |
| Дата добавления | 21.06.2018 |
| Размер файла | 14,8 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
О применении квантовых вычислений к информационным системам
Берзин Д.В.
Аннотация
В этой работе показывается, что если квантовые вычисления будут применены в информационных системах, то это может значительно улучшить их производительность.
Ключевые слова: ИТ, информационная система, прикладная информатика, кубит, алгоритмы поиска, Z-буфер.
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).
Измерение единичного кубита проецирует квантовое состояние на одно из базовых состояний, ассоциированных с измерительным устройством. Результат измерения - вероятностный, и процесс измерения изменяет состояние к измеренному. Измерениями мы вторгаемся в систему. Согласно принципам квантовой механики, действие сопровождается проецированием пространства состояния системы, или ее коллапсом, который является необратимым процессом, так что измерение - это последний шаг, после которого система разрушается и уже не годится для практических целей. В таком смысле измерение может дать только частичную информацию.
Можно перечислить по меньшей мере два вида прикладных проблем, для которых использование квантовых компьютеров принесет однозначные преимущества.
1. Алгоритмы поиска.
Следующая проблема хорошо известна. Нам дан неупорядоченный набор элементов a , a ,…, a. Требуется найти определенный элемент a . Например, ищется определенный номер в телефонной книге, принадлежащий человеку, имя которого неизвестно. Классический алгоритм требует N /2 шагов для списка из N номеров. Квантовый алгоритм Гровера [2] требует только количества состояний порядка .
2. Разложение целых чисел на множители.
Рассмотрим классическую задачу разложения заданного целого числа N в произведение его простых делителей. На данный момент лучший алгоритм требует количество вычислений порядка exp[2L (log L) ], где L= log N. Квантовый алгоритм Шора [3] требует только O(L ) шагов. Таким образом, использование квантовых вычислений позволит относительно решить задачи, трудные для классических вычислений.
Естественно ожидать, что квантовые алгоритмы были бы весьма эффективны не только в задачах поиска и в арифметике. Например, алгоритм Гровера может быть очень полезным в информационных системах. Рассмотрим в качестве частного случая хорошо известную в CAD процедуру, называемую Z-буфер. Рассмотрим неупорядоченное множество, состоящее из N точек в R . Проблема заключается в их сортировке вдоль оси z. Предположим, например, что N=1000. На основании вышесказанного, используя квантовые вычисления, мы выполним процедуру сортировки приблизительно в 16 раз быстрее, чем используя обычный компьютер. Без сомнения, мы можем решать подобные проблемы намного эффективней, используя квантовые вычисления вместо классических алгоритмов. Безусловно, квантовые вычисления требуют специальных устройств (т.е. квантовых компьютеров), чтобы стать рабочим инструментом для науки и бизнеса. Научные исследования в этом направлении очень перспективны, и можно ожидать, что квантовые компьютеры станут повседневной реальностью в обозримом будущем.
Литература
1. Д.В.Берзин “Квантовые вычисления и автоматизированные системы проектирования” // Международный научно-исследовательский журнал = Research Journal of International Studies, №8 (27), август 2014, с.9
2. L.K.Grover. “Quantum mechanics helps in searching for a needle in a haystack.” // Phys.Rev.Lett. 79 (1997), 325-328.
3. P.W.Shor “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer.” // SIAM J. Comput., 26:5 (1997), 1484-1509.
Размещено на Allbest.ru
...Подобные документы
Число как основное понятие математики. Натуральные числа. Простые числа Мерсенна, совершенные числа. Рациональные числа. Дробные числа. Дроби в Древнем Египте, Древнем Риме. Отрицательные числа. Комплексные, векторные, матричные, трансфинитные числа.
реферат [104,5 K], добавлен 12.03.2004Простые числа-близнецы - числа, находящиеся на расстоянии друг от друга в 2 единицы.
научная работа [65,3 K], добавлен 12.07.2008Письменная история числа "пи", происхождение его обозначения и "погоня" за десятичными знаками. Определение числа "пи" как отношения длины окружности к её диаметру. История числа "е", мнемоника и мнемоническое правило, числа с собственными именами.
реферат [125,9 K], добавлен 28.11.2010Основные задачи при изучении курса "Высшая математика", Числовые множества: натуральные, целые, рациональные, действительные числа. Модуль числа, интервал, окрестность, отрезок, числовая ось. Аналитическая геометрия, скалярное произведение и вектор.
методичка [201,2 K], добавлен 26.10.2009Аксиомы линейного векторного пространства. Произведение любого вектора на число 0. Аксиомы размерности, доказательство теоремы. Дистрибутивность скалярного произведения векторов относительно сложения векторов. Требования, предъявляемые к системе аксиом.
реферат [80,9 K], добавлен 28.03.2014Априорный выбор числа итераций в методе простых с попеременно чередующимся шагом. Доказательство сходимости процесса в исходной норме гильбертова пространства. Оценка погрешности и решение неравенств. Случай неединственного решения с попеременной.
дипломная работа [695,6 K], добавлен 17.02.2012Определение числа e, вычисление его приближенного значения и его трансцендентность. Анализ формул числа е с помощью рядов и пределов функции. Проявление числа e в реальной жизни и его практическое применение. Применение числа e в математических задачах.
курсовая работа [352,9 K], добавлен 17.05.2021Понятие и характеристика линейного пространства, его главные свойства и особенности. Исследование аксиом векторного пространства. Анализ отличий и признаков векторного подпространства. Базис и формулы линейного пространств, определение его размерности.
реферат [249,4 K], добавлен 21.01.2011Геометрическое представление комплексных чисел, алгебраическая и тригонометрическая формы. Свойства арифметических операций над комплексными числами: правила сложения (вычитания) их радиус-векторов, произведение (частное) модуля числа; формула Муавра.
презентация [147,4 K], добавлен 17.09.2013Комплексные числа в алгебраической форме. Степень мнимой единицы. Геометрическая интерпретация комплексных чисел. Тригонометрическая форма. Приложение теории комплексных чисел к решению уравнений 3-й и 4-й степени. Комплексные числа и параметры.
дипломная работа [1,1 M], добавлен 10.12.2008Мнимые и действительные, равные и сопряжённые комплексные числа; модуль и аргумент. Арифметические действия над множеством комплексных чисел: сумма, разность, произведение, деление. Представление комплексных чисел на координатной комплексной плоскости.
презентация [60,3 K], добавлен 17.09.2013Применение способа решета Эратосфена для поиска из заданного ряда простых чисел до некоторого целого значения. Рассмотрение проблемы простых чисел-близнецов. Доказательство бесконечности простых чисел-близнецов в исходном многочлене первой степени.
контрольная работа [66,0 K], добавлен 05.10.2010Особенности ариорного выбора числа итераций в методе простых итераций с попеременно чередующимся шагом для уравнений I рода. Анализ и постановка задачи. Сходимость при точной правой части. Сходимость при приближенной правой части. Оценка погрешности.
контрольная работа [187,3 K], добавлен 28.05.2010Первая таблица простых чисел, составленная математиком Эратосфеном. Периодические цикады как род цикад с 13- и 17-летними жизненными циклами, распространенных в Северной Америки. Принцип действия кредитной карты. Закономерности и свойства простых чисел.
научная работа [25,8 K], добавлен 28.01.2014Определение понятия антипростого числа как естественного обобщения правильных степеней. Доказательство постулата Бертрана и китайской теоремы об остатках. Исследование натуральных рядов, частоты и последовательности встречаемости антипростых чисел.
реферат [750,4 K], добавлен 18.01.2011Числа натурального ряда, их закономерное периодическое изменение: сведение бесконечного к конечному путем выявления периодичности. Обоснование метода поиска простых чисел с помощью "решета" Баяндина. Закон динамического сохранения относительных величин.
книга [359,0 K], добавлен 28.03.2012Проблема решения уравнений в целых числах: от Диофанта до доказательства теоремы Ферма. Сущность теоремы о делимости данного числа на произведение двух взаимно простых чисел, особенности ее применения к решению неопределенных уравнений в целых числах.
курсовая работа [108,5 K], добавлен 10.03.2014Система, свойства и модели комплексных чисел. Категоричность и непротиворечивость аксиоматической теории комплексных чисел. Корень четной степени из отрицательного числа. Матрицы второго порядка, действительные числа. Операции сложения и умножения матриц.
курсовая работа [1,1 M], добавлен 15.06.2011Поиски и доказательства простоты чисел Мерсенна. Окончание простых чисел Мерсенна на цифру 1 и 7. Вопрос сужения диапазона поиска. Эффективный алгоритм Миллера-Рабина. Разделение алгоритмов на вероятностные и детерминированные. Числа джойнт ряда.
статья [127,5 K], добавлен 28.03.2012Обзор истории происхождения процентов, применение процентных вычислений в задачах. Решение задач по формуле сложных процентов разными способами, нахождение процентов от числа. Применение процентов в жизни: исследование бюджета семьи и посещения кружков.
курсовая работа [126,9 K], добавлен 09.09.2010
