论文标题
经典和量子混合方案的最佳甲骨文分离
An optimal oracle separation of classical and quantum hybrid schemes
论文作者
论文摘要
最近，Chia，Chung and Lai（Stoc 2020）以及Coudron和Menda（Stoc 2020）表明，存在一个Oracle $ \ Mathcal {O} $，以至于$ \ Mathsf {Bqp}^\ MathCal {o} （\ Mathsf {bqnc^{bpp}}）^\ Mathcal {o} $。实际上，Chia等。事实证明，有一个更强有力的声明：对于任何深度参数$ d $，都存在一个分离量子深度$ d $和$ 2D+1 $的甲骨文，当允许多项式时间计算时。这意味着相对于甲骨文，量子深度加倍，使经典和量子混合方案具有更多的计算能力。 在本文中，我们表明，对于任何深度参数$ d $，都存在一个分离量子深度$ d $和$ d+1 $的甲骨文，当允许使用多项式时间经典计算时。这给出了经典和量子混合方案的最佳甲骨文分离。为了证明我们的结果，我们考虑了$ d $ dumentive Simon的问题（这是Chia等人所考虑的Simon的问题的变体）和受“原位”置换甲骨文启发的甲骨文。
Recently, Chia, Chung and Lai (STOC 2020) and Coudron and Menda (STOC 2020) have shown that there exists an oracle $\mathcal{O}$ such that $\mathsf{BQP}^\mathcal{O} \neq (\mathsf{BPP^{BQNC}})^\mathcal{O} \cup (\mathsf{BQNC^{BPP}})^\mathcal{O}$. In fact, Chia et al. proved a stronger statement: for any depth parameter $d$, there exists an oracle that separates quantum depth $d$ and $2d+1$, when polynomial-time classical computation is allowed. This implies that relative to an oracle, doubling quantum depth gives classical and quantum hybrid schemes more computational power. In this paper, we show that for any depth parameter $d$, there exists an oracle that separates quantum depth $d$ and $d+1$, when polynomial-time classical computation is allowed. This gives an optimal oracle separation of classical and quantum hybrid schemes. To prove our result, we consider $d$-Bijective Shuffling Simon's Problem (which is a variant of $d$-Shuffling Simon's Problem considered by Chia et al.) and an oracle inspired by an "in-place" permutation oracle.
