Насколько эффективны точные «квантовые» вычисления, если вы приостановите унитарность?

Краткий вопрос

Какова вычислительная мощность «квантовых» схем, если мы допускаем неунитарные (но все еще обратимые) вентили и требуем, чтобы выходные данные давали правильный ответ с уверенностью?

Этот вопрос в некотором смысле касается того, что происходит с классом $\mathsf{EQP}$ когда вы разрешаете схемам использовать больше, чем просто унитарные вентили. (Мы все еще вынуждены ограничивать себя обратимыми воротами над $\mathbb C$ если мы хотим иметь четко определенную модель вычислений.)

(Этот вопрос подвергся некоторым изменениям в свете некоторой путаницы с моей стороны в отношении известных результатов о таких схемах в унитарном случае.)

О "точных" квантовых вычислениях

Для этого вопроса я определяю $\mathsf{EQP}$ как класс задач, которые могут быть точно решены с помощью однородного семейства квантовых цепей, где коэффициенты каждого унитарного элемента вычисляются с помощью машин Тьюринга, ограниченных полиномиальным временем (из входной строки $1^n$ ) для каждого входного размера $n$ , и что компоновка схемы как направленной сети также может быть произведена за полиномиальное время. Под «точно» решено, я имею в виду, что измерение выходного бита дает $|0\rangle$ с уверенностью в случаях нет, и $|1\rangle$ с уверенностью в случаях YES.

Предостережения:

• Даже ограничиваясь унитарными воротами, это понятие $\mathsf{EQP}$ отличается от того, что было описано Бернштейном и Вазирани с использованием квантовых машин Тьюринга. Вышеприведенное определение позволяет семейству схем $\{ C_n \}$ в принципе иметь бесконечный набор затворов - конечно, каждая отдельная схема $C_n$ использует только конечное подмножество - поскольку затворы фактически вычисляются из входных данных. (Квантовая машина Тьюринга может моделировать любой конечный набор затворов, который вам нравится, но может моделировать только конечные наборы затворов, потому что у него есть только конечное число переходов.)

• Эта модель вычислений упрощает любые проблемы в $\mathsf P$ , потому что унитарный может содержать один вентиль, который жестко кодирует решение любой задачи в $\mathsf P$ (его коэффициенты, в конце концов, определяются вычислением за многократное время). Таким образом, конкретная временная или пространственная сложность задач не обязательно представляет интерес для таких схем.

Мы можем добавить к этим оговоркам наблюдение, что практические реализации квантовых компьютеров все равно будут иметь шум. Эта модель вычислений интересна прежде всего для теоретических соображений , так как один по вопросам составления унитарных преобразований , а не осуществимые вычислений, а также в качестве точной версии . В частности, несмотря на вышеуказанные предостережений, мы имеем P ⊆ E Q P ⊆ B Q P .$\mathsf{BQP}$$\mathsf{P} \subseteq \mathsf{EQP} \subseteq \mathsf{BQP}$

Причина для определения так , как я делаю это так , что DISCRETE-LOG можно положить в E Q P . Согласно [  Mosca + Zalka 2003  ], существует алгоритм полиномиального времени для построения унитарной схемы, которая точно решает экземпляры DISCRETE-LOG, создавая точные версии QFT в зависимости от входного модуля. Я полагаю, что тогда мы можем поместить DISCRETE-LOG в E Q P , как определено выше, встраивая элементы построения схемы в способ вычисления коэффициентов затвора. (Таким образом, результат DISCRETE-LOG ∈ E Q P по существу выполняется с помощью fiat, но опирается на конструкцию Mosca + Zalka.)$\mathsf{EQP}$$\mathsf{EQP}$$\mathsf{EQP}$$\in \mathsf{EQP}$

Приостановка унитарности

Пусть будет вычислительным классом, который мы получим, если мы приостановим ограничение, что ворота будут унитарными, и позволим им распределяться по обратимым преобразованиям. Можем ли мы поместить этот класс (или даже охарактеризовать его) в терминах других традиционных недетерминированных классов C ?$\mathsf{EQP_{\mathrm{GL}}}$$\mathbf C$

Одна из причин, по которой я спрашиваю: если - класс задач, эффективно решаемых с ограниченной ошибкой , с помощью однородных семейств "неунитарных квантовых" цепей - где экземпляры YES дают выходной результат | 1 ⟩ с вероятностью по меньшей мере , 2/3, и никаких случаев с вероятностью не более 1/3 (после нормализации состояния-вектор) - затем [Ааронсона 2005] показывает , что Б В Р О Л = Р Р . То есть: приостановка унитарности в этом случае эквивалентна разрешению неограниченной ошибки.$\mathsf{BQP}_{\mathrm{GL}}$$|1\rangle$$\mathsf{BQP}_{\mathrm{GL}} = \mathsf{PP}$

Получается ли аналогичный результат или какой-либо четкий результат для ?$\mathsf{EQP_{\mathrm{GL}}}$

Короткий ответ. Оказывается, что приостановка требования унитарных преобразований и требование, чтобы каждая операция была обратимой, приводит к точным классам, определяемым пробелами. Классы специфические о которых идет речь и 'новый' подкласс L P W P P , оба из которых находятся между S P P и C = P . Эти классы имеют довольно технические определения, которые кратко описаны ниже; хотя теперь эти определения в принципе могут быть заменены определениями в терминах неунитарных «квантовых» алгоритмов.$\mathsf{LWPP}$$\mathsf{LPWPP}$$\mathsf{SPP}$$\mathsf{C_=P}$

Класс подсчета содержит изоморфизм графов. Он также содержит весь класс U P , поэтому мы не ожидаем, что точные унитарные квантовые алгоритмы будут такими же мощными, как неунитарные классы (как мы могли бы показать N P ⊆ B Q P ).$\mathsf{SPP}$$\mathsf{UP}$$\mathsf{NP \subseteq BQP}$

Более длинный ответ.

• В моем вопросе я предложил переопределить чтобы учесть проблемы, которые могут быть решены однородными семействами схем, в которых используются логические элементы, которые эффективно вычисляются, но не обязательно взяты из конечного набора вентилей. Я больше не уверен, что это хорошая идеяпереопределить E Q P таким образом, хотя я действительно считаю, что такие семейства схем заслуживают изучения. Вместо этогомы можем назвать этот класс чем-то вроде U n i t a r y P $\mathsf{EQP}$ $\mathsf{EQP}$$\mathsf{UnitaryP_{\mathbb C}}$

  Можно показать, что , который до недавнего времени был самым известным связан на E Q P . Класс L W P P более или менее соответствует задачам, для которых существует рандомизированный алгоритм, в котором экземпляры NO дают результат 1 с вероятностью точно 0,5, а экземпляры YES дают результат 1 с некоторой вероятностью, которая может быть эффективно и точно рассчитывается в рациональной форме, которая больше (но, возможно, экспоненциально близко) к 0,5. Техническое определение L W $\mathsf{UnitaryP_{\mathbb C} \subseteq LWPP}$$\mathsf{EQP}$$\mathsf{LWPP}$ представлен в терминах недетерминированных машин Тьюринга, но больше не освещает.$\mathsf{LWPP}$

  Если мы определим как эквивалент обратимого затвора U n i $\mathsf{GLP}_{\mathbb C}$ , так что это набор задач, которые точно решаютсясемействамиобратимыхцепей с эффективно вычисляемыми коэффициентами затвора, то G L Р С = Ь Ш Р Р .$\mathsf{UnitaryP_{\mathbb C}}$$\mathsf{GLP_{\mathbb C} = LWPP}$

• Если ограничиться конечным затвором-множеств, то можно показать , что унитарные семьи цепи могут быть смоделированы в подмножестве , которую можно назвать L P W P P . (Используя приведенное выше описание L W P P , это соответствует рандомизированным алгоритмам, где вероятность получения выхода 1 для экземпляров YES точно$\mathsf{LWPP}$$\mathsf{LPWPP}$$\mathsf{LWPP}$ , для некоторого полинома p некоторые целое число$m^{t(x)} / 2^{p(|x|)}$$p$$m$и некоторый эффективно вычислимый многочлен .)$t$

  Если мы определим быть обратима затвором эквивалент E Q P , как это обычно определяется, можно показать , что Е В Р О Л ⊆ L P W P P .$\mathsf{EQP_{\mathrm{GL}}}$$\mathsf{EQP}$$\mathsf{EQP_{\mathrm{GL}} \subseteq LPWPP}$

Исправление относительно ДИСКРЕТНОГО ЛОГА.

$\mathsf{EQP}$$\mathsf{UnitaryP_{\mathbb C}}$

Ссылка.

• де Бёдрап, О точном подсчете и квазиквантовой сложности , [ arXiv: 1509.07789 ].