dimod.generators.frustrated_loop

frustrated_loop(graph: Union[int, Tuple[Collection[Hashable], Collection[Tuple[Hashable, Hashable]]], Collection[Tuple[Hashable, Hashable]], networkx.classes.graph.Graph], num_cycles: int, R: float = inf, cycle_predicates: Collection[Callable[[List[Hashable]], bool]] = (), max_failed_cycles: int = 100, plant_solution: bool = True, planted_solution: Optional[Mapping[Hashable, int]] = None, seed: Optional[int] = None) → dimod.binary.binary_quadratic_model.BinaryQuadraticModel[source]

Generate a frustrated-loop problem.

A generic frustrated-loop (FL) problem is a sum of Hamiltonians, each generated from a single loop, as follows:

  1. Generate a loop by random walking on the specified graph, graph.

  2. If the cycle meets provided predicates, continue; if not, return to step 1.

  3. Choose one edge of the loop uniformly at random to be anti-ferromagnetic (AFM, coupling value of 1) and all others ferromagnetic (-1). Or if plant_solution is False, sample uniformly couplers subject to the constraint that there are an odd number of AFM couplers.

  4. Add the loop’s interactions to the FL problem. If at any time the absolute value of an interaction in the FL problem, accumulated on an edge over good loops, exceeds a given maximum, R, remove that edge from consideration in the loop generation procedure.

This is a generic generator of FL problems that encompasses both the original FL problem definition 1 and the limited FL problem definition 2.

Parameters

  • graph – The graph to build the frustrated loops on. Either an integer, n, interpreted as a complete graph of size n, a nodes/edges pair, a list of edges, or a NetworkX graph.

  • num_cyles – Desired number of frustrated cycles.

  • R – Maximum absolute interaction weight an edge can accumulate from good cycles.

  • cycle_predicates – An iterable of functions, which should accept a cycle and return a bool.

  • max_failed_cycles – Maximum number of failures to find a cycle before terminating.

  • plant_solution – Select frustrated loops with only 1 AFM coupler all 1 (and all -1) solutions are among the ground states.

  • planted_solution – A dictionary assigning variables to spin states. When provided, and planted_solution=True spin states are relabeled so that the variable assignment becomes a planted ground state in place of the all 1 solution. This option is deprecated; use of spin-reversal transforms is recommended for this purpose.

  • seed – Random seed.

1

Hen, I., J. Job, T. Albash, T.F. Rønnow, M. Troyer, D. Lidar. Probing for quantum speedup in spin glass problems with planted solutions. https://arxiv.org/abs/1502.01663v2

2

King, A.D., T. Lanting, R. Harris. Performance of a quantum annealer on range-limited constraint satisfaction problems. https://arxiv.org/abs/1502.02098