Where: Atlantic Building 3100A (QuICS)

Speaker: Brad Lackey (University of Maryland) - http://www.umiacs.umd.edu/~bclackey/

Abstract: The RIT homepage is: http://www.umiacs.umd.edu/~bclackey/QI-RIT2017Fall.html .

Where: Atlantic 3100A

Speaker: Brad Lackey (University of Maryland) - http://www.umiacs.umd.edu/~bclackey/

Abstract: I will provide a rapid introduction to the foundations of quantum theory, with an emphasis on the differences between classical and quantum probability.

Where: Atlantic 3100A

Speaker: Brad Lackey (University of Maryland) - http://www.umiacs.umd.edu/~bclackey

Abstract: I will continue with a rapid introduction to the foundations of quantum theory, focusing on bipartite systems and measurement.

Where: Atlantic 3100A

Speaker: Carl Miller (University of Maryland, College Park) - http://www.umiacs.umd.edu/~camiller/

Abstract: The conventional way to express proofs in quantum information is via vector spaces and linear operators. I will discuss a newer, intuitive approach which is based on local manipulations of box-and-wire diagrams. The first talk will introduce picture elements for some basic concepts (registers, states, processes). The primary references for this material are arXiv:1510.05468, arXiv:1605.08617, and the book Picturing Quantum Processes by B. Coecke and A. Kissinger.

Where: Atlantic 3100A

Speaker: Carl Miller (University of Maryland, College Park) - http://www.umiacs.umd.edu/~camiller/

Abstract: I will continue with an introduction to proofs-by-picture in quantum information, and discuss some directions for further development.

Where: Atlantic 3100A

Speaker: Yuan Su (University of Maryland) -

Abstract: This talk will focus on the quantum strategy formalism proposed by Gus Gutoski and John Watrous. In this new formalism, the strategy of each participant in any multi-party interaction is associated with a positive semidefinite operator, and the interaction output probability is given by the inner product of two such operators. The first part of the talk discusses basic notions of quantum strategy formalism, with occasional detour to quantum information preliminaries.

References:

[1] J. Watrous, The Theory of Quantum Information, https://cs.uwaterloo.ca/~watrous/TQI/.

[2] G. Gutoski and J. Watrous, Toward a general theory of quantum games.

[3] G. Chiribella, G. M. D'Ariano, and P. Perinotti, Theoretical framework for quantum networks.

Where: Atlantic 3100A

Speaker: Yuan Su (University of Maryland) -

Abstract: This talk will focus on the quantum strategy formalism proposed by Gus Gutoski and John Watrous. In this new formalism, the strategy of each participant in any multi-party interaction is associated with a positive semidefinite operator, and the interaction output probability is given by the inner product of two such operators. The second part of the talk presents a characterization of strategies in terms of linear constraints on positive semidefinite operators, with occasional detour to quantum information preliminaries.

Where: Atlantic 3100A

Speaker: Shaopeng Zhu (University of Maryland) -

Abstract: We introduce a method to convert sigma protocols, a 3-round proof system where the prover interacts with the verifier via three messages ("commitment", "challenge" and "response") and tries to convince the verifier of the validity of its proof, into non-interactive zero-knowledge proofs (NIZK), where the verifier can efficiently verify the proof without learning any additional "knowledge" or having extra interaction(s). According to Unruh's paper [1], this is the first known such conversion that is secure against quantum adversaries.

References:

[1]: Unruh, Dominique. "Non-Interactive Zero-Knowledge Proofs in the Quantum Random Oracle Model." EUROCRYPT (2). 2015.

Where: Atlantic 3100A

Speaker: Carl Miller (University of Maryland) - http://www.umiacs.umd.edu/~camiller

Abstract: Parallel repetition occurs when N copies of a nonlocal game are played simultaneously. In some cases, an optimal strategy for this setting is for the players to play each copy of the game independently. In other cases, they can actually win more often by coordinating their answers to different copies of the game. Determining when there is a benefit to this kind of coordination is a subtle problem that involves interesting mathematics. I will present an approach to the quantum parallel repetition problem that uses semidefinite programming duality.

Reference: R. Cleve, W. Slofstra, F. Unger, S. Upadhyay. Perfect Parallel Repetition Theorem for Quantum XOR Proof Systems. Computational Complexity 17, pp. 282-299 (2008).

Where: Atlantic 3100A

Speaker: Aaron Ostrander (University of Maryland) -

Abstract: Two player binary constraint games are games where Alice and Bob are

asked to assign 0 and 1 to variables subject to some constraints. The

magic pentagram game and magic square game are two such games with

unique quantum strategies that win with probability 1 (while classical

strategies succeed with probability less than 1). For a class of games

that generalizes the magic square and pentagram, we show that any game

with a unique strategy is basically equivalent to either the magic

square or magic pentagram. We provide a graph theoretic

characterization of these games.

Where: Atlantic 3100A

Speaker: Spencer Breiner (National Institute of Standards and Technology) -

Abstract: In this talk I will discuss some additional aspects of Coecke & Kissinger's diagrammatic language for quantum processes. I will begin with a brief review of string diagrams and quantum ("doubled") processes. I will introduce Frobenius algebras together with their diagrammatic analogues, called spiders. These can be used to encode orthonormal bases, providing a means for describing measurement and encoding. This allows us to incorporate both quantum and classical data, as well as their interaction, into the diagrammatic formalism.

Where: Atlantic 3100A

Speaker: Brad Lackey (University of Maryland) - http://www.umiacs.umd.edu/~bclackey/

Abstract: We examine analogues of Bell’s inequalities for nonlocal games with synchronous correlations. Unlike general correlations and the CHSH inequality, there can be no quantum Bell violation among synchronous correlations with two measurement settings. However we exhibit explicit analogues of

Bell’s inequalities for synchronous correlation with three measurement settings and two outputs, provide an analogue of Tsirl’son’s bound in this setting.

Where: Atlantic 3100A

Speaker: Brad Lackey (University of Maryland) - http://www.umiacs.umd.edu/~bclackey

Abstract: We finish our discussion from last week of synchronous quantum correlations. We continue our example of three measurement settings and two outputs and provide an analogue of Tsirl’son’s bound in this setting, and give explicit quantum correlations that saturate this bound. If time allows, we will discuss categories whose morphisms are the classical, quantum, or nonsignaling nonlocal games with synchronous correlations, and characterize sections, retractions, monomorphisms, and epimorphisms in each of these categories.

Where: Atlantic 3100A

Speaker: Aarthi Sundaram (University of Maryland) -

Abstract: Unique games are non-local games where the constraints enforced by the verifier are ‘unique’ constraints (i.e., permutations). The Unique Games Conjecture (UGC) by Khot in 2002 states that approximating the value of these games using classical strategies is NP-hard. I will present an approach to approximate the value of a unique game when the provers share entanglement thereby falsifying a variant of the UGC for entangled provers. Essentially, the proof uses semi-definite programming (SDP) and a "quantum rounding technique" which takes a solution to an SDP and transforms it into a strategy for entangled provers. Additionally, by taking advantage of the structure of the SDP used, a parallel repetition thoerem for unique entangled games can also be shown.

Reference: Unique Games with Entangled Provers Are Easy. Julia Kempe, Oded Regev, and Ben Toner. SIAM Journal on Computing 2010 39:7, 3207-3229. arXiv:0710.0655

Where: Atlantic Building 3100A

Speaker: Brad Lackey and Carl Miller (University of Maryland) -

Abstract: We'll discuss logistics, and then give some short advertisements for papers that we'd like to discuss during the spring semester. Suggestions and contributions are welcome! More information can be found on the QI-RIT website: http://www.umiacs.umd.edu/~bclackey/QI-RIT2018Spring.html .

Where: Atlantic 3100A

Speaker: Carl Miller (University of Maryland, College Park) - http://www.umiacs.umd.edu/~camiller

Abstract: A recent paper of Bravyi, Gosset, and Koenig demonstrates a constant-depth quantum circuit for solving a particular mathematical problem, while at the same time showing that there is no constant-depth classical circuit that can solve the same problem. The proof involves showing that such a classical circuit would imply unreasonably effective strategies at certain multiplayer games. In the talk I will examine some of the technical tools used to achieve this result.

Reference: S. Bravyi, D. Gosset, R. Koenig, "Quantum advantage with shallow circuits." arXiv:1704.00690. (2017)

Where: Atlantic 3100A

Speaker: Brad Lackey (University of Maryland) - http://www.umiacs.umd.edu/~bclackey

Abstract: Synchronous correlations are a class of nonlocal games that behave like functions between finite sets. We examine categories whose morphisms are games with synchronous classical, quantum, or general nonsignaling correlations, characterizing when morphisms in these categories are monic, epic, sections, or retractions.

Where: Atlantic 3100A

Speaker: Brad Lackey (University of Maryland) - http://www.umiacs.umd.edu/~bclackey

Abstract: Synchronous correlations are a class of nonlocal games that behave like functions between finite sets. We examine categories whose morphisms are games with synchronous classical, quantum, or general nonsignaling correlations, characterizing when morphisms in these categories are monic, epic, sections, or retractions.