BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Drupal iCal API//EN
X-WR-CALNAME:Events items teaser
X-WR-TIMEZONE:America/Toronto
BEGIN:VTIMEZONE
TZID:America/Toronto
X-LIC-LOCATION:America/Toronto
BEGIN:DAYLIGHT
TZNAME:EDT
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
DTSTART:20230312T070000
END:DAYLIGHT
BEGIN:STANDARD
TZNAME:EST
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
DTSTART:20231105T060000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
UID:69ec2e6090b1e
DTSTART;TZID=America/Toronto:20231116T150000
SEQUENCE:0
TRANSP:TRANSPARENT
DTEND;TZID=America/Toronto:20231116T160000
URL:https://uwaterloo.ca/institute-for-quantum-computing/events/new-approac
 hes-complexity-quantum-graphs
LOCATION:QNC - Quantum Nano Centre 200 University Avenue West Waterloo ON N
 2L 3G1 Canada
SUMMARY:New Approaches to Complexity via Quantum Graphs
CLASS:PUBLIC
DESCRIPTION:IQC\, CS\, & MATH SEMINAR - ERIC CULF\, UNIVERSITY OF WATERLOO
  \n\nQuantum Nano Centre\, 200 University Ave West\, Room QNC 1201\nWater
 loo\, ON\, CA N2L 3G1 +ZOOM\n\nProblems based on the structure of graphs 
 -- for example finding\ncliques\, independent sets\, or colourings -- are 
 of fundamental\nimportance in classical complexity. It is well motivated t
 o consider\nsimilar problems about quantum graphs\, which are an operator 
 system\ngeneralisation of graphs. Defining well-formulated decision proble
 ms\nfor quantum graphs faces several technical challenges\, and\nconsequen
 tly the connections between quantum graphs and complexity\nhave been under
 explored.\n\nIn this work\, we introduce and study the clique problem for 
 quantum\ngraphs. Our approach utilizes a well-known connection between qua
 ntum\ngraphs and quantum channels. The inputs for our problems are present
 ed\nas quantum channels induced by circuits\, which implicitly determine a
 \ncorresponding quantum graph. We also use this approach to reimagine\nthe
  clique and independent set problems for classical graphs\, by\ntaking the
  inputs to be circuits of deterministic or noisy channels\nwhich implicitl
 y determine confusability graphs. We show that\, by\nvarying the collectio
 n of channels in the language\, these give rise to\ncomplete problems for 
 the classes NP\, MA\, QMA\, and QMA(2). In this\nway\, we exhibit a classi
 cal complexity problem whose natural\nquantisation is QMA(2)\, rather than
  QMA\, which is commonly assumed.\n      \n\nTo prove the resu
 lts in the quantum case\, we make use of methods\ninspired by self-testing
 . To illustrate the utility of our techniques\,\nwe include a new proof of
  the reduction of QMA(k) to QMA(2) via\ncliques for quantum graphs. We als
 o study the complexity of a version\nof the independent set problem for qu
 antum graphs\, and provide\npreliminary evidence that it may be in general
  weaker in complexity\,\ncontrasting to the classical case where the cliqu
 e and independent set\nproblems are equivalent.       \n\nThis
  talk is based on work with Arthur Mehta\n(arxiv.org/abs/2309.12887)
DTSTAMP:20260425T030048Z
END:VEVENT
END:VCALENDAR