Complexity of Fermionic 2-SAT

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 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.

Fixed abstract for v2

References in corpus (9)

• Periodic table for topological insulators and superconductors
• Solving and Verifying the boolean Pythagorean Triples problem via Cube-and-Conquer
• Fermionic Gaussian states: an introduction to numerical approaches
• Pairing in fermionic systems: A quantum information perspective
• The Power of Noisy Fermionic Quantum Computation
• Quantum proofs can be verified using only single qubit measurements
• Space-Time Circuit-to-Hamiltonian Construction and Its Applications
• Complete Characterization of the Ground Space Structure of Two-Body Frustration-Free Hamiltonians for Qubits
• Quantum 3-SAT is QMA1-complete