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

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

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

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

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

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

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

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

Другим примером может быть квантовая схема глубины логарифма (или глубины полилога) с доступом к классическому компьютеру. Это даст что - то вроде .$BPP^{BQNC}$

$X(f)\leq D(f)$$R_2(f)$

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

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

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

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