BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Gus Gutoski

Gus Gutoski contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
quant-phComputational ComplexityCryptography and SecurityComputer Science and Game Theory

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
11works
0followers
4topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

11 published item(s)

preprint2016arXiv

Optimal bounds for semi-honest quantum oblivious transfer

Oblivious transfer is a fundamental cryptographic primitive in which Bob transfers one of two bits to Alice in such a way that Bob cannot know which of the two bits Alice has learned. We present an optimal security bound for quantum oblivious transfer protocols under a natural and demanding definition of what it means for Alice to cheat. Our lower bound is a smooth tradeoff between the probability B with which Bob can guess Alice's bit choice and the probability A with which Alice can guess both of Bob's bits given that she learns one of the bits with certainty. We prove that 2B + A is greater than or equal to 2 in any quantum protocol for oblivious transfer, from which it follows that one of the two parties must be able to cheat with probability at least 2/3. We prove that this bound is optimal by exhibiting a family of protocols whose cheating probabilities can be made arbitrarily close to any point on the tradeoff curve.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Process tomography for unitary quantum channels

We study the number of measurements required for quantum process tomography under prior information, such as a promise that the unknown channel is unitary. We introduce the notion of an interactive observable and we show that any unitary channel acting on a $d$-level quantum system can be uniquely identified among all other channels (unitary or otherwise) with only $O(d^2)$ interactive observables, as opposed to the $O(d^4)$ required for tomography of arbitrary channels. This result generalizes, so that channels with at most $q$ Kraus operators can be identified with only $O(qd^2)$ interactive observables. Slight improvements can be obtained if we wish to identify such a channel only among unital channels or among other channels with $q$ Kraus operators. These results are proven via explicit construction of large subspaces of Hermitian matrices with various conditions on rank, eigenvalues, and partial trace. Our constructions are built upon various forms of totally nonsingular matrices.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Quantum interactive proofs and the complexity of separability testing

We identify a formal connection between physical problems related to the detection of separable (unentangled) quantum states and complexity classes in theoretical computer science. In particular, we show that to nearly every quantum interactive proof complexity class (including BQP, QMA, QMA(2), and QSZK), there corresponds a natural separability testing problem that is complete for that class. Of particular interest is the fact that the problem of determining whether an isometry can be made to produce a separable state is either QMA-complete or QMA(2)-complete, depending upon whether the distance between quantum states is measured by the one-way LOCC norm or the trace norm. We obtain strong hardness results by proving that for each n-qubit maximally entangled state there exists a fixed one-way LOCC measurement that distinguishes it from any separable state with error probability that decays exponentially in n.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Interactive proofs with competing teams of no-signaling provers

This paper studies a generalization of multi-prover interactive proofs in which a verifier interacts with two competing teams of provers: one team attempts to convince the verifier to accept while the other attempts to convince the verifier to reject. Each team consists of two provers who jointly implement a no-signaling strategy. No-signaling strategies are a curious class of joint strategy that cannot in general be implemented without communication between the provers, yet cannot be used as a black box to establish communication between them. Attention is restricted in this paper to two-turn interactions in which the verifier asks questions of each of the four provers and decides whether to accept or reject based on their responses. We prove that the complexity class of decision problems that admit two-turn interactive proofs with competing teams of no-signaling provers is a subset of PSPACE. This upper bound matches existing PSPACE lower bounds on the following two disparate and weaker classes of interactive proof: 1. Two-turn multi-prover interactive proofs with only one team of no-signaling provers. 2. Two-turn competing-prover interactive proofs with only one prover per team. Our result implies that the complexity of these two models is unchanged by the addition of a second competing team of no-signaling provers in the first case and by the addition of a second no-signaling prover to each team in the second case. Moreover, our result unifies and subsumes prior PSPACE upper bounds on these classes.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

On a measure of distance for quantum strategies

The present paper studies an operator norm that captures the distinguishability of quantum strategies in the same sense that the trace norm captures the distinguishability of quantum states or the diamond norm captures the distinguishability of quantum channels. Characterizations of its unit ball and dual norm are established via strong duality of a semidefinite optimization problem. A full, formal proof of strong duality is presented for the semidefinite optimization problem in question. This norm and its properties are employed to generalize a state discrimination result of Ref. [GW05]. The generalized result states that for any two convex sets S,T of strategies there exists a fixed interactive measurement scheme that successfully distinguishes any choice of s in S from any choice of t in T with bias proportional to the minimal distance between the sets S and T as measured by this norm. A similar discrimination result for channels then follows as a special case.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Parallel approximation of min-max problems

This paper presents an efficient parallel approximation scheme for a new class of min-max problems. The algorithm is derived from the matrix multiplicative weights update method and can be used to find near-optimal strategies for competitive two-party classical or quantum interactions in which a referee exchanges any number of messages with one party followed by any number of additional messages with the other. It considerably extends the class of interactions which admit parallel solutions, demonstrating for the first time the existence of a parallel algorithm for an interaction in which one party reacts adaptively to the other. As a consequence, we prove that several competing-provers complexity classes collapse to PSPACE such as QRG(2), SQG and two new classes called DIP and DQIP. A special case of our result is a parallel approximation scheme for a specific class of semidefinite programs whose feasible region consists of lists of semidefinite matrices that satisfy a transcript-like consistency condition. Applied to this special case, our algorithm yields a direct polynomial-space simulation of multi-message quantum interactive proofs resulting in a first-principles proof of QIP=PSPACE.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Quantum one-time programs

One-time programs are modelled after a black box that allows a single evaluation of a function, and then self-destructs. Because software can, in principle, be copied, general one-time programs exists only in the hardware token model: it has been shown that any function admits a one-time program as long as we assume access to physical devices called one-time memories. Quantum information, with its well-known property of no-cloning, would, at first glance, prevent the basic copying attack for classical programs. We show that this intuition is false: one-time programs for both classical and quantum maps, based solely on quantum information, do not exist, even with computational assumptions. We complement this strong impossibility proof by an equally strong possibility result: assuming the same basic one-time memories as used for classical one-time programs, we show that every quantum map has a quantum one-time program that is secure in the universal composability framework. Our construction relies on a new, simpler quantum authentication scheme and corresponding mechanism for computing on authenticated data.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Quantum Strategies and Local Operations

This thesis is divided into two parts. In Part I we introduce a new formalism for quantum strategies, which specify the actions of one party in any multi-party interaction involving the exchange of multiple quantum messages among the parties. This formalism associates with each strategy a single positive semidefinite operator acting only upon the tensor product of the input and output message spaces for the strategy. We establish three fundamental properties of this new representation for quantum strategies and we list several applications, including a quantum version of von Neumann's celebrated 1928 Min-Max Theorem for zero-sum games and an efficient algorithm for computing the value of such a game. In Part II we establish several properties of a class of quantum operations that can be implemented locally with shared quantum entanglement or classical randomness. In particular, we establish the existence of a ball of local operations with shared randomness lying within the space spanned by the no-signaling operations and centred at the completely noisy channel. The existence of this ball is employed to prove that the weak membership problem for local operations with shared entanglement is strongly NP-hard. We also provide characterizations of local operations in terms of linear functionals that are positive and "completely" positive on a certain cone of Hermitian operators, under a natural notion of complete positivity appropriate to that cone. We end the thesis with a discussion of the properties of no-signaling quantum operations.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

Properties of Local Quantum Operations with Shared Entanglement

Multi-party local quantum operations with shared quantum entanglement or shared classical randomness are studied. The following facts are established: (i) There is a ball of local operations with shared randomness lying within the space spanned by the no-signaling operations and centred at the completely noisy channel. (ii) The existence of the ball of local operations with shared randomness is employed to prove that the weak membership problem for local operations with shared entanglement is strongly NP-hard. (iii) Local operations with shared entanglement are characterized in terms of linear functionals that are ``completely'' positive on a certain cone K of separable Hermitian operators, under a natural notion of complete positivity appropriate to that cone. Local operations with shared randomness (but not entanglement) are also characterized in terms of linear functionals that are merely positive on that same cone K. (iv) Existing characterizations of no-signaling operations are generalized to the multi-party setting and recast in terms of the Choi-Jamiolkowski representation for quantum super-operators. It is noted that the standard nonlocal box is an example of a no-signaling operation that is separable, yet cannot be implemented by local operations with shared entanglement.

0 citations0 reviewsNo code linkedOpen access
preprint2007arXiv

Toward a general theory of quantum games

We study properties of quantum strategies, which are complete specifications of a given party's actions in any multiple-round interaction involving the exchange of quantum information with one or more other parties. In particular, we focus on a representation of quantum strategies that generalizes the Choi-Jamiołkowski representation of quantum operations. This new representation associates with each strategy a positive semidefinite operator acting only on the tensor product of its input and output spaces. Various facts about such representations are established, and two applications are discussed: the first is a new and conceptually simple proof of Kitaev's lower bound for strong coin-flipping, and the second is a proof of the exact characterization QRG = EXP of the class of problems having quantum refereed games.

0 citations0 reviewsNo code linkedOpen access
preprint2004arXiv

Quantum Interactive Proofs with Competing Provers

This paper studies quantum refereed games, which are quantum interactive proof systems with two competing provers: one that tries to convince the verifier to accept and the other that tries to convince the verifier to reject. We prove that every language having an ordinary quantum interactive proof system also has a quantum refereed game in which the verifier exchanges just one round of messages with each prover. A key part of our proof is the fact that there exists a single quantum measurement that reliably distinguishes between mixed states chosen arbitrarily from disjoint convex sets having large minimal trace distance from one another. We also show how to reduce the probability of error for some classes of quantum refereed games.

0 citations0 reviewsNo code linkedOpen access