Recursive QAOA functions

A set of utility functions for RQAOA

openqaoa.algorithms.rqaoa.rqaoa_utils.ada_max_terms(exp_vals_z, corr_matrix, n_max)[source]

Extracts the n_max+1 expectation values (single spin and correlation) with highest magnitude, computes the average among them and selects the ones above average for elimination. The maximum number of potential candidates is n_max.

Parameters:

  • exp_vals_z (np.array) – Single spin expectation values.

  • corr_matrix (np.array) – Correlation matrix.

  • n_max (np.array) – Maximum number of potential candidates for elimination.

Returns:

max_terms_and_stats – Dictionary containing terms to be eliminated and their expectation values.

Return type:

dict

openqaoa.algorithms.rqaoa.rqaoa_utils.final_solution(elimination_tracker, cl_states, hamiltonian)[source]

Constructs the final solution to the problem by obtaining the final states from adding the removed spins into the classical results and computing the corresponding energy.

Parameters:

  • elimination_tracker (list) – List of dictionaries, where each dictionary contains the elimination rules applied at each step of the process. Dictionary keys correspond to spin pairs (i,j), always with i<j to ensure proper reconstruction of the state, where spin j was eliminated in favor of i. The values of each pair correspond to the correlation sign between spins i and j. For fixed spins, in the pair (i,j), i is None, and the dictionary value corresponds to the fixed state of j.

  • cl_states (list) – Set of states as solutions in

  • hamiltonian (Hamiltonian) – Hamiltonian object containing the original problem statement.

Returns:

full_solution – Dictionary containing the solution states of the problem and their respective energies.

Return type:

dict

openqaoa.algorithms.rqaoa.rqaoa_utils.find_parent(spin_map, spin, factor=1)[source]

Finds parent spin recursively following the chain of dependencies in the spin map.

Parameters:

  • spin_map (dict) – Mapping containing all dependencies for eliminated spins.

  • spin (int) – Spin whose parent we want to find.

  • factor (int, optional) – Defaults to 1 to initialize the multiplicative factor.

Returns:

  • parent_spin (int) – Parent spin.

  • factor (int) – Cumulative factor connecting the input spin with its parent spin.

openqaoa.algorithms.rqaoa.rqaoa_utils.max_terms(exp_vals_z, corr_matrix, n_elim)[source]

Extracts the n_elim expectation values (single spin and correlation) with highest magnitude, and uses them to impose the elimination constraint on the spins.

Parameters:

  • exp_vals_z (np.array) – Single spin expectation values.

  • corr_matrix (np.array) – Correlation matrix.

  • n_elim (int) – Number of spins to eliminate.

Returns:

max_terms_and_stats – Dictionary containing terms to be eliminated and their expectation values.

Return type:

dict

openqaoa.algorithms.rqaoa.rqaoa_utils.problem_from_dict(problem_dict)[source]

Transforms a QUBO problem, input as a dictionary, into a QUBO problem, output as a QUBO object, ensuring proper labelling of the nodes. For example, for a set of nodes [0,1,4,6] with edges [(0,1),(1,4),(4,6),(0,6)], after the relabelling, the Hamiltonian object will be constructed with node labels [0,1,2,3] and edges [(0,1),(1,2),(2,3),(1,3)].

Parameters:

problem_dict (dict) – QUBO problem as a dictionary containing the edges as keys and weights as values.

Returns:

problem – A QUBO problem object constructed using the classical_hamiltonian() method.

Return type:

QUBO

openqaoa.algorithms.rqaoa.rqaoa_utils.redefine_problem(problem, spin_map)[source]

Returns the QUBO object of the reduced problem. Using the spin map, we construct a dictionary containing the new set of edges and weights defining the new problem.

Parameters:

  • hamiltonian (Hamiltonian) – Hamiltonian object containing the problem statement.

  • spin_map (dict) – Dictionary containing the spin dependencies.

Returns:

  • new_problem (QUBO) – QUBO object containing the reduced problem statement after spin eliminations.

  • spin_map (dict) – Updated spin_map with sponatenous eliminations from cancellations during spin removal process.

openqaoa.algorithms.rqaoa.rqaoa_utils.solution_for_vanishing_instances(hamiltonian, spin_map)[source]

Constructs the final solution of the smallest non vanishing problem by fixing the vanishing spins arbitrarily to 1 while obeying the correlations identified by the last run of QAOA before the problem vanished. Computing the classical energy of the generated string.

Parameters:

  • spin_map (dict) – Spin map containing the correlations and eliminations of the smallest non-vanishing problem statement.

  • hamiltonian (Hamiltonian) – Hamiltonian object containing the smallest non vanishing problem statement.

Returns:

  • cl_energy (float) – The energy of the solution wrt the cost Hamiltonian.

  • cl_ground_state (list) – The (single) classical solution to the problem reconstructed accordingly to the last spin map. Represented as a binary string and then cast to a list to match the output of the ground_state_hamiltonian function which is used usually.

openqaoa.algorithms.rqaoa.rqaoa_utils.spin_mapping(problem, max_terms_and_stats)[source]

Generates a map between spins in the original problem graph and in the reduced graph. Elimination constraints from correlations define a constrained spin, to be removed, and a parent spin, to be kept. Parent spins determine the state of multiple spins by a chain of dependencies between spins due to the different constraints. Note that there is always a parent spin and only one. If cycles are present, less edges will be eliminated to satisfy this requirement. Constraints following from biases result in fixing spins to a specific value. In this case, the parent spin is set to None. Spins in the map that are not eliminated are mapped to themselves.

Parameters:

  • problem (QUBO) – QUBO problem object containing the problem statement.

  • max_terms_and_stats (dict) – Dictionary containing the terms to be eliminated and their expectation values.

Returns:

spin_map – Dictionary containing all the mapping dependencies. The keys correspond to the original spins. The values are tuple pairs, containing the parent spin and the factor relating both. The structure is: { old_spin : (factor, new_spin) }.

Return type:

dict