Полная задача для PromiseBQP
Назовём задачу $B$ полной для класса $\mathcal C$, если $B\in\mathcal C$ и любая задача из $\mathcal C$ сводится к $B$ за детерминированное полиномиальное время ($\mathcal C\subseteq P^B$). (a) В PromiseBQP входят задачи с обещанием — пары непересекающихся множеств $\Pi_{\rm YES},\Pi_{\rm NO}\subseteq\{0,1\}^*$, для которых равномерное семейство полиномиальных квантовых схем с ограниченной ошибкой определяет, какому множеству принадлежит вход, если он дан из их объединения. Приведите пример полной задачи для PromiseBQP. Подсказка. Достаточно определений. (b) Объясните основную трудность поиска языка $L\subseteq\{0,1\}^*$, полного для BQP.