Alternating Sectors Chain

class qubovert.problems.AlternatingSectorsChain(*args, **kwargs)

AlternatingSectorsChain.

Class to manage converting Alternating Sectors Chain to and from its QUBO and QUSO formluations.

The Alternating Sectors Chain problem has a solution for which all the boolean variables or spins are equal. It is a trivial problem, but useful for benchmarking some solvers or solving techniques.

AlternatingSectorsChain inherits some methods and attributes from the Problem class. See help(qubovert.problems.Problem).

Example

>>> from qubovert.problems import AlternatingSectorsChain
>>> from any_module import qubo_solver
>>> # or you can use my bruteforce solver...
>>> # from qubovert.utils import solve_qubo_bruteforce as qubo_solver
>>> problem = AlternatingSectorsChain(10)
>>> Q  = problem.to_qubo()
>>> obj, sol = qubo_solver(Q)
>>> solution = problem.convert_solution(sol)
>>> print(solution)
(0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
# or (1, 1, 1, 1, 1, 1, 1, 1, 1, 1)
>>> print(problem.is_solution_valid(solution))
True  # since they are all the same.

__init__.

The Alternating Sectors Chain problem has a solution for which all the boolean variables or spins are equal. It is a trivial problem, but useful for benchmarking some solvers or solving techniques.

Parameters
  • num_binary_variables (int > 0.) – Number of variables in the problem.

  • chain_length (int > 1 (optional, defaults to 3)) – The length of a chain of couples.

  • min_strength (int > 0 (optional, defaults to 1)) – The strength of the couples for the minimium chain.

  • max_strength (int > 0 (optional, defaults to 10)) – The strength of the couples for the maximum chain.

Examples

>>> args = n, l, min_s, max_s = 6, 3, 1, 5
>>> problem = AlternatingSectorsChain(*args)
>>> h, J, offset = problem.to_quso(pbc=True)
>>> h
{}
>>> offset
0
>>> J
{(0, 1): 5, (1, 2): 5, (2, 3): 5, (3, 4): 1, (4, 5): 1, (5, 0): 1}
convert_solution(solution, spin=False)

convert_solution.

Convert the solution to the QUBO or QUSO to the solution to the Alternating Sectors Chain problem.

Parameters
  • solution (iterable or dict.) – The QUBO or QUSO solution output. The QUBO solution output is either a list or tuple where indices specify the label of the variable and the element specifies whether it’s 0 or 1 for QUBO (or 1 or -1 for QUSO), or it can be a dictionary that maps the label of the variable to is value.

  • spin (bool (optional, defaults to False)) – spin indicates whether solution is the solution to the boolean {0, 1} formulation of the problem or the spin {1, -1} formulation of the problem. This parameter usually does not matter, and it will be ignored if possible. The only time it is used is if solution contains all 1’s. In this case, it is unclear whether solution came from a spin or boolean formulation of the problem, and we will figure it out based on the spin parameter.

Returns

res – Value of each spin, -1 or 1.

Return type

tuple.

Examples

>>> problem = AlternatingSectorsChain(5)
>>> problem.convert_solution([0, 0, 1, 0, 1])
(1, 1, -1, 1, -1)
>>> problem.convert_solution([-1, -1, 1, -1, 1])
(-1, -1, 1, -1, 1)
is_solution_valid(solution, spin=False)

is_solution_valid.

Returns whether or not the proposed solution is the correct solution, ie that all the variables are equal.

Parameters
  • solution (iterable or dict.) – solution can be the output of AlternatingSectorsChain.convert_solution, or the QUBO or QUSO solver output. The QUBO solution output is either a list or tuple where indices specify the label of the variable and the element specifies whether it’s 0 or 1 for QUBO (or 1 or -1 for QUSO), or it can be a dictionary that maps the label of the variable to is value.

  • spin (bool (optional, defaults to False)) – spin indicates whether solution is the solution to the boolean {0, 1} formulation of the problem or the spin {1, -1} formulation of the problem. This parameter usually does not matter, and it will be ignored if possible. The only time it is used is if solution contains all 1’s. In this case, it is unclear whether solution came from a spin or boolean formulation of the problem, and we will figure it out based on the spin parameter.

Returns

valid – True if the proposed solution is valid, else False.

Return type

boolean.

property num_binary_variables

num_binary_variables.

The number of binary variables that the QUBO and QUSO use.

Returns

num – The number of variables in the QUBO/QUSO formulation.

Return type

integer.

solve_bruteforce(*args, **kwargs)

solve_bruteforce.

Solve the problem bruteforce. THIS SHOULD NOT BE USED FOR LARGE PROBLEMS! This is implemented in the parent qubovert.utils.Problem class. Some problems use a lot of slack binary variables for their QUBO/QUSO formulations. If this is the case, then the child class for this problem should override this method with a better bruteforce solver. But, for problems that do not use slack variables, this method will suffice. It converts the problem to QUBO, solves it with qubovert.utils.solve_qubo_bruteforce, and then calls and returns convert_solution.

Parameters

aruments (arguments and keyword arguments.) – Contains args and kwargs for the to_qubo method. Also contains a all_solutions boolean flag, which indicates whether or not to return all the solutions, or just the best one found. all_solutions defaults to False.

Returns

res – If all_solutions is False, then res is just the output of the convert_solution method. If all_solutions is True, then res is a list of outputs of the convert_solution method, e.g. a converted solution for each solution that the bruteforce solver returns.

Return type

the output or outputs of the convert_solution method.

to_pubo(*args, **kwargs)

to_pubo.

Since the model is already degree two, self.to_pubo will simply return qubovert.utils.PUBOMatrix(self.to_qubo(*args, **kwargs)).

Returns

P – The upper triangular PUBO matrix, a PUBOMatrix object. For most practical purposes, you can use PUBOMatrix in the same way as an ordinary dictionary. For more information, see help(qubovert.utils.PUBOMatrix).

Return type

qubovert.utils.PUBOMatrix object.

to_puso(*args, **kwargs)

to_puso.

Create and return PUSO model representing the problem. Should be implemented in child classes. If this method is not implemented in the child class, then it simply calls to_pubo or to_quso and converts to a PUSO formulation.

Parameters

arguments (Defined in the child class.) – They should be parameters that define lagrange multipliers or factors in the QUSO model.

Returns

H – For most practical purposes, you can use PUSOMatrix in the same way as an ordinary dictionary. For more information, see help(qubovert.utils.PUSOMatrix).

Return type

qubovert.utils.PUSOMatrix object.

Raises
  • RecursionError` if neither to_pubo nor to_puso are define

  • in the subclass.

to_qubo(*args, **kwargs)

to_qubo.

Create and return upper triangular QUBO representing the problem. Should be implemented in child classes. If this method is not implemented in the child class, then it simply calls to_quso and converts the quso formulation to a QUBO formulation.

Parameters

arguments (Defined in the child class.) – They should be parameters that define lagrange multipliers or factors in the QUBO.

Returns

Q – The upper triangular QUBO matrix, a QUBOMatrix object. For most practical purposes, you can use QUBOMatrix in the same way as an ordinary dictionary. For more information, see help(qubovert.utils.QUBOMatrix).

Return type

qubovert.utils.QUBOMatrix object.

Raises
  • RecursionError` if neither to_qubo nor to_quso are define

  • in the subclass.

to_quso(pbc=False)

to_quso.

Create and return the alternating Sectors chain problem in QUSO form The J coupling matrix for the QUSO will be returned as an uppertriangular dictionary. Thus, the problem becomes minimizing \(\sum_{i <= j} z_i z_j J_{ij} + \sum_{i} z_i h_i + offset\).

Parameters

pbc (bool (optional, defaults to False)) – Whether or not to use periodic boundary conditions.

Returns

L – For most practical purposes, you can use QUSOMatrix in the same way as an ordinary dictionary. For more information, see help(qubovert.utils.QUSOMatrix).

Return type

qubovert.utils.QUSOMatrix object.

Example

>>> args = n, l, min_s, max_s = 6, 3, 1, 5
>>> problem = AlternatingSectorsChain(*args)
>>> L = problem.to_quso(pbc=True)
>>> L
{(0, 1): 5, (1, 2): 5, (2, 3): 5, (3, 4): 1, (4, 5): 1, (5, 0): 1}
>>> L = problem.to_quso(pbc=False)
>>> L
{(0, 1): 5, (1, 2): 5, (2, 3): 5, (3, 4): 1, (4, 5): 1}