BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//CERN//INDICO//EN
BEGIN:VEVENT
SUMMARY:Complexity of Fermionic 2-SAT [Confirmed]
DTSTART:20250305T160000Z
DTEND:20250305T173000Z
DTSTAMP:20260617T135700Z
UID:indico-event-1060@events.perimeterinstitute.ca
DESCRIPTION:Speakers: Maarten Stroeks (Delft University of Technology)\n\n
 In this talk\, I will discuss the complexity of a fermionic analogue of Qu
 antum k-SAT. In this Fermionic k-SAT problem\, one is given the task to de
 cide 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 tha
 t this problem can be solved efficiently classically for k = 2. In additio
 n\, we show that deciding whether there exists a satisfying assignment wit
 h a given fixed particle number parity can also be done efficiently classi
 cally for Fermionic 2-SAT: this problem is a quantum-fermionic extension o
 f asking whether a classical 2-SAT problem has a solution with a given Ham
 ming weight parity. We also prove that deciding whether there exists a sat
 isfying assignment for particle-number-conserving Fermionic 2-SAT for some
  given particle number is NP-complete. Complementary to this\, we show tha
 t Fermionic 9-SAT is QMA_1-hard. \n\nhttps://events.perimeterinstitute.ca
 /event/1060/
LOCATION:PI/4-405 - Bob Room (Perimeter Institute for Theoretical Physics)
URL:https://events.perimeterinstitute.ca/event/1060/
END:VEVENT
END:VCALENDAR