Edit Profile (opens in new tab) Watrous, John Compute Distance To: Compute Author ID: watrous.john Published as: Watrous, John; Watrous, J. Documents Indexed: 42 Publications since 1995, including 1 Book Co-Authors: 40 Co-Authors with 26 Joint Publications 1,047 Co-Co-Authors all top 5 Co-Authors 16 single-authored 3 Jain, Rahul 3 Molina, Abel 3 Russo, Vincent F. 3 Upadhyay, Sarvagya 2 Ambainis, Andris 2 Bach, Eric 2 Gutoski, Gus 2 Ji, Zhengfeng 2 Johnston, Nathaniel 2 Leung, Debbie W. 2 Vidick, Thomas 1 Aaronson, Scott 1 Bandyopadhyay, Somshubhro 1 Beigi, Salman 1 Cleve, Richard 1 Coppersmith, Susan N. 1 Cosentino, Alessandro 1 de Beaudrap, J. Niel 1 Gerhardt, Heath 1 Ghosh, Soumik 1 Girard, Mark W. 1 Goldschen, Marcel Paz 1 Ito, Tsuyoshi 1 Joynt, Robert 1 Jozsa, Richard 1 Kitaev, Alexei Yu. 1 Kobayashi, Hirotada 1 Kraus, Barbara 1 Levick, Jeremy 1 Li, Chi-Kwong 1 Mittal, Rajat 1 Miyake, Akimasa 1 Nayak, Ashwin 1 Paulsen, Vern Ival 1 Poon, Yiu-Tung 1 Puzzuoli, Daniel 1 Shor, Peter Williston 1 Toner, Ben 1 Vishwanath, Ashvin 1 Yu, Nengkun all top 5 Serials 3 Journal of Computer and System Sciences 3 Chicago Journal of Theoretical Computer Science 3 Proceedings of the Royal Society of London. Series A. Mathematical, Physical and Engineering Sciences 3 Quantum Information & Computation 2 Theoretical Computer Science 2 Theory of Computing 2 Proceedings of the Royal Society of London. A. Mathematical, Physical and Engineering Sciences 1 Communications in Mathematical Physics 1 IEEE Transactions on Information Theory 1 SIAM Journal on Computing 1 Algorithmica 1 Computational Complexity 1 Theory of Computing Systems 1 Journal of the ACM 1 Annales Henri Poincaré 1 Foundations and Trends in Theoretical Computer Science all top 5 Fields 31 Quantum theory (81-XX) 28 Computer science (68-XX) 8 Information and communication theory, circuits (94-XX) 5 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 4 Operations research, mathematical programming (90-XX) 2 Group theory and generalizations (20-XX) 2 Functional analysis (46-XX) 2 Statistical mechanics, structure of matter (82-XX) 1 Combinatorics (05-XX) 1 Number theory (11-XX) 1 Linear and multilinear algebra; matrix theory (15-XX) 1 Operator theory (47-XX) 1 Probability theory and stochastic processes (60-XX) 1 Relativity and gravitational theory (83-XX) Publications by Year all cited Publications top 5 cited Publications Citations contained in zbMATH Open 37 Publications have been cited 700 times in 561 Documents Cited by ▼ Year ▼ One-dimensional quantum walks. Zbl 1323.81021Ambainis, Andris; Bach, Eric; Nayak, Ashwin; Vishwanath, Ashvin; Watrous, John 139 2001 The theory of quantum information. Zbl 1393.81004Watrous, John 109 2018 Two-way finite automata with quantum and classical states. Zbl 1061.68047Ambainis, Andris; Watrous, John 52 2002 Zero-knowledge against quantum attacks. Zbl 1186.81048Watrous, John 44 2009 Quantum simulations of classical random walks and undirected graph connectivity. Zbl 0990.68519Watrous, John 41 2001 Towards a general theory of quantum games. Zbl 1232.91112Gutoski, Gus; Watrous, John 27 2007 Parallelization, amplification, and exponential time simulation of quantum interactive proof systems. Zbl 1296.68057Kitaev, Alexei; Watrous, John 26 2000 Notes on super-operator norms induced by Schatten norms. Zbl 1162.47308Watrous, J. 24 2005 One-dimensional quantum walks with absorbing boundaries. Zbl 1107.81010Bach, Eric; Coppersmith, Susan; Goldschen, Marcel Paz; Joynt, Robert; Watrous, John 23 2004 PSPACE has constant-round quantum interactive proof systems. Zbl 1026.68121Watrous, John 15 2003 Space-bounded quantum complexity. Zbl 0947.68051Watrous, John 15 1999 Closed timelike curves make quantum and classical computing equivalent. Zbl 1186.81035Aaronson, Scott; Watrous, John 15 2009 Sharp quantum versus classical query complexity separations. Zbl 1012.68220de Beaudrap, J. Niel; Cleve, Richard; Watrous, John 14 2002 On the complexity of simulating space-bounded quantum computations. Zbl 1068.68066Watrous, John 14 2003 Semidefinite programs for completely bounded norms. Zbl 1213.81047Watrous, John 13 2009 Distinguishing quantum operations having few Kraus operators. Zbl 1156.81015Watrous, John 10 2008 On one-dimensional quantum cellular automata. Zbl 0938.68733Watrous, John 10 1995 Coherent state exchange in multi-prover quantum interactive proof systems. Zbl 1286.68157Leung, Debbie; Toner, Ben; Watrous, John 10 2013 Optimal counterfeiting attacks and generalizations for Wiesner’s quantum money. Zbl 1451.81214Molina, Abel; Vidick, Thomas; Watrous, John 9 2013 Two-message quantum interactive proofs are in PSPACE. Zbl 1292.68068Jain, Rahul; Upadhyay, Sarvagya; Watrous, John 9 2009 Simpler semidefinite programs for completely bounded norms. Zbl 1286.81036Watrous, John 8 2013 Limitations on separable measurements by convex optimization. Zbl 1359.94236Bandyopadhyay, Somshubhro; Cosentino, Alessandro; Johnston, Nathaniel; Russo, Vincent; Watrous, John; Yu, Nengkun 7 2015 Relationships between quantum and classical space-bounded complexity classes. Zbl 0935.68043Watrous, John 7 1998 Continuous-time quantum walks on the symmetric group. Zbl 1279.81056Gerhardt, Heath; Watrous, John 7 2003 Matchgate and space-bounded quantum computations are equivalent. Zbl 1195.81034Jozsa, Richard; Kraus, Barbara; Miyake, Akimasa; Watrous, John 6 2010 Quantum proofs. Zbl 1339.68094Vidick, Thomas; Watrous, John 6 2015 Zero-knowledge against quantum attacks. Zbl 1301.68131Watrous, John 6 2006 Hedging bets with correlated quantum strategies. Zbl 1372.91020Molina, Abel; Watrous, John 6 2012 Mixing doubly stochastic quantum channels with the completely depolarizing channel. Zbl 1172.81322Watrous, John 6 2009 Quantum interactive proofs with competing provers. Zbl 1118.68493Gutoski, Gus; Watrous, John 5 2005 Quantum algorithms for solvable groups. Zbl 1323.68289Watrous, John 5 2001 Quantum interactive proofs with short messages. Zbl 1221.68090Beigi, Salman; Shor, Peter; Watrous, John 3 2011 Quantum interactive proofs with weak error bounds. Zbl 1347.68152Ito, Tsuyoshi; Kobayashi, Hirotada; Watrous, John 2 2012 \(\mathrm{QIP} = \mathrm{PSPACE}\). Zbl 1293.68133Jain, Rahul; Ji, Zhengfeng; Upadhyay, Sarvagya; Watrous, John 2 2010 Ancilla dimension in quantum channel discrimination. Zbl 1364.81069Puzzuoli, Daniel; Watrous, John 2 2017 Revisiting the simulation of quantum Turing machines by quantum circuits. Zbl 1472.81279Molina, Abel; Watrous, John 2 2019 \(\mathrm{QIP} = \mathrm{PSPACE}\). Zbl 1281.68117Jain, Rahul; Ji, Zhengfeng; Upadhyay, Sarvagya; Watrous, John 1 2011 Revisiting the simulation of quantum Turing machines by quantum circuits. Zbl 1472.81279Molina, Abel; Watrous, John 2 2019 The theory of quantum information. Zbl 1393.81004Watrous, John 109 2018 Ancilla dimension in quantum channel discrimination. Zbl 1364.81069Puzzuoli, Daniel; Watrous, John 2 2017 Limitations on separable measurements by convex optimization. Zbl 1359.94236Bandyopadhyay, Somshubhro; Cosentino, Alessandro; Johnston, Nathaniel; Russo, Vincent; Watrous, John; Yu, Nengkun 7 2015 Quantum proofs. Zbl 1339.68094Vidick, Thomas; Watrous, John 6 2015 Coherent state exchange in multi-prover quantum interactive proof systems. Zbl 1286.68157Leung, Debbie; Toner, Ben; Watrous, John 10 2013 Optimal counterfeiting attacks and generalizations for Wiesner’s quantum money. Zbl 1451.81214Molina, Abel; Vidick, Thomas; Watrous, John 9 2013 Simpler semidefinite programs for completely bounded norms. Zbl 1286.81036Watrous, John 8 2013 Hedging bets with correlated quantum strategies. Zbl 1372.91020Molina, Abel; Watrous, John 6 2012 Quantum interactive proofs with weak error bounds. Zbl 1347.68152Ito, Tsuyoshi; Kobayashi, Hirotada; Watrous, John 2 2012 Quantum interactive proofs with short messages. Zbl 1221.68090Beigi, Salman; Shor, Peter; Watrous, John 3 2011 \(\mathrm{QIP} = \mathrm{PSPACE}\). Zbl 1281.68117Jain, Rahul; Ji, Zhengfeng; Upadhyay, Sarvagya; Watrous, John 1 2011 Matchgate and space-bounded quantum computations are equivalent. Zbl 1195.81034Jozsa, Richard; Kraus, Barbara; Miyake, Akimasa; Watrous, John 6 2010 \(\mathrm{QIP} = \mathrm{PSPACE}\). Zbl 1293.68133Jain, Rahul; Ji, Zhengfeng; Upadhyay, Sarvagya; Watrous, John 2 2010 Zero-knowledge against quantum attacks. Zbl 1186.81048Watrous, John 44 2009 Closed timelike curves make quantum and classical computing equivalent. Zbl 1186.81035Aaronson, Scott; Watrous, John 15 2009 Semidefinite programs for completely bounded norms. Zbl 1213.81047Watrous, John 13 2009 Two-message quantum interactive proofs are in PSPACE. Zbl 1292.68068Jain, Rahul; Upadhyay, Sarvagya; Watrous, John 9 2009 Mixing doubly stochastic quantum channels with the completely depolarizing channel. Zbl 1172.81322Watrous, John 6 2009 Distinguishing quantum operations having few Kraus operators. Zbl 1156.81015Watrous, John 10 2008 Towards a general theory of quantum games. Zbl 1232.91112Gutoski, Gus; Watrous, John 27 2007 Zero-knowledge against quantum attacks. Zbl 1301.68131Watrous, John 6 2006 Notes on super-operator norms induced by Schatten norms. Zbl 1162.47308Watrous, J. 24 2005 Quantum interactive proofs with competing provers. Zbl 1118.68493Gutoski, Gus; Watrous, John 5 2005 One-dimensional quantum walks with absorbing boundaries. Zbl 1107.81010Bach, Eric; Coppersmith, Susan; Goldschen, Marcel Paz; Joynt, Robert; Watrous, John 23 2004 PSPACE has constant-round quantum interactive proof systems. Zbl 1026.68121Watrous, John 15 2003 On the complexity of simulating space-bounded quantum computations. Zbl 1068.68066Watrous, John 14 2003 Continuous-time quantum walks on the symmetric group. Zbl 1279.81056Gerhardt, Heath; Watrous, John 7 2003 Two-way finite automata with quantum and classical states. Zbl 1061.68047Ambainis, Andris; Watrous, John 52 2002 Sharp quantum versus classical query complexity separations. Zbl 1012.68220de Beaudrap, J. Niel; Cleve, Richard; Watrous, John 14 2002 One-dimensional quantum walks. Zbl 1323.81021Ambainis, Andris; Bach, Eric; Nayak, Ashwin; Vishwanath, Ashvin; Watrous, John 139 2001 Quantum simulations of classical random walks and undirected graph connectivity. Zbl 0990.68519Watrous, John 41 2001 Quantum algorithms for solvable groups. Zbl 1323.68289Watrous, John 5 2001 Parallelization, amplification, and exponential time simulation of quantum interactive proof systems. Zbl 1296.68057Kitaev, Alexei; Watrous, John 26 2000 Space-bounded quantum complexity. Zbl 0947.68051Watrous, John 15 1999 Relationships between quantum and classical space-bounded complexity classes. Zbl 0935.68043Watrous, John 7 1998 On one-dimensional quantum cellular automata. Zbl 0938.68733Watrous, John 10 1995 all cited Publications top 5 cited Publications all top 5 Cited by 877 Authors 18 Qiu, Daowen 18 Segawa, Etsuo 18 Yakaryılmaz, Abuzer 17 Konno, Norio 14 Li, Lvzhou 11 Nechita, Ion 11 Suzuki, Akito 11 Zheng, Shenggen 10 D’Ariano, Giacomo Mauro 10 Perinotti, Paolo 9 Say, A. C. Cem 8 Gruska, Jozef 8 Watrous, John 7 Nishimura, Harumichi 7 Puchała, Zbigniew 6 Bluhm, Andreas 6 Grünbaum, Francisco Alberto 6 Le Gall, François 6 Myers, Robert C. 6 Sato, Iwao 6 Shirokov, Maksim Evgen’evich 6 Sikora, Jamie 6 Velázquez, Luis 6 Werner, Albert H. 5 Aaronson, Scott 5 Bisio, Alessandro 5 Broadbent, Anne 5 Childs, Andrew M. 5 Kendon, Viv M. 5 Maeda, Masaya 5 Paulsen, Vern Ival 5 Rastëgin, Alekseĭ Èduardovich 5 Tosini, Alessandro 5 Wilde, Mark M. 5 Yamakami, Tomoyuki 5 Yang, Yuguang 4 Baumeler, Ämin 4 Beigi, Salman 4 Berta, Mario 4 Cedzich, Christopher 4 Gutoski, Gus 4 Hancock, Edwin Robert 4 Harrow, Aram Wettroth 4 Jenčová, Anna 4 Johnston, Nathaniel 4 Junge, Marius 4 Kerenidis, Iordanis 4 King, Christopher K. 4 Kobayashi, Hirotada 4 Kuklinski, Parker 4 Leung, Debbie W. 4 Li, Dan 4 Mereghetti, Carlo 4 Nayak, Ashwin 4 Palano, Beatrice 4 Pawela, Łukasz 4 Plosker, Sarah 4 Rahaman, Mizanur 4 Werner, Reinhard F. 4 Ying, Mingsheng 3 Baryshnikov, Yuliy M. 3 Bianchi, Maria Paola 3 Bitansky, Nir 3 Brandão, Fernando G. S. L. 3 Chapman, Shira 3 Doron, Dean 3 Emms, David M. 3 Funakawa, Daiju 3 Gainutdinova, Aida 3 Geib, T. 3 Gharibian, Sevag 3 Girard, Mark W. 3 Grilo, Alex Bredariol 3 Han, Qi 3 Higuchi, Yusuke 3 Kang, Yuanbao 3 Kashefi, Elham 3 Kiumi, Chusei 3 Kon, Mark A. 3 Kothari, Robin 3 Lardizabal, Carlos F. 3 Li, Chi-Kwong 3 Liu, Chaobin 3 Love, Peter J. 3 Mateus, Paulo C. 3 Montanaro, Ashley 3 Ohno, Hiromichi 3 Pemantle, Robin 3 Rouzé, Cambyse 3 Ruan, Shan-Ming 3 Santha, Miklos 3 Štefaňák, Martin 3 Stilck França, Daniel 3 Sundaram, Aarthi 3 Ta-Shma, Amnon 3 Tanaka, Yohei 3 Tate, Tatsuya 3 Unruh, Dominique 3 Wada, Kazuyuki 3 Wilson, Richard Charles ...and 777 more Authors all top 5 Cited in 97 Serials 101 Quantum Information Processing 37 Journal of Mathematical Physics 29 Theoretical Computer Science 27 Communications in Mathematical Physics 22 Linear Algebra and its Applications 20 Journal of High Energy Physics 13 International Journal of Theoretical Physics 11 Algorithmica 11 International Journal of Quantum Information 11 Journal of Physics A: Mathematical and Theoretical 10 Physics Letters. A 10 Journal of Computer and System Sciences 10 SIAM Journal on Computing 9 International Journal of Foundations of Computer Science 8 Annales Henri Poincaré 7 Letters in Mathematical Physics 7 Reviews in Mathematical Physics 7 Foundations of Physics 6 Physica A 6 Information and Computation 6 Computational Complexity 6 New Journal of Physics 5 Journal of Cryptology 5 Lobachevskii Journal of Mathematics 5 Natural Computing 4 Journal of Statistical Physics 4 Reports on Mathematical Physics 4 Proceedings of the Royal Society of London. A. Mathematical, Physical and Engineering Sciences 3 Information Processing Letters 3 Journal of Combinatorial Theory. Series A 3 MSCS. Mathematical Structures in Computer Science 3 Annals of Physics 3 Pattern Recognition 3 Theory of Computing Systems 3 Interdisciplinary Information Sciences (IIS) 3 Quantum Studies: Mathematics and Foundations 2 International Journal of Modern Physics B 2 Advances in Mathematics 2 Journal of Functional Analysis 2 Journal of the Mathematical Society of Japan 2 Physica D 2 Machine Learning 2 Communications in Statistics. Theory and Methods 2 Mathematical Programming. Series A. Series B 2 ELA. The Electronic Journal of Linear Algebra 2 Open Systems & Information Dynamics 2 Chicago Journal of Theoretical Computer Science 2 Infinite Dimensional Analysis, Quantum Probability and Related Topics 2 Proceedings of the Royal Society of London. Series A. Mathematical, Physical and Engineering Sciences 2 Journal of Statistical Mechanics: Theory and Experiment 2 Physical Review A, Third Series 2 RAIRO. Theoretical Informatics and Applications 2 Computer Science Review 2 Philosophical Transactions of the Royal Society of London. A. Mathematical, Physical and Engineering Sciences 1 Computer Physics Communications 1 Discrete Mathematics 1 European Journal of Physics 1 Journal of Mathematical Analysis and Applications 1 Physics Reports 1 Reviews of Modern Physics 1 Acta Mathematica Vietnamica 1 Annali di Matematica Pura ed Applicata. Serie Quarta 1 International Journal of Mathematics and Mathematical Sciences 1 Journal of Mathematical Psychology 1 Probability Theory and Related Fields 1 New Generation Computing 1 Discrete & Computational Geometry 1 Journal of the American Mathematical Society 1 Formal Aspects of Computing 1 Sugaku Expositions 1 International Journal of Mathematics 1 Japan Journal of Industrial and Applied Mathematics 1 Designs, Codes and Cryptography 1 Bulletin of the American Mathematical Society. New Series 1 SIAM Journal on Optimization 1 Journal of Mathematical Sciences (New York) 1 Random Operators and Stochastic Equations 1 The Electronic Journal of Combinatorics 1 Journal of Convex Analysis 1 Sbornik: Mathematics 1 Discrete and Continuous Dynamical Systems 1 The Journal of Fourier Analysis and Applications 1 RAIRO. Theoretical Informatics and Applications 1 Foundations of Computational Mathematics 1 Journal of Systems Science and Complexity 1 Journal of Machine Learning Research (JMLR) 1 Parallel Processing Letters 1 The European Physical Journal B. Condensed Matter and Complex Systems 1 Probability Surveys 1 Theory of Computing 1 Journal of Theoretical Biology 1 Forum of Mathematics, Pi 1 Forum of Mathematics, Sigma 1 ACM Transactions on Computation Theory 1 Special Matrices 1 Pacific Journal of Mathematics for Industry 1 SIAM Journal on Applied Algebra and Geometry all top 5 Cited in 45 Fields 443 Quantum theory (81-XX) 187 Computer science (68-XX) 95 Information and communication theory, circuits (94-XX) 92 Probability theory and stochastic processes (60-XX) 76 Statistical mechanics, structure of matter (82-XX) 56 Functional analysis (46-XX) 51 Operator theory (47-XX) 40 Combinatorics (05-XX) 36 Linear and multilinear algebra; matrix theory (15-XX) 16 Relativity and gravitational theory (83-XX) 15 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 14 Operations research, mathematical programming (90-XX) 12 Partial differential equations (35-XX) 11 Dynamical systems and ergodic theory (37-XX) 9 Statistics (62-XX) 9 Numerical analysis (65-XX) 6 Number theory (11-XX) 4 Mathematical logic and foundations (03-XX) 4 Group theory and generalizations (20-XX) 4 Convex and discrete geometry (52-XX) 4 Differential geometry (53-XX) 3 Several complex variables and analytic spaces (32-XX) 3 Ordinary differential equations (34-XX) 3 Difference and functional equations (39-XX) 3 Manifolds and cell complexes (57-XX) 2 Algebraic geometry (14-XX) 2 Associative rings and algebras (16-XX) 2 Functions of a complex variable (30-XX) 2 Harmonic analysis on Euclidean spaces (42-XX) 2 Global analysis, analysis on manifolds (58-XX) 2 Mechanics of particles and systems (70-XX) 2 Optics, electromagnetic theory (78-XX) 1 General and overarching topics; collections (00-XX) 1 History and biography (01-XX) 1 Order, lattices, ordered algebraic structures (06-XX) 1 Field theory and polynomials (12-XX) 1 Category theory; homological algebra (18-XX) 1 Topological groups, Lie groups (22-XX) 1 Abstract harmonic analysis (43-XX) 1 Integral equations (45-XX) 1 Calculus of variations and optimal control; optimization (49-XX) 1 Geometry (51-XX) 1 Classical thermodynamics, heat transfer (80-XX) 1 Biology and other natural sciences (92-XX) 1 Systems theory; control (93-XX) Citations by Year