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. 1. Generate a loop by random walking on the support graph. 2. If the cycle is “good” (according to provided predicates), continue, else go to 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 precision 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 definition from [1] and the limited FL problem definition from [2]

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