Advanced search options

Sorted by: relevance · author · university · date | New search

You searched for `subject:(nonlocal games)`

.
Showing records 1 – 3 of
3 total matches.

▼ Search Limiters

University of Waterloo

1.
Russo, Vincent.
Extended *Nonlocal* * Games*.

Degree: 2017, University of Waterloo

URL: http://hdl.handle.net/10012/11620

The notions of entanglement and nonlocality are among the most striking ingredients found in quantum information theory. One tool to better understand these notions is the model of nonlocal games; a mathematical framework that abstractly models a physical system. The simplest instance of a nonlocal game involves two players, Alice and Bob, who are not allowed to communicate with each other once the game has started and who play cooperatively against an adversary referred to as the referee.
The focus of this thesis is a class of games called extended nonlocal games, of which nonlocal games are a subset. In an extended nonlocal game, the players initially share a tripartite state with the referee. In such games, the winning conditions for Alice and Bob may depend on outcomes of measurements made by the referee, on its part of the shared quantum state, in addition to Alice and Bob's answers to the questions sent by the referee.
We build up the framework for extended nonlocal games and study their properties and how they relate to nonlocal games. In doing so, we study the types of strategies that Alice and Bob may adopt in such a game. For instance, we refer to strategies where Alice and Bob use quantum resources as standard quantum strategies and strategies where there is an absence of entanglement as an unentangled strategy. These formulations of strategies are purposefully reminiscent of the respective quantum and classical strategies that Alice and Bob use in a nonlocal game, and we also consider other types of strategies with a similar correspondence for the class of extended nonlocal games.
We consider the value of an extended nonlocal game when Alice and Bob apply a particular strategy, again in a similar manner to the class of nonlocal games. Unlike computing the unentangled value where tractable algorithms exist, directly computing the standard quantum value of an extended nonlocal game is an intractable problem. We introduce a technique that allows one to place upper bounds on the standard quantum value of an extended nonlocal game. Our technique is a generalization of what we refer to as the QC hierarchy which was studied independently in works by Doherty, Liang, Toner, and Wehner as well as by Navascues, Pironio, and Acin. This technique yields an upper bound approximation for the quantum value of a nonlocal game.
We also consider the question of whether or not the dimensionality of the state that Alice and Bob share as part of their standard quantum strategy makes any difference in how well they can play the game. That is, does there exist an extended nonlocal game where Alice and Bob can win with a higher probability if they share a state where the dimension is infinite? We answer this question in the affirmative and provide a specific example of an extended nonlocal game that exhibits this behavior.
We study a type of extended nonlocal game referred to as a monogamy-of-entanglement game, introduced by Tomamichel, Fehr, Kaniewski, and Wehner, and present a number of new results for this…

Subjects/Keywords: quantum information; quantum complexity theory; nonlocal games

Record Details Similar Records

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^{th} Edition):

Russo, V. (2017). Extended Nonlocal Games. (Thesis). University of Waterloo. Retrieved from http://hdl.handle.net/10012/11620

Note: this citation may be lacking information needed for this citation format:

Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16^{th} Edition):

Russo, Vincent. “Extended Nonlocal Games.” 2017. Thesis, University of Waterloo. Accessed October 16, 2019. http://hdl.handle.net/10012/11620.

Note: this citation may be lacking information needed for this citation format:

Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^{th} Edition):

Russo, Vincent. “Extended Nonlocal Games.” 2017. Web. 16 Oct 2019.

Vancouver:

Russo V. Extended Nonlocal Games. [Internet] [Thesis]. University of Waterloo; 2017. [cited 2019 Oct 16]. Available from: http://hdl.handle.net/10012/11620.

Note: this citation may be lacking information needed for this citation format:

Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Russo V. Extended Nonlocal Games. [Thesis]. University of Waterloo; 2017. Available from: http://hdl.handle.net/10012/11620

Not specified: Masters Thesis or Doctoral Dissertation

University of Waterloo

2.
Paddock, Connor.
Algebraic and combinatorial aspects of incidence groups and linear system non-local *games* arising from graphs.

Degree: 2019, University of Waterloo

URL: http://hdl.handle.net/10012/14744

To every linear binary-constraint system (LinBCS) non-local game, there is an associated algebraic object called the solution group. Cleve, Liu, and Slofstra showed that a LinBCS game has a perfect quantum strategy if and only if an element, denoted by J, is non-trivial in this group. In this work, we restrict to the set of graph-LinBCS games, which arise from ℤ_{2}-linear systems Ax=b, where A is the incidence matrix of a connected graph, and b is a (non-proper) vertex 2-colouring. In this context, Arkhipov's theorem states that the corresponding graph-LinBCS game has a perfect quantum strategy, and no perfect classical strategy, if and only if the graph is non-planar and the 2-colouring b has odd parity. In addition to efficient methods for detecting quantum and classical strategies for these games, we show that computing the classical value, a problem that is NP-hard for general LinBCS games can be done efficiently. In this work, we describe a graph-LinBCS game by a 2-coloured graph and call the corresponding solution group a graph incidence group. As a consequence of the Robertson-Seymour theorem, we show that every quotient-closed property of a graph incidence group can be expressed by a finite set of forbidden graph minors. Using this result, we recover one direction of Arkhipov's theorem and derive the forbidden graph minors for the graph incidence group properties: finiteness, and abelianness. Lastly, using the representation theory of the graph incidence group, we discuss how our graph minor criteria can be used to deduce information about the perfect strategies for graph-LinBCS games.

Subjects/Keywords: nonlocal games; quantum correlations; quantum information; algebraic graph theory; graph minors; graph incidence groups; linear system nonlocal games; Arkhipov's theorem

Record Details Similar Records

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^{th} Edition):

Paddock, C. (2019). Algebraic and combinatorial aspects of incidence groups and linear system non-local games arising from graphs. (Thesis). University of Waterloo. Retrieved from http://hdl.handle.net/10012/14744

Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16^{th} Edition):

Paddock, Connor. “Algebraic and combinatorial aspects of incidence groups and linear system non-local games arising from graphs.” 2019. Thesis, University of Waterloo. Accessed October 16, 2019. http://hdl.handle.net/10012/14744.

Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^{th} Edition):

Paddock, Connor. “Algebraic and combinatorial aspects of incidence groups and linear system non-local games arising from graphs.” 2019. Web. 16 Oct 2019.

Vancouver:

Paddock C. Algebraic and combinatorial aspects of incidence groups and linear system non-local games arising from graphs. [Internet] [Thesis]. University of Waterloo; 2019. [cited 2019 Oct 16]. Available from: http://hdl.handle.net/10012/14744.

Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Paddock C. Algebraic and combinatorial aspects of incidence groups and linear system non-local games arising from graphs. [Thesis]. University of Waterloo; 2019. Available from: http://hdl.handle.net/10012/14744

Not specified: Masters Thesis or Doctoral Dissertation

University of Waterloo

3. Hornby, Taylor. Concentration Bounds from Parallel Repetition Theorems.

Degree: 2018, University of Waterloo

URL: http://hdl.handle.net/10012/13638

This thesis contributes to the study of parallel repetition theorems and concentration bounds for nonlocal games and quantum interactive proofs. We make the following contributions:
- A lemma that is useful for converting parallel repetition theorems (bounds on the probability of winning all instances of a nonlocal game which is being repeated in parallel) into concentration bounds (bounds on winning a certain fraction of the instances).
- Exponentially-decaying concentration bounds for two-player games on the uniform distribution and k-player free games, against quantum strategies.
- A proof that given a quantum interactive proof system with parameters α (the probability with which the verifier can be convinced to accept when they should accept) and β (the soundness error), as long as α > β, both the soundness error and completeness error can be reduced exponentially by repeating the protocol in parallel and requiring an (α + β)/2 fraction of the repetitions to be won. Our result requires a log-factor more repetitions than are necessary in the classical case.

Subjects/Keywords: quantum information; parallel repetition; nonlocal games; interactive proofs; concentration bounds

Record Details Similar Records

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^{th} Edition):

Hornby, T. (2018). Concentration Bounds from Parallel Repetition Theorems. (Thesis). University of Waterloo. Retrieved from http://hdl.handle.net/10012/13638

Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16^{th} Edition):

Hornby, Taylor. “Concentration Bounds from Parallel Repetition Theorems.” 2018. Thesis, University of Waterloo. Accessed October 16, 2019. http://hdl.handle.net/10012/13638.

Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^{th} Edition):

Hornby, Taylor. “Concentration Bounds from Parallel Repetition Theorems.” 2018. Web. 16 Oct 2019.

Vancouver:

Hornby T. Concentration Bounds from Parallel Repetition Theorems. [Internet] [Thesis]. University of Waterloo; 2018. [cited 2019 Oct 16]. Available from: http://hdl.handle.net/10012/13638.

Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Hornby T. Concentration Bounds from Parallel Repetition Theorems. [Thesis]. University of Waterloo; 2018. Available from: http://hdl.handle.net/10012/13638

Not specified: Masters Thesis or Doctoral Dissertation