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.
arXiv comment5 pages, 1 figure
References in corpus (19)
- Strengths and Weaknesses of Quantum Computing
- Topological fault-tolerance in cluster state quantum computation
- Most quantum states are too entangled to be useful as computational resources
- Measurement-based quantum computation beyond the one-way model
- Verifiable measurement-only blind quantum computing with stabilizer testing
- Computational power of correlations
- Affleck-Kennedy-Lieb-Tasaki State on a Honeycomb Lattice is a Universal Quantum Computational Resource
- Symmetry-protected phases for measurement-based quantum computation
- 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
- Are random pure states useful for quantum computation?
- Quantum computational capability of a 2D valence bond solid phase
- Interactive proofs for BQP via self-tested graph states
- Resource quality of a symmetry-protected topologically ordered phase for quantum computation
- Quantum Commuting Circuits and Complexity of Ising Partition Functions
- Thermal States as Universal Resources for Quantum Computation with Always-on Interactions
- Quantum proofs can be verified using only single qubit measurements
- Topologically protected measurement-based quantum computation on the thermal state of a nearest-neighbor two-body Hamiltonian with spin-3/2 particles
- Hardness of approximation for quantum problems