Gus Gutoski - Academic Home Page

Postdoctoral researcher
Perimeter Institute for Theoretical Physics
ggutoski (at) perimeterinstitute (dot) ca

Publications

Hierarchical deterministic Bitcoin wallets that tolerate key leakage
Gus Gutoski and Douglas Stebila
To appear in Financial Cryptography 2015. Cryptology ePrint Archive, Report 2014/998.

Optimal bounds for quantum weak oblivious transfer
André Chailloux, Gus Gutoski, and Jamie Sikora
Preprint: arXiv:1310.3262 [quant-ph]

Process tomography for unitary quantum channels
Gus Gutoski and Nathaniel Johnston
Journal of Mathematical Physics, 55(3):032201, 2014. arXiv:1309.0840 [quant-ph]

Quantum interactive proofs and the complexity of entanglement detection
Gus Gutoski, Patrick Hayden, Kevin Milner, and Mark M. Wilde
Theory of Computing, 11(3):59-103, 2015. Published version or arXiv:1308.5788 [quant-ph]

Quantum one-time programs
Anne Broadbent, Gus Gutoski, and Douglas Stebila
Extended abstract in Proceedings of Advances in Cryptology -- CRYPTO 2013, volume 8043 of Lecture Notes in Computer Science, pages 344-360, 2013. Cryptology ePrint Archive, Report 2013/343.
Preliminary full version available at arXiv:1211.1080 [quant-ph]
Recorded talk at QCrypt2013.

Interactive proofs with competing teams of no-signaling provers
Gus Gutoski
Chicago Journal of Theoretical Computer Science, 2013(7), 2013. Published version or ECCC TR10-187 or arXiv:1012.0821 [cs.CC]

Parallel approximation of min-max problems
Gus Gutoski and Xiaodi Wu
Computational Complexity, 22(2):385-428, 2013.
Invited to a special issue for selected papers from CCC 2012. arXiv:1011.2787 [quant-ph]

A preliminary version appeared in Proceedings of the 27th IEEE Conference on Computational Complexity (CCC 2012), pages 21-31, 2012.

On a measure of distance for quantum strategies
Gus Gutoski
Journal of Mathematical Physics, 53(3):032202, 2012. arXiv:1008.4636 [quant-ph]

Properties of local quantum operations with shared entanglement
Gus Gutoski
Quantum Information and Computation, 9(9&10):739-764, 2009. arXiv:0805.2209 [quant-ph]

Toward a general theory of quantum games
Gus Gutoski and John Watrous
In Proceedings of the 39th ACM Symposium on Theory of Computing (STOC 2007), pages 565-574, 2007. arXiv:quant-ph/0611234

Upper bounds for quantum interactive proofs with competing provers
Gus Gutoski
In Proceedings of the 20th IEEE Conference on Computational Complexity (CCC 2005), pages 334-343, 2005. [PDF]

Quantum interactive proofs with competing provers
Gus Gutoski and John Watrous
In Proceedings of the 22nd Symposium on Theoretical Aspects of Computer Science (STACS 2005), volume 3404 of Lecture Notes in Computer Science, pages 605-616, 2005. arXiv:cs/0412102 [cs.CC]

Theses

Quantum strategies and local operations
Gus Gutoski
PhD thesis, University of Waterloo, 2009. arXiv:1003.0038 [quant-ph]

Short quantum games
Gus Gutoski
Master's thesis, University of Calgary, 2005. arXiv:cs/0511017 [cs.CC]

Teaching

QIC 890/891 (Spring 2013, Spring 2014) -- Selected Advanced Topics in Quantum Information
Topic: Topics in quantum cryptography (6 hours of lecture)

Lecture 1: Random numbers, coin tossing
Lecture 2: Bit commitment, authentication
Lecture 3: Encode-encrypt schemes, security of the trap scheme
Lecture 4: Quantum computing on authenticated data
Assignment

QIC 890/891 (Spring 2012) -- Selected Advanced Topics in Quantum Information
Topic: Quantum strategies (6 hours of lecture)

Lecture 1: Definitions of quantum strategies
Lecture 2: The link product, combinations of strategies, output probabilities
Lecture 3: Characterization of strategies
Lecture 4: Min-max theorem for zero-sum quantum games, maximum output probabilities, an efficient min-max algorithm
Assignment and solutions

Last Update: March 26, 2015