<?xml version="1.0" encoding="UTF-8"?><?xml-stylesheet type="text/xsl" href="static/style.xsl"?><OAI-PMH xmlns="http://www.openarchives.org/OAI/2.0/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.openarchives.org/OAI/2.0/ http://www.openarchives.org/OAI/2.0/OAI-PMH.xsd"><responseDate>2026-11-22T17:37:09Z</responseDate><request verb="GetRecord" identifier="oai:uwspace.uwaterloo.ca:10012/19418" metadataPrefix="dim">https://dspacemainprd01.lib.uwaterloo.ca/server/oai/request</request><GetRecord><record><header><identifier>oai:uwspace.uwaterloo.ca:10012/19418</identifier><datestamp>2025-03-26T23:37:48Z</datestamp><setSpec>com_10012_9924</setSpec><setSpec>com_10012_1</setSpec><setSpec>col_10012_9928</setSpec><setSpec>col_10012_6</setSpec></header><metadata><dim:dim xmlns:dim="http://www.dspace.org/xmlns/dspace/dim" xmlns:doc="http://www.lyncode.com/xoai" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.dspace.org/xmlns/dspace/dim http://www.dspace.org/schema/dim.xsd">
   <dim:field mdschema="dc" element="contributor" qualifier="advisor">Yard, Jon</dim:field>
   <dim:field mdschema="dc" element="contributor" qualifier="advisor">Slofstra, William</dim:field>
   <dim:field mdschema="dc" element="contributor" qualifier="author" authority="52940a55-ae71-4bf2-b105-2cc9c6566e40" confidence="600">Paul-Paddock, Connor</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2023-05-04T18:17:55Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2023-05-04T18:17:55Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued">2023-05-04</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="submitted">2023-05-02</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">http://hdl.handle.net/10012/19418</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract" lang="en">Quantum correlations can be viewed as particular abstract states on the tensor product of&#xd;
operator systems which model quantum measurement scenarios. In the paradigm of nonlocal games,&#xd;
this perspective illustrates a connection between optimal strategies and certain&#xd;
representations of a finitely presented $*$-algebra affiliated with the nonlocal game.&#xd;
This algebraic interpretation of quantum correlations arising from nonlocal games has been&#xd;
valuable in recent years. In particular, the connection between representations and&#xd;
strategies has been useful for investigating and separating the various frameworks for&#xd;
quantum correlation as well as in developing cryptographic primitives for untrusted&#xd;
quantum devices. However to make use of this correspondence in a realistic setting one&#xd;
needs mathematical guarantees that this correspondence is robust to noise.&#xd;
&#xd;
We address this issue by considering the situation where the correlations are not ideal.&#xd;
We show that near-optimal finite-dimensional quantum strategies using arbitrary quantum&#xd;
states are approximate representations of the affiliated nonlocal game algebra for&#xd;
synchronous, boolean constraint systems (BCS), and XOR nonlocal games. This result&#xd;
robustly extends the correspondence between optimal strategies and finite-dimensional&#xd;
representations of the nonlocal game algebras for these prominent classes of nonlocal&#xd;
games. We also show that finite-dimensional approximate representations of these nonlocal&#xd;
game algebras are close to near-optimal strategies employing a maximally entangled state.&#xd;
As a corollary, we deduce that near-optimal quantum strategies are close to a near-optimal&#xd;
quantum strategy using a maximally entangled state.&#xd;
&#xd;
A boolean constraint system $B$ is $pp$-definable from another boolean constraint system&#xd;
$B&amp;apos;$ if there is a $pp$-formula defining $B$ over $B&amp;apos;$. There is such a $pp$-formula if all the constraints in $B$ can be defined via conjunctions of relations in $B&amp;apos;$ using additional boolean variables if needed. We associate a finitely presented $*$-algebra, called a BCS algebra, to each boolean constraint system $B$. We show that $pp$-definability can be interpreted algebraically as $*$-homomorphisms between BCS algebras. This allows us to classify boolean constraint languages and separations between various generalized notions of satisfiability. These types of satisfiability&#xd;
are motivated by nonlocal games and the various frameworks for quantum correlations and&#xd;
state-independent contextuality. As an example, we construct a BCS that is $C^*$-satisfiable in the sense that it has a representation on a Hilbert space $H$ but has no tracial&#xd;
representations, and thus no interpretation in terms of commuting operator correlations.</dim:field>
   <dim:field mdschema="dc" element="language" qualifier="iso" lang="en">en</dim:field>
   <dim:field mdschema="dc" element="publisher" lang="en">University of Waterloo</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">quantum information</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">nonlocal games</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">approximate representation theory</dim:field>
   <dim:field mdschema="dc" element="title" lang="en">Near-optimal quantum strategies for nonlocal games, approximate representations, and BCS algebras</dim:field>
   <dim:field mdschema="dc" element="type" lang="en">Doctoral Thesis</dim:field>
   <dim:field mdschema="dc" element="pending">false</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="department" lang="en">Combinatorics and Optimization</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="discipline" lang="en">Combinatorics and Optimization (Quantum Information)</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="grantor" lang="en">University of Waterloo</dim:field>
   <dim:field mdschema="uws-etd" element="degree" lang="en">Doctor of Philosophy</dim:field>
   <dim:field mdschema="uws-etd" element="embargo" qualifier="terms" lang="en">0</dim:field>
   <dim:field mdschema="uws" element="contributor" qualifier="advisor">Yard, Jon</dim:field>
   <dim:field mdschema="uws" element="contributor" qualifier="advisor">Slofstra, William</dim:field>
   <dim:field mdschema="uws" element="contributor" qualifier="affiliation1" lang="en">Faculty of Mathematics</dim:field>
   <dim:field mdschema="uws" element="published" qualifier="city" lang="en">Waterloo</dim:field>
   <dim:field mdschema="uws" element="published" qualifier="country" lang="en">Canada</dim:field>
   <dim:field mdschema="uws" element="published" qualifier="province" lang="en">Ontario</dim:field>
   <dim:field mdschema="uws" element="typeOfResource" lang="en">Text</dim:field>
   <dim:field mdschema="uws" element="peerReviewStatus" lang="en">Unreviewed</dim:field>
   <dim:field mdschema="uws" element="scholarLevel" lang="en">Graduate</dim:field>
   <dim:field mdschema="others" element="access-status">open.access</dim:field>
</dim:dim>
</metadata></record></GetRecord></OAI-PMH>