Quantum Games and Protocols
2014-02-24..2014-02-28
Berkeley, United States
as the organisers put it
This workshop will focus on quantum interactive proofs and entangled quantum games. It will include recent advances in our understanding of the complexity class QMIP of multiple entangled provers, as well as QPIP, quantum polynomial time bounded provers. The workshop will also address quantum PCP from an interactive proof perspective. Enquiries may be sent to the organizers at this address.
who it's for
quantum complexity theorists, quantum cryptographers, quantum information theorists, theoretical computer scientists, experimental quantum optics researchers, postdoctoral researchers
topics
CHSH game rigidity; device-independent randomness certification; delegated blind quantum computation; measurement-based brickwork state; boson sampling verification; quantum PCP obstructions; parallel repetition for entangled games; complexity of entangled provers (QMIP); quantum coin flipping protocols; quantum obfuscation of classical circuits; semidefinite programming hierarchies in quantum information
| title | author | length |
|---|---|---|
| Tests for "Quantumness" | Umesh Vazirani | 42m |
The core is the CHSH game: two noncommunicating devices get random bits and output bits, a classical strategy tops out at 3/4 vs 0.85 (cos^2(pi/8)) while… | ||
| Games to Establish Structure in an Unknown Hilbert Space | Ben W. Reichardt | 48m |
Introduces a concrete, testable claim: playing the CHSH game gives quantum devices a maximum win rate of cos^2(pi/8) ≈ 0.85 and a rigidity statement that… | ||
| Blind and Verifiable Quantum Computation | Joe Fitzsimons | 39m |
Delegation protocol encodes a measurement-based quantum computation on a brickwork state: the client prepares single-qubit rotations (plus random Z flips) and… | ||
| From Photonic Quantum Cloud Computing to Interactive Proofs | Philip Walther | 36m |
Photonic experiments implement a blind, measurement-based delegated computation using an optical cluster state built from spontaneous parametric downconversion… | ||
| Tick-tock Goes the Clock | Daniel Nagaj | 01h 03m |
Claims an improvement of the promise gap in history‑state Hamiltonian constructions from about 1/L^3 to 1/L^2 by analyzing clock spectra; shows the clock… | ||
| Limitations for Quantum PCPs | Fernando Brandao | 58m |
Shows a concrete obstruction to a straightforward quantum PCP: using a quantum de Finetti-type bound (extended beyond permutation symmetry) and monogamy of… | ||
| An Approach To The Sliding Scale Conjecture Via Parallel Repetition For Low Degree Testing | Dana Moshkovitz | 01h 03m |
Proposes repeating the low‑degree (line vs line) test in parallel to turn a base soundness of about 1/|F| into error roughly 1/|F|^k, and proves this by… | ||
| A Survey on the Complexity of Entangled Provers | Zhengfeng Ji | 01h 03m |
Describes how classical multi‑prover PCP-style protocols are rewritten to resist entangled provers, proving completeness and inverse‑polynomial soundness gaps… | ||
| Quantum Proofs of Knowledge | Dominique Unruh | 01h 03m |
Classical sigma-protocol extractors fail against quantum provers because copying and rewinding break on quantum states; security uses Watrous-style quantum… | ||
| How to Encrypt a Functionality | Amit Sahai | 01h 04m |
Claims a concrete candidate for indistinguishability obfuscation built from a new “algebraic jigsaw puzzle” instantiation of approximate multilinear maps… | ||
| Quantum Obfuscation of Classical Circuits | Paul Christiano | 32m |
Proposal maps a classical circuit to a single quantum state that can be used to evaluate the function while (plausibly) leaking no more than black‑box access… | ||
| Delegated Quantum Computation from Sequential Games | Ben W. Reichardt | 39m |
Shows a constructive route to fully delegated quantum computation with a fully classical verifier and two untrusted quantum servers, proving QIP is contained… | ||
| Forcing Trust: Nonlocal Games and Untrusted-device Cryptography | Carl Miller | 49m |
Presents a proof that untrusted, multi-part quantum devices yield more output randomness than the small trusted seed produces, achieving exponential randomness… | ||
| Infinite Randomness Expansion with a Constant Number of Devices | Henry Yuen | 27m |
Claims an unbounded (infinite) certified randomness expansion starting from a constant m‑bit seed (m ~ 100–1000), by alternating a VV exponential-expansion… | ||
| How to Delegate Computations: The Power of No-Signaling Proofs | Ran Raz | 55m |
Gives a concrete one-round delegation protocol that lets a weak verifier check any function f computable in time t: prover runs in poly(t), verifier runs in n… | ||
| Entanglement in Many Body Quantum Systems | David Pérez-García | 01h 08m |
Describes concrete examples and results: the quantum dimer / resonating valence bond construction gives an equal‑weight ground state at the Rokhsar–Kivelson… | ||
| Games and Grothendieck's Tensor Norms | Marius Junge | 01h 07m |
A concrete dictionary maps game values to tensor norms: classical correlations = epsilon norm, quantum correlations = min norm, and quantum XOR values equal a… | ||
| Semidefinite Hierarchies in Quantum Information | Pablo Parrilo | 52m |
Semidefinite hierarchies convert hard nonnegativity and separability checks into tractable sum of squares and SDP feasibility problems by representing… | ||
| Monogamy of Non-signaling Correlations | Aram Harrow | 52m |
Shows that any k‑extendable non‑signaling box has a local hidden‑variable approximation with trace‑distance error O(sqrt((log |A|)/k)), proved by bounding… | ||
| A Short Tour of the Laws of Entanglement (And How to Evade Them) | Patrick Hayden | 47m |
Constructs a family of embezzling states with Schmidt coefficients ~1/√j (normalization ~log n) that let two separated parties convert a product target into an… | ||
| Direct Products and Parallel Repetition | Irit Dveer Dinur | 01h 08m |
Proves an exponential parallel-repetition bound for projection games with entanglement: if the entangled value is 1 − ε then the k-fold repeated entangled… | ||
| Parallel Repetition of Entangled Games with Exponential Decay via the Superposed Information Cost | André Chailloux | 33m |
Shows that for games with independent uniform questions, if one-shot entangled value equals 1 − ε then the n-fold entangled value falls exponentially with n… | ||
| A Parallel Repetition Theorem for Entangled Two-player One-round Games Under Product Distributions | Attila Pereszlényi | 29m |
For entangled two-player one-round games with a product input distribution the k-fold parallel repetition lowers the maximum winning probability exponentially… | ||
| Quantum Weak Coin Flipping with Arbitrarily Small Bias | Iordanis Kerenidis | 01h 05m |
Claim: quantum weak coin flipping can reach arbitrarily small bias (ε → 0). Proof uses Kitaev SDP duality, rewrites cheating bounds as point games built from… | ||
| Quantum Cryptography: From Theory to Practice | Eleni Diamanti | 35m |
Describes turning theory into experiments: adapts QKD hardware (lasers, fibers, single-photon detectors) to implement a loss-tolerant coin flipping protocol… | ||
| Quantum and Classical Coin-flipping Protocols Based on Bit-commitment and their Point Games | Jamie Sikora | 34m |
Defines a restricted family of coin‑flipping protocols by four probability vectors and shows the cheating SDPs collapse to an LP‑like polytope, enabling… | ||
| A Tensor Network View of Kitaev's Lower Bound for Strong Coin Flipping | Zeph Landau | 29m |
Recasts Kitaev’s lower bound for strong coin flipping as a tensor‑network duality game, showing Alice’s and Bob’s strategy sets become convex cones of positive… | ||
| Verification of BosonSampling Devices | Scott Aaronson | 58m |
BosonSampling uses N identical photons through an M‑mode linear optical network so output probabilities equal the permanent of N×N submatrix amplitudes, giving… | ||
| nothing matches | ||