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