Квантовый алгоритм может помочь ИИ думать быстрее
Один из способов, которым «думают» компьютеры, — это анализ отношений в больших наборах данных. Международная команда исследователей показала, что квантовые компьютеры могут сделать такой анализ быстрее, чем классические компьютеры, для более широкого набора типов данных, чем это ожидалось ранее.
Предлагаемый алгоритм квантовой линейной системы команды публикуется в Physical Review Letters. В будущем это может помочь решить различные проблемы, такие как прогноз цены на товары, взаимодействие в социальных сетях или построение химических структур.
«Предыдущий квантовый алгоритм такого рода относился к очень специфическому типу проблемы. Нам нужно обновление, если мы хотим добиться квантового ускорения для других данных», — говорит Жикуан Чжао, автор работы.
Первый алгоритм квантовой линейной системы был предложен в 2009 году другой группой исследователей. Этот алгоритм начал исследование квантовых форм машинного обучения или искусственного интеллекта.
Алгоритм линейной системы работает на большой матрице данных. Например, трейдер может попытаться предсказать будущую цену товаров. Матрица может фиксировать исторические данные о движении цен с течением времени и данные об особенностях, которые могут влиять на эти цены, такие как обменные курсы валют. Алгоритм вычисляет, насколько сильно каждая функция коррелирует с другой путем «инвертирования» матрицы. Затем эту информацию можно использовать для экстраполяции в будущее.
«В анализе матрицы много вычислений. Когда он выходит за пределы, скажем, 10 000 на 10 000 записей, для классических компьютеров анализировать становится трудно», — объясняет Чжао. Это связано с тем, что количество вычислительных шагов быстро растет с количеством элементов в матрице: каждое удвоение размера матрицы увеличивает длину вычисления в восемь раз.
Алгоритм 2009 года может лучше справляться с большими матрицами, но только если их данные разрежены. В этих случаях между элементами существуют ограниченные отношения, которые часто не соответствуют реальным данным. Чжао, Пракаш и Уоссниг представляют новый алгоритм, который быстрее, чем классические и предыдущие квантовые версии, без ограничений на данные, с которыми он работает.
В качестве приблизительного руководства, для квадратной матрицы размером 10 000, классический алгоритм займет порядка триллиона вычислительных шагов, первый квантовый алгоритм — несколько десятков тысяч шагов, а новый квантовый алгоритм — всего лишь сотни шагов. Алгоритм опирается на метод, известный как оценка квантового сингулярного значения.
Чтобы показать реальное квантовое преимущество перед классическими алгоритмами, потребуются большие квантовые компьютеры. Чжао оценивает, что «мы, возможно, смотрим на три-пять лет в будущее, когда мы сможем фактически использовать аппаратное обеспечение, созданное экспериментаторами, чтобы сделать значимые квантовые вычисления».
Больше информации: Leonard Wossnig et al, Quantum Linear System Algorithm for Dense Matrices, Physical Review Letters (2018). DOI: 10.1103/PhysRevLett.120.050502