toqito.nonlocal_games.binary_constraint_system_game

Two-player binary constraint system (BCS) game.

Module Contents

toqito.nonlocal_games.binary_constraint_system_game.create_bcs_constraints(M, b)[source]

Construct a list of constraints in tensor form for a binary constraint system (BCS) game.

This function builds a list of constraints by converting each row of the binary matrix M of shape (m, n) and the corresponding element of the binary vector b into an n-dimensional tensor of shape (2, 2, …, 2) (one axis per variable).

The conversion works as follows:

  1. For the i-th constraint, compute the constant value as rhs = (-1)**(b[i]).

  2. Create an n-dimensional array (tensor) of shape (2,)*n filled with -rhs.

  3. Compute the index from the first n entries of the i-th row of M by taking each value modulo 2.

  4. Set the tensor element at that index to rhs.

For example: If M[i] = [1, 1] and b[i] = 0 (so rhs = 1): The tensor is of shape (2, 2) and is created as:

np.array([[-1, -1], [-1, -1]]

The index is computed as (1 % 2, 1 % 2) = (1, 1). At position (1, 1), the value is set to 1, resulting in:

np.array([[-1, -1], [-1, 1]]

This tensor now represents the constraint in full detail.

Parameters:

  • M (numpy.ndarray) – A 2D binary NumPy array of shape (m, n). Each row represents a constraint on n variables.

  • b (numpy.ndarray) – A 1D binary array of length m. Each entry defines the sign of the constraint.

Returns:

A list of NumPy arrays, each of shape (2,)*n. Each tensor represents one constraint in tensor form.

Return type:

list[numpy.ndarray]

Examples

```python exec=”1” source=”above” import numpy as np from toqito.nonlocal_games.binary_constraint_system_game import create_bcs_constraints

M = np.array([[1, 1], [1, 1]], dtype=int) b = np.array([0, 1], dtype=int) constraints = create_bcs_constraints(M, b) print(constraints[0].shape) ```

toqito.nonlocal_games.binary_constraint_system_game.generate_solution_group(M, b)[source]

Generate a bitmask representation for a binary constraint system (BCS) game.

This function converts each row of the binary matrix M into an integer bitmask, pairing it with the corresponding parity from b. The bitmask representation can be useful for analyzing linear system games.

Notes The method used to determine the existence of a perfect commuting strategy was originally introduced in [@Cleve_2016_Perfect].

Examples

```python exec=”1” source=”above” import numpy as np from toqito.nonlocal_games.binary_constraint_system_game import generate_solution_group

M = np.array([[1, 1, 0], [0, 1, 1]]) b = np.array([0, 1]) row_masks, parity = generate_solution_group(M, b) print(row_masks) # Output: [3, 6] print(parity) # Output: [0, 1] ```

Parameters:

  • M (numpy.ndarray) – A binary matrix of shape (m, n).Each row encodes which variables appear in a constraint.

  • b (numpy.ndarray) – A binary vector of length m.Each entry determines the parity for its corresponding constraint row.

Returns:

A list of integer bitmasks. A list of parity values.

Return type:

tuple[list[int], list[int]]

toqito.nonlocal_games.binary_constraint_system_game.check_perfect_commuting_strategy(M, b)[source]

Determine whether a perfect commuting-operator strategy exists for a BCS game.

This function checks if the binary constraint system defined by Mx = b admits a perfect commuting-operator strategy. It converts the constraints to bitmask form, performs Gaussian elimination over (mathrm{GF}(2)), and examines the resulting constraint graph for cycles that indicate a nontrivial solution.

Parameters:

  • M (numpy.ndarray) – A binary matrix representing a system of parity constraints.

  • b (numpy.ndarray) – A binary vector representing the right-hand side of the constraint equations.

Returns:

True if a perfect commuting-operator strategy exists; otherwise, False.

Return type:

bool

Examples

```python exec=”1” source=”above” import numpy as np from toqito.nonlocal_games.binary_constraint_system_game import check_perfect_commuting_strategy

M = np.array([[1, 1], [1, 1]]) b = np.array([0, 1]) print(check_perfect_commuting_strategy(M, b)) ```