Skip to content

Add constrained extended nonlocal games support for SDP upper bounds and reproduce constrained BB84 #1519

@vprusso

Description

@vprusso

toqito.nonlocal_games.ExtendedNonlocalGame already handles standard extended nonlocal games, but it does not yet have a way to represent the constrained variant studied in Escolà-Farràs and Speelman, Lossy-and-Constrained Extended Non-Local Games with Applications to Quantum Cryptography (arXiv:2405.13717).

I do not want this issue to turn into "implement the whole paper." The target here is much narrower:

  • add support for linear constraints on answer events in the SDP upper-bound routine for extended nonlocal games;
  • use that support to reproduce the constrained BB84 monogamy-of-entanglement example from the paper.

Relevant code:

What should be added:

  • a way to specify linear constraints on answer-event probabilities for an ExtendedNonlocalGame;
  • support for those constraints in the SDP upper-bound path;
  • at least one helper or test fixture for the constrained BB84 game from the paper;
  • regression tests covering the constrained BB84 case.

Suggested scope:

  • it is fine to limit this to the upper-bound SDP path for now;
  • it is fine if the initial interface is fairly simple, as long as it is documented and testable;
  • do not try to solve the full lossy case in this issue.

Acceptance criteria:

  • existing extended nonlocal game tests continue to pass;
  • the new constrained BB84 tests pass;
  • the implementation reproduces the expected unconstrained BB84 value as a sanity check;
  • the PR explains clearly how the paper’s constraints were translated into the toqito SDP formulation.

Out of scope:

  • full lossy-and-constrained game support;
  • reproducing every application from the paper;
  • refactoring unrelated nonlocal game code.

A good PR for this issue should include a short note pointing to the part of the paper being implemented and explaining the mapping from the paper’s notation to the variables used in toqito.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions