Tata Institute of Fundamental Research
QIP = PSPACE
Seminar
Speaker:
Pranab Sen
School of Technology and Computer Science
Tata Institute of Fundamental Research
Homi Bhabha Road
Date:
Wednesday, 16 Sep 2009 (all day)
Venue:
A-212 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
I propose to give a series of lectures explaining the recent paper by Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay and John Watrous showing that the class of problems having quantum interactive proofs is the same as the class of problems having classical deterministic
algorithms running in polynomial space. This was a decade long open problem in quantum computational complexity and is an excellent piece of work.
We shall refresh our memories on quantum computation and interactive proofs if needed. Earlier work showing that quantum interactive proofs need use at most three messages will also be briefly discussed. The first lecture will be a high level teaser of things to come.
| Speaker: | Pranab Sen School of Technology and Computer Science Tata Institute of Fundamental Research Homi Bhabha Road |
| Date: | Wednesday, 16 Sep 2009 (all day) |
| Venue: | A-212 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
I propose to give a series of lectures explaining the recent paper by Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay and John Watrous showing that the class of problems having quantum interactive proofs is the same as the class of problems having classical deterministic
algorithms running in polynomial space. This was a decade long open problem in quantum computational complexity and is an excellent piece of work.
We shall refresh our memories on quantum computation and interactive proofs if needed. Earlier work showing that quantum interactive proofs need use at most three messages will also be briefly discussed. The first lecture will be a high level teaser of things to come.
algorithms running in polynomial space. This was a decade long open problem in quantum computational complexity and is an excellent piece of work.
We shall refresh our memories on quantum computation and interactive proofs if needed. Earlier work showing that quantum interactive proofs need use at most three messages will also be briefly discussed. The first lecture will be a high level teaser of things to come.