Finding resource states of measurement-based quantum computing is harder than quantum computing
arXiv:1609.00457 · doi:10.1103/PhysRevA.96.052308
Abstract
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.
5 pages, 1 figure
References in corpus (10)
- Topological fault-tolerance in cluster state quantum computation
- Measurement-based quantum computation beyond the one-way model
- Verifiable measurement-only blind quantum computing with stabilizer testing
- Computational power of correlations
- Measurement-based quantum computer in the gapped ground state of a two-body Hamiltonian
- Quantum computation on the edge of a symmetry-protected topological order
- Quantum computational capability of a 2D valence bond solid phase
- Resource quality of a symmetry-protected topologically ordered phase for quantum computation
- Thermal States as Universal Resources for Quantum Computation with Always-on Interactions
- Quantum proofs can be verified using only single qubit measurements