  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.
