Dear all,
This week will be the fifth "Harvard Quantum Information Group Meeting", which
will be held on Thursday, October 27th at 4:30 pm in Jefferson 250.
This week, Chinmay Nirke from IBM will talk about the complexity of quantum proofs.
Title: Classical oracle separations between QMA and QCMA (joint work with Anand Natarajan,
MIT)
Abstract: It is a long-standing open question in quantum complexity theory whether the
definition of non-deterministic quantum computation requires quantum witnesses (QMA) or if
classical witnesses suffice (QCMA). We make progress on this question by constructing a
randomized classical oracle separating the respective computational complexity classes.
Previous separations [Aaronson-Kuperberg, Fefferman-Kimmel] required a quantum unitary
oracle. The separating problem is deciding whether a distribution supported on regular
un-directed graphs either consists of multiple connected components (yes instances) or
consists of one expanding connected component (no instances) where the graph is given in
an adjacency-list format by the oracle. Therefore, the oracle is a distribution over n-bit
boolean functions.
In this talk, I will give a more pedagogical introduction to the subject – including how
to think about the complexity of quantum proofs. Questions are welcome, especially from
audience members unfamiliar with the area!
Here is the link of
<https://calendar.google.com/calendar/u/0?cid=Y185MWI0YjdkMWE3YmJjYzkwODNlNTIzMDczM2I3NDYwZGU5YWJkMzdkMWE5NjAyYWI4YTg3MTZmNWNlYThiZGZlQGdyb3VwLmNhbGVuZGFyLmdvb2dsZS5jb20>google
calenda
<https://calendar.google.com/calendar/u/0?cid=Y185MWI0YjdkMWE3YmJjYzkwODNlNTIzMDczM2I3NDYwZGU5YWJkMzdkMWE5NjAyYWI4YTg3MTZmNWNlYThiZGZlQGdyb3VwLmNhbGVuZGFyLmdvb2dsZS5jb20>r
for the next few meetings.
The meeting is open to everyone at Harvard interested in quantum information, including
those in condensed matter physics, AMO physics, high energy physics, computer science,
chemistry, etc. The format includes weekly tutorials (by both external and internal
speakers) of contemporary topics in quantum information and quantum computing, aimed for a
broad scientific audience.
We will also try to foster connections between different groups at Harvard which are
interested in or involved with quantum information, and build a broader community.
Hope to see you all there. If you would like to join the mailing list for this meeting,
please e-mail harvardqimeeting(a)gmail.com <mailto:harvardqimeeting@gmail.com> which
will add you.
Show replies by date