RIT on Quantum Information Archives for Academic Year 2017


Quantum Information RIT Organizational Meeting.

When: Mon, August 28, 2017 - 4:15pm
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 .

Foundations of Quantum Theory (part 1)

When: Mon, September 18, 2017 - 4:15pm
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.

Foundations of Quantum Theory II

When: Mon, September 25, 2017 - 4:15pm
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.

Picture-Languages for Quantum Information I

When: Mon, October 2, 2017 - 4:15pm
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.

Picture-Languages for Quantum Information II

When: Mon, October 9, 2017 - 4:15pm
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.

Quantum Strategy Formalism I

When: Mon, October 16, 2017 - 4:15pm
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.

Quantum Strategy Formalism II

When: Mon, October 23, 2017 - 4:15pm
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.

A Quantum-Secure Non-Interactive Zero-Knowledge Proof System

When: Mon, October 30, 2017 - 4:15pm
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.

Parallel Repetition of Nonlocal Games

When: Mon, November 6, 2017 - 4:15pm
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).

Characterization of Rigid Magic Binary Constraint Games on Graphs

When: Mon, November 13, 2017 - 4:15pm
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.

Syntax & Semantics in Quantum Information

When: Mon, November 20, 2017 - 4:15pm
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.


Nonlocal games with synchronous correlations

When: Mon, November 27, 2017 - 4:15pm
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.

Nonlocal games with synchronous correlations (cont'd).

When: Mon, December 4, 2017 - 4:15pm
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.

Unique Games are Easy with Entangled Provers

When: Mon, December 11, 2017 - 4:15pm
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

Organizational Meeting

When: Mon, January 29, 2018 - 4:15pm
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 .

Constant-depth quantum circuits and nonlocal games

When: Mon, February 5, 2018 - 4:15pm
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)

Morphisms in Categories of Nonlocal Games

When: Mon, February 12, 2018 - 4:15pm
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.

Morphisms in categories of nonlocal games (cont'd)

When: Mon, February 19, 2018 - 4:15pm
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.

The set of quantum correlations is not closed

When: Mon, February 26, 2018 - 4:15pm
Where: Atlantic 3100A
Speaker: Brad Lackey (University of Maryland) - http://www.umiacs.umd.edu/~bclackey
Abstract: We review Slofstra's construction of a family of nonlocal games that cannot be won with certainty using any finite-dimensional quantum strategy, however can be played perfectly in the limit of such strategies. The key methodology is to link a perfect strategy for such a game to a finite-dimensional representation of a specific finitely-presented group constructed from the game. Reference: Slofstra, arXiv:1703.08618.

Graph Correlation Functions

When: Mon, March 5, 2018 - 4:15pm
Where: Atlantic 3100A
Speaker: Aaron Ostrander (University of Maryland) - http://quics.umd.edu/people/aaron-ostrander
Abstract: Slofstra recently showed that the set of quantum correlations is not
closed; however, his construction (for the observables that exhibit
non-closure) requires advanced group theory. Following this result,
Dykema et. al. developed a graph theoretic proof of the non-closure of
the set of quantum correlations. We will begin going through the
lemmas of https://arxiv.org/abs/1709.05032 that are part of this graph
theoretic proof.

Vectorial correlations and non-closure of the set of quantum correlations

When: Mon, March 12, 2018 - 4:15pm
Where: Atlantic 3100A
Speaker: Aaron Ostrander (University of Maryland) - http://quics.umd.edu/people/aaron-ostrander
Abstract: We will develop some lemmas about vectorial correlations.
Combining these with the lemmas we proved about graph correlation
functions last week, we will conclude the proof of non-closure of the
set of correlations by Dykema et. al.

Quantum cryptography from the pretty good measurement

When: Mon, March 26, 2018 - 4:15pm
Where: Atlantic 3100A
Speaker: Carl Miller (University of Maryland) - http://www.umiacs.umd.edu/~camiller/
Abstract: The pretty good measurement is a formal way of choosing a strategy to guess the value of a classical register given quantum side information. The pretty good measurement is not always optimal, but can be proven to be near-optimal in a precise sense. As a consequence, an adversary who uses the pretty good measurement is almost as good as the strongest possible adversary. In the talk, I will discuss how this simple construction provides some short and elegant proofs of security in quantum cryptography.

Schur-Weyl duality and its application to qubit purification

When: Mon, April 2, 2018 - 4:15pm
Where: Atlantic 3100A
Speaker: Honghao Fu (University of Maryland) -
Abstract: Schur-Weyl duality is one of the remarkable results in representation theory, which connects the irreducible representations of the symmetric group to the irreducible algebraic representation of the general linear group of a complex vector space. It is also an important tool in the study of quantum information. In this talk, I will give an overview of Schur-Weyl duality which covers the background and some of the related topics. Then I will give an example to show how it is applied in quantum Information. The application is called qubit purification, which aims at producing one qubit with high fidelity out of many copies of identical unknown depolarized qubits.

Schur-Weyl duality and its application to qubit purification (Part II)

When: Mon, April 9, 2018 - 4:15pm
Where: Atlantic 3100A
Speaker: Honghao Fu (University of Maryland) -
Abstract: In the second part of this talk, I am going to focus on the application of Schur-Weyl duality to the qubit purification problem. In this problem, we are given N copies of a depolarized qubit state. The goal is to apply a procedure that will produce a qubit state that has high fidelity to the original state. The optimal procedure for this is known, and it is designed based on the Schur decomposition of the state of the N qubits. We are going to see how Schur-Weyl duality is applied to this problem and how the structure of the irreducible representation of the unitary group makes the optimal procedure simple.

The ZX-calculus: Quantum theory with spiders

When: Mon, April 16, 2018 - 4:15pm
Where: Atlantic 3100A
Speaker: Spencer Breiner (National Institute of Standards and Technology) -
Abstract: In this talk I will give a brief introduction to the ZX-calculus, a formal system of diagrams and graphical manipulations which can be used to give proofs about quantum processes. The first half of the talk will connect the mathematical structures involved--monoidal categories, Frobenius/Hopf algebras--with their physical interpretation in quantum theory. In the remaining time I will demonstrate by example how these methods can help to simplify and clarify quantum analyses.

Point games and Coin Flipping protocols

When: Mon, April 23, 2018 - 4:15pm
Where: Atlantic 3100A
Speaker: Aarthi Sundaram (University of Maryland) - http://quics.umd.edu/people/aarthi-sundaram
Abstract: Kitaev's point game formalism was used by Mochon (arXiv:0711.4114) to show the existence of a quantum weak coin flipping protocol with arbitrarily small bias and is a fundamental result in quantum cryptography. Though this result has been used as a black-box in a number of other follow-up results, the novel techniques used in this proof (especially Kitaev's point game formalism) are not well understood. It is believed that a complete grasp of these techiniques could shed more light on the role of entanglement in quantum protocols as well as find other applications where point games can be used. One direction to find this understanding may lie in finding a graphical calculus representation for point games. As a first step in that direction, I will discuss our current grasp of this formalism based on the work done by Aharanov et al. (arXiv:1402.7166) to simplify and clarify some parts of Mochon's original proof.

The two conjuctive fragments of linear logic

When: Mon, April 30, 2018 - 4:15pm
Where: Atlantic 3100A
Speaker: Brad Lackey (University of Maryland) - http://www.umiacs.umd.edu/~bclackey/
Abstract: We present the two simple fragments of linear logic coming from the additive conjunction and multiplicative conjunction (and their associated units). Specifically we look at the syntax of these related logics, and their algebraic and categorical semantics. Our goal is to highlight the relationship between these systems and operational quantum theories, quantum resource theories, and graphical languages for quantum programming. This is ongoing joint work with Aarthi Sundaram.

Quantum computation and 3-manifold invariants

When: Mon, May 7, 2018 - 4:15pm
Where: Atlantic 3100A
Speaker: Gorjan Alagic (University of Maryland) - http://www.alagic.org
Abstract: Topological quantum computation (TQC) is an alternative model of quantum computation, where computations are described via topological braids rather than unitary circuits. As it turns out, there are other models which also have this property, but where the underlying topological objects are higher-dimensional analogues of braids. Understanding this model has led to interesting results, such as quantum algorithms for approximating certain 3-manifold invariants and simulating so-called "topological quantum field theories" in (2+1) dimensions. In this talk, I will give a brief introduction to this area and a high-level overview of some of the main results.