dimod.generators.frustrated_loop

frustrated_loop(graph, num_cycles, R=inf, cycle_predicates=(), max_failed_cycles=100, planted_solution=None, seed=None)[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 support 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; all other edges are ferromagnetic.

  4. Add the loop’s coupler values to the FL problem. If at any time the magnitude of a coupler in the FL problem exceeds a given recision R, remove that coupler from consideration in the loop generation procedure.

This is a generic generator of FL problems that encompasses both the original FL problem definition1 and the limited FL problem definition2.

Parameters

  • graph (int/tuple[nodes, edges]/list[edge]/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 (int) – Desired number of frustrated cycles.

  • R (int, optional, default=inf) – Maximum interaction weight.

  • cycle_predicates (tuple[function], optional) – An iterable of functions, which should accept a cycle and return a bool.

  • max_failed_cycles (int, optional, default=100) – Maximum number of failures to find a cycle before terminating.

  • planted_solution (dict, optional, default=None) – 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 (int, optional, default=None) – 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