Теперь квантовый компьютер может работать с графикой

Квантовые компьютеры — гипотетические вычислительные устройства, работа которых базируется на явлениях квантовой механики. На заре создания теории предполагалось, что подобные машины будут превосходить классические компьютеры в разы. Однако, за пределами криптографии (в которой квантовые компьютеры могут применяться для быстрого разложения чисел на множители) у квантовых компьютеров не обнаружилось существенных преимуществ перед классическими машинами.

В рамках новой работы ученым удалось создать алгоритм решения системы обыкновенных линейных уравнений c N неизвестными за время порядка lg N. Для сравнения, лучшие классические алгоритмы работают за время порядка N. Таким образом, например, для решения системы с 1010 неизвестными обычный компьютер выполнит несколько десятков миллиардов действий, в то время как его квантовый "коллега" — несколько десятков. По словам ученых, учитывая, что системы линейных уравнений используются, например, при обработке изображений, создании 3D графики и предсказании погоды, алгоритм делает квантовые компьютеры крайне эффективными в данных областях.

Работа была воспринята специалистами по вопросу крайне неоднозначно. Многие отмечают, что решение системы уравнений будет храниться в памяти квантового компьютера в виде суперпозиций состояний кубитов, что означает отсутствие точного решения в привычном понимании этого слова — каждое состояние реализуется с некоторой вероятностью. Чтобы "извлечь" классическое решение из памяти квантового компьютера, может потребоваться огромное число шагов, которое съест выигрыш от быстрого вычисления. Аналогичным образом, "загрузка" информации в кубиты также может оказаться очень ресурсоемким процессом.

Для сравнения, квантовый алгоритм проверки простоты числа работает следующим образом: он либо предъявляет разложение числа на множители, либо выдает неопределенный ответ (который можно легко распознать). Последнее означает, что число с вероятностью 1/2 простое. Если, применив алгоритм 100 раз, неопределенный ответ был получен все 100 раз, то можно утверждать, что число простое с вероятностью 1/2100.

По материалам "Lenta.ru".