标题： 通过加权图态的保真度估计验证交换量子计算 显示英文标题

标题： Verifying commuting quantum computations via fidelity estimation of weighted graph states

摘要： 瞬时量子多项式时间模型（或IQP模型）是展示量子计算相对于经典计算机优势的有前景的模型之一。 如果IQP模型可以被经典计算机高效模拟，将得到计算机科学中不太可能的结果（在一些未证明的猜想下）。 为了在实验中使用中等或大规模的IQP电路来演示这种优势，不可避免地需要高效地验证所构建的IQP电路是否正常工作。 存在两种类型的IQP模型，每种类型都是在超图状态或加权图状态上的采样。 对于第一类IQP模型，已经提出了多项式时间验证协议。 在本文中，我们为第二类IQP模型提出验证协议。 为此，我们为以下四种情况分别提出了加权图状态的多项式时间保真度估计协议，其中验证者可以（i）选择任何测量基并执行自适应测量，（ii）仅选择受限的测量基并执行自适应测量，（iii）选择任何测量基并仅执行非自适应测量，以及（iv）仅选择受限的测量基并仅执行非自适应测量。 在我们所有的验证协议中，验证者的量子操作仅包括单量子比特测量。 由于我们假设量子态没有独立同分布的性质，我们的协议适用于任何情况。 显示英文摘要

摘要： The instantaneous quantum polynomial time model (or the IQP model) is one of promising models to demonstrate a quantum computational advantage over classical computers. If the IQP model can be efficiently simulated by a classical computer, an unlikely consequence in computer science can be obtained (under some unproven conjectures). In order to experimentally demonstrate the advantage using medium or large-scale IQP circuits, it is inevitable to efficiently verify whether the constructed IQP circuits faithfully work. There exists two types of IQP models, each of which is the sampling on hypergraph states or weighted graph states. For the first-type IQP model, polynomial-time verification protocols have already been proposed. In this paper, we propose verification protocols for the second-type IQP model. To this end, we propose polynomial-time fidelity estimation protocols of weighted graph states for each of the following four situations where a verifier can (i) choose any measurement basis and perform adaptive measurements, (ii) only choose restricted measurement bases and perform adaptive measurements, (iii) choose any measurement basis and only perform non-adaptive measurements, and (iv) only choose restricted measurement bases and only perform non-adaptive measurements. In all of our verification protocols, the verifier's quantum operations are only single-qubit measurements. Since we assume no i.i.d. property on quantum states, our protocols work in any situation.