Quantum 2-SAT on Low Dimensional Systems is QMA_1-Complete
Squid: Schools for Quantum Information Development via YouTube
Pass the PMP® Exam on Your First Try — Expert-Led Training
Learn AI, Data Science & Business — Earn Certificates That Get You Hired
Overview
Google, IBM & Meta Certificates – 40% Off
One plan covers every Professional Certificate on Coursera.
Unlock All Certificates
Learn about groundbreaking research in quantum complexity theory through this conference talk that explores the complexity transition points in Quantum Satisfiability (QSAT) problems. Delve into two major findings: the QMA_1-completeness of (2,5)-QSAT and the QMA_1-hardness of (3,d)-QSAT on one-dimensional systems. Discover novel approaches including a direct embedding method combining clock construction with 2D circuit-to-Hamiltonian construction, and a black-box reduction technique for embedding arbitrary 1D Hamiltonians into effective 1D QSAT instances. Explore the implications of these findings for quantum complexity theory, including a new simplified analytic proof utilizing Unitary Labelled Graphs and a "Nullspace Connection Lemma" that improves soundness analysis. Presented at the 19th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2024), this talk advances understanding of quantum computational complexity and its fundamental boundaries.
Syllabus
Quantum 2-SAT on low dimensional systems is QMA_1-complete | Rudolph, Gharibian, Nagaj | TQC 2024
Taught by
Squid: Schools for Quantum Information Development