Skip to content

\(BQP\)

\(PostBQP\)

\(PostBQP = PP\)

Aaronson 也证明了更改量子计算法则可以使新的 \(BQP'=PP\)

具体地, 可以改变两个法则:

  1. 量子门不止支持酉运算, 还支持线性运算
  2. 测量量子比特 \(\vert x \rangle\) 得到某一结果的概率不止是 \(|\alpha_x|^2\), 而可以是 \(|\alpha_x|^p\), 其中 \(p> 2\) 且为偶数

\(P\) 与 \(BQP\)

\(P\subseteq BPP \subseteq BQP \subseteq P-SPACE\)

证明: \(P \subseteq BQP\)

这比较好理解, 因为每个经典的电路都可以用量子电路来模拟

而经典电路

证明: \(BQP \subseteq P-SPACE\)

\(PH\)

\(L\in \sum_i\) 如果存在图灵机多项式时间给出结果, 并且

\(x\in L \xLeftrightarrow{} \exists w_1\forall w_2 \cdots Q_iw_i,M(x, w_1, \cdots, w_i)=1\)

其中 \(Q_i=\left\\{ \begin{array}{l}\forall, i偶数\\\\ \exists, i 奇数\end{array}\right.\)

\(L\in \prod_i\) 如果存在图灵机多项式时间给出结果, 并且

\(x\in L \xLeftrightarrow{} \forall w_1\exists w_2 \cdots Q_iw_i,M(x, w_1, \cdots, w_i)=1\)

其中 \(Q_i=\left\\{ \begin{array}{l}\exists, i偶数\\\\ \forall, i 奇数\end{array}\right.\)

可以发现一些性质:

  • \(\sum_0 = \prod_0 = P\)
  • \(\sum_1 = NP, \prod_1 = coNP\)
  • \(co\sum_i=\prod_i, co\prod_i=\sum_i\)
  • \(\sum_i,\prod_i\subseteq \sum_{i+1}, \sum_i,\prod_i\subseteq \prod_{i+1}\)

则定义 \(PH=\bigcup_i\sum_i=\bigcup_i\prod_i\)

所以 \(NP, coNP\subseteq PH\)

在黑盒分隔条件下, \(BQP\) 不包含于 \(PH\)

\(P=NP\) 等价于 \(P=PH\)

\(BQP\) 与 \(NPC\)

我们已知 Shor 算法即属于 \(BQP\), 又属于 \(NP\), 但我们不知道它是否属于 \(NPC\)

目前为止并没有证据表明 \(NPC\) 与 \(BQP\) 之间的关系

但是假如我们发现了一个 \(NPC\) 问题一定不属于 \(BQP\), 那么由于 \(P\subseteq BQP\), 就可以有\(P\not=NPC\), 进而 \(P\not=NP\)