Toward a general theory of quantum games

Abstract

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.

23 pages, 12pt font, single-column compilation of STOC 2007 final version

Cited by in corpus (83)

• Experimental Superposition of Orders of Quantum Gates
• Quantum circuits cannot control unknown operations
• Quantum Shannon theory with superpositions of trajectories
• Quantum computation with programmable connections between gates
• Amortized Channel Divergence for Asymptotic Quantum Channel Discrimination
• Quantum Algorithmic Measurement
• Composable security of delegated quantum computation
• An Experimental Implementation of Oblivious Transfer in the Noisy Storage Model
• Key recycling in authentication
• Unforgeable Noise-Tolerant Quantum Tokens
• Quantum circuits with classical versus quantum control of causal order
• Theoretical framework for Higher-Order Quantum Theory
• Dynamical Entanglement
• Can a quantum state over time resemble a quantum state at a single time?
• Updating the Born rule
• Entanglement cost and quantum channel simulation
• Witnesses of causal nonseparability: an introduction and a few case studies
• On the definition and characterisation of multipartite causal (non)separability
• Geometric distinguishability measures limit quantum channel estimation and discrimination
• A short impossibility proof of Quantum Bit Commitment
• Causal structures and the classification of higher order quantum computations
• A channel-based framework for steering, non-locality and beyond
• Unitary channel discrimination beyond group structures: Advantages of sequential and indefinite-causal-order strategies
• Quantum Private Information Retrieval has linear communication complexity
• Policies for elementary links in a quantum network
• Causal Boxes: Quantum Information-Processing Systems Closed under Composition
• Resource theories of multi-time processes: A window into quantum non-Markovianity
• Causally nonseparable processes admitting a causal model
• Deterministic transformations between unitary operations: Exponential advantage with adaptive quantum circuits and the power of indefinite causality
• Causation does not explain contextuality
• Optimal networks for Quantum Metrology: semidefinite programs and product rules
• Can quantum mechanics help distributed computing?
• Causal order as a resource for quantum communication
• Process tomography for unitary quantum channels
• Jordan products of quantum channels and their compatibility
• Base norms and discrimination of generalized quantum channels
• A device-independent protocol for XOR oblivious transfer
• Simple and maximally robust processes with no classical common-cause or direct-cause explanation
• Higher-order Process Matrix Tomography of a passively-stable Quantum SWITCH
• Monotones in General Resource Theories
• Conditional Quantum Walk and Iterated Quantum Games
• Consequences of preserving reversibility in quantum superchannels
• Conditions for optimal input states for discrimination of quantum channels
• Characterising the Hierarchy of Multi-time Quantum Processes with Classical Memory
• Parallel approximation of min-max problems
• A prototype of quantum von Neumann architecture
• A search for quantum coin-flipping protocols using optimization techniques
• Fully-Optimized Quantum Metrology: Framework, Tools, and Applications
• Quantum game theory and the complexity of approximating quantum Nash equilibria
• A competitive game whose maximal Nash-equilibrium payoff requires quantum resources for its achievement
• Existence of processes violating causal inequalities on time-delocalised subsystems
• Entanglement-breaking superchannels
• Quantum metrology in the finite-sample regime
• Different instances of time as different quantum modes: quantum states across space-time for continuous variables
• Memory Effects in Quantum Processes
• The resource theory of nonclassicality of channel assemblages
• Towards a general framework of Randomized Benchmarking incorporating non-Markovian Noise
• Generalized quantum process discrimination problems
• Universal construction of decoders from encoding black boxes
• Simple upper and lower bounds on the ultimate success probability for discriminating arbitrary finite-dimensional quantum processes
• Towards Quantum One-Time Memories from Stateless Hardware
• Quantum Information Processing and Composite Quantum Fields
• Composable and Finite Computational Security of Quantum Message Transmission
• The spatiotemporal doubled density operator: a unified framework for analyzing spatial and temporal quantum processes
• Extremality conditions for generalized channels
• A survey of universal quantum von Neumann architecture
• Idler-Free Multi-Channel Discrimination via Multipartite Probe States
• Quantum circuit simulation of superchannels
• Causal influence in operational probabilistic theories
• Probabilistic unitary synthesis with optimal accuracy
• Learning in Quantum Common-Interest Games and the Separability Problem
• The Min-Entropy of Classical-Quantum Combs for Measurement-Based Applications
• Efficient tensor networks for control-enhanced quantum metrology
• No-Regret Learning and Equilibrium Computation in Quantum Games
• Multi-time quantum process tomography on a superconducting qubit
• On the convex structure of process POVMs
• A de Finetti theorem for quantum causal structures
• Characterising transformations between quantum objects, 'completeness' of quantum properties, and transformations without a fixed causal order
• Breaking barriers in two-party quantum cryptography via stochastic semidefinite programming
• On the composable security of weak coin flipping
• Time-reversal of rank-one quantum strategy functions
• Online learning of a panoply of quantum objects
• A Quadratic Speedup in Finding Nash Equilibria of Quantum Zero-Sum Games