Pinned quantum Merlin-Arthur: The power of fixing a few qubits in proofs

Nagaj D, Hangleiter D, Eisert J, Schwarz M (2021)

Publication Type: Journal article

Publication year: 2021

Journal

Physical Review A American Physical Society

Book Volume: 103

Article Number: 012604

Journal Issue: 1

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 leads to difficult static questions about the 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 quantum-Merlin-Arthur-complete. Second, we investigate pinned dynamics and demonstrate that fixing a single qubit via often repeated measurements results in universal quantum computation with commuting Hamiltonians. Finally, we discuss variants of the ground-state connectivity (GSCON) problem in light of pinning, and show that stoquastic GSCON is quantum-classical Merlin-Arthur-complete.

Involved external institutions

Slovak Academy of Sciences (SAS) / Slovenská akadémia vied (SAV) SK Slovakia (SK) Freie Universität Berlin DE Germany (DE)

How to cite

APA:

Nagaj, D., Hangleiter, D., Eisert, J., & Schwarz, M. (2021). Pinned quantum Merlin-Arthur: The power of fixing a few qubits in proofs. Physical Review A, 103(1). https://doi.org/10.1103/PhysRevA.103.012604

MLA:

Nagaj, Daniel, et al. "Pinned quantum Merlin-Arthur: The power of fixing a few qubits in proofs." Physical Review A 103.1 (2021).

BibTeX: Download