Один чистый кубит

Одна чистая квантовая схема кубита, которая оценивает след $U$

Модель One Clean Qubit вычислений выполняется $n$ кубитная система с одним чистым состоянием и $n-1$ максимально смешанные состояния . Эта модель была мотивирована сильно смешанными состояниями, которые преобладают в квантовых компьютерах ядерного магнитного резонанса . Это описывается матрицей плотности $\rho =\left|0\right\rangle \langle 0|\otimes {\frac {I}{2}}$, где I — единичная матрица . В теории сложности ; DQC1 вычислений также известный как детерминистическое квантовое вычисление с одним чистым кубитом, представляет собой класс задач принятия решений, решаемых машиной с одним чистым кубитом за полиномиальное время, после измерения первого кубита, с вероятностью ошибки не более 1/poly(n) для всех случаев. .

Границы ошибок и компоновка

Самое стандартное определение DQC1 требует, чтобы при измерении выходного кубита правильно принимался или отклонялся входной сигнал, максимум с ошибкой. $1/q(n)$ для заданного некоторого полинома q с учетом разрыва в вероятностях принятия $[0,1/2-1/q(n)]$ для НЕТ экземпляров и $[1/2+1/q(n),1]$ для случаев ДА. Большинство вероятностных классов, таких как BPP , BQP и RP, не зависят от точного вероятностного разрыва, поскольку любой полиномиальный разрыв приемлемости может быть усилен до фиксированного разрыва, такого как (1/3,2/3). Заметным исключением является PP , который допускает экспоненциально малые зазоры.

DQC1 не допускает очевидного понятия параллельной компоновки или усиления: не существует четкой конструкции для преобразования схемы, скажем, с приемочным зазором (2/5,3/5) в более точную (1/5,4/5). ) разрыв принятия.

Известно, что DQC1 обеспечивает возможность компоновки в том смысле, что «один» чистый кубит можно модернизировать до «двух» чистых кубитов или даже $log(n)$ много чистых кубитов без изменения класса Вычисления с унитариями и одним чистым кубитом. Диджей Шеперд. </ref> Это также не усиливается путем измерения всех этих чистых кубитов (в отличие от только первого чистого кубита).

Отношение к другим классам

Потому что столько, сколько $O(\log(n))$ кубиты разрешены, DQC1 содержит все вычисления в пространстве журнала . Он закрыт под $\oplus$L сокращения также. Неизвестно, содержит ли он BPP или даже P. Он содержится в BQP, и предполагается, что его содержание является строгим.

Известно, что смоделировать задачу выборки даже для трёх выходных кубитов классически сложно, в том смысле, что это повлечёт за собой коллапс PH .

Термин DQC1 вместо этого использовался для обозначения проблем принятия решений, решаемых классической схемой с полиномиальным временем, которая адаптивно выполняет запросы к полиномиальному числу схем DQC1. В этом смысле использования класс, естественно, содержит весь BPP, а мощность класса сосредоточена на «внутренней квантовой» мощности.

Оценка трассировки

Оценка трассировки завершена для DQC1 . Позволять $U$ быть унитарным $2^{n}\times 2^{n}$ матрица. Учитывая состояние $|\psi \rangle$, тест Адамара может оценить $\left\langle \psi \right|U\left|\psi \right\rangle$ где ${\textstyle {\frac {1}{2}}+{\frac {1}{2}}{\mathcal {Re}}(\left\langle \psi \right|U\left|\psi \right\rangle )}$ — вероятность того, что измеренный чистый кубит равен 0. $I/2^{n}$ входы со смешанным состоянием можно моделировать, позволяя $|\psi \rangle$ выбираться равномерно случайным образом из $2^{n}$ вычислительные базовые состояния. При измерении вероятность того, что окончательный результат равен 0, равна $${\frac {1}{2^{n}}}\sum _{x\subset \{0,1\}^{n}}{\frac {1+{\mathcal {Re}}\left\langle x\right|U\left|x\right\rangle }{2}}={\frac {1}{2}}+{\frac {1}{2}}{\frac {{\mathcal {Re}}(Tr(U))}{2^{n}}}.$$ Чтобы оценить мнимую часть $Tr(U)$чистый кубит инициализируется ${\textstyle {\frac {1}{\sqrt {2}}}\left(\left|0\right\rangle -i\left|1\right\rangle \right)}$ вместо ${\textstyle {\frac {1}{\sqrt {2}}}\left(\left|0\right\rangle +\left|1\right\rangle \right)}$.

DQC1-полные проблемы

Помимо оценки унитарного следа, оценка коэффициента в разложении Паули унитарного объекта и аппроксимация полинома Джонса при корне пятой степени из единицы также являются DQC1-полными . Фактически, оценка трассировки является частным случаем оценки коэффициента разложения Паули.