论文标题
混合量子古典电路的甲骨文分离
Oracle separations of hybrid quantum-classical circuits
论文作者
论文摘要
量子计算研究中的一个重要理论问题，在近期量子设备的背景下实际上与之相关，是要了解混合模型的计算能力，该计算能力将多时间经典计算与短深度量子计算相结合。在这里，我们考虑了两个这样的模型：CQ_D捕获多项式经典算法的场景，该算法多次查询d-depth量子计算机； QC_D与基于测量的量子计算更类似，并捕获D-Depth量子计算机的场景，能够根据经典计算处理的测量结果更改应用门的顺序。 Chia，Chung＆Lai（Stoc 2020）和Coudron＆Menda（Stoc 2020）表明，相对于甲骨文，这些模型（具有D = log^o（1）（n））比BQP（可通过Poly-time Computitation解决的问题类别）较弱，相对于Oracle，与Oracle相关的Jozsa的猜测是相关的世界。我们表明，尽管CQ_D和QC_D之间有相似之处，但两个模型是无与伦比的，即CQ_D $ \ nsubseteq $ QC_D和QC_D $ \ nsubseteq $ cq_d相对于Oracle。换句话说，存在一个模型可以解决的问题，但不能解决另一个模型，反之亦然。我们通过考虑捕获两种模型之间区分的新甲骨文问题，并引入本质上随机甲骨文的概念，即甲骨文的响应本质上是随机的，这用于我们的第二个结果。虽然我们离开显示第二个相对于标准甲骨文作为空旷的问题的第二个分离，但我们认为，随机甲壳的概念可能具有独立的兴趣，即研究抗拒标准Oracle模型中分离的复杂性类别。与早期作品相比，我们的构造还产生了混合模型和BQP之间更简单的甲骨文分离。
An important theoretical problem in the study of quantum computation, that is also practically relevant in the context of near-term quantum devices, is to understand the computational power of hybrid models, that combine poly-time classical computation with short-depth quantum computation. Here, we consider two such models: CQ_d which captures the scenario of a polynomial-time classical algorithm that queries a d-depth quantum computer many times; and QC_d which is more analogous to measurement-based quantum computation and captures the scenario of a d-depth quantum computer with the ability to change the sequence of gates being applied depending on measurement outcomes processed by a classical computation. Chia, Chung & Lai (STOC 2020) and Coudron & Menda (STOC 2020) showed that these models (with d=log^O(1) (n)) are strictly weaker than BQP (the class of problems solvable by poly-time quantum computation), relative to an oracle, disproving a conjecture of Jozsa in the relativised world. We show that, despite the similarities between CQ_d and QC_d, the two models are incomparable, i.e. CQ_d $\nsubseteq$ QC_d and QC_d $\nsubseteq$ CQ_d relative to an oracle. In other words, there exist problems that one model can solve but not the other and vice versa. We do this by considering new oracle problems that capture the distinctions between the two models and by introducing the notion of an intrinsically stochastic oracle, an oracle whose responses are inherently randomised, which is used for our second result. While we leave showing the second separation relative to a standard oracle as an open problem, we believe the notion of stochastic oracles could be of independent interest for studying complexity classes which have resisted separation in the standard oracle model. Our constructions also yield simpler oracle separations between the hybrid models and BQP, compared to earlier works.
