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