论文标题
通过浅量子电路对非会员的验证
Verification of Group Non-membership by Shallow Quantum Circuits
论文作者
论文摘要
决策问题是答案是是或否。由于$ \ mathsf {np} $的量子类似物（非确定多项式时间），类$ \ mathsf {qma} $（量子Merlin-Arthur）包含的决策问题，其实例可以用量子计算机有效地进行有效验证。已知组元素的组非会员（GNM）的问题已知为$ \ mathsf {qma} $。对GNM验证的先前工作需要$ O（n^5）$组甲骨文调用的量子电路。在这里，我们提出了一种有效的方法来验证GNM问题，将电路深度降低到$ O（1）$，以及Qubits的数量降低了一半。我们进一步实验证明了该方案，其中采用了四元素组中的两元素亚组进行验证任务。在实验中观察到明显的完整性差距。
Decision problems are the problems whose answer is either YES or NO. As the quantum analogue of $\mathsf{NP}$ (nondeterministic polynomial time), the class $\mathsf{QMA}$ (quantum Merlin-Arthur) contains the decision problems whose YES instance can be verified efficiently with a quantum computer. The problem of deciding the group non-membership (GNM) of a group element is known to be in $\mathsf{QMA}$. Previous works on the verification of GNM required a quantum circuit with $O(n^5)$ group oracle calls. Here we propose an efficient way to verify GNM problems, reducing the circuit depth to $O(1)$ and the number of qubits by half. We further experimentally demonstrate the scheme, in which two-element subgroups in a four-element group are employed for the verification task. A significant completeness-soundness gap is observed in the experiment.
