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:
Generate a loop by random walking on the specified graph,
graph
.If the cycle meets provided predicates, continue; if not, return to step 1.
Choose one edge of the loop to be anti-ferromagnetic (an interaction value of +1 for the edge) and all others ferromagnetic (-1).
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