Модели вычислений строго между классическими и квантовыми с точки зрения сложности запросов

18

Хорошо известно, что квантовые компьютеры являются строго более мощными, чем их классические аналоги, с точки зрения сложности запросов .

Существуют ли другие модели (естественные или искусственные), которые строго находятся между квантовой и классической с точки зрения сложности запросов?

Разделение может быть на

  • конкретные проблемы: модель X вычисляет функцию со строго большим количеством запросов, чем с квантовыми, но с меньшим количеством запросов, чем нижняя граница для классического, илие
  • различные проблемы: модель X вычисляет функцию со строго большим количеством запросов, чем квантовая, но вычисляет функцию с меньшим количеством запросов, чем классическая.f1f2

В обоих случаях мы хотим, чтобы каждая функция имела чтобы избежать примеров, которые трудно сравнить с квантовыми (например, сложность сертификата недетерминированных запросов). Здесь (и ) - сложность двустороннего квантового (и классического рандомизированного) запроса с ошибками, а неравенства находятся в пределах постоянных факторов.fQ2(f)X(f)R2(f)Q2(f)R2(f)1/3

Артем Казнатчеев
источник

Ответы:

8

Один простой способ придумать такую ​​модель - это сначала создать ограниченную модель квантовых вычислений, которая все еще может делать что-то неклассическое, а затем просто дать ей классические вычисления бесплатно.

Примером этой стратегии является модель единого чистого кубита (вместе с машиной BPP). Некоторые ссылки: О силе одного бита квантовой информации , вычисление с унитарными единицами и полиномами одного чистого кубита и оценка Джонса - полная проблема для одного чистого кубита .

Другим примером может быть квантовая схема глубины логарифма (или глубины полилога) с доступом к классическому компьютеру. Это даст что - то вроде .ВппВQNС

Робин Котари
источник
Это, безусловно, работает для вычислительной сложности, но работает ли это для сложности запросов? Я не сразу вижу проблемы, для которой модель одного чистого кубита + BPP дает лучшую сложность запроса, чем классическая машина. Кроме того, в общем случае этот метод может потерпеть неудачу, так как классические вычисления с помощью компьютера группы Клиффорда или компьютера совпадения повышают их до универсальных квантовых вычислений.
Джо Фитцзимонс
@JoeFitzsimons: Я не могу думать о проблеме из головы, но я думаю, что Дэн Шепард показывает разделение оракула между BPP и единственной чистой моделью кубита в своей статье. Ваш второй пункт верен, конечно.
Робин Котари
Но, безусловно, разделение оракула не обязательно подразумевает разделение сложности запроса.
Джо Фитцзимонс
Я согласен с @JoeFitzsimons, хотя модель DQC1 интересна, я не видел разделения сложности запросов для нее. Кажется, трудно представить естественные проблемы, такие как оценка трассировки или вариант полинома Джонса, предложенный Питером Шором, в модели запросов.
Артем Казнатчеев
7

Икс(е)D(е)р2(е)

Джо Фитцсимонс
источник
2
пLпL
2

Возможно, более наглядным примером такого рода вычислительных моделей является DQC1, объясненный @RobinKothari в его ответе. Смотрите ссылки в его ответе для хорошего знакомства с моделью.

Также, совсем недавно, в журнале Nature была хорошая статья о Quantum Discord. Квантовый Раздор - это теоретико-информационная мера неклассических корреляций, обобщающая запутанность. Вот ссылка . Там вы увидите, что есть примеры вычислений, где запутанность не играет фундаментальной роли, то есть другие неклассические корреляции - это те, которые заботятся об ускорении вычислений. Это происходит в DQC1 для вычисления следа матрицы (см. Статью Датты, Шаджи и Пещер ). Что интересно в этой статье, так это то, что она раскрывает вопрос об «алгоритмах на основе квантового разногласия», т. Е. Алгоритмах, в которых вам не требуется запутывание для квантового ускорения. Это что-то между полным квантовым вычислением и классическим.

Другая модель, которая, возможно, попадает в эту категорию (между полной квантовой и классической) - это линейная оптическая модель Архипова и Ааронсона. Смотрите этот вопрос для хорошего объяснения.

Я не знаю, где эти модели подходят с точки зрения сложности запросов, но может быть хорошей отправной точкой.

Маркос Вильягра
источник