BQP только о времени? Это имеет смысл?

Класс сложности BQP (квантовое полиномиальное время с ограниченной ошибкой), по-видимому, определяется только с учетом фактора времени. Это всегда значимо? Существуют ли алгоритмы, где вычислительное время масштабируется полиномиально с размером входного сигнала, но другие ресурсы, такие как масштаб памяти, экспоненциально?

BQP определяется с учетом размера цепи , то есть общего количества вентилей. Это означает, что он включает в себя:

• Количество кубитов - потому что мы можем игнорировать любые кубиты, на которые не действуют врата. Это будет ограничено полиномиально относительно размера ввода и часто является скромным полиномом (например, алгоритм Шора включает только количество кубитов, которое является постоянным фактором, умноженным на размер ввода).
• Глубина контура (или «время») - потому что самое длинное вычисление может занять, если мы выполняем один вентиль за другим, не выполняя никаких операций параллельно.
• Связь с системами управления - поскольку выполняемые ворота берутся из некоторого конечного набора затворов, и даже если мы допускаем промежуточные измерения, объем связи, необходимый для указания результата измерения, и объем вычислений, необходимых для определения того, что будет сделано дальше обычно является константой для каждой операции.
• Взаимодействия между квантовыми системами - даже если мы рассмотрим архитектуру, которая не имеет общих взаимодействий или чего-либо близкого к ней, мы можем смоделировать наличие такой связи, выполняя явные операции SWAP, которые сами могут быть разложены на постоянное число двух -кубитные операции. Это может дать нам заметные полиномиальные издержки, которые влияют на практичность алгоритма для данной архитектуры, но не скрывают экспоненциальный объем работы.
• Энергия - опять же, потому что цепи разлагаются на конечный набор затворов, нет очевидного способа получить очевидное ускорение, «делая ворота быстрее» или скрывая работу в экзотическом взаимодействии, если наша граница в терминах количество операций, выполненных из довольно базового набора операций. Это соображение является более важным в адиабатических квантовых вычислениях: мы не можем попытаться избежать небольших промежутков, просто усиливая весь энергетический ландшафт настолько, насколько нам нравится - это означает, что вместо этого нам нужно больше времени, чтобы выполнить вычисления, соответствующие на схеме схемы схема с большим количеством ворот.

По сути, подсчет количества шлюзов из набора постоянного размера захватывает многие вещи, о которых вы могли бы беспокоиться, как о практических ресурсах: он оставляет очень мало места, чтобы скрыть все, что тайно очень дорого.

По крайней мере, не для памяти, поскольку каждый доступ к памяти требует $O(1)$ 'время'.

В термине «сложность времени» «время» вводит в заблуждение, поскольку мы фактически считаем количество элементарных операций, необходимых для выполнения алгоритма. При дополнительном предположении, что эти операции могут быть выполнены в$O(1)$время », мы можем сказать, что наш алгоритм имеет« временную сложность ». Но на самом деле мы имеем в виду, что у нас есть «сложность операции», которую мы выражаем во времени.

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

В то время как в определении BQP и для квантовых алгоритмов мы рассматриваем сложность схемы вместо «сложности операции», сложность схемы может быть снова определена в терминах операций на машинах Тьюринга, поэтому применимы те же рассуждения.