标题： 寻找基于测量的量子计算资源态比量子计算本身更困难 显示英文标题

标题： Finding resource states of measurement-based quantum computing is harder than quantum computing

摘要： 基于测量的量子计算可以通过仅对某些多量子比特态（例如图态、阿fel-Kennedy-Lieb-Tasaki（AKLT）态以及若干张量网络态）进行自适应单量子比特测量来实现通用量子计算。寻找新的基于测量的量子计算资源态是一项艰巨的任务，因为对于一个给定的态，在该态上存在指数级数量可能的测量模式。在本文中，我们考虑了这样一个问题：对于给定的态和一组酉算符，是否存在一种基于测量的量子计算方法可以在该态上实现集合中的所有酉算符。我们证明了这个问题是QCMA困难的，这意味着寻找新的基于测量的量子计算资源态比量子计算本身更难（除非BQP等于QCMA）。我们还推导了该问题的一个上界：该问题是多项式层次结构第二层的量子版本中的一个问题。 显示英文摘要

摘要： Measurement-based quantum computing enables universal quantum computing with only adaptive single-qubit measurements on certain many-qubit states, such as the graph state, the Affleck-Kennedy-Lieb-Tasaki (AKLT) state, and several tensor-network states. Finding new resource states of measurement-based quantum computing is a hard task, since for a given state there are exponentially many possible measurement patterns on the state. In this paper, we consider the problem of deciding, for a given state and a set of unitary operators, whether there exists a way of measurement-based quantum computing on the state that can realize all unitaries in the set, or not. We show that the decision problem is QCMA-hard, which means that finding new resource states of measurement-based quantum computing is harder than quantum computing itself (unless BQP is equal to QCMA). We also derive an upperbound of the decision problem: the problem is in a quantum version of the second level of the polynomial hierarchy.