About the author:
Daniel is CTO at rhome GmbH, and Co-Founder at Aqarios GmbH. He holds a M.Sc. in Computer Science from LMU Munich, and has published papers in reinforcement learning and quantum computing. He writes about technical topics in quantum computing and startups.
jrnl · home about list ventures publications LinkedIn Join my Slack

# Isoenergetic Cluster Move explained

Check out the Quantum-Assisted Genetic Algorithm (QAGA). This is a genetic algorithm for solving the QUBO problem, but it uses a quantum computer for recombination and for mutation. Thus, this is a hybrid algorithm. When I first saw this paper and the algorithm, I did not understand the isoenergetic cluster move - the input of the algorithm is a QUBO, and the output is a solution vector. The individuals in the genetic algorithm are also solution vectors. So how could it then be that recombination (and specifically, the isoenergetic cluster move) worked on 2-dimensional data?

*Figure from the QAGA paper linked above.

The way it works now is as follows.

  1. First, pick two potential solution vectors.
  2. Save the XOR difference between those two vectors.
  3. Interpret the QUBO as a graph, and remove the nodes in which values of both vectors are equal. This results in a reduced graph.
  4. Pick a random node from the reduced graph, and compute its cluster (connected components to that node).
  5. The corresponding indices in both solution vectors are now flipped based on the nodes in that cluster.

With this, it is possible to use the isoenergetic cluster move as a recombination operator in a genetic algorithm, such as QAGA. Note that as the mutation operator, reverse annealing is used.

Published on