31:
618:
623:
218:
equivalent: together, the authors showed that quantum effects do not offer advantages for computation if computers can send information to the past through a type of
505:
488:
124:
136:
88:
45:
628:
264:
140:
643:
441:
Kitaev, Alexei; Watrous, John (2000). "Parallelization, amplification, and exponential time simulation of quantum interactive proof systems".
450:
234:
41:
349:
523:
194: = PSPACE. This was preceded by a series of results, showing QIP can be constrained to 3 messages, QIP is contained in
638:
594:
279:
132:
84:
166:
633:
578:
160:
203:
466:
Rahul Jain; Sarvagya
Upadhyay; John Watrous (2009). "Two-message quantum interactive proofs are in PSPACE".
199:
613:
128:
80:
219:
148:
144:
76:
405:
215:
175:
171:
324:
467:
379:
519:
446:
423:
152:
66:
511:
413:
357:
191:
179:
120:
95:
62:
533:
198:, and the 2-message version of QIP is in PSPACE. He has also published important papers on
529:
283:
183:
207:
443:
STOC '00: Proceedings of the thirty-second annual ACM symposium on Theory of computing
418:
400:
607:
320:
223:
507:
Proc. 36th Annual
Symposium on Foundations of Computer Science (Milwaukee, WI, 1995)
276:
487:
Kondacs, A.; Watrous, J. (1997). "On the power of quantum finite state automata".
378:
Rahul Jain; Zhengfeng Ji; Sarvagya
Upadhyay; John Watrous (2009). "QIP = PSPACE".
211:
260:
590:
515:
427:
574:
549:
295:
238:
100:
490:
Proceedings of the 38th Annual
Symposium on Foundations of Computer Science
307:
30:
554:
143:. He was a faculty member in the Department of Computer Science at the
504:
Watrous, John (1995). "On one-dimensional quantum cellular automata".
187:
472:
384:
230:
510:. Los Alamitos, CA: IEEE Comput. Soc. Press. pp. 528–537.
195:
116:
401:"PSPACE has constant-round quantum interactive proof systems"
412:(3). Essex, UK: Elsevier Science Publishers Ltd.: 575–588.
308:
List of editors of
Quantum Information & Computation
115:
is the
Technical Director of IBM Quantum Education at
182:, and the quantum analogue of the celebrated result
550:"How Time-Traveling Could Affect Quantum Computing"
94:
72:
58:
37:
21:
8:
619:Academic staff of the University of Waterloo
125:David R. Cheriton School of Computer Science
137:Perimeter Institute for Theoretical Physics
89:Perimeter Institute for Theoretical Physics
46:State University of New York at Stony Brook
29:
18:
471:
417:
383:
265:Canadian Institute for Advanced Research
141:Canadian Institute for Advanced Research
256:
254:
250:
624:University of Wisconsin–Madison alumni
296:List of editors of Theory of Computing
167:Quantum Information & Computation
7:
178:. He is well known for his work on
210:, he showed that certain forms of
164:and former editor for the journal
147:from 2002 to 2006 where he held a
14:
216:quantum and classical computation
170:. His research interests include
629:Theoretical computer scientists
595:Institute for Quantum Computing
235:University of Wisconsin–Madison
158:He is an editor of the journal
133:Institute for Quantum Computing
85:Institute for Quantum Computing
42:University of Wisconsin–Madison
644:Quantum information scientists
16:Theoretical computer scientist
1:
579:Mathematics Genealogy Project
419:10.1016/S0304-3975(01)00375-9
135:, an affiliate member of the
286:at the QuantumWorks website.
660:
222:proposed by the physicist
180:quantum interactive proofs
445:. ACM. pp. 608–617.
348:Dave Bacon (2009-07-28).
237:under the supervision of
204:quantum cellular automata
106:
51:
28:
548:Lisa Zyga (2008-11-20).
516:10.1109/SFCS.1995.492583
329:Computational Complexity
200:quantum finite automata
119:and was a professor of
639:Canada Research Chairs
399:Watrous, John (2003).
129:University of Waterloo
81:University of Waterloo
220:closed timelike curve
149:Canada Research Chair
145:University of Calgary
113:John Harrison Watrous
77:University of Calgary
23:John Harrison Watrous
634:Cellular automatists
139:and a Fellow of the
406:Theor. Comput. Sci.
354:The Quantum Pontiff
176:quantum computation
172:quantum information
161:Theory of Computing
282:2011-07-06 at the
131:, a member of the
493:. pp. 66–75.
452:978-1-58113-184-0
350:"OMG QIP=PSPACE!"
153:quantum computing
110:
109:
67:Quantum Computing
53:Scientific career
651:
598:
588:
582:
572:
566:
565:
563:
562:
545:
539:
537:
501:
495:
494:
484:
478:
477:
475:
463:
457:
456:
438:
432:
431:
421:
396:
390:
389:
387:
375:
369:
368:
366:
365:
356:. Archived from
345:
339:
338:
336:
335:
317:
311:
305:
299:
293:
287:
274:
268:
258:
229:He obtained his
121:computer science
96:Doctoral advisor
63:Computer Science
33:
19:
659:
658:
654:
653:
652:
650:
649:
648:
604:
603:
602:
601:
589:
585:
573:
569:
560:
558:
547:
546:
542:
526:
503:
502:
498:
486:
485:
481:
465:
464:
460:
453:
440:
439:
435:
398:
397:
393:
377:
376:
372:
363:
361:
347:
346:
342:
333:
331:
319:
318:
314:
306:
302:
294:
290:
284:Wayback Machine
275:
271:
259:
252:
247:
233:in 1998 at the
87:
83:
79:
44:
38:Alma mater
24:
17:
12:
11:
5:
657:
655:
647:
646:
641:
636:
631:
626:
621:
616:
606:
605:
600:
599:
583:
567:
540:
524:
496:
479:
458:
451:
433:
391:
370:
340:
325:"QIP = PSPACE"
323:(2009-07-29).
312:
300:
288:
269:
249:
248:
246:
243:
208:Scott Aaronson
108:
107:
104:
103:
98:
92:
91:
74:
70:
69:
60:
56:
55:
49:
48:
39:
35:
34:
26:
25:
22:
15:
13:
10:
9:
6:
4:
3:
2:
656:
645:
642:
640:
637:
635:
632:
630:
627:
625:
622:
620:
617:
615:
614:Living people
612:
611:
609:
596:
592:
587:
584:
580:
576:
571:
568:
557:
556:
551:
544:
541:
535:
531:
527:
525:0-8186-7183-1
521:
517:
513:
509:
508:
500:
497:
492:
491:
483:
480:
474:
469:
462:
459:
454:
448:
444:
437:
434:
429:
425:
420:
415:
411:
408:
407:
402:
395:
392:
386:
381:
374:
371:
360:on 2010-01-05
359:
355:
351:
344:
341:
330:
326:
322:
321:Lance Fortnow
316:
313:
309:
304:
301:
297:
292:
289:
285:
281:
278:
273:
270:
266:
262:
257:
255:
251:
244:
242:
240:
236:
232:
227:
225:
224:David Deutsch
221:
217:
213:
209:
205:
201:
197:
193:
189:
186: =
185:
181:
177:
173:
169:
168:
163:
162:
156:
154:
150:
146:
142:
138:
134:
130:
126:
122:
118:
114:
105:
102:
99:
97:
93:
90:
86:
82:
78:
75:
71:
68:
64:
61:
57:
54:
50:
47:
43:
40:
36:
32:
27:
20:
591:John Watrous
586:
575:John Watrous
570:
559:. Retrieved
553:
543:
506:
499:
489:
482:
461:
442:
436:
409:
404:
394:
373:
362:. Retrieved
358:the original
353:
343:
332:. Retrieved
328:
315:
303:
291:
277:John Watrous
272:
261:John Watrous
228:
165:
159:
157:
112:
111:
73:Institutions
52:
212:time travel
608:Categories
597:directory.
561:2009-12-30
364:2009-12-30
334:2009-12-30
245:References
473:0905.1300
428:0304-3975
385:0907.4737
239:Eric Bach
214:can make
101:Eric Bach
280:Archived
267:website.
593:at the
577:at the
555:PhysOrg
534:1619103
263:at the
206:. With
127:at the
123:at the
532:
522:
449:
426:
188:PSPACE
59:Fields
468:arXiv
380:arXiv
231:Ph.D.
520:ISBN
447:ISBN
424:ISSN
202:and
174:and
512:doi
414:doi
410:292
196:EXP
192:QIP
151:in
117:IBM
610::
552:.
530:MR
528:.
518:.
422:.
403:.
352:.
327:.
253:^
241:.
226:.
190::
184:IP
155:.
65:,
581:.
564:.
538:.
536:.
514::
476:.
470::
455:.
430:.
416::
388:.
382::
367:.
337:.
310:.
298:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
