Pinned QMA: The power of fixing a few qubits in proofs
arXiv:2001.03636 · doi:10.1103/PhysRevA.103.012604
Abstract
What could happen if we pinned a single qubit of a system and fixed it in a particular state? First, we show that this can greatly increase the complexity of static questions -- ground state properties of local Hamiltonian problems with restricted types of terms. In particular, we show that the Pinned commuting and Pinned Stoquastic Local Hamiltonian problems are QMA complete. Second, we show that pinning a single qubit via often repeated measurements also results in universal quantum computation already with commuting and stoquastic Hamiltonians. Finally, we discuss variants of the Ground State Connectivity (GSCON) problem in light of pinning, and show that Stoquastic GSCON is QCMA complete. We hence identify a comprehensive picture of the computational power of pinning, reminiscent of the power of the one clean qubit model.
arXiv comment12 pages, rewritten version. This was a poster at QIP 2019
References in corpus (31)
- Fault-tolerant quantum computation by anyons
- Logic gates at the surface code threshold: Superconducting qubits poised for fault-tolerant quantum computing
- Universal Quantum Computation with ideal Clifford gates and noisy ancillas
- Universal computation by quantum walk
- On the Power of One Bit of Quantum Information
- Universal computation by multi-particle quantum walk
- Quantum Zeno dynamics: mathematical and physical aspects
- Classical simulation of noninteracting-fermion quantum circuits
- Realizable Hamiltonians for Universal Adiabatic Quantum Computers
- Hamiltonian complexity
- Quantum Hamiltonian Complexity
- Universal Quantum Hamiltonians
- Perturbative Gadgets at Arbitrary Orders
- Easing the Monte Carlo sign problem
- Entanglement negativity bounds for fermionic Gaussian states
- Combining Topological Hardware and Topological Software: Color Code Quantum Computing with Topological Superconductor Networks
- Quantum Computing in Plato's Cave
- Hamiltonian Quantum Cellular Automata in 1D
- On the Computational Complexity of Curing the Sign Problem
- Exact gate-sequences for universal quantum computation using the XY-interaction alone
- Hardness of classically sampling one clean qubit model with constant total variation distance error
- Universal adiabatic quantum computation via the space-time circuit-to-Hamiltonian construction
- QMA-complete problems for stoquastic Hamiltonians and Markov matrices
- Universal 2-local Hamiltonian Quantum Computing
- Ground state connectivity of local Hamiltonians
- The Complexity of Stoquastic Local Hamiltonian Problems
- BQP-complete Problems Concerning Mixing Properties of Classical Random Walks on Sparse Graphs
- QCMA hardness of ground space connectivity for commuting Hamiltonians
- Hamiltonian Purification
- Quantum speedup in stoquastic adiabatic quantum computation
- On the Complexity of Two Dimensional Commuting Local Hamiltonians