Power of one nonclean qubit
Power of one nonclean qubit
复制标题
一个非洁净量子位的幂
DOI：
10.1103/physreva.95.042336
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Harumichi Nishimura
中科院分区：
文献类型：
--
作者：
Tomoyuki Morimae;Keisuke Fujii;Harumichi Nishimura
一个干净的量子比特模型(或DQC1模型)是量子计算的一种受限模型，其中只有一个初始状态的量子比特是纯的，其他量子比特最大限度地混合在一起。虽然该模型不是通用的，但它可以有效地解决几个经典有效解未知的问题。此外，最近的研究表明，如果经典地有效地模拟一个干净的量子比特模型，多项式层次将坍塌到第二个水平。然而，一个干净的量子比特模型的缺点是干净的量子比特太干净：例如，在现实的核磁共振实验中，极化程度不够高，不足以获得完全纯粹的量子比特。在这篇文章中，我们考虑一个更现实的一个干净的量子比特模型，其中干净的量子比特不是干净的，而是去极化的。我们首先证明，对于任何极化，如果我们取适当大的乘法误差，则在经典多项式时间内可以计算模型的输出概率分布的乘法误差。这一结果与理想的一个干净的量子比特模型形成了强烈的对比，在理想的一个干净的量子比特模型中，具有相同误差量的经典有效的乘法误差计算(甚至采样)会导致多项式层次的崩溃。接下来，我们证明了，对于由反多项式下界的任何极化，除非BQP(有界误差量子多项式时间)包含在多项式族的第二水平，否则不可能对模型的输出概率分布进行经典有效采样(根据足够小的乘法误差或指数级小的加性误差)，这表明了对一个非干净量子比特模型的经典有效模拟的困难。
The one-clean qubit model (or the DQC1 model) is a restricted model of quantum computing where only a single qubit of the initial state is pure and others are maximally mixed. Although the model is not universal, it can efficiently solve several problems whose classical efficient solutions are not known. Furthermore, it was recently shown that if the one-clean qubit model is classically efficiently simulated, the polynomial hierarchy collapses to the second level. A disadvantage of the one-clean qubit model is, however, that the clean qubit is too clean: for example, in realistic NMR experiments, polarizations are not high enough to have the perfectly pure qubit. In this paper, we consider a more realistic one-clean qubit model, where the clean qubit is not clean, but depolarized. We first show that, for any polarization, a multiplicative-error calculation of the output probability distribution of the model is possible in a classical polynomial time if we take an appropriately large multiplicative error. The result is in strong contrast with that of the ideal one-clean qubit model where the classical efficient multiplicative-error calculation (or even the sampling) with the same amount of error causes the collapse of the polynomial hierarchy. We next show that, for any polarization lower-bounded by an inverse polynomial, a classical efficient sampling (in terms of a sufficiently small multiplicative error or an exponentially small additive error) of the output probability distribution of the model is impossible unless BQP (bounded error quantum polynomial time) is contained in the second level of the polynomial hierarchy, which suggests the hardness of the classical efficient simulation of the one nonclean qubit model.