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, 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 “good” 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 to be anti-ferromagnetic (an interaction value of +1 for the edge) and all others ferromagnetic (-1).

  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.

  • planted_solution – Other solutions with the same energy may exist, but the energy value of the (possibly degenerate) ground state will hold. If None, planted_solution is: {v: -1 for v in graph}

  • 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