Скачать или смотреть Quantum 2-SAT on low dimensional systems is QMA_1-complete | Rudolph, Gharibian, Nagaj | TQC 2024

Quantum 2-SAT on low dimensional systems is QMA_1-complete: Direct embeddings and black-box simulation | Dorian Rudolph, Sevag Gharibian, Daniel Nagaj

Despite the fundamental role the Quantum Satisfiability (QSAT) problem has played in quantum complexity theory, a central question remains open: At which local dimension does the complexity of QSAT transition from "easy" to "hard"? Here, we study QSAT with each constraint acting on a k-dimensional and l-dimensional qudit pair, denoted (k,l)-QSAT. Our first main result shows that, surprisingly, QSAT on qubits can remain QMA_1-hard, in that (2,5)-QSAT is QMA_1-complete. (QMA_1 is a quantum analogue of MA with perfect completeness.) In contrast, (2,2)-QSAT (i.e. Quantum 2-SAT on qubits) is well-known to be poly-time solvable [Bravyi, 2006]. Our second main result proves that (3,d)-QSAT on the 1D line with d = O(1) is also QMA_1-hard. Finally, we initiate the study of (2,d)-QSAT on the 1D line by giving a frustration-free 1D Hamiltonian with a unique, entangled ground state. As implied by our title, our first result uses a direct embedding: We combine a novel clock construction with the 2D circuit-to-Hamiltonian construction of [Gosset and Nagaj, 2013]. Of note is a new simplified and analytic proof for the latter (as opposed to a partially numeric proof in [GN13]). This exploits Unitary Labelled Graphs [Bausch, Cubitt, Ozols, 2017] together with a new "Nullspace Connection Lemma", allowing us to break low energy analyses into small patches of projectors, and to improve the soundness analysis of [GN13] from Omega(1/T^6) to Omega(1/T^2), for T the number of gates. Our second result goes via black-box reduction: Given an arbitrary 1D Hamiltonian H on d'-dimensional qudits, we show how to embed it into an effective 1D (3,d)-QSAT instance, for d = O(1). Our approach may be viewed as a weaker notion of "simulation" (à la [Bravyi, Hastings 2017], [Cubitt, Montanaro, Piddock 2018]). As far as we are aware, this gives the first "black-box simulation"-based QMA_1-hardness result.

TQC 2024 | 9-13 September 2024 at OIST, Japan
http://tqc-conference.org

19th Conference on the Theory of Quantum Computation, Communication and Cryptography.

TQC is a leading annual international conference for students and researchers working in the theoretical aspects of quantum information science. The scientific objective is to bring together the theoretical quantum information science community to present and discuss the latest advances in the field.


Organisation:
OIST: Okinawa Institute for Science and Technology
Squids: Schools for Quantum Information Development



Sponsors:
JPMorganChase
Google Quantum AI
Horizon Quantum Computing
Quantinuum
Japan National Tourism Organization