№ 2908Квантовые вычисленияУровень 5

Включение BQP в PP

В класс PP входят языки, для которых вероятностная машина Тьюринга за полиномиальное время принимает каждый вход из языка с вероятностью не менее $1/2$, а каждый другой вход — с вероятностью меньше $1/2$. Докажите, что $\mathrm{BQP}\subseteq\mathrm{PP}$, усилив оценку $\mathrm{BQP}\subseteq P^{\# P}$. Подсказка. Выразите вероятность принятия схемы как сумму экспоненциального числа комплексных чисел, каждое из которых вычислимо за полиномиальное время. Затем используйте эту сумму для проверки порога $1/2$.

Предложить решение

Войти, чтобы отправить материал.