BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//132.216.98.100//NONSGML kigkonsult.se iCalcreator 2.20.4//
BEGIN:VEVENT
UID:20251103T181401EST-6128bwHGcf@132.216.98.100
DTSTAMP:20251103T231401Z
DESCRIPTION:Title: Efficient algorithms for quantum constraint satisfaction
  problems.\n\nAbstract: The study of Boolean constraint satisfaction probl
 ems\, such as MAX-k-SAT\, is central to theoretical computer science. In t
 he quantum setting\, there is a natural generalization of MAX-k-SAT\, know
 n as the k-local Hamiltonian problem (k-LH)\, which is complete for the qu
 antum analogue of NP [Kitaev\, 1999]. Moreover\, k-LH is appealing in that
  it encodes a fundamental physical question: What is the energy of a given
  quantum system when cooled to low temperature? In this talk\, we begin wi
 th an introduction to complexity theoretic background regarding k-LH. We t
 hen give an optimal linear-time algorithm for the quantum analogue of 2 SA
 T\, improving upon the quartic-time quantum 2-SAT algorithm of [Bravyi\, 2
 006]. Our work exploits the transfer matrix techniques of [Laumann et al.\
 , 2010] from the study of random quantum 2-SAT\, and bears similarities wi
 th both the classic linear time 2-SAT algorithms of [Even\, Itai\, and Sha
 mir\, 1976] (based on backtracking)\, and [Aspvall\, Plass\, and Tarjan\,1
 979] (based on strongly connected components).\n
DTSTART:20181130T150000Z
DTEND:20181130T160000Z
LOCATION:Room 3195\, CA\, Pav. André-Aisenstadt
SUMMARY:Sevag Gharibian\, Universität Paderborn\, Germany\, and Virginia Co
 mmonwealth University\, USA 
URL:/mathstat/channels/event/sevag-gharibian-universit
 at-paderborn-germany-and-virginia-commonwealth-university-usa-292148
END:VEVENT
END:VCALENDAR