Для каких вычислительных задач квантовые подходы превзойдут классические и насколько именно? Ответы на эти вопросы — одна из важнейших целей современной теоретической информатики. Однако доказательство теоретических ограничений возможностей классических вычислительных моделей чрезвычайно сложно, поскольку многие идеализированные классические модели могут имитировать произвольные машины Тьюринга при наличии достаточных ресурсов. Вместо этого мы противопоставляем квантовые вычисления более ограниченным вычислительным моделям, таким как некоторые ограниченные версии больших языковых моделей (LLM).
Наше исследование продолжает серию работ по неглубоким квантовым схемам, а именно схемам, в которых глубина остается постоянной по мере увеличения количества кубитов. Знаковый результат исследователей IBM Сергея Бравия, Дэвида Госсета и Роберта Кёнига, опубликованный в журнале Science in 2018, показал, что определенная модель квантовых схем постоянной глубины может решать специфические задачи поиска, которые не под силу сопоставимым классическим схемам постоянной глубины. С тех пор исследователи неуклонно укрепляли этот результат, доказывая различные концепции квантового разделения по сравнению со все более выразительными моделями классических вычислений. В рамках этого направления классический оппонент становился все более мощным, в то время как квантовая сторона оставалась удивительно неглубокой.
Учитывая успех и повсеместное распространение LLM в современных вычислительных задачах, нас закономерно заинтересовало, существует ли теоретическое разделение между неглубокими квантовыми схемами и LLM. В частности, наша работа была направлена на поиск таких разделений для двух основных типов вычислительных задач:
- Функциональные разделения: вычисление значения функции, т.е. получение правильного результата для заданного входного сигнала, например, извлечение конкретной информации в ответ на запрос.
- Разделения по выборке: получение входных данных и генерация выходных данных в соответствии с желаемым распределением вероятностей — например, создание нового текста или изображений в ответ на запрос.
Наша недавняя работа, опубликованная на arXiv, доказывает существование по одной задаче в каждом из этих классов, для которых неглубокие квантовые схемы имеют доказуемое преимущество перед LLM. Конечно, это теоретические результаты, а не немедленно применимые на практике или готовые к реализации. Современные большие языковые модели работают на гораздо более зрелых и масштабных вычислительных ресурсах, чем шумные квантовые компьютеры меньшего масштаба, доступные сегодня.
Тем не менее, наша работа демонстрирует, что возможно в масштабе по мере развития квантовых технологий. В частности, мы доказываем, что существуют вычислительные задачи, для которых неглубокие квантовые схемы имеют внутреннее преимущество перед LLM; мы надеемся, что эти идеи откроют путь к разработке конкретных тестов, сравнивающих квантовые системы и LLM при решении этих сложных задач.
Разделение между неглубокими квантовыми схемами и LLM для функциональной задачи
Функциональные задачи возникают в повседневном использовании LLM, от поиска до приложений для обмена сообщениями. LLM обычно решают эти задачи с помощью базовой архитектуры, называемой трансформером. Получив необработанные входные данные, трансформер токенизирует ввод, встраивает полученные токены в виде последовательности векторов, а затем многократно перевзвешивает эти векторы по нескольким слоям, используя изученные параметры и механизм масштабированного скалярного произведения, называемый вниманием, для захвата связей между токенами.
В частности, наша работа сосредоточена на трансформерах только с декодером, которые лежат в основе многих современных известных LLM (включая GPT, Claude и Llama). Эта архитектура обычно используется в авторегрессионных языковых моделях: получив входной запрос, модель последовательно генерирует новые токены, создавая желаемый результат.
Предыдущие работы по вычислительной сложности transformers уже выявили задачи, требующие значительных вычислительных ресурсов. Одной из таких задач является так называемая функция итерированного индекса.
Представьте, что вы ищете запись в указателе в конце книги, но вместо того, чтобы указывать на страницу в той же книге, запись указывает на запись в указателе во второй книге. Эта запись, в свою очередь, указывает на запись в указателе в третьей книге и так далее. Задача итерированного индекса спрашивает, где вы окажетесь после прохождения этой цепочки ссылок через множество последовательных книг.
Адаптация этого существующего результата дала нам классическую половину потенциального разделения: нижнюю границу, показывающую, что трансформерам нужны достаточно большие вычислительные ресурсы для решения задачи итерированного индекса. Чтобы завершить разделение, оставалось показать соответствующую верхнюю границу, а именно, что эта задача решаема неглубокими квантовыми схемами.
Мы действительно показали, что задача решаема квантовой схемой почти постоянной глубины, оснащенной одним классическим логическим элементом И. Мы также показали, что эту глубину нельзя существенно улучшить (например, ее нельзя сделать по-настоящему постоянной).
Подпись к изображению: Иллюстрация неглубокой квантовой схемы, вычисляющей функцию индекса (поиск бита в таблице данных). Это формирует строительный блок для нашего разделения между квантовыми схемами и трансформерами с ограниченными ресурсами. Вставка A^j — это параллельные схемы малой глубины, которые проверяют каждый возможный индекс и возвращают бит по соответствующему адресу в таблице данных.
Разделение между неглубокими квантовыми схемами и LLM для дистрибутивной задачи
Дистрибутивные задачи представляют собой еще один фундаментальный вариант использования современных больших языковых моделей. Вместо получения одного правильного ответа, как в функциональной задаче, цель здесь состоит в том, чтобы сгенерировать один из многих возможных результатов в соответствии с желаемым распределением вероятностей. Самые известные примеры дистрибутивных задач возникают при генерации изображений, решаемой сегодня диффузионными моделями, такими как DALL·E или Stable Diffusion.
В нашей статье исследуются диффузионные языковые модели (DLM), которые обучаются путем «искажения» текста случайным шумом, а затем их учат восстанавливать исходный текст, обращая процесс искажения шаг за шагом, итеративно раскрывая токены. Во время тестирования, получив запрос, эти модели начинают со случайного шума и итеративно удаляют его, пока не создадут результат в желаемой форме.
Мы снова обратились к предыдущим классическим работам, в которых изучалась задача, называемая выборкой четности — задача, похожая на ту, что использовали Бравий и соавторы для сравнения квантовых и классических неглубоких схем в 2018 году. Это задача, которая является «сложной» только для диффузионных моделей, и ее можно описать следующим образом. Имея строку из 0 и 1, можно спросить о ее четности — имеет ли она четное или нечетное количество единиц.
У этой задачи есть простой квантовый подход с использованием квантовой схемы постоянной глубины: используя такие свойства, как запутанность и интерференция, можно предсказать четность неизвестной строки и тем самым эффективно выбирать строки с заданной четностью. Но как справляются классические модели?
Предыдущие исследования диффузионных языковых моделей уже выявили ограничения в том, насколько хорошо они могут решать определенную версию этой задачи выборки. Однако эти результаты не охватывали ДЯМ, оснащенные цепочкой рассуждений (chain-of-thought) — способностью «показывать ход решения» путем генерации и использования промежуточных токенов, что, как правило, делает модель значительно более мощной.
Наша цель состояла в том, чтобы распространить классическую нижнюю границу на эту более сильную модель. Мы доказали, что даже если диффузионная языковая модель имеет доступ к некоторому объему цепочки рассуждений, она все равно не может эффективно воспроизвести распределение, генерируемое неглубокой квантовой схемой. Это дает нам второе разделение: на этот раз для задачи выборки, а не для функциональной задачи.
Что дальше?
Наша работа носит сугубо теоретический характер и состоит из математических доказательств. Мы должны признать, что современные квантовые компьютеры ограничены в своих возможностях и подвержены шумам и ошибкам, в то время как классические LLM имеют доступ к передовому вычислительному оборудованию в беспрецедентных масштабах.
Действительно, наша работа не определяет точный масштаб, при котором квантовые системы превзойдут эти классические LLM в изученных конкретных задачах — лишь то, что асимптотически квантовые схемы будут превосходить LLM при их прямом сравнении.
Мы считаем, что подобные исследования помогают обосновать усилия по созданию квантовых компьютеров. За последнее десятилетие исследователи обнаружили задачи, в которых неглубокие квантовые схемы могут обойти все более мощные модели классических вычислений. Мы надеемся и дальше расширять эти границы.
В каких задачах неглубокие квантовые схемы превосходят более мощные модели, помимо LLM? Как соотносятся менее ограниченные квантовые схемы? В конечном счете, наша цель — составить полную карту безусловных разделений между полностью общими квантовыми и классическими вычислениями, но до этого «святого грааля» еще очень далеко.
Тем временем эта работа должна и дальше стимулировать разработку алгоритмов и приложений для квантовых вычислений — особенно учитывая существование задач, недоступных для изученных здесь моделей LLM, но решаемых даже ограниченными моделями отказоустойчивых квантовых вычислений.
Это также открывает более широкую перспективу: вместо того чтобы рассматривать квантовые компьютеры и LLM только как конкурентов, возможно, квантовые вычисления со временем смогут дополнить классические системы ИИ, позволяя им решать задачи, которые в противном случае потребовали бы значительно больших вычислительных ресурсов. Эта работа помогает понять различия между квантовыми вычислениями и искусственным интеллектом, вселяя в нас оптимизм относительно будущего с полноценными квантово-классическими гибридными моделями вычислений.
