Оракулярное разделение между много- и логарифмическими квантовыми цепями

Следующая проблема появляется в списке Ааронсона « Десять полуградовых вызовов для теории квантовых вычислений» .

Is $\mathsf{BQP}=\mathsf{BPP}^{\mathsf{BQNC}}$ Другими словами, может ли «квантовая» часть любого квантового алгоритма быть сжата до глубины , если мы готовы сделать классическую постобработку за полиномиальное время? (Известно, что это верно для алгоритма Шора.) Если это так, то создание квантового компьютера общего назначения было бы намного проще, чем принято считать! Между прочим, нетрудно дать разделение оракула между и , но вопрос в том, есть ли какая-то конкретная функция, "создающая экземпляр" такого оракула. $\mathrm{polylog}(n)$ $\mathsf{BQP}$ $\mathsf{BPP}^{\mathsf{BQNC}}$

Было высказано предположение , по Jozsa , что ответ на этот вопрос да в «» измерения на основе модели квантовых вычислений ":. , Где локальные измерения, адаптивные местные ворота и эффективная классическая постобработки разрешено Смотрите также эту соответствующую должность .

Вопрос . Я хотел бы знать об известном в настоящее время разделении оракула между этими классами (или, по крайней мере, разделении оракула, на которое ссылается Ааронсон).

cc.complexity-theory quantum-computing circuit-complexity quantum-information circuit-depth Хуан Бермехо Вега
источник

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

Робин Котари

Оракулярное разделение между много- и логарифмическими квантовыми цепями

Ответы: