Maarten Stroeks, Barbara M. Terhal (Dec 10 2024).
Abstract: We introduce the fermionic satisfiability problem, Fermionic
k-SAT: this is the problem of deciding 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. In addition, we show that deciding whether there exists a satisfying assignment for a given fixed particle number parity can also be solved efficiently classically: 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.
