PIRSA:25030160

Video URL

https://pirsa.org/25030160

Complexity of Fermionic 2-SAT

Stroeks, M. (2025). Complexity of Fermionic 2-SAT. Perimeter Institute for Theoretical Physics. https://pirsa.org/25030160

Stroeks, Maarten. Complexity of Fermionic 2-SAT. Perimeter Institute for Theoretical Physics, Mar. 05, 2025, https://pirsa.org/25030160 

          @misc{ scivideos_PIRSA:25030160,
            doi = {10.48660/25030160},
            url = {https://pirsa.org/25030160},
            author = {Stroeks, Maarten},
            keywords = {Quantum Information},
            language = {en},
            title = {Complexity of Fermionic 2-SAT},
            publisher = {Perimeter Institute for Theoretical Physics},
            year = {2025},
            month = {mar},
            note = {PIRSA:25030160 see, \url{https://scivideos.org/pirsa/25030160}}
          }

Maarten Stroeks

Talk numberPIRSA:25030160
DOI10.48660/25030160
Source RepositoryPIRSA
Collection
Talk Type Scientific Series
Subject

Abstract

In this talk, I will discuss the complexity of a fermionic analogue of Quantum k-SAT. In this Fermionic k-SAT problem, one is given the task to decide whether there is a fermionic state in the null-space of a collection of fermionic, parity-conserving, projectors on n fermionic modes, where each fermionic projector involves at most k fermionic modes. We prove that this problem can be solved efficiently classically for k = 2. In addition, we show that deciding whether there exists a satisfying assignment with a given fixed particle number parity can also be done efficiently classically for Fermionic 2-SAT: this problem is a quantum-fermionic extension of asking whether a classical 2-SAT problem has a solution with a given Hamming weight parity. We also prove that deciding whether there exists a satisfying assignment for particle-number-conserving Fermionic 2-SAT for some given particle number is NP-complete. Complementary to this, we show that Fermionic 9-SAT is QMA_1-hard.