Testing quantum satisfiability

CS/Math Seminar - Dominic Verdon (University of Bristol) 

The quantum Boolean satisfiability problem, quantum k-SAT for short, is the quantum analogue of the classical Boolean satisfiability problem. It is QMA_1-complete for k >2, and therefore appears very difficult to solve in general. In this talk I will discuss a property testing approach to quantum k-SAT which, given the promise that an instance of the problem is either (i) satisfiable or (ii) far from satisfiable by a product state, yields a polynomial-time algorithm for deciding which of the two mutually exclusive properties (i) or (ii) holds.  To show this we apply some tools from combinatorics, entanglement theory and algebraic geometry. The talk is based on joint work with Ashley Montanaro and Changpeng Shao (https://arxiv.org/abs/2301.10699).

Topic: IQC CS MATH Seminar

NOTE Time: Dec 14, 2023 10:00 Eastern Time (US and Canada)

Join Zoom Meeting

https://uwaterloo.zoom.us/j/93836820491?pwd=Y0Y4VmFVSTJyUjlhUDdNaDZpMHl5Zz09

Meeting ID: 938 3682 0491

Passcode: 399903