In [1]:
# Import required libraries for QAOA and quantum computing
from enum import Enum
import matplotlib.pyplot as plt
import numpy as np
from qiskit import QuantumCircuit, transpile
from qiskit_aer import AerSimulator
class QAOANavigator:
"""Class for maze navigation using QAOA
(Quantum Approximate Optimization Algorithm).
QAOA is used to find optimal path from start
to target with minimization of cycling penalties.
"""
def __init__(self, maze, start, target, radius=2, p_layers=3):
"""Initialize navigator with maze and parameters."""
self.maze = maze
self.height, self.width = maze.shape
self.start = start
self.target = target
self.radius = radius
self.p_layers = p_layers # QAOA layers
self.current_pos = start
self.path = [start]
self.visited = {start}
self.position_visit_count = {start: 1}
self.step_count = 0
self.max_steps = 300
self.qaoa_calls = []
self.betas = np.linspace(0, 1,
p_layers)[::-1] # [1.0, 0.5, 0.0] for p=3
self.gammas = np.linspace(0, 1, p_layers) # [0.0, 0.5, 1.0] for p=3
# === Helper methods for geometry and distances ===
def _manhattan_distance(self, pos1, pos2):
"""Calculate Manhattan distance between two positions."""
return abs(pos1[0] - pos2[0]) + abs(pos1[1] - pos2[1])
def _compute_reachability_matrix(self, center_pos):
"""Create reachability matrix for positions
in 5x5 neighborhood relative to current position.
Checks if there exists a path without walls to individual positions."""
cy, cx = center_pos
grid = np.zeros((5, 5), dtype=float)
for i in range(5):
for j in range(5):
my = cy - 2 + i
mx = cx - 2 + j
if 0 <= my < self.maze.shape[0] and 0 <= mx < self.maze.shape[1]:
grid[i, j] = 1.0 if self.maze[my, mx] == 0 else 0.0
else:
grid[i, j] = 0.0
"""
Covariance matrix:
A B C D E
1 A2xA1+B1xA1 C1xB1+B2xB1 C2xC1 D2xD1+C1xD1 D1xE1+E2xE1
2 A3xA2+B2xA2 B3xB2+C2xB2 C2 C2xD2+D3xD2 D2xE2+E3xE2
3 B3xA3 B3 start D3 D3xE3
4 A3xA4+B4xA4 B3xB4+C4xB4 C4 D3xD4+C4xD4 E3xE4+D4xE4
5 A4xA5+B5xA5 B4xB5+C5xB5 C4xC5 C5xD5+D4xD5 E4xE5+D5xE5
"""
# Calculate reachability of individual positions from center (C3)
reach = np.zeros((5, 5), dtype=float)
reach[2, 2] = 1.0 # Start (C3)
reachC2 = grid[1, 2]
reachB3 = grid[2, 1]
reachD3 = grid[2, 3]
reachC4 = grid[3, 2]
reachB2 = reachB3 * grid[1, 1] + reachC2 * grid[1, 1]
reachD2 = reachC2 * grid[1, 3] + reachD3 * grid[1, 3]
reachB4 = reachB3 * grid[3, 1] + reachC4 * grid[3, 1]
reachD4 = reachD3 * grid[3, 3] + reachC4 * grid[3, 3]
reachC1 = reachC2 * grid[0, 2]
reachA3 = reachB3 * grid[2, 0]
reachE3 = reachD3 * grid[2, 4]
reachC5 = reachC4 * grid[4, 2]
reachB1 = reachC1 * grid[0, 1] + reachB2 * grid[0, 1]
reachD1 = reachD2 * grid[0, 3] + reachC1 * grid[0, 3]
reachA2 = reachA3 * grid[1, 0] + reachB2 * grid[1, 0]
reachE2 = reachD2 * grid[1, 4] + reachE3 * grid[1, 4]
reachA4 = reachA3 * grid[3, 0] + reachB4 * grid[3, 0]
reachE4 = reachE3 * grid[3, 4] + reachD4 * grid[3, 4]
reachB5 = reachB4 * grid[4, 1] + reachC5 * grid[4, 1]
reachD5 = reachC5 * grid[4, 3] + reachD4 * grid[4, 3]
reachA1 = reachA2 * grid[0, 0] + reachB1 * grid[0, 0]
reachE1 = reachD1 * grid[0, 4] + reachE2 * grid[0, 4]
reachA5 = reachA4 * grid[4, 0] + reachB5 * grid[4, 0]
reachE5 = reachE4 * grid[4, 4] + reachD5 * grid[4, 4]
reach[0, 0] = reachA1
reach[0, 1] = reachB1
reach[0, 2] = reachC1
reach[0, 3] = reachD1
reach[0, 4] = reachE1
reach[1, 0] = reachA2
reach[1, 1] = reachB2
reach[1, 2] = reachC2
reach[1, 3] = reachD2
reach[1, 4] = reachE2
reach[2, 0] = reachA3
reach[2, 1] = reachB3
reach[2, 2] = 1.0 # start
reach[2, 3] = reachD3
reach[2, 4] = reachE3
reach[3, 0] = reachA4
reach[3, 1] = reachB4
reach[3, 2] = reachC4
reach[3, 3] = reachD4
reach[3, 4] = reachE4
reach[4, 0] = reachA5
reach[4, 1] = reachB5
reach[4, 2] = reachC5
reach[4, 3] = reachD5
reach[4, 4] = reachE5
return reach
# === Obstacle detection and movement validation ===
def _check_wall_between(self, pos1, pos2):
"""
Check if there is a wall between two positions.
Detects obstacles in straight line
and in corners during diagonal movement.
"""
y0, x0 = pos1
y1, x1 = pos2
dy = abs(y1 - y0)
dx = abs(x1 - x0)
is_pure_diagonal = dy > 0 and dx > 0 and dy == dx
corners = set()
if is_pure_diagonal:
corner1 = (y0, x1)
corner2 = (y1, x0)
corners = {corner1, corner2}
corner1_free = False
if (0 <= corner1[0] < self.maze.shape[0] and
0 <= corner1[1] < self.maze.shape[1]):
corner1_free = self.maze[corner1] == 0
corner2_free = False
if (0 <= corner2[0] < self.maze.shape[0] and
0 <= corner2[1] < self.maze.shape[1]):
corner2_free = self.maze[corner2] == 0
if not corner1_free and not corner2_free:
return True
min_y = min(y0, y1)
max_y = max(y0, y1)
min_x = min(x0, x1)
max_x = max(x0, x1)
for y in range(min_y, max_y + 1):
for x in range(min_x, max_x + 1):
if (y, x) == pos1 or (y, x) == pos2:
continue
if is_pure_diagonal and (y, x) in corners:
continue
if 0 <= y < self.maze.shape[0] and 0 <= x < self.maze.shape[1]:
if self.maze[y, x] == 1:
return True
return False
def _get_neighbors(self, pos=None):
"""
Get list of valid neighboring positions within given radius.
Returns only positions without walls and checks target reachability.
"""
if pos is None:
pos = self.current_pos
neighbors = []
target_checked = False
target_blocked = False
for dr in range(-self.radius, self.radius + 1):
for dc in range(-self.radius, self.radius + 1):
if dr == 0 and dc == 0:
continue
abs_dr = abs(dr)
abs_dc = abs(dc)
if abs_dr > 0 and abs_dc > 0 and abs_dr == abs_dc:
continue
new_pos = (pos[0] + dr, pos[1] + dc)
if not (0 <= new_pos[0] < self.maze.shape[0] and
0 <= new_pos[1] < self.maze.shape[1]):
continue
if self.maze[new_pos] == 1:
continue
if new_pos == self.target:
target_checked = True
if self._check_wall_between(pos, new_pos):
target_blocked = True
if self.step_count % 20 == 0:
print(f" DEBUG: Target {self.target} wall {pos}")
continue
else:
if self.step_count % 20 == 0:
print(f" DEBUG: Target {self.target} free {pos}")
neighbors.append(new_pos)
return neighbors
def _count_walls_around(self, pos):
"""
Count number of walls in immediate vicinity of position (8 neighbors).
"""
wall_count = 0
y, x = pos
for dy in [-1, 0, 1]:
for dx in [-1, 0, 1]:
if dy == 0 and dx == 0:
continue
ny, nx = y + dy, x + dx
if not (0 <= ny < self.maze.shape[0] and
0 <= nx < self.maze.shape[1]):
wall_count += 1
continue
if self.maze[ny, nx] == 1:
wall_count += 1
return wall_count
def _count_open_space(self, pos):
"""
Count number of free positions in 5x5 neighborhood.
"""
open_count = 0
y, x = pos
for dy in range(-2, 3):
for dx in range(-2, 3):
if dy == 0 and dx == 0:
continue
ny, nx = y + dy, x + dx
if not (0 <= ny < self.maze.shape[0] and
0 <= nx < self.maze.shape[1]):
continue
if self.maze[ny, nx] == 0:
open_count += 1
return open_count
# === Cost function and penalties ===
def _compute_single_cost(self, pos, near_target=False):
"""
Calculate cost function for single position.
Includes penalties for repeated visits,
cycling, and bonuses for moving toward target.
Exponential penalties strongly discourage revisiting same positions.
"""
max_dist = max(1, self._manhattan_distance(self.start, self.target))
dist = self._manhattan_distance(pos, self.target)
h = dist / max_dist
if pos == self.target:
return -1000.0
target_dy = self.target[0] - self.current_pos[0]
target_dx = self.target[1] - self.current_pos[1]
move_dy = pos[0] - self.current_pos[0]
move_dx = pos[1] - self.current_pos[1]
dir_bonus = 7.0 if near_target else 5.0
dir_penalty = 7.0 if near_target else 5.0
if target_dy != 0:
if (target_dy > 0 and move_dy > 0) or (target_dy < 0 and
move_dy < 0):
h -= dir_bonus
elif (target_dy > 0 and move_dy < 0) or (target_dy < 0 and
move_dy > 0):
h += dir_penalty
if target_dx != 0:
if (target_dx > 0 and move_dx > 0) or (target_dx < 0 and
move_dx < 0):
h -= dir_bonus
elif (target_dx > 0 and move_dx < 0) or (target_dx < 0 and
move_dx > 0):
h += dir_penalty
current_dist = self._manhattan_distance(self.current_pos, self.target)
if dist < current_dist:
h -= 2.5 if near_target else 2.0
elif dist > current_dist:
h += 5.0 if near_target else 3.5
wall_count = self._count_walls_around(pos)
if wall_count >= 3:
wall_penalty = 2.0**(wall_count - 2)
h += wall_penalty
recent_steps = 20
if len(self.path) >= recent_steps:
recent_visits = sum(1 for p in self.path[-recent_steps:]
if self.position_visit_count.get(p, 0) > 1)
stuck_ratio = recent_visits / recent_steps
is_stuck = stuck_ratio > 0.3
else:
is_stuck = False
if pos in self.visited:
visits = self.position_visit_count.get(pos, 0)
if is_stuck:
open_count = self._count_open_space(pos)
openness_ratio = open_count / 24.0
dy = pos[0] - self.current_pos[0]
dx = pos[1] - self.current_pos[1]
direction_change = False
if len(self.path) >= 3:
prev_dy = self.path[-1][0] - self.path[-2][0]
prev_dx = self.path[-1][1] - self.path[-2][1]
direction_change = (abs(dy - prev_dy)
> 1) or (abs(dx - prev_dx) > 1)
if openness_ratio > 0.5:
penalty = 6.0 * visits
elif direction_change:
penalty = 4.0 * visits
else:
penalty = 6.0 * (9**visits)
else:
penalty = 6.0 * (9**visits)
h += penalty
else:
open_count = self._count_open_space(pos)
openness_ratio = open_count / 24.0
if wall_count < 3:
base_bonus = 10.0
elif wall_count < 5:
base_bonus = 5.0
else:
base_bonus = 0.0
open_bonus = 5.0 * openness_ratio
h -= base_bonus + open_bonus # Bonus for new, open positions
if len(self.path) >= 1:
current_open = self._count_open_space(self.current_pos)
target_open = self._count_open_space(pos)
if target_open > current_open:
improvement = (target_open - current_open) / 24.0
h -= 3.0 * improvement
if len(self.path) >= 2:
prev_pos = self.path[-2]
if pos == prev_pos:
h += 40.0 # High penalty for direct return
if len(self.path) >= 5:
recent_path = self.path[-5:]
if pos in recent_path:
steps_ago = len(self.path) - recent_path.index(pos) - 1
backtrack_penalty = 25.0 / max(1, steps_ago)
h += backtrack_penalty
free_neighbors = 0
for ndy in [-1, 0, 1]:
for ndx in [-1, 0, 1]:
if ndy == 0 and ndx == 0:
continue
ny = pos[0] + ndy
nx = pos[1] + ndx
if (0 <= ny < self.maze.shape[0] and
0 <= nx < self.maze.shape[1] and
self.maze[ny, nx] == 0):
free_neighbors += 1
if free_neighbors >= 6:
h -= 3.0
elif free_neighbors >= 4:
h -= 1.5
if dist < 5:
h -= 2.5 if near_target else 2.0
step_distance = abs(pos[0] -
self.current_pos[0]) + abs(pos[1] -
self.current_pos[1])
if step_distance > 1:
h -= 0.5
return h
def _same_direction(self, pos1, pos2):
"""
Determine if two positions are in the same direction
relative to target.
"""
target_dy = self.target[0] - self.current_pos[0]
target_dx = self.target[1] - self.current_pos[1]
move1_dy = pos1[0] - self.current_pos[0]
move1_dx = pos1[1] - self.current_pos[1]
move2_dy = pos2[0] - self.current_pos[0]
move2_dx = pos2[1] - self.current_pos[1]
same_y = False
if target_dy != 0:
if (target_dy > 0 and move1_dy > 0 and
move2_dy > 0) or (target_dy < 0 and move1_dy < 0 and
move2_dy < 0):
same_y = True
same_x = False
if target_dx != 0:
if (target_dx > 0 and move1_dx > 0 and
move2_dx > 0) or (target_dx < 0 and move1_dx < 0 and
move2_dx < 0):
same_x = True
return same_y or same_x
# === Candidate preparation and QUBO matrix ===
def _prepare_all_candidates(self, near_target=False):
"""
Prepare list of candidate positions for next step.
Filters positions by reachability and calculates their cost functions.
"""
neighbors = self._get_neighbors()
if len(neighbors) == 0:
return [], [], {}
reach_matrix = self._compute_reachability_matrix(self.current_pos)
reachable_neighbors = []
for pos in neighbors:
current_to_target = self._manhattan_distance(
self.current_pos, self.target)
is_target = pos == self.target
if is_target and current_to_target <= 5:
reachable_neighbors.append(pos)
if self.step_count % 20 == 0:
print(
f" TARGET {pos} Inserted (ignore reachability, dist={current_to_target})"
)
continue
grid_y = pos[0] - self.current_pos[0] + 2
grid_x = pos[1] - self.current_pos[1] + 2
if 0 <= grid_y < 5 and 0 <= grid_x < 5:
if reach_matrix[grid_y, grid_x] > 0:
reachable_neighbors.append(pos)
else:
if self.step_count % 20 == 0:
print(
f" REACHABILITY: {pos} not completed from {self.current_pos} !"
)
else:
reachable_neighbors.append(pos)
if len(reachable_neighbors) == 0:
return [], [], {}
h_values = []
for pos in reachable_neighbors:
h = self._compute_single_cost(pos, near_target)
has_wall = self._check_wall_between(self.current_pos, pos)
if has_wall:
h += 100.0
h_values.append(h)
idx_to_pos = {i: pos for i, pos in enumerate(reachable_neighbors)}
return reachable_neighbors, h_values, idx_to_pos
def _build_qubo_matrix(self, positions, h_values):
"""
Build QUBO matrix (h vector and J matrix) for QAOA optimization.
h contains individual position costs,
J describes interactions between positions.
"""
n = len(positions)
h = np.array(h_values, dtype=float)
J = np.zeros((n, n))
if self.step_count == 0:
for i in range(n):
for j in range(i + 1, n):
J[i, j] = +50.0
else:
for i in range(n):
for j in range(i + 1, n):
if self._same_direction(positions[i], positions[j]):
J[i, j] = -2.0
else:
J[i, j] = +5.0
return h, J
# === QAOA quantum circuit ===
def _create_qaoa_circuit(self, h, J, gammas, betas):
"""
Create QAOA quantum circuit with p layers.
Circuit applies:
cost Hamiltonian (using RZ and RZZ)
and mixer Hamiltonian (using RX).
"""
n_qubits = len(h)
qc = QuantumCircuit(n_qubits)
qc.h(range(n_qubits))
for p in range(self.p_layers):
gamma = gammas[p]
beta = betas[p]
for i in range(n_qubits):
qc.rz(2 * gamma * h[i], i)
for i in range(n_qubits):
for j in range(i + 1, n_qubits):
if J[i, j] != 0:
qc.rzz(2 * gamma * J[i, j], i, j)
for i in range(n_qubits):
qc.rx(2 * beta, i)
qc.measure_all()
return qc
def _run_qaoa(self, h, J):
"""
Run QAOA algorithm on quantum simulator.
Returns best measured bitstring and results histogram.
"""
qc = self._create_qaoa_circuit(h, J, self.gammas, self.betas)
backend = AerSimulator()
qc_transpiled = transpile(qc, backend)
job = backend.run(qc_transpiled, shots=100)
counts = job.result().get_counts()
best_bitstring = max(counts, key=counts.get)
return best_bitstring, counts
# === Next step selection ===
def _select_next_position(self):
"""
Main method for selecting next position using QAOA.
Creates QUBO problem from candidate positions
and calls QAOA for optimization.
"""
if self.current_pos == self.target:
return self.target
dist_to_target = self._manhattan_distance(self.current_pos, self.target)
near_target = dist_to_target < 10
positions, h_values, idx_to_pos = self._prepare_all_candidates(
near_target)
if len(positions) == 0:
print("ERROR: No valid candidates!")
return self.current_pos
print(f"\n Step: {self.step_count + 1} - {len(positions)} candidates")
recent_steps = 20
if len(self.path) >= recent_steps:
recent_visits = sum(1 for p in self.path[-recent_steps:]
if self.position_visit_count.get(p, 0) > 1)
stuck_ratio = recent_visits / recent_steps
if self.step_count % 20 == 0:
current_walls = self._count_walls_around(self.current_pos)
h, J = self._build_qubo_matrix(positions, h_values)
print(f"H_values: {h}")
print(f"J_matrix: {J.shape}, nonzero: {np.count_nonzero(J)}")
bitstring, counts = self._run_qaoa(h, J)
n = len(h)
# Decode bitstring: '1' means selected position
selected_indices = [
n - 1 - i for i, bit in enumerate(bitstring) if bit == "1"
]
print(f"QAOA bitstring: {bitstring} ({bitstring.count('1')} ones)")
print(f"Selected indices: {selected_indices}")
if len(selected_indices) == 0:
best_idx = 0 # Fallback to best h value
print("WARNING: No selection, fallback to best h")
else:
best_idx = min(selected_indices, key=lambda i: h[i])
next_pos = positions[best_idx]
self.qaoa_calls.append(next_pos)
print(f"Selected: idx={best_idx}, pos={next_pos}, h={h[best_idx]:.2f}")
return next_pos
# === Main navigation loop ===
def find_path(self):
"""
Main method for finding path from start to target.
Iteratively calls QAOA to select next steps
until reaching target or max_steps.
"""
while self.step_count < self.max_steps:
if self.current_pos == self.target:
print(f"\n\nCompleted in {self.step_count} steps")
return self.path
next_pos = self._select_next_position()
self.current_pos = next_pos
self.path.append(next_pos)
self.visited.add(next_pos)
self.position_visit_count[next_pos] = (
self.position_visit_count.get(next_pos, 0) + 1)
self.step_count += 1
dist = self._manhattan_distance(self.current_pos, self.target)
print(f"Steps {self.step_count}: {self.current_pos}, dist: {dist}")
print(f"\nNot completed in {self.max_steps} steps")
return self.path
# === Path visualization ===
def _draw_smart_path(self, ax, path):
"""
Smart path drawing considering different movement types
(straight, L-shapes, diagonals).
"""
if not path or len(path) < 2:
return
for i in range(len(path) - 1):
y1, x1 = path[i]
y2, x2 = path[i + 1]
abs_dy = abs(y2 - y1)
abs_dx = abs(x2 - x1)
dir_y = 1 if y2 > y1 else -1 if y2 < y1 else 0
dir_x = 1 if x2 > x1 else -1 if x2 < x1 else 0
if abs_dy + abs_dx == 1:
ax.plot([x1, x2], [y1, y2],
"r-",
linewidth=3,
alpha=0.7,
zorder=10)
elif (abs_dy == 2 and abs_dx == 1) or (abs_dy == 1 and abs_dx == 2):
if abs_dy == 2 and abs_dx == 1:
check_start = (y1, x1 + dir_x)
check_end = (y2, x2 - dir_x)
is_wall_start = (not (0 <= check_start[0] < self.height and
0 <= check_start[1] < self.width) or
self.maze[check_start[0],
check_start[1]] == 1)
is_wall_end = (not (0 <= check_end[0] < self.height and
0 <= check_end[1] < self.width) or
self.maze[check_end[0], check_end[1]] == 1)
if is_wall_start and is_wall_end:
point1 = (y1 + dir_y, x1)
point2 = (y1 + dir_y, x2)
point3 = (y2, x2)
ax.plot(
[x1, point1[1]],
[y1, point1[0]],
"r-",
linewidth=3,
alpha=0.7,
zorder=10,
)
ax.plot(
[point1[1], point2[1]],
[point1[0], point2[0]],
"r-",
linewidth=3,
alpha=0.7,
zorder=10,
)
ax.plot(
[point2[1], point3[1]],
[point2[0], point3[0]],
"r-",
linewidth=3,
alpha=0.7,
zorder=10,
)
elif is_wall_start:
ax.plot([x1, x1], [y1, y2],
"r-",
linewidth=3,
alpha=0.7,
zorder=10)
ax.plot([x1, x2], [y2, y2],
"r-",
linewidth=3,
alpha=0.7,
zorder=10)
elif is_wall_end:
ax.plot([x1, x2], [y1, y1],
"r-",
linewidth=3,
alpha=0.7,
zorder=10)
ax.plot([x2, x2], [y1, y2],
"r-",
linewidth=3,
alpha=0.7,
zorder=10)
else:
mid_y = y1 + dir_y
check_mid = (mid_y, x1)
is_wall_mid = (not (0 <= check_mid[0] < self.height and
0 <= check_mid[1] < self.width) or
self.maze[check_mid[0],
check_mid[1]] == 1)
if is_wall_mid:
ax.plot(
[x1, x2],
[y1, y1],
"r-",
linewidth=3,
alpha=0.7,
zorder=10,
)
ax.plot(
[x2, x2],
[y1, y2],
"r-",
linewidth=3,
alpha=0.7,
zorder=10,
)
else:
ax.plot(
[x1, x1],
[y1, y2],
"r-",
linewidth=3,
alpha=0.7,
zorder=10,
)
ax.plot(
[x1, x2],
[y2, y2],
"r-",
linewidth=3,
alpha=0.7,
zorder=10,
)
else:
check_start = (y1 + dir_y, x1)
check_end = (y2 - dir_y, x2)
is_wall_start = (not (0 <= check_start[0] < self.height and
0 <= check_start[1] < self.width) or
self.maze[check_start[0],
check_start[1]] == 1)
is_wall_end = (not (0 <= check_end[0] < self.height and
0 <= check_end[1] < self.width) or
self.maze[check_end[0], check_end[1]] == 1)
if is_wall_start and is_wall_end:
point1 = (y1, x1 + dir_x)
point2 = (y2, x1 + dir_x)
point3 = (y2, x2)
ax.plot(
[x1, point1[1]],
[y1, point1[0]],
"r-",
linewidth=3,
alpha=0.7,
zorder=10,
)
ax.plot(
[point1[1], point2[1]],
[point1[0], point2[0]],
"r-",
linewidth=3,
alpha=0.7,
zorder=10,
)
ax.plot(
[point2[1], point3[1]],
[point2[0], point3[0]],
"r-",
linewidth=3,
alpha=0.7,
zorder=10,
)
elif is_wall_start:
ax.plot([x1, x2], [y1, y1],
"r-",
linewidth=3,
alpha=0.7,
zorder=10)
ax.plot([x2, x2], [y1, y2],
"r-",
linewidth=3,
alpha=0.7,
zorder=10)
elif is_wall_end:
ax.plot([x1, x1], [y1, y2],
"r-",
linewidth=3,
alpha=0.7,
zorder=10)
ax.plot([x1, x2], [y2, y2],
"r-",
linewidth=3,
alpha=0.7,
zorder=10)
else:
mid_x = x1 + dir_x
check_mid = (y1, mid_x)
is_wall_mid = (not (0 <= check_mid[0] < self.height and
0 <= check_mid[1] < self.width) or
self.maze[check_mid[0],
check_mid[1]] == 1)
if is_wall_mid:
ax.plot(
[x1, x1],
[y1, y2],
"r-",
linewidth=3,
alpha=0.7,
zorder=10,
)
ax.plot(
[x1, x2],
[y2, y2],
"r-",
linewidth=3,
alpha=0.7,
zorder=10,
)
else:
ax.plot(
[x1, x2],
[y1, y1],
"r-",
linewidth=3,
alpha=0.7,
zorder=10,
)
ax.plot(
[x2, x2],
[y1, y2],
"r-",
linewidth=3,
alpha=0.7,
zorder=10,
)
elif (abs_dy == 0 and 2 <= abs_dx <= 4) or (abs_dx == 0 and
2 <= abs_dy <= 4):
ax.plot([x1, x2], [y1, y2],
"r-",
linewidth=3,
alpha=0.7,
zorder=10)
elif abs_dy == abs_dx and 2 <= abs_dy <= 4:
step_size = abs_dy
corner_x = (y1 + (step_size - 1) * dir_y, x2)
is_wall_x = (not (0 <= corner_x[0] < self.height and
0 <= corner_x[1] < self.width) or
self.maze[corner_x[0], corner_x[1]] == 1)
if is_wall_x:
ax.plot([x1, x1], [y1, y2],
"r-",
linewidth=3,
alpha=0.7,
zorder=10)
ax.plot([x1, x2], [y2, y2],
"r-",
linewidth=3,
alpha=0.7,
zorder=10)
else:
ax.plot([x1, x2], [y1, y1],
"r-",
linewidth=3,
alpha=0.7,
zorder=10)
ax.plot([x2, x2], [y1, y2],
"r-",
linewidth=3,
alpha=0.7,
zorder=10)
elif abs_dy == 1 and abs_dx == 1:
corner_x = (y1, x2)
corner_y = (y2, x1)
is_wall_x = (not (0 <= corner_x[0] < self.height and
0 <= corner_x[1] < self.width) or
self.maze[corner_x[0], corner_x[1]] == 1)
is_wall_y = (not (0 <= corner_y[0] < self.height and
0 <= corner_y[1] < self.width) or
self.maze[corner_y[0], corner_y[1]] == 1)
if is_wall_x and not is_wall_y:
ax.plot([x1, x1], [y1, y2],
"r-",
linewidth=3,
alpha=0.7,
zorder=10)
ax.plot([x1, x2], [y2, y2],
"r-",
linewidth=3,
alpha=0.7,
zorder=10)
elif is_wall_y and not is_wall_x:
ax.plot([x1, x2], [y1, y1],
"r-",
linewidth=3,
alpha=0.7,
zorder=10)
ax.plot([x2, x2], [y1, y2],
"r-",
linewidth=3,
alpha=0.7,
zorder=10)
elif not is_wall_x:
ax.plot([x1, x2], [y1, y1],
"r-",
linewidth=3,
alpha=0.7,
zorder=10)
ax.plot([x2, x2], [y1, y2],
"r-",
linewidth=3,
alpha=0.7,
zorder=10)
else:
ax.plot([x1, x2], [y1, y2],
"r--",
linewidth=2,
alpha=0.5,
zorder=10)
ax.plot(
(x1 + x2) / 2,
(y1 + y2) / 2,
"yo",
markersize=6,
alpha=0.7,
zorder=11,
)
else:
ax.plot([x1, x2], [y1, y2],
"r--",
linewidth=2,
alpha=0.5,
zorder=10)
ax.plot(
(x1 + x2) / 2,
(y1 + y2) / 2,
"yo",
markersize=6,
alpha=0.7,
zorder=11,
)
def visualize_path(self, path):
"""
Complete visualization of maze and found path.
Displays start, target, path and traversal statistics.
"""
import matplotlib.pyplot as plt
visual = np.ones((self.height, self.width, 3))
for y in range(self.height):
for x in range(self.width):
if self.maze[y, x] == 1:
visual[y, x] = [0, 0, 0]
if path:
for i, (y, x) in enumerate(path):
if (y, x) not in [self.start, self.target]:
progress = i / len(path)
r = 0.3 + 0.5 * progress
g = 0.3 * (1 - progress)
b = 0.9
visual[y, x] = [r, g, b]
for y, x in self.qaoa_calls:
visual[y, x] = [1, 0.6, 0]
sy, sx = self.start
visual[sy, sx] = [0, 1, 0]
ty, tx = self.target
visual[ty, tx] = [1, 0, 0]
fig, ax = plt.subplots(figsize=(18, 14))
ax.imshow(visual, interpolation="nearest", origin="upper")
reached = path[-1] == self.target if path else False
status = "success" if reached else "Failed"
efficiency = (self._manhattan_distance(self.start, self.target) /
len(path) * 100 if path else 0)
title = f"{status} | Length: {len(path)} "
title += f"Efficiency: {efficiency:.1f}% | QAOA steps: {len(self.qaoa_calls)}x"
ax.set_title(
title,
fontsize=15,
fontweight="bold",
color="darkgreen" if reached else "darkred",
pad=20,
)
if path and len(path) > 1:
self._draw_smart_path(ax, path)
ax.plot(
path[0][1],
path[0][0],
"go",
markersize=18,
markeredgecolor="darkgreen",
markeredgewidth=3,
label="Start",
zorder=12,
)
if reached:
ax.plot(
path[-1][1],
path[-1][0],
"r*",
markersize=28,
markeredgecolor="darkred",
markeredgewidth=3,
label="Start",
zorder=12,
)
else:
ax.plot(
path[-1][1],
path[-1][0],
"rx",
markersize=24,
markeredgecolor="darkred",
markeredgewidth=3,
label="End",
zorder=12,
)
if self.qaoa_calls:
qaoa_y = [p[0] for p in self.qaoa_calls]
qaoa_x = [p[1] for p in self.qaoa_calls]
ax.scatter(
qaoa_x,
qaoa_y,
c="orange",
marker="D",
s=150,
edgecolors="black",
linewidths=1,
label="QAOA steps",
zorder=11,
)
for i, (qy, qx) in enumerate(self.qaoa_calls[:300]):
ax.text(
qx,
qy,
str(i + 1),
color="white",
fontsize=9,
fontweight="bold",
ha="center",
va="center",
zorder=12,
)
if len(self.qaoa_calls) > 300:
ax.text(
0.5,
0.98,
f"( {len(self.qaoa_calls)})",
transform=ax.transAxes,
ha="center",
va="top",
fontsize=10,
style="italic",
color="gray",
)
ax.grid(True, alpha=0.3, color="gray", linewidth=0.5)
ax.legend(loc="upper right", fontsize=12, framealpha=0.9)
ax.set_xlabel("X", fontsize=12)
ax.set_ylabel("Y", fontsize=12)
plt.tight_layout()
plt.savefig("qaoa_maze_path.png", dpi=200, bbox_inches="tight")
plt.show()
In [2]:
# === Maze definition ===
# Maze as 2D numpy array:
# 0 = free path, 1 = wall, 2 = start position, 3 = target position
maze = np.array([
[2, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1],
[1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1],
[0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0],
[0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1],
[1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0],
[0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1],
[1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0],
[0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1],
[0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 3],
[1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1],
[0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1],
[0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0],
[0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
])
start_pos = tuple(np.argwhere(maze == 2)[0])
target_pos = tuple(np.argwhere(maze == 3)[0])
maze_binary = (maze == 1).astype(int)
print(f"Maze shape: {maze.shape}")
print(f"Start: {start_pos}")
print(f"Target: {target_pos}")
print(f"Manhattan distance: {abs(target_pos[0]-start_pos[0]) + abs(target_pos[1]-start_pos[1])}")
print(f"\nWalls: {np.sum(maze == 1)} ({np.sum(maze == 1) / maze.size * 100:.1f}%)")
Maze shape: (20, 30) Start: (np.int64(0), np.int64(0)) Target: (np.int64(12), np.int64(29)) Manhattan distance: 41 Walls: 156 (26.0%)
In [3]:
# === Maze preparation for navigation ===
# Convert maze to binary format and identify start/target positions
plt.figure(figsize=(15, 10))
plt.imshow(maze_binary, cmap='binary', origin='upper')
plt.plot(start_pos[1], start_pos[0], 'go', markersize=20, label='Start', zorder=10)
plt.plot(target_pos[1], target_pos[0], 'r*', markersize=30, label='End', zorder=10)
plt.title(f'Maze {maze.shape}', fontsize=16, fontweight='bold')
plt.xlabel('columns', fontsize=12)
plt.ylabel('rows', fontsize=12)
plt.legend(fontsize=14, loc='upper right')
plt.grid(True, alpha=0.3, linewidth=0.5)
plt.tight_layout()
plt.show()
In [4]:
# === Maze visualization ===
# Display maze with start and target positions
import time
navigator = QAOANavigator(
maze_binary,
start_pos,
target_pos,
radius=2,
p_layers=3
)
navigator.max_steps = 400
start_time = time.time()
path = navigator.find_path()
elapsed = time.time() - start_time
print(f"time (s) {elapsed:.1f} sekund")
print(f"sec/step: {elapsed/len(path):.2f}")
REACHABILITY: (np.int64(2), np.int64(0)) not completed from (np.int64(0), np.int64(0)) !
Step: 1 - 4 candidates
H_values: [-10.64939024 -13.50711382 71.30182927 70.6351626 ]
J_matrix: (4, 4), nonzero: 6
QAOA bitstring: 0010 (1 ones)
Selected indices: [1]
Selected: idx=1, pos=(np.int64(0), np.int64(2)), h=-13.51
Steps 1: (np.int64(0), np.int64(2)), dist: 39
Step: 2 - 7 candidates
H_values: [119. 5.10060976 -10.9898374 -22.82317073 80.79471545
-18.9898374 -25.01422764]
J_matrix: (7, 7), nonzero: 21
QAOA bitstring: 1110110 (5 ones)
Selected indices: [6, 5, 4, 2, 1]
Selected: idx=6, pos=(np.int64(2), np.int64(2)), h=-25.01
Steps 2: (np.int64(2), np.int64(2)), dist: 37
Step: 3 - 13 candidates
H_values: [ 9.60060976 103.45121951 99.1351626 -6.69817073 91.16971545
3.74288618 -7.1148374 -3.07317073 -23.28861789 71.78760163
-17.74695122 -23.39634146 71.57926829]
J_matrix: (13, 13), nonzero: 78
QAOA bitstring: 0110101001100 (6 ones)
Selected indices: [11, 10, 8, 6, 3, 2]
Selected: idx=11, pos=(np.int64(4), np.int64(2)), h=-23.40
Steps 3: (np.int64(4), np.int64(2)), dist: 35
Step: 4 - 12 candidates
H_values: [ -2.6148374 99.65243902 6.92682927 -8.03861789 -18.21239837
3.90243902 -6.74695122 -22.92073171 -22.40345528 -23.58739837
-19.55284553 82.20426829]
J_matrix: (12, 12), nonzero: 66
QAOA bitstring: 010000101011 (5 ones)
Selected indices: [10, 5, 3, 1, 0]
Selected: idx=10, pos=(np.int64(5), np.int64(4)), h=-19.55
Steps 4: (np.int64(5), np.int64(4)), dist: 32
Step: 5 - 8 candidates
H_values: [ -4.4796748 -7.83739837 -2.36178862 129.60365854 -6.40345528
-8.83739837 0.13821138 -1.57723577]
J_matrix: (8, 8), nonzero: 28
QAOA bitstring: 11111110 (7 ones)
Selected indices: [7, 6, 5, 4, 3, 2, 1]
Selected: idx=5, pos=(np.int64(5), np.int64(2)), h=-8.84
Steps 5: (np.int64(5), np.int64(2)), dist: 34
Step: 6 - 11 candidates
H_values: [ -2.43089431 -8.28861789 -13.9796748 108.90243902 68.68699187
-17.40345528 -6.9796748 -14.86178862 100.2804878 98.85365854
82.59654472]
J_matrix: (11, 11), nonzero: 55
QAOA bitstring: 01011010111 (7 ones)
Selected indices: [9, 7, 6, 4, 2, 1, 0]
Selected: idx=7, pos=(np.int64(5), np.int64(3)), h=-14.86
Steps 6: (np.int64(5), np.int64(3)), dist: 33
Step: 7 - 11 candidates
H_values: [ -3.28861789 -8.9796748 -12.71239837 -2.24695122 -7.42073171
-8.92784553 -7.4796748 108.66260163 54.5304878 -2.07723577
87.70426829]
J_matrix: (11, 11), nonzero: 55
QAOA bitstring: 10010011100 (5 ones)
Selected indices: [10, 7, 4, 3, 2]
Selected: idx=2, pos=(np.int64(3), np.int64(4)), h=-12.71
Steps 7: (np.int64(3), np.int64(4)), dist: 34
Step: 8 - 10 candidates
H_values: [ 98.85365854 164.52743902 -8.66361789 -8.8546748 -12.23678862
58.30008711 -21.90345528 98.67987805 51.94715447 -7.07723577]
J_matrix: (10, 10), nonzero: 45
QAOA bitstring: 1011001101 (6 ones)
Selected indices: [9, 7, 6, 3, 2, 0]
Selected: idx=6, pos=(np.int64(4), np.int64(4)), h=-21.90
Steps 8: (np.int64(4), np.int64(4)), dist: 33
Step: 9 - 8 candidates
H_values: [ 97.62093496 -4.16361789 104.82926829 59.22865854 -8.04573171
-13.42784553 57.52569686 51.0304878 ]
J_matrix: (8, 8), nonzero: 28
QAOA bitstring: 00110101 (4 ones)
Selected indices: [5, 4, 2, 0]
Selected: idx=5, pos=(np.int64(4), np.int64(5)), h=-13.43
Steps 9: (np.int64(4), np.int64(5)), dist: 32
Step: 10 - 7 candidates
H_values: [ 2.62093496 -4.8546748 2.76321138 -8.54573171 104.47154472
60.55487805 -1.95223577]
J_matrix: (7, 7), nonzero: 21
QAOA bitstring: 0000010 (1 ones)
Selected indices: [1]
Selected: idx=1, pos=(np.int64(3), np.int64(3)), h=-4.85
Steps 10: (np.int64(3), np.int64(3)), dist: 35
Step: 11 - 13 candidates
H_values: [ 97.80182927 97.3851626 92.49593496 -7.43089431 -7.78861789
47.60704607 -12.73678862 -12.24695122 -22.92073171 86.35191638
49.32926829 50.30487805 42.7804878 ]
J_matrix: (13, 13), nonzero: 78
QAOA bitstring: 1110010011000 (6 ones)
Selected indices: [12, 11, 10, 7, 4, 3]
Selected: idx=7, pos=(np.int64(4), np.int64(1)), h=-12.25
Steps 11: (np.int64(4), np.int64(1)), dist: 36
Step: 12 - 12 candidates
H_values: [ 8.74288618 -7.8648374 54.27743902 -7.05589431 91.60365854
4.40243902 44.47865854 -23.79573171 -22.6046748 42.17987805
93.35365854 -22.79573171]
J_matrix: (12, 12), nonzero: 66
QAOA bitstring: 100111000001 (5 ones)
Selected indices: [11, 8, 7, 6, 0]
Selected: idx=7, pos=(np.int64(4), np.int64(3)), h=-23.80
Steps 12: (np.int64(4), np.int64(3)), dist: 34
Step: 13 - 11 candidates
H_values: [164.65243902 -2.43089431 62.35365854 -7.73678862 102.65582656
60.35365854 46.88821138 50.05321508 -12.4796748 48.05487805
-7.07723577]
J_matrix: (11, 11), nonzero: 55
QAOA bitstring: 11110001101 (7 ones)
Selected indices: [10, 9, 8, 7, 3, 2, 0]
Selected: idx=8, pos=(np.int64(5), np.int64(1)), h=-12.48
Steps 13: (np.int64(5), np.int64(1)), dist: 35
Step: 14 - 11 candidates
H_values: [106.92682927 -7.43089431 -13.78861789 62.65077605 91.57926829
44.32926829 47.30487805 -22.29573171 91.53760163 -22.40345528
80.11382114]
J_matrix: (11, 11), nonzero: 55
QAOA bitstring: 11011010000 (5 ones)
Selected indices: [10, 9, 7, 6, 4]
Selected: idx=9, pos=(np.int64(7), np.int64(1)), h=-22.40
Steps 14: (np.int64(7), np.int64(1)), dist: 33
Step: 15 - 9 candidates
H_values: [101.75138581 153.95426829 -7.04573171 2.53760163 -14.76117886
-13.28556911 -21.7195122 -6.51117886 -13.95223577]
J_matrix: (9, 9), nonzero: 36
QAOA bitstring: 001001011 (4 ones)
Selected indices: [6, 3, 1, 0]
Selected: idx=6, pos=(np.int64(8), np.int64(1)), h=-21.72
Steps 15: (np.int64(8), np.int64(1)), dist: 32
Step: 16 - 8 candidates
H_values: [ 8.85365854 -7.67073171 102.26321138 91.58943089 2.72154472
-14.57723577 -13.57723577 -13.76829268]
J_matrix: (8, 8), nonzero: 28
QAOA bitstring: 11101010 (5 ones)
Selected indices: [7, 6, 5, 3, 1]
Selected: idx=5, pos=(np.int64(8), np.int64(2)), h=-14.58
Steps 16: (np.int64(8), np.int64(2)), dist: 31
Step: 17 - 8 candidates
H_values: [ 97.70426829 7.03760163 1.11382114 92.60670732 2.22154472
102.20356473 98.98882114 91.23170732]
J_matrix: (8, 8), nonzero: 28
QAOA bitstring: 00110110 (4 ones)
Selected indices: [5, 4, 2, 1]
Selected: idx=2, pos=(np.int64(7), np.int64(2)), h=1.11
Steps 17: (np.int64(7), np.int64(2)), dist: 32
Step: 18 - 10 candidates
H_values: [166.32424677 108.85365854 2.03760163 61.86737805 -12.28556911
-12.39329268 -2.77845528 90.04181185 72.08231707 91.04776423]
J_matrix: (10, 10), nonzero: 45
QAOA bitstring: 1010000110 (4 ones)
Selected indices: [9, 7, 2, 1]
Selected: idx=2, pos=(np.int64(7), np.int64(0)), h=2.04
Steps 18: (np.int64(7), np.int64(0)), dist: 34
Step: 19 - 8 candidates
H_values: [154.22865854 4.22865854 45.94376694 88.69715447 -12.77845528
43.69359756 -11.51117886 -19.20223577]
J_matrix: (8, 8), nonzero: 28
QAOA bitstring: 01001100 (3 ones)
Selected indices: [6, 3, 2]
Selected: idx=6, pos=(np.int64(9), np.int64(0)), h=-11.51
Steps 19: (np.int64(9), np.int64(0)), dist: 32
Step: 20 - 6 candidates
H_values: [104.89176829 54.55487805 2.72154472 153.51998645 -13.70223577
81.08231707]
J_matrix: (6, 6), nonzero: 15
QAOA bitstring: 110011 (4 ones)
Selected indices: [5, 4, 1, 0]
Selected: idx=4, pos=(np.int64(9), np.int64(1)), h=-13.70
Steps 20: (np.int64(9), np.int64(1)), dist: 31
REACHABILITY: (np.int64(10), np.int64(3)) not completed from (np.int64(9), np.int64(1)) !
Step: 21 - 9 candidates
H_values: [ 69.71815718 59.80487805 159.09627728 60.2804878 107.25107604
-13.26829268 93.85670732 -13.79268293 80.30792683]
J_matrix: (9, 9), nonzero: 36
QAOA bitstring: 111110101 (7 ones)
Selected indices: [8, 7, 6, 5, 4, 2, 0]
Selected: idx=7, pos=(np.int64(11), np.int64(1)), h=-13.79
Steps 21: (np.int64(11), np.int64(1)), dist: 29
Step: 22 - 8 candidates
H_values: [171.59627728 104.51998645 2.23170732 4.85670732 -14.31707317
-22.48373984 -21.62601626 70.3495935 ]
J_matrix: (8, 8), nonzero: 28
QAOA bitstring: 10100101 (4 ones)
Selected indices: [7, 5, 2, 0]
Selected: idx=5, pos=(np.int64(12), np.int64(1)), h=-22.48
Steps 22: (np.int64(12), np.int64(1)), dist: 28
Step: 23 - 8 candidates
H_values: [ -3.26829268 100.02310655 4.62398374 -12.37601626 75.57520325
103.75609756 -13.18495935 80.45731707]
J_matrix: (8, 8), nonzero: 28
QAOA bitstring: 11011110 (6 ones)
Selected indices: [7, 6, 4, 3, 2, 1]
Selected: idx=6, pos=(np.int64(14), np.int64(1)), h=-13.18
Steps 23: (np.int64(14), np.int64(1)), dist: 30
Step: 24 - 12 candidates
H_values: [ 93.62398374 85.43292683 -22.62601626 -29.04979675 4.25609756
-24.16768293 -25.0254065 -7.28556911 -20.00101626 9.01321138
-7.55284553 -13.78556911]
J_matrix: (12, 12), nonzero: 66
QAOA bitstring: 000001101001 (4 ones)
Selected indices: [6, 5, 3, 0]
Selected: idx=3, pos=(np.int64(13), np.int64(3)), h=-29.05
Steps 24: (np.int64(13), np.int64(3)), dist: 27
Step: 25 - 11 candidates
H_values: [155.81929047 -12.61585366 79.29369919 -7.62601626 -7.7754065
105.92218351 -8.7754065 79.84247967 -3.89329268 -9.25101626
85.39126016]
J_matrix: (11, 11), nonzero: 55
QAOA bitstring: 00000101011 (4 ones)
Selected indices: [5, 3, 1, 0]
Selected: idx=1, pos=(np.int64(12), np.int64(3)), h=-12.62
Steps 25: (np.int64(12), np.int64(3)), dist: 26
Step: 26 - 8 candidates
H_values: [-12.6402439 -15.83130081 92.37398374 96.16990022 75.69308943
90.95731707 -14.4004065 80.57520325]
J_matrix: (8, 8), nonzero: 28
QAOA bitstring: 10111001 (5 ones)
Selected indices: [7, 5, 4, 3, 0]
Selected: idx=0, pos=(np.int64(12), np.int64(4)), h=-12.64
Steps 26: (np.int64(12), np.int64(4)), dist: 25
Step: 27 - 8 candidates
H_values: [ 76.00203252 106.72110286 -15.33130081 -23.68902439 91.5995935
76.00203252 90.5995935 80.21747967]
J_matrix: (8, 8), nonzero: 28
QAOA bitstring: 10010110 (4 ones)
Selected indices: [7, 4, 2, 1]
Selected: idx=2, pos=(np.int64(12), np.int64(5)), h=-15.33
Steps 27: (np.int64(12), np.int64(5)), dist: 24
Step: 28 - 12 candidates
H_values: [ 81.44308943 75.89430894 66.13414634 106.65142276 -23.18902439
-23.71341463 160.62007505 -13.05691057 -23.89735772 90.82520325
-14.53252033 -18.8902439 ]
J_matrix: (12, 12), nonzero: 66
QAOA bitstring: 111101110111 (10 ones)
Selected indices: [11, 10, 9, 8, 6, 5, 4, 2, 1, 0]
Selected: idx=8, pos=(np.int64(13), np.int64(7)), h=-23.90
Steps 28: (np.int64(13), np.int64(7)), dist: 23
Step: 29 - 13 candidates
H_values: [-13.37296748 -22.23069106 71.4949187 98.96036585 -23.21341463
82.15447154 -8.68191057 -7.87296748 -4.65752033 -8.20630081
-3.99085366 -8.68191057 86.83536585]
J_matrix: (13, 13), nonzero: 78
QAOA bitstring: 1101000100001 (5 ones)
Selected indices: [12, 11, 9, 5, 0]
Selected: idx=0, pos=(np.int64(11), np.int64(6)), h=-13.37
Steps 29: (np.int64(11), np.int64(6)), dist: 24
Step: 30 - 13 candidates
H_values: [ 96.90853659 -8.65752033 -14.0152439 107.82520325 -8.18191057
-23.73069106 -23.5050813 161.00261324 -23.18902439 -28.32113821
86.31808943 -21.87296748 80.02251407]
J_matrix: (13, 13), nonzero: 78
QAOA bitstring: 1110011001000 (6 ones)
Selected indices: [12, 11, 10, 7, 6, 3]
Selected: idx=6, pos=(np.int64(11), np.int64(8)), h=-23.51
Steps 30: (np.int64(11), np.int64(8)), dist: 22
Step: 31 - 9 candidates
H_values: [ 95.7347561 97.72764228 96.06808943 100.26129178 -8.48069106
-12.52947154 -13.31402439 -22.82113821 155.20383275]
J_matrix: (9, 9), nonzero: 36
QAOA bitstring: 010010110 (4 ones)
Selected indices: [7, 4, 2, 1]
Selected: idx=7, pos=(np.int64(12), np.int64(8)), h=-22.82
Steps 31: (np.int64(12), np.int64(8)), dist: 21
Step: 32 - 9 candidates
H_values: [ 90.58536585 92.3699187 60.07243482 95.80444251 -8.43902439
-7.96341463 -12.34552846 91.25203252 90.91869919]
J_matrix: (9, 9), nonzero: 36
QAOA bitstring: 110110111 (7 ones)
Selected indices: [8, 7, 5, 4, 2, 1, 0]
Selected: idx=4, pos=(np.int64(12), np.int64(6)), h=-8.44
Steps 32: (np.int64(12), np.int64(6)), dist: 23
Step: 33 - 13 candidates
H_values: [ 91.88414634 -13.80691057 -19.16463415 55.76681747 44.8699187
65.1097561 63.33536585 -23.21341463 84.87426409 -12.99796748
-9.78252033 -14.1402439 -18.83130081]
J_matrix: (13, 13), nonzero: 78
QAOA bitstring: 1101000011111 (8 ones)
Selected indices: [12, 11, 9, 4, 3, 2, 1, 0]
Selected: idx=2, pos=(np.int64(10), np.int64(7)), h=-19.16
Steps 33: (np.int64(10), np.int64(7)), dist: 24
Step: 34 - 12 candidates
H_values: [ 96.90853659 87.27642276 -3.09146341 -8.2652439 92.22764228
-8.11585366 -8.05691057 -23.60569106 81.97052846 89.89430894
-23.71341463 139.81864673]
J_matrix: (12, 12), nonzero: 66
QAOA bitstring: 101010000011 (5 ones)
Selected indices: [11, 9, 7, 1, 0]
Selected: idx=7, pos=(np.int64(11), np.int64(7)), h=-23.61
Steps 34: (np.int64(11), np.int64(7)), dist: 23
Step: 35 - 14 candidates
H_values: [ -3.53252033 -8.8902439 87.04369919 96.88414634 100.76681747
91.9949187 60.08536585 45.27187948 -13.02947154 158.08536585
-23.21341463 -17.84552846 -13.37296748 46.06097561]
J_matrix: (14, 14), nonzero: 91
QAOA bitstring: 10110100010100 (6 ones)
Selected indices: [13, 11, 10, 8, 4, 2]
Selected: idx=10, pos=(np.int64(12), np.int64(7)), h=-23.21
Steps 35: (np.int64(12), np.int64(7)), dist: 22
Step: 36 - 12 candidates
H_values: [ -8.80691057 54.96794161 95.59222561 -13.02947154 62.83536585
60.79626973 45.22648084 -12.84552846 -8.80691057 54.93597561
-9.1402439 -13.83130081]
J_matrix: (12, 12), nonzero: 66
QAOA bitstring: 100000010100 (3 ones)
Selected indices: [11, 4, 2]
Selected: idx=11, pos=(np.int64(14), np.int64(7)), h=-13.83
Steps 36: (np.int64(14), np.int64(7)), dist: 24
Step: 37 - 13 candidates
H_values: [ 49.75542005 84.79416112 139.01219512 -13.55691057 44.56097561
-9.53252033 -8.3902439 -4.50813008 -8.05691057 92.01930894
-3.50813008 -8.53252033 87.06808943]
J_matrix: (13, 13), nonzero: 78
QAOA bitstring: 0010000100010 (3 ones)
Selected indices: [10, 5, 1]
Selected: idx=5, pos=(np.int64(14), np.int64(5)), h=-9.53
Steps 37: (np.int64(14), np.int64(5)), dist: 26
Step: 38 - 16 candidates
H_values: [154.6097561 47.58536585 39.06097561 154.65853659 -23.55691057
39.06097561 -8.9004065 -8.42479675 -23.7652439 84.82065997
-3.87601626 -8.63313008 -19.05691057 -3.87601626 -8.9004065
-13.50813008]
J_matrix: (16, 16), nonzero: 120
QAOA bitstring: 0110111111111111 (14 ones)
Selected indices: [14, 13, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
Selected: idx=8, pos=(np.int64(14), np.int64(6)), h=-23.77
Steps 38: (np.int64(14), np.int64(6)), dist: 25
Step: 39 - 13 candidates
H_values: [ 52.58536585 44.06097561 39.71226104 -23.37296748 -9.04979675
100.59843206 45.2798103 -4.35873984 -8.24085366 81.33536585
-4.0254065 -8.50813008 -13.53252033]
J_matrix: (13, 13), nonzero: 78
QAOA bitstring: 0010011011011 (7 ones)
Selected indices: [10, 7, 6, 4, 3, 1, 0]
Selected: idx=3, pos=(np.int64(13), np.int64(6)), h=-23.37
Steps 39: (np.int64(13), np.int64(6)), dist: 24
Step: 40 - 12 candidates
H_values: [ 46.08536585 38.93597561 160.1097561 44.56097561 139.01219512
-8.18191057 44.56097561 95.70020325 100.55420054 -4.63313008
-8.99085366 -13.68191057]
J_matrix: (12, 12), nonzero: 66
QAOA bitstring: 011010011011 (7 ones)
Selected indices: [10, 9, 7, 4, 3, 1, 0]
Selected: idx=10, pos=(np.int64(15), np.int64(6)), h=-8.99
Steps 40: (np.int64(15), np.int64(6)), dist: 26
Step: 41 - 15 candidates
H_values: [-19.05691057 84.76104153 39.06097561 -14.04979675 45.26765083
-9.35873984 -8.88313008 -23.55691057 -23.66463415 -4.00101626
-8.00813008 -18.43191057 -3.66768293 -8.2754065 -13.50813008]
J_matrix: (15, 15), nonzero: 105
QAOA bitstring: 001111110110000 (8 ones)
Selected indices: [12, 11, 10, 9, 8, 7, 5, 4]
Selected: idx=8, pos=(np.int64(15), np.int64(8)), h=-23.66
Steps 41: (np.int64(15), np.int64(8)), dist: 24
Step: 42 - 10 candidates
H_values: [148.93597561 154.8597561 99.91704108 -8.30691057 -12.48069106
-3.75813008 -7.43191057 -3.75813008 -7.90752033 -4.22357724]
J_matrix: (10, 10), nonzero: 45
QAOA bitstring: 1010110000 (4 ones)
Selected indices: [9, 7, 5, 4]
Selected: idx=4, pos=(np.int64(15), np.int64(9)), h=-12.48
Steps 42: (np.int64(15), np.int64(9)), dist: 23
Step: 43 - 8 candidates
H_values: [154.21036585 -8.93191057 100.60139149 -3.90752033 -7.24796748
-2.90752033 0.77642276 97.96036585]
J_matrix: (8, 8), nonzero: 28
QAOA bitstring: 10101011 (5 ones)
Selected indices: [7, 5, 3, 1, 0]
Selected: idx=1, pos=(np.int64(15), np.int64(7)), h=-8.93
Steps 43: (np.int64(15), np.int64(7)), dist: 25
Step: 44 - 14 candidates
H_values: [ 49.6667612 44.06097561 54.25914634 44.58536585 -9.50813008
60.60438444 45.19512195 90.18597561 -4.1504065 -8.03252033
-18.24796748 -3.2754065 -8.50813008 -12.90752033]
J_matrix: (14, 14), nonzero: 91
QAOA bitstring: 00010111000010 (5 ones)
Selected indices: [10, 8, 7, 6, 1]
Selected: idx=10, pos=(np.int64(16), np.int64(9)), h=-18.25
Steps 44: (np.int64(16), np.int64(9)), dist: 24
Step: 45 - 7 candidates
H_values: [94.7195122 50.5312137 -9.03252033 -7.55691057 -4.00813008 1.27642276
3.63414634]
J_matrix: (7, 7), nonzero: 21
QAOA bitstring: 1010100 (3 ones)
Selected indices: [6, 4, 2]
Selected: idx=2, pos=(np.int64(16), np.int64(7)), h=-9.03
Steps 45: (np.int64(16), np.int64(7)), dist: 26
Step: 46 - 13 candidates
H_values: [ 48.9847561 44.08536585 -14.50813008 45.19115145 45.12915743
-9.1504065 -8.00813008 -22.93191057 84.68060395 -3.79268293
-8.00813008 -9.72357724 1.05792683]
J_matrix: (13, 13), nonzero: 78
QAOA bitstring: 0110111111100 (9 ones)
Selected indices: [11, 10, 8, 7, 6, 5, 4, 3, 2]
Selected: idx=7, pos=(np.int64(16), np.int64(8)), h=-22.93
Steps 46: (np.int64(16), np.int64(8)), dist: 25
Step: 47 - 11 candidates
H_values: [148.71036585 54.13414634 44.46036585 -8.88313008 100.34054169
45.15354767 -3.5254065 -7.40752033 92.46036585 106.05792683
98.63414634]
J_matrix: (11, 11), nonzero: 55
QAOA bitstring: 01010110100 (5 ones)
Selected indices: [9, 7, 5, 4, 2]
Selected: idx=7, pos=(np.int64(17), np.int64(8)), h=-7.41
Steps 47: (np.int64(17), np.int64(8)), dist: 26
Step: 48 - 11 candidates
H_values: [ 49.26667099 43.96036585 44.56097561 -13.88313008 85.17793792
-8.5254065 -8.38313008 -14.22357724 -12.53963415 127.62398374
133.99186992]
J_matrix: (11, 11), nonzero: 55
QAOA bitstring: 01011110010 (6 ones)
Selected indices: [9, 7, 6, 5, 4, 1]
Selected: idx=7, pos=(np.int64(17), np.int64(9)), h=-14.22
Steps 48: (np.int64(17), np.int64(9)), dist: 25
Step: 49 - 10 candidates
H_values: [ 48.83536585 49.43597561 54.66606124 45.10619919 -9.00813008
100.5647019 -12.03963415 106.05792683 4.13414634 38.99186992]
J_matrix: (10, 10), nonzero: 45
QAOA bitstring: 0110000111 (5 ones)
Selected indices: [8, 7, 2, 1, 0]
Selected: idx=8, pos=(np.int64(18), np.int64(9)), h=4.13
Steps 49: (np.int64(18), np.int64(9)), dist: 26
Step: 50 - 5 candidates
H_values: [149.00558943 43.58536585 85.49186992 88.15323436 39.49186992]
J_matrix: (5, 5), nonzero: 10
QAOA bitstring: 11010 (3 ones)
Selected indices: [4, 3, 1]
Selected: idx=4, pos=(np.int64(19), np.int64(9)), h=39.49
Steps 50: (np.int64(19), np.int64(9)), dist: 27
Step: 51 - 4 candidates
H_values: [148.51935042 47.13058943 81.58536585 90.16606124]
J_matrix: (4, 4), nonzero: 6
QAOA bitstring: 0100 (1 ones)
Selected indices: [2]
Selected: idx=2, pos=(np.int64(17), np.int64(10)), h=81.59
Steps 51: (np.int64(17), np.int64(10)), dist: 24
Step: 52 - 5 candidates
H_values: [154.31097561 154.3597561 59.87434242 63.9847561 240.17936992]
J_matrix: (5, 5), nonzero: 10
QAOA bitstring: 11000 (2 ones)
Selected indices: [4, 3]
Selected: idx=3, pos=(np.int64(17), np.int64(9)), h=63.98
Steps 52: (np.int64(17), np.int64(9)), dist: 25
Step: 53 - 10 candidates
H_values: [ 48.83536585 49.43597561 54.13414634 44.58536585 -9.00813008
60.00914634 90.59556994 106.05792683 66.12434242 95.15853659]
J_matrix: (10, 10), nonzero: 45
QAOA bitstring: 1010001000 (3 ones)
Selected indices: [9, 7, 3]
Selected: idx=3, pos=(np.int64(16), np.int64(9)), h=44.59
Steps 53: (np.int64(16), np.int64(9)), dist: 24
Step: 54 - 7 candidates
H_values: [ 54.1097561 49.93597561 59.13414634 59.9847561 -4.00813008
536.1097561 65.60584445]
J_matrix: (7, 7), nonzero: 21
QAOA bitstring: 1111101 (6 ones)
Selected indices: [6, 5, 4, 3, 2, 0]
Selected: idx=4, pos=(np.int64(17), np.int64(7)), h=-4.01
Steps 54: (np.int64(17), np.int64(7)), dist: 27
Step: 55 - 15 candidates
H_values: [ 49.00914634 44.1097561 39.08536585 -14.1504065 44.63414634
511.57556193 -8.79268293 -7.7754065 44.63414634 480.09052533
105.89837398 1.55792683 154.63414634 119.85670732 22.62398374]
J_matrix: (15, 15), nonzero: 105
QAOA bitstring: 010010100011011 (7 ones)
Selected indices: [13, 10, 8, 4, 3, 1, 0]
Selected: idx=3, pos=(np.int64(16), np.int64(5)), h=-14.15
Steps 55: (np.int64(16), np.int64(5)), dist: 28
Step: 56 - 14 candidates
H_values: [-19.42479675 44.00914634 39.1097561 -13.87601626 -24.25813008
39.1097561 -8.64329268 -8.37601626 -23.50813008 44.13414634
-3.20223577 -8.16768293 89.63930582 0.89837398]
J_matrix: (14, 14), nonzero: 91
QAOA bitstring: 11001100110111 (9 ones)
Selected indices: [13, 12, 9, 8, 5, 4, 2, 1, 0]
Selected: idx=4, pos=(np.int64(15), np.int64(5)), h=-24.26
Steps 56: (np.int64(15), np.int64(5)), dist: 27
Step: 57 - 15 candidates
H_values: [-24.05691057 39.08536585 -13.9004065 44.63414634 39.08536585
-8.87601626 -8.60873984 44.63414634 44.1097561 -3.64329268
100.65462494 49.13414634 -3.64329268 -8.66768293 -13.2754065 ]
J_matrix: (15, 15), nonzero: 105
QAOA bitstring: 111001101101011 (10 ones)
Selected indices: [14, 13, 12, 9, 8, 6, 5, 3, 1, 0]
Selected: idx=0, pos=(np.int64(13), np.int64(5)), h=-24.06
Steps 57: (np.int64(13), np.int64(5)), dist: 25
Step: 58 - 12 candidates
H_values: [139.08536585 160.13414634 48.08536585 39.03658537 44.58536585
44.06097561 95.8495935 59.75914634 49.08536585 95.51626016
99.74649955 54.50914634]
J_matrix: (12, 12), nonzero: 66
QAOA bitstring: 001001111001 (6 ones)
Selected indices: [9, 6, 5, 4, 3, 0]
Selected: idx=3, pos=(np.int64(12), np.int64(7)), h=39.04
Steps 58: (np.int64(12), np.int64(7)), dist: 22
Step: 59 - 12 candidates
H_values: [ -8.80691057 54.21036585 54.81097561 -13.02947154 62.83536585
60.06097561 44.51219512 -12.84552846 99.81430155 54.93597561
59.2347561 54.33536585]
J_matrix: (12, 12), nonzero: 66
QAOA bitstring: 101110011110 (8 ones)
Selected indices: [11, 9, 8, 7, 4, 3, 2, 1]
Selected: idx=3, pos=(np.int64(11), np.int64(9)), h=-13.03
Steps 59: (np.int64(11), np.int64(9)), dist: 21
Step: 60 - 8 candidates
H_values: [ 97.04369919 2.72764228 164.08536585 2.9949187 59.18597561
60.03658537 526.85801394 -12.34552846]
J_matrix: (8, 8), nonzero: 28
QAOA bitstring: 10000100 (2 ones)
Selected indices: [7, 2]
Selected: idx=7, pos=(np.int64(12), np.int64(9)), h=-12.35
Steps 60: (np.int64(12), np.int64(9)), dist: 20
REACHABILITY: (np.int64(11), np.int64(11)) not completed from (np.int64(12), np.int64(9)) !
REACHABILITY: (np.int64(12), np.int64(11)) not completed from (np.int64(12), np.int64(9)) !
REACHABILITY: (np.int64(13), np.int64(11)) not completed from (np.int64(12), np.int64(9)) !
REACHABILITY: (np.int64(14), np.int64(10)) not completed from (np.int64(12), np.int64(9)) !
Step: 61 - 6 candidates
H_values: [ -2.6300813 59.06097561 100.82579161 491.71761985 60.01219512
159.18597561]
J_matrix: (6, 6), nonzero: 15
QAOA bitstring: 111011 (5 ones)
Selected indices: [5, 4, 3, 1, 0]
Selected: idx=0, pos=(np.int64(10), np.int64(9)), h=-2.63
Steps 61: (np.int64(10), np.int64(9)), dist: 22
Step: 62 - 8 candidates
H_values: [ 97.27642276 0.75203252 95.7347561 3.22764228 154.18597561
50.43592394 149.01219512 89.91883936]
J_matrix: (8, 8), nonzero: 28
QAOA bitstring: 10100110 (4 ones)
Selected indices: [7, 5, 2, 1]
Selected: idx=1, pos=(np.int64(8), np.int64(9)), h=0.75
Steps 62: (np.int64(8), np.int64(9)), dist: 24
Step: 63 - 9 candidates
H_values: [ -2.46646341 0.46747967 97.1097561 105.15853659 -7.22357724
-7.22357724 85.6097561 -12.27235772 89.83531418]
J_matrix: (9, 9), nonzero: 36
QAOA bitstring: 001111101 (6 ones)
Selected indices: [6, 5, 4, 3, 2, 0]
Selected: idx=5, pos=(np.int64(8), np.int64(8)), h=-7.22
Steps 63: (np.int64(8), np.int64(8)), dist: 25
Step: 64 - 9 candidates
H_values: [ -7.46646341 -4.53252033 107.18292683 -6.99085366 88.50203252
85.96747967 -23.08130081 148.46036585 144.82142143]
J_matrix: (9, 9), nonzero: 36
QAOA bitstring: 011000000 (2 ones)
Selected indices: [7, 6]
Selected: idx=6, pos=(np.int64(9), np.int64(8)), h=-23.08
Steps 64: (np.int64(9), np.int64(8)), dist: 24
Step: 65 - 11 candidates
H_values: [105.28353659 -7.49085366 -12.72357724 96.78353659 100.51959216
-8.90752033 -8.7652439 -12.27235772 86.06808943 148.68597561
144.51219512]
J_matrix: (11, 11), nonzero: 55
QAOA bitstring: 00010010111 (5 ones)
Selected indices: [7, 4, 2, 1, 0]
Selected: idx=2, pos=(np.int64(7), np.int64(9)), h=-12.72
Steps 65: (np.int64(7), np.int64(9)), dist: 25
Step: 66 - 8 candidates
H_values: [ 97.3495935 0.96747967 92.25203252 0.15853659 -6.99085366
48.47599085 89.36359166 -12.77235772]
J_matrix: (8, 8), nonzero: 28
QAOA bitstring: 00100101 (3 ones)
Selected indices: [5, 2, 0]
Selected: idx=5, pos=(np.int64(8), np.int64(9)), h=48.48
Steps 66: (np.int64(8), np.int64(9)), dist: 24
Step: 67 - 9 candidates
H_values: [ -2.46646341 0.46747967 97.1097561 105.15853659 100.50658149
60.49437148 85.6097561 -12.27235772 49.41158537]
J_matrix: (9, 9), nonzero: 36
QAOA bitstring: 001100101 (4 ones)
Selected indices: [6, 5, 2, 0]
Selected: idx=0, pos=(np.int64(6), np.int64(8)), h=-2.47
Steps 67: (np.int64(6), np.int64(8)), dist: 27
Step: 68 - 10 candidates
H_values: [106.10670732 -7.41768293 86.55792683 -7.2754065 -14.65752033
-13.5152439 97.05792683 -22.49085366 44.35789043 514.85099085]
J_matrix: (10, 10), nonzero: 45
QAOA bitstring: 0100111111 (7 ones)
Selected indices: [8, 5, 4, 3, 2, 1, 0]
Selected: idx=4, pos=(np.int64(6), np.int64(9)), h=-14.66
Steps 68: (np.int64(6), np.int64(9)), dist: 26
Step: 69 - 10 candidates
H_values: [ 97.58231707 107.66565041 81.77642276 100.54315197 -12.7652439
-12.74796748 95.28353659 44.98289043 49.1097561 479.96415373]
J_matrix: (10, 10), nonzero: 45
QAOA bitstring: 0101111111 (8 ones)
Selected indices: [8, 6, 5, 4, 3, 2, 1, 0]
Selected: idx=4, pos=(np.int64(6), np.int64(10)), h=-12.77
Steps 69: (np.int64(6), np.int64(10)), dist: 25
Step: 70 - 9 candidates
H_values: [ 87.09247967 97.3495935 81.75203252 60.03167091 104.01293422
-12.24796748 -12.77235772 87.50914634 584.95301291]
J_matrix: (9, 9), nonzero: 36
QAOA bitstring: 111100101 (6 ones)
Selected indices: [8, 7, 6, 5, 2, 0]
Selected: idx=6, pos=(np.int64(6), np.int64(12)), h=-12.77
Steps 70: (np.int64(6), np.int64(12)), dist: 23
Step: 71 - 6 candidates
H_values: [ -3.03252033 -8.05691057 87.25203252 -7.24796748 105.23289043
3.25203252]
J_matrix: (6, 6), nonzero: 15
QAOA bitstring: 100000 (1 ones)
Selected indices: [5]
Selected: idx=5, pos=(np.int64(6), np.int64(11)), h=3.25
Steps 71: (np.int64(6), np.int64(11)), dist: 24
Step: 72 - 8 candidates
H_values: [105.15853659 -8.03252033 -13.05691057 -7.22357724 63.3662892
65.72207494 90.42862267 154.6097561 ]
J_matrix: (8, 8), nonzero: 28
QAOA bitstring: 01010000 (2 ones)
Selected indices: [6, 4]
Selected: idx=4, pos=(np.int64(6), np.int64(9)), h=63.37
Steps 72: (np.int64(6), np.int64(9)), dist: 26
Step: 73 - 10 candidates
H_values: [ 97.58231707 107.66565041 81.77642276 60.15853659 50.33686877
89.94768469 95.28353659 44.6097561 49.1097561 479.58536585]
J_matrix: (10, 10), nonzero: 45
QAOA bitstring: 1001010110 (5 ones)
Selected indices: [9, 6, 4, 2, 1]
Selected: idx=4, pos=(np.int64(6), np.int64(10)), h=50.34
Steps 73: (np.int64(6), np.int64(10)), dist: 25
Step: 74 - 9 candidates
H_values: [ 87.09247967 97.3495935 81.75203252 11.65853659 61.9912892
2.43747853 1.90819783 87.50914634 110.58536585]
J_matrix: (9, 9), nonzero: 36
QAOA bitstring: 101100010 (4 ones)
Selected indices: [8, 6, 5, 1]
Selected: idx=6, pos=(np.int64(6), np.int64(12)), h=1.91
Steps 74: (np.int64(6), np.int64(12)), dist: 23
Step: 75 - 6 candidates
H_values: [-3.03252033 -8.05691057 87.25203252 -7.24796748 63.21186877 17.92783161]
J_matrix: (6, 6), nonzero: 15
QAOA bitstring: 111110 (5 ones)
Selected indices: [5, 4, 3, 2, 1]
Selected: idx=1, pos=(np.int64(4), np.int64(12)), h=-8.06
Steps 75: (np.int64(4), np.int64(12)), dist: 25
Step: 76 - 11 candidates
H_values: [ 86.42581301 97.14126016 0.75914634 0.28353659 -7.40752033
-22.74796748 -15.31402439 -22.74796748 79.32825203 6.91869919
47.90819783]
J_matrix: (11, 11), nonzero: 55
QAOA bitstring: 01010101110 (6 ones)
Selected indices: [9, 7, 5, 3, 2, 1]
Selected: idx=7, pos=(np.int64(5), np.int64(12)), h=-22.75
Steps 76: (np.int64(5), np.int64(12)), dist: 24
Step: 77 - 8 candidates
H_values: [ 0.13414634 86.94308943 105.15853659 52.32722185 89.56097561
-7.22357724 118.19308943 8.39881345]
J_matrix: (8, 8), nonzero: 28
QAOA bitstring: 10011001 (4 ones)
Selected indices: [7, 4, 3, 0]
Selected: idx=0, pos=(np.int64(3), np.int64(12)), h=0.13
Steps 77: (np.int64(3), np.int64(12)), dist: 26
Step: 78 - 8 candidates
H_values: [ 87.74186992 80.3597561 -22.93191057 95.40853659 -3.05691057
79.81097561 81.77642276 36.42320369]
J_matrix: (8, 8), nonzero: 28
QAOA bitstring: 01011100 (4 ones)
Selected indices: [6, 4, 3, 2]
Selected: idx=2, pos=(np.int64(3), np.int64(13)), h=-22.93
Steps 78: (np.int64(3), np.int64(13)), dist: 25
Step: 79 - 10 candidates
H_values: [ 97.55792683 -7.25813008 87.30081301 -8.07418699 55.84247967
87.09247967 -22.74796748 71.70325203 101.41431322 79.32825203]
J_matrix: (10, 10), nonzero: 45
QAOA bitstring: 1001111111 (8 ones)
Selected indices: [9, 6, 5, 4, 3, 2, 1, 0]
Selected: idx=6, pos=(np.int64(4), np.int64(13)), h=-22.75
Steps 79: (np.int64(4), np.int64(13)), dist: 24
Step: 80 - 11 candidates
H_values: [ -8.69918699 85.6097561 52.31370347 81.06097561 -8.03252033
12.30121179 -14.93902439 -23.29674797 87.27642276 112.56097561
79.51219512]
J_matrix: (11, 11), nonzero: 55
QAOA bitstring: 00010001111 (5 ones)
Selected indices: [7, 3, 2, 1, 0]
Selected: idx=7, pos=(np.int64(4), np.int64(15)), h=-23.30
Steps 80: (np.int64(4), np.int64(15)), dist: 22
REACHABILITY: (np.int64(2), np.int64(14)) not completed from (np.int64(4), np.int64(15)) !
REACHABILITY: (np.int64(6), np.int64(15)) not completed from (np.int64(4), np.int64(15)) !
Step: 81 - 10 candidates
H_values: [ 94.72764228 116.80526892 -7.93902439 51.91004118 0.56097561
-23.48780488 -23.34552846 70.96341463 89.51219512 70.96341463]
J_matrix: (10, 10), nonzero: 45
QAOA bitstring: 0000000110 (2 ones)
Selected indices: [2, 1]
Selected: idx=2, pos=(np.int64(3), np.int64(15)), h=-7.94
Steps 81: (np.int64(3), np.int64(15)), dist: 23
Step: 82 - 7 candidates
H_values: [ 87.66869919 -15.04674797 106.90182155 36.85709819 71.65447154
89.45325203 70.90447154]
J_matrix: (7, 7), nonzero: 21
QAOA bitstring: 1010001 (3 ones)
Selected indices: [6, 4, 0]
Selected: idx=6, pos=(np.int64(5), np.int64(16)), h=70.90
Steps 82: (np.int64(5), np.int64(16)), dist: 20
Step: 83 - 13 candidates
H_values: [ 1.56877431e+02 7.82520325e-02 1.05310976e+02 -7.73780488e+00
-1.83699187e+01 -2.32865854e+01 -1.51026423e+01 9.52621951e+01
-2.32865854e+01 8.20813008e+01 8.14217480e+01 -1.53109756e+01
8.20813008e+01]
J_matrix: (13, 13), nonzero: 78
QAOA bitstring: 0100001100000 (3 ones)
Selected indices: [11, 6, 5]
Selected: idx=5, pos=(np.int64(5), np.int64(17)), h=-23.29
Steps 83: (np.int64(5), np.int64(17)), dist: 19
Step: 84 - 9 candidates
H_values: [104.95325203 95.23780488 116.84146341 -7.34552846 81.60569106
52.17530488 -14.60264228 86.94613821 89.68902439]
J_matrix: (9, 9), nonzero: 36
QAOA bitstring: 100100100 (3 ones)
Selected indices: [8, 5, 2]
Selected: idx=5, pos=(np.int64(5), np.int64(16)), h=52.18
Steps 84: (np.int64(5), np.int64(16)), dist: 20
Step: 85 - 13 candidates
H_values: [ 1.16862180e+02 7.82520325e-02 1.05310976e+02 -7.73780488e+00
-1.83699187e+01 3.67720566e+01 -1.51026423e+01 9.52621951e+01
-2.32865854e+01 8.20813008e+01 8.14217480e+01 -1.53109756e+01
8.20813008e+01]
J_matrix: (13, 13), nonzero: 78
QAOA bitstring: 1001110111110 (9 ones)
Selected indices: [12, 9, 8, 7, 5, 4, 3, 2, 1]
Selected: idx=8, pos=(np.int64(6), np.int64(16)), h=-23.29
Steps 85: (np.int64(6), np.int64(16)), dist: 19
Step: 86 - 11 candidates
H_values: [116.53658537 -8.23780488 87.15447154 104.95325203 58.16042393
89.89735772 0.26219512 -7.55386179 -13.26219512 -14.81097561
81.18902439]
J_matrix: (11, 11), nonzero: 55
QAOA bitstring: 00101110100 (5 ones)
Selected indices: [8, 6, 5, 4, 2]
Selected: idx=8, pos=(np.int64(7), np.int64(14)), h=-13.26
Steps 86: (np.int64(7), np.int64(14)), dist: 20
Step: 87 - 9 candidates
H_values: [-4.67479675e-02 7.62195122e-01 4.12646195e+01 7.62195122e-01
-2.30782520e+01 -1.53109756e+01 8.71788618e+01 8.05467480e+01
7.93313008e+01]
J_matrix: (9, 9), nonzero: 36
QAOA bitstring: 011011011 (6 ones)
Selected indices: [7, 6, 4, 3, 1, 0]
Selected: idx=4, pos=(np.int64(7), np.int64(15)), h=-23.08
Steps 87: (np.int64(7), np.int64(15)), dist: 19
Step: 88 - 12 candidates
H_values: [104.82825203 112.52850255 -7.55386179 0.13719512 52.16042393
-14.93597561 -12.91869919 86.27947154 -23.43597561 80.39735772
-15.79369919 79.84857724]
J_matrix: (12, 12), nonzero: 66
QAOA bitstring: 010100011000 (4 ones)
Selected indices: [10, 8, 4, 3]
Selected: idx=8, pos=(np.int64(8), np.int64(15)), h=-23.44
Steps 88: (np.int64(8), np.int64(15)), dist: 18
Step: 89 - 11 candidates
H_values: [105.26219512 -8.05386179 106.75077096 105.26219512 52.25753228
92.08130081 86.04674797 -15.16869919 80.24085366 81.16463415
71.53252033]
J_matrix: (11, 11), nonzero: 55
QAOA bitstring: 01101010100 (5 ones)
Selected indices: [9, 8, 6, 4, 2]
Selected: idx=4, pos=(np.int64(7), np.int64(15)), h=52.26
Steps 89: (np.int64(7), np.int64(15)), dist: 19
Step: 90 - 12 candidates
H_values: [104.82825203 112.23780488 -7.55386179 0.13719512 12.14689579
-14.93597561 -12.91869919 86.27947154 36.60472206 80.39735772
-15.79369919 79.84857724]
J_matrix: (12, 12), nonzero: 66
QAOA bitstring: 010001001010 (4 ones)
Selected indices: [10, 6, 3, 1]
Selected: idx=10, pos=(np.int64(9), np.int64(15)), h=-15.79
Steps 90: (np.int64(9), np.int64(15)), dist: 17
Step: 91 - 13 candidates
H_values: [116.76558266 57.74431351 95.18902439 96.52947154 12.2231153
-8.82825203 -8.35264228 -14.65142276 -14.75914634 86.48069106
71.71646341 89.43191057 79.38313008]
J_matrix: (13, 13), nonzero: 78
QAOA bitstring: 0101001010110 (6 ones)
Selected indices: [11, 9, 6, 4, 2, 1]
Selected: idx=6, pos=(np.int64(9), np.int64(14)), h=-8.35
Steps 91: (np.int64(9), np.int64(14)), dist: 18
Step: 92 - 13 candidates
H_values: [105.26219512 112.73813991 97.17886179 -7.84552846 -8.20325203
40.19872506 -15.15142276 -12.8699187 -23.33536585 71.53252033
-19.04369919 -15.56808943 79.19918699]
J_matrix: (13, 13), nonzero: 78
QAOA bitstring: 0011010000010 (4 ones)
Selected indices: [10, 9, 7, 1]
Selected: idx=10, pos=(np.int64(11), np.int64(13)), h=-19.04
Steps 92: (np.int64(11), np.int64(13)), dist: 17
Step: 93 - 13 candidates
H_values: [ -2.84552846 -8.82825203 94.59492327 5.23780488 -8.01930894
2.42174797 -7.60264228 -15.06808943 -15.92581301 97.39735772
-15.06808943 -13.12703252 71.55691057]
J_matrix: (13, 13), nonzero: 78
QAOA bitstring: 1011111011011 (10 ones)
Selected indices: [12, 10, 9, 8, 7, 6, 4, 3, 1, 0]
Selected: idx=8, pos=(np.int64(11), np.int64(15)), h=-15.93
Steps 93: (np.int64(11), np.int64(15)), dist: 15
Step: 94 - 10 candidates
H_values: [164.71374966 95.34857724 96.48069106 81.71646341 99.69241192
0.43191057 -15.11686992 94.93191057 71.66768293 71.29979675]
J_matrix: (10, 10), nonzero: 45
QAOA bitstring: 0101010000 (3 ones)
Selected indices: [8, 6, 4]
Selected: idx=6, pos=(np.int64(11), np.int64(16)), h=-15.12
Steps 94: (np.int64(11), np.int64(16)), dist: 14
Step: 95 - 12 candidates
H_values: [ 1.68180592e+02 3.48577236e-01 9.57408537e+01 9.66646341e+01
-7.46747967e+00 -6.80894309e-02 1.03515579e+02 -2.34329268e+01
8.01432927e+01 8.70325203e+01 -2.17002033e+01 7.14837398e+01]
J_matrix: (12, 12), nonzero: 66
QAOA bitstring: 111100110011 (8 ones)
Selected indices: [11, 10, 9, 8, 5, 4, 1, 0]
Selected: idx=10, pos=(np.int64(13), np.int64(16)), h=-21.70
Steps 95: (np.int64(13), np.int64(16)), dist: 14
Step: 96 - 11 candidates
H_values: [157.75967086 89.36320255 -23.55792683 -19.85670732 -7.94308943
-7.46747967 -23.01626016 -15.24898374 5.78963415 0.82418699
89.44207317]
J_matrix: (11, 11), nonzero: 55
QAOA bitstring: 01000000111 (4 ones)
Selected indices: [9, 2, 1, 0]
Selected: idx=2, pos=(np.int64(12), np.int64(16)), h=-23.56
Steps 96: (np.int64(12), np.int64(16)), dist: 13
Step: 97 - 12 candidates
H_values: [-12.96747967 82.21646341 99.80691057 58.48242086 86.95934959
-22.83231707 -14.85670732 92.05691057 95.11028062 -15.24898374
100.55691057 -4.67581301]
J_matrix: (12, 12), nonzero: 66
QAOA bitstring: 111100101000 (6 ones)
Selected indices: [11, 10, 9, 8, 5, 3]
Selected: idx=5, pos=(np.int64(12), np.int64(17)), h=-22.83
Steps 97: (np.int64(12), np.int64(17)), dist: 12
Step: 98 - 9 candidates
H_values: [ 91.90752033 162.49858562 99.70803062 -14.35670732 -14.88109756
91.90752033 -12.64126016 100.07418699 89.69207317]
J_matrix: (9, 9), nonzero: 36
QAOA bitstring: 111000110 (5 ones)
Selected indices: [8, 7, 6, 2, 1]
Selected: idx=6, pos=(np.int64(13), np.int64(17)), h=-12.64
Steps 98: (np.int64(13), np.int64(17)), dist: 13
Step: 99 - 9 candidates
H_values: [157.72156546 81.95934959 84.55584082 80.11890244 -7.96747967
59.97419537 -14.87398374 105.55691057 95.17479675]
J_matrix: (9, 9), nonzero: 36
QAOA bitstring: 001100100 (3 ones)
Selected indices: [6, 5, 2]
Selected: idx=6, pos=(np.int64(13), np.int64(18)), h=-14.87
Steps 99: (np.int64(13), np.int64(18)), dist: 12
Step: 100 - 11 candidates
H_values: [-11.04065041 54.44717521 -14.35670732 79.88617886 59.59398867
100.07748984 105.32418699 0.44207317 97.03252033 0.29979675
86.44207317]
J_matrix: (11, 11), nonzero: 55
QAOA bitstring: 01011100001 (5 ones)
Selected indices: [9, 7, 6, 5, 0]
Selected: idx=0, pos=(np.int64(11), np.int64(18)), h=-11.04
Steps 100: (np.int64(11), np.int64(18)), dist: 12
REACHABILITY: (np.int64(9), np.int64(17)) not completed from (np.int64(11), np.int64(18)) !
REACHABILITY: (np.int64(9), np.int64(18)) not completed from (np.int64(11), np.int64(18)) !
REACHABILITY: (np.int64(10), np.int64(16)) not completed from (np.int64(11), np.int64(18)) !
REACHABILITY: (np.int64(11), np.int64(16)) not completed from (np.int64(11), np.int64(18)) !
REACHABILITY: (np.int64(11), np.int64(20)) not completed from (np.int64(11), np.int64(18)) !
Step: 101 - 5 candidates
H_values: [154.31707317 -14.35670732 79.88617886 154.57217521 89.42541489]
J_matrix: (5, 5), nonzero: 10
QAOA bitstring: 01111 (4 ones)
Selected indices: [3, 2, 1, 0]
Selected: idx=1, pos=(np.int64(12), np.int64(18)), h=-14.36
Steps 101: (np.int64(12), np.int64(18)), dist: 11
Step: 102 - 10 candidates
H_values: [162.34146341 100.42278497 85.11890244 58.94207317 60.04020768
-14.38109756 -15.23882114 59.09146341 58.29520818 -5.30792683]
J_matrix: (10, 10), nonzero: 45
QAOA bitstring: 1110111100 (7 ones)
Selected indices: [9, 8, 7, 5, 4, 3, 2]
Selected: idx=5, pos=(np.int64(12), np.int64(19)), h=-14.38
Steps 102: (np.int64(12), np.int64(19)), dist: 10
Step: 103 - 8 candidates
H_values: [ 76.5945122 59.29268293 103.52081794 -14.73882114 -23.76321138
159.43717121 75.92784553 99.69207317]
J_matrix: (8, 8), nonzero: 28
QAOA bitstring: 01110111 (6 ones)
Selected indices: [6, 5, 4, 2, 1, 0]
Selected: idx=4, pos=(np.int64(12), np.int64(21)), h=-23.76
Steps 103: (np.int64(12), np.int64(21)), dist: 8
Step: 104 - 12 candidates
H_values: [-12.25609756 -19.61382114 -10.9054878 -26.49593496 106.49390244
4.38617886 -25.99593496 -16.35365854 -11.44715447 102.93495935
-11.58943089 89.55284553]
J_matrix: (12, 12), nonzero: 66
QAOA bitstring: 100101011011 (7 ones)
Selected indices: [11, 8, 6, 4, 3, 1, 0]
Selected: idx=3, pos=(np.int64(11), np.int64(23)), h=-26.50
Steps 104: (np.int64(11), np.int64(23)), dist: 7
Step: 105 - 12 candidates
H_values: [ 1.86890244 -5.48882114 87.15345528 1.86890244 -5.01321138
-4.4054878 -4.13821138 -16.97865854 -5.00304878 95.9426467
-15.72865854 75.18089431]
J_matrix: (12, 12), nonzero: 66
QAOA bitstring: 011011111011 (9 ones)
Selected indices: [10, 9, 7, 6, 5, 4, 3, 1, 0]
Selected: idx=7, pos=(np.int64(11), np.int64(24)), h=-16.98
Steps 105: (np.int64(11), np.int64(24)), dist: 6
Step: 106 - 8 candidates
H_values: [101.26117886 101.26117886 -4.76321138 103.16582975 -4.50304878
-17.61077236 87.87906504 87.66361789]
J_matrix: (8, 8), nonzero: 28
QAOA bitstring: 01000000 (1 ones)
Selected indices: [6]
Selected: idx=6, pos=(np.int64(12), np.int64(22)), h=87.88
Steps 106: (np.int64(12), np.int64(22)), dist: 7
Step: 107 - 10 candidates
H_values: [ -5.13109756 -12.48882114 -19.51321138 4.11890244 -11.13821138
184.88905991 3.88617886 63.43321719 -15.72865854 95.41056911]
J_matrix: (10, 10), nonzero: 45
QAOA bitstring: 0001001000 (2 ones)
Selected indices: [6, 3]
Selected: idx=6, pos=(np.int64(12), np.int64(20)), h=3.89
Steps 107: (np.int64(12), np.int64(20)), dist: 9
Step: 108 - 10 candidates
H_values: [ 80.74390244 168.29268293 -2.38109756 -26.13821138 66.26829268
66.74390244 41.92876681 81.28611632 166.16768293 81.41056911]
J_matrix: (10, 10), nonzero: 45
QAOA bitstring: 0000000000 (0 ones)
Selected indices: []
WARNING: No selection, fallback to best h
Selected: idx=0, pos=(np.int64(10), np.int64(21)), h=80.74
Steps 108: (np.int64(10), np.int64(21)), dist: 10
Step: 109 - 9 candidates
H_values: [ 86.51829268 80.63617886 -23.86382114 -24.38821138 -22.9054878
38.90221319 192.45760743 43.69512195 38.90658076]
J_matrix: (9, 9), nonzero: 36
QAOA bitstring: 101111100 (6 ones)
Selected indices: [8, 6, 5, 4, 3, 2]
Selected: idx=3, pos=(np.int64(10), np.int64(23)), h=-24.39
Steps 109: (np.int64(10), np.int64(23)), dist: 8
Step: 110 - 12 candidates
H_values: [ 2.01829268 -5.21443089 87.42784553 -4.73882114 88.71239837
102.9797515 -4.73882114 -11.4054878 41.67073171 87.99695122
48.40221319 -16.10365854]
J_matrix: (12, 12), nonzero: 66
QAOA bitstring: 110100000100 (4 ones)
Selected indices: [11, 10, 8, 2]
Selected: idx=11, pos=(np.int64(12), np.int64(23)), h=-16.10
Steps 110: (np.int64(12), np.int64(23)), dist: 6
Step: 111 - 8 candidates
H_values: [-5.36382114 95.80376681 -4.4054878 56.17073171 94.99695122 62.69512195
63.39800443 95.17784553]
J_matrix: (8, 8), nonzero: 28
QAOA bitstring: 00000000 (0 ones)
Selected indices: []
WARNING: No selection, fallback to best h
Selected: idx=0, pos=(np.int64(10), np.int64(22)), h=-5.36
Steps 111: (np.int64(10), np.int64(22)), dist: 9
Step: 112 - 12 candidates
H_values: [ -4.98170732 -12.21443089 -4.50609756 79.90345528 63.47117517
41.92447975 97.11890244 -25.63821138 137.64634146 48.19512195
41.17073171 79.87782294]
J_matrix: (12, 12), nonzero: 66
QAOA bitstring: 101110101000 (6 ones)
Selected indices: [11, 9, 8, 7, 5, 3]
Selected: idx=7, pos=(np.int64(11), np.int64(22)), h=-25.64
Steps 112: (np.int64(11), np.int64(22)), dist: 8
Step: 113 - 10 candidates
H_values: [ -5.25609756 -12.61382114 103.07386999 4.11890244 -3.9054878
41.54573171 44.64634146 59.2195122 41.54573171 88.05284553]
J_matrix: (10, 10), nonzero: 45
QAOA bitstring: 1100101000 (4 ones)
Selected indices: [9, 8, 5, 3]
Selected: idx=3, pos=(np.int64(11), np.int64(20)), h=4.12
Steps 113: (np.int64(11), np.int64(20)), dist: 10
Step: 114 - 7 candidates
H_values: [148.44473742 -22.9054878 83.79739468 157.76829268 47.5945122
38.42073171 70.92784553]
J_matrix: (7, 7), nonzero: 21
QAOA bitstring: 0010001 (2 ones)
Selected indices: [4, 0]
Selected: idx=4, pos=(np.int64(12), np.int64(20)), h=47.59
Steps 114: (np.int64(12), np.int64(20)), dist: 9
Step: 115 - 10 candidates
H_values: [148.49390244 168.29268293 99.96912766 41.41833624 66.26829268
66.74390244 41.69512195 41.04573171 166.16768293 81.41056911]
J_matrix: (10, 10), nonzero: 45
QAOA bitstring: 1000000100 (2 ones)
Selected indices: [9, 2]
Selected: idx=9, pos=(np.int64(14), np.int64(21)), h=81.41
Steps 115: (np.int64(14), np.int64(21)), dist: 10
Step: 116 - 12 candidates
H_values: [ 6.24442726e+02 4.36951220e+01 1.38545732e+02 -2.34471545e+01
-6.50406504e-02 -1.49471545e+01 -1.34715447e+01 9.63170732e+01
-7.35670732e+00 -4.34959350e+00 -8.70731707e+00 -1.43983740e+01]
J_matrix: (12, 12), nonzero: 66
QAOA bitstring: 110101110010 (7 ones)
Selected indices: [11, 10, 8, 6, 5, 4, 1]
Selected: idx=5, pos=(np.int64(14), np.int64(22)), h=-14.95
Steps 116: (np.int64(14), np.int64(22)), dist: 9
Step: 117 - 10 candidates
H_values: [148.19512195 3.05995935 103.46514138 -15.34654472 -17.03760163
1.91768293 -4.29776423 89.57012195 1.91768293 -5.77337398]
J_matrix: (10, 10), nonzero: 45
QAOA bitstring: 0111111111 (9 ones)
Selected indices: [8, 7, 6, 5, 4, 3, 2, 1, 0]
Selected: idx=4, pos=(np.int64(14), np.int64(24)), h=-17.04
Steps 117: (np.int64(14), np.int64(24)), dist: 7
Step: 118 - 8 candidates
H_values: [ 75.05589431 105.93881044 5.65345528 -16.8953252 101.70223577
4.32012195 88.27134146 2.8445122 ]
J_matrix: (8, 8), nonzero: 28
QAOA bitstring: 11011001 (5 ones)
Selected indices: [7, 6, 4, 3, 0]
Selected: idx=3, pos=(np.int64(14), np.int64(25)), h=-16.90
Steps 118: (np.int64(14), np.int64(25)), dist: 6
Step: 119 - 7 candidates
H_values: [-17.81910569 -4.96138211 5.27845528 106.88812301 4.08739837
80.20528455 109.9695122 ]
J_matrix: (7, 7), nonzero: 21
QAOA bitstring: 1010000 (2 ones)
Selected indices: [6, 4]
Selected: idx=4, pos=(np.int64(15), np.int64(25)), h=4.09
Steps 119: (np.int64(15), np.int64(25)), dist: 7
Step: 120 - 9 candidates
H_values: [ -5.21138211 98.52845528 85.3618587 72.76422764 4.57012195
-17.85365854 -26.54471545 79.4796748 101.41056911]
J_matrix: (9, 9), nonzero: 36
QAOA bitstring: 100110001 (4 ones)
Selected indices: [8, 5, 4, 0]
Selected: idx=5, pos=(np.int64(15), np.int64(26)), h=-17.85
Steps 120: (np.int64(15), np.int64(26)), dist: 6
REACHABILITY: (np.int64(17), np.int64(25)) not completed from (np.int64(15), np.int64(26)) !
REACHABILITY: (np.int64(17), np.int64(26)) not completed from (np.int64(15), np.int64(26)) !
Step: 121 - 11 candidates
H_values: [101.78861789 74.7398374 159.38081574 65.07317073 4.07012195
106.88440692 -25.91971545 -28.11077236 110.4695122 80.78861789
86.92073171]
J_matrix: (11, 11), nonzero: 55
QAOA bitstring: 11001101100 (6 ones)
Selected indices: [10, 9, 6, 5, 3, 2]
Selected: idx=6, pos=(np.int64(15), np.int64(27)), h=-25.92
Steps 121: (np.int64(15), np.int64(27)), dist: 5
Step: 122 - 12 candidates
H_values: [-18.2601626 159.3546748 -19.73577236 -13.74288618 66.38081574
106.73320587 -27.61077236 -17.21849593 -5.3953252 100.48678862
-6.20426829 -11.8953252 ]
J_matrix: (12, 12), nonzero: 66
QAOA bitstring: 011001111101 (8 ones)
Selected indices: [10, 9, 6, 5, 4, 3, 2, 0]
Selected: idx=6, pos=(np.int64(15), np.int64(28)), h=-27.61
Steps 122: (np.int64(15), np.int64(28)), dist: 4
Step: 123 - 9 candidates
H_values: [ 88.3648374 -27.42682927 65.7296748 102.83203525 -16.71849593
-4.58638211 0.29573171 -5.3953252 99.41361789]
J_matrix: (9, 9), nonzero: 36
QAOA bitstring: 101000001 (3 ones)
Selected indices: [8, 6, 0]
Selected: idx=6, pos=(np.int64(17), np.int64(27)), h=0.30
Steps 123: (np.int64(17), np.int64(27)), dist: 7
Step: 124 - 14 candidates
H_values: [151.8512595 41.32856279 71.80589431 -26.5203252 -5.44715447
-5.51321138 -25.8953252 -15.08638211 2.41056911 -4.13821138
-9.43699187 11.32723577 4.30284553 -2.09654472]
J_matrix: (14, 14), nonzero: 91
QAOA bitstring: 01100000111110 (7 ones)
Selected indices: [12, 11, 5, 4, 3, 2, 1]
Selected: idx=3, pos=(np.int64(16), np.int64(27)), h=-26.52
Steps 124: (np.int64(16), np.int64(27)), dist: 6
Step: 125 - 12 candidates
H_values: [-20.23577236 -34.92682927 159.17073171 41.82520325 75.78150407
-25.71138211 101.55284553 103.25234328 91.91361789 102.17784553
-4.63821138 -11.03760163]
J_matrix: (12, 12), nonzero: 66
QAOA bitstring: 000100101111 (6 ones)
Selected indices: [8, 5, 3, 2, 1, 0]
Selected: idx=1, pos=(np.int64(14), np.int64(28)), h=-34.93
Steps 125: (np.int64(14), np.int64(28)), dist: 3
Step: 126 - 7 candidates
H_values: [ 99.38211382 1.26422764 -6.24288618 172.39634146 60.67417388
108.8512595 -5.21138211]
J_matrix: (7, 7), nonzero: 21
QAOA bitstring: 0000101 (2 ones)
Selected indices: [2, 0]
Selected: idx=2, pos=(np.int64(14), np.int64(29)), h=-6.24
Steps 126: (np.int64(14), np.int64(29)), dist: 2
Step: 127 - 6 candidates
H_values: [88.6148374 -6.36077236 93.65142276 61.87195122 4.78150407 94.66361789]
J_matrix: (6, 6), nonzero: 15
QAOA bitstring: 011000 (2 ones)
Selected indices: [4, 3]
Selected: idx=4, pos=(np.int64(15), np.int64(29)), h=4.78
Steps 127: (np.int64(15), np.int64(29)), dist: 3
Step: 128 - 6 candidates
H_values: [-13.36077236 90.25039339 54.87195122 53.34756098 161.71975416
94.3546748 ]
J_matrix: (6, 6), nonzero: 15
QAOA bitstring: 110101 (4 ones)
Selected indices: [5, 4, 2, 0]
Selected: idx=0, pos=(np.int64(14), np.int64(27)), h=-13.36
Steps 128: (np.int64(14), np.int64(27)), dist: 4
Step: 129 - 10 candidates
H_values: [ -7.36788618 86.44105691 -17.7601626 39.27002113 49.74719319
173.17073171 62.99695122 91.27317073 62.34165396 -11.71138211]
J_matrix: (10, 10), nonzero: 45
QAOA bitstring: 0111010011 (6 ones)
Selected indices: [8, 7, 6, 4, 1, 0]
Selected: idx=0, pos=(np.int64(12), np.int64(27)), h=-7.37
Steps 129: (np.int64(12), np.int64(27)), dist: 2
Step: 130 - 5 candidates
H_values: [ -6.05894309 -1000. -3.5101626 96.54597367
146.26696918]
J_matrix: (5, 5), nonzero: 10
QAOA bitstring: 00011 (2 ones)
Selected indices: [1, 0]
Selected: idx=1, pos=(np.int64(12), np.int64(29)), h=-1000.00
Steps 130: (np.int64(12), np.int64(29)), dist: 0
Completed in 130 steps
time (s) 35.0 sekund
sec/step: 0.27
In [5]:
# === Run QAOA navigation ===
# Create navigator and find path from start to target
navigator.visualize_path(path)
print(f" Steps: {len(path)}")
print(f" Unique position: {len(set(path))}")
print(f" Repeat visits: {len(path) - len(set(path))}")
print(f" QAOA steps: {len(navigator.qaoa_calls)}")
print(
f" Manhattan length: {abs(target_pos[0]-start_pos[0]) + abs(target_pos[1]-start_pos[1])}"
)
Steps: 131 Unique position: 121 Repeat visits: 10 QAOA steps: 130 Manhattan length: 41
In [6]:
def generate_maze(height: int,
width: int,
complexity: float = 0.3) -> np.ndarray:
maze = np.zeros((height, width), dtype=int)
n_walls = int(height * width * complexity)
wall_positions = np.random.choice(height * width, n_walls, replace=False)
for pos in wall_positions:
y, x = divmod(pos, width)
if (y, x) not in [(0, 0), (height - 1, width - 1)]:
maze[y, x] = CellType.WALL.value
return maze
class CellType(Enum):
EMPTY = 0
WALL = 1
START = 0
GOAL = 0
maze = generate_maze(30, 50, 0.2)
start_pos = (0, 0)
target_pos = (29, 49)
navigator = QAOANavigator(maze, start_pos, target_pos, radius=2, p_layers=3)
navigator.max_steps = 500
start_time = time.time()
path = navigator.find_path()
elapsed = time.time() - start_time
print(f"\n time: {elapsed:.1f} sekund")
print(f"sec/steps: {elapsed/len(path):.2f}")
Step: 1 - 4 candidates
H_values: [-10.42948718 80.04487179 -11.94230769 71.54487179]
J_matrix: (4, 4), nonzero: 6
QAOA bitstring: 0010 (1 ones)
Selected indices: [1]
Selected: idx=1, pos=(1, 2), h=80.04
Steps 1: (1, 2), dist: 75
Step: 2 - 10 candidates
H_values: [224. 93.44871795 4.82051282 -5.60897436 -21.96794872
-23.1474359 -0.81730769 -23.63461538 -29.82692308 -25.1474359 ]
J_matrix: (10, 10), nonzero: 45
QAOA bitstring: 1111111000 (7 ones)
Selected indices: [9, 8, 7, 6, 5, 4, 3]
Selected: idx=8, pos=(2, 4), h=-29.83
Steps 2: (2, 4), dist: 72
Step: 3 - 15 candidates
H_values: [ 3.94871795 -3.2724359 108.46153846 -6.8974359 -18.33974359
-8.00961538 -7.5224359 -23.79807692 -24.64423077 86.2275641
-24.13141026 -29.32371795 81.24358974 -23.9775641 -28.99038462]
J_matrix: (15, 15), nonzero: 105
QAOA bitstring: 001101000000110 (5 ones)
Selected indices: [12, 11, 9, 2, 1]
Selected: idx=11, pos=(3, 6), h=-29.32
Steps 3: (3, 6), dist: 69
Step: 4 - 15 candidates
H_values: [ -2.61858974 -7.83974359 -12.8525641 104.92307692 -8.51923077
-9.00641026 -8.51923077 -23.50320513 -23.80769231 -13.4775641
-23.50320513 -28.82051282 -18.58653846 -23.59935897 -28.61217949]
J_matrix: (15, 15), nonzero: 105
QAOA bitstring: 000001000110111 (6 ones)
Selected indices: [9, 5, 4, 2, 1, 0]
Selected: idx=9, pos=(4, 4), h=-13.48
Steps 4: (4, 4), dist: 70
Step: 5 - 14 candidates
H_values: [ 96.9775641 72.42307692 -13.79807692 96.2275641 -8.63141026
114.25961538 -8.03525641 -7.75641026 -23.49038462 -24.00320513
-12.63141026 -22.86538462 -28.59935897 79.69230769]
J_matrix: (14, 14), nonzero: 91
QAOA bitstring: 10000011000111 (6 ones)
Selected indices: [13, 7, 6, 2, 1, 0]
Selected: idx=2, pos=(2, 5), h=-13.80
Steps 5: (2, 5), dist: 71
Step: 6 - 15 candidates
H_values: [ 8.94871795 1.7275641 -3.28525641 -1.96794872 -7.11858974
-18.3525641 -8.0224359 66.67307692 -24.01923077 -24.53205128
-24.01923077 -29.00320513 101.8974359 -23.99038462 -29.00320513]
J_matrix: (15, 15), nonzero: 105
QAOA bitstring: 100101111111101 (11 ones)
Selected indices: [14, 11, 9, 8, 7, 6, 5, 4, 3, 2, 0]
Selected: idx=14, pos=(4, 6), h=-29.00
Steps 6: (4, 6), dist: 68
Step: 7 - 15 candidates
H_values: [113.11858974 -9.14423077 -14.15705128 -4.13141026 65.25961538
-18.80769231 66.1474359 -7.99038462 -23.51602564 -23.82051282
-12.86538462 -23.09935897 -10.30769231 -23.61217949 -20.125 ]
J_matrix: (15, 15), nonzero: 105
QAOA bitstring: 000011010100011 (6 ones)
Selected indices: [10, 9, 7, 5, 1, 0]
Selected: idx=9, pos=(4, 8), h=-23.82
Steps 7: (4, 8), dist: 66
Step: 8 - 10 candidates
H_values: [ 95.71794872 86.35897436 68.20604396 -7.80769231 81.79166667
105.99679487 -8.14102564 -14.625 86.90064103 89.875 ]
J_matrix: (10, 10), nonzero: 45
QAOA bitstring: 0111101110 (7 ones)
Selected indices: [8, 7, 6, 5, 3, 2, 1]
Selected: idx=7, pos=(4, 9), h=-14.62
Steps 8: (4, 9), dist: 65
Step: 9 - 8 candidates
H_values: [ -8.76602564 86.88782051 -3.75320513 -7.61217949 90.07051282
-8.76602564 105.22115385 86.88782051]
J_matrix: (8, 8), nonzero: 28
QAOA bitstring: 00110100 (3 ones)
Selected indices: [5, 4, 2]
Selected: idx=5, pos=(4, 7), h=-8.77
Steps 9: (4, 7), dist: 67
Step: 10 - 14 candidates
H_values: [ -4.14423077 -9.15705128 -4.14423077 -8.00320513 -18.61217949
-8.49038462 63.49679487 48.41758242 92. -13.08653846
-23.11217949 -18.61217949 -15.125 79.86217949]
J_matrix: (14, 14), nonzero: 91
QAOA bitstring: 11001111101000 (8 ones)
Selected indices: [13, 12, 9, 8, 7, 6, 5, 3]
Selected: idx=12, pos=(6, 7), h=-15.12
Steps 10: (6, 7), dist: 65
Step: 11 - 14 candidates
H_values: [ 6.71217949e+01 1.03180403e+02 1.57498932e+02 -3.08653846e+00
-7.61217949e+00 6.73076923e-02 -7.61217949e+00 -1.46378205e+01
-1.51506410e+01 -2.29294872e+01 7.15448718e+01 9.02788462e+01
-1.51506410e+01 7.13365385e+01]
J_matrix: (14, 14), nonzero: 91
QAOA bitstring: 10111000100100 (6 ones)
Selected indices: [13, 11, 10, 9, 5, 2]
Selected: idx=9, pos=(7, 7), h=-22.93
Steps 11: (7, 7), dist: 64
Step: 12 - 10 candidates
H_values: [ 96.77564103 -8.23717949 104.94230769 106.83333333 89.72435897
95.79166667 -14.77564103 70.86538462 -23.45512821 71.19871795]
J_matrix: (10, 10), nonzero: 45
QAOA bitstring: 0001000110 (3 ones)
Selected indices: [6, 2, 1]
Selected: idx=6, pos=(8, 7), h=-14.78
Steps 12: (8, 7), dist: 63
Step: 13 - 13 candidates
H_values: [ 96.88782051 65.83333333 95.36217949 103.0982906 81.54487179
0.79166667 1.27884615 -23.16346154 -24.00961538 87.07051282
-22.95512821 -29.0224359 70.9775641 ]
J_matrix: (13, 13), nonzero: 78
QAOA bitstring: 0001000010000 (2 ones)
Selected indices: [9, 4]
Selected: idx=4, pos=(7, 9), h=81.54
Steps 13: (7, 9), dist: 62
Step: 14 - 11 candidates
H_values: [ 95.97435897 170.29166667 0.72435897 -18.25961538 -22.75961538
-23.2724359 200.68269231 -23.63461538 -20.32692308 81.19871795
-24.1474359 ]
J_matrix: (11, 11), nonzero: 55
QAOA bitstring: 01011001000 (4 ones)
Selected indices: [9, 7, 6, 3]
Selected: idx=7, pos=(8, 9), h=-23.63
Steps 14: (8, 9), dist: 61
Step: 15 - 15 candidates
H_values: [105.36217949 0.34935897 -12.74679487 166.74358974 102.56759907
-18.2724359 65.39102564 -7.66346154 -23.3974359 -15.20192308
-12.95512821 -23.3974359 -18.8974359 -24.24358974 70.41025641]
J_matrix: (15, 15), nonzero: 105
QAOA bitstring: 100000101111100 (7 ones)
Selected indices: [14, 8, 6, 5, 4, 3, 2]
Selected: idx=8, pos=(8, 10), h=-23.40
Steps 15: (8, 10), dist: 60
Step: 16 - 11 candidates
H_values: [ 5.34935897 -7.74679487 -12.75961538 -7.25961538 -8.16346154
102.36538462 -14.70192308 -14.79807692 86.82371795 71.48076923
80.75641026]
J_matrix: (11, 11), nonzero: 55
QAOA bitstring: 11011011010 (7 ones)
Selected indices: [10, 9, 7, 6, 4, 3, 1]
Selected: idx=7, pos=(8, 12), h=-14.80
Steps 16: (8, 12), dist: 58
Step: 17 - 8 candidates
H_values: [ 97.24038462 97.24038462 101.31730769 0.54807692 -23.14423077
80.35576923 -24.32371795 70.99679487]
J_matrix: (8, 8), nonzero: 28
QAOA bitstring: 11011111 (7 ones)
Selected indices: [7, 6, 4, 3, 2, 1, 0]
Selected: idx=6, pos=(10, 12), h=-24.32
Steps 17: (10, 12), dist: 56
Step: 18 - 13 candidates
H_values: [105.29807692 105.02930403 -7.51923077 -9.08974359 -8.26923077
-23.25320513 -23.97435897 -14.1025641 -23.79487179 -29.32051282
-19.96153846 -25.30769231 -29.65384615]
J_matrix: (13, 13), nonzero: 78
QAOA bitstring: 0001100100000 (3 ones)
Selected indices: [9, 8, 5]
Selected: idx=9, pos=(11, 14), h=-29.32
Steps 18: (11, 14), dist: 53
Step: 19 - 12 candidates
H_values: [ 97.17628205 87.15064103 106.38461538 -7.97435897 81.41666667
-8.66987179 -7.97435897 -14.68269231 -24.04166667 -19.54166667
-24.55448718 70.43269231]
J_matrix: (12, 12), nonzero: 66
QAOA bitstring: 100010010110 (5 ones)
Selected indices: [11, 7, 4, 2, 1]
Selected: idx=7, pos=(12, 12), h=-14.68
Steps 19: (12, 12), dist: 54
Step: 20 - 16 candidates
H_values: [ -3.64423077 61.18853695 -13.25320513 -3.8525641 -8.16987179
90.74198718 -9.07371795 -8.58653846 -23.90384615 -24.41666667
-14.08653846 -24.32051282 -29.42948718 -19.61217949 -24.625
-29.42948718]
J_matrix: (16, 16), nonzero: 120
QAOA bitstring: 1001001101110100 (8 ones)
Selected indices: [15, 12, 9, 8, 6, 5, 4, 2]
Selected: idx=15, pos=(14, 13), h=-29.43
Steps 20: (14, 13), dist: 51
Step: 21 - 15 candidates
H_values: [105.91289593 -8.90384615 -13.91666667 -4.22435897 -8.41666667
-19.44230769 -9.23717949 -8.75 -23.73397436 -24.03846154
-13.70833333 -23.73397436 -29.05128205 -19.23397436 -24.24679487]
J_matrix: (15, 15), nonzero: 105
QAOA bitstring: 010111100010001 (7 ones)
Selected indices: [13, 11, 10, 9, 8, 4, 0]
Selected: idx=9, pos=(14, 15), h=-24.04
Steps 21: (14, 15), dist: 49
Step: 22 - 13 candidates
H_values: [ 95.83333333 86.47435897 -4.16666667 -8.69230769 -18.84294872
100.79273504 -8.35897436 -23.34294872 -23.6474359 -13.85897436
-23.55128205 -20.16025641 -23.85576923]
J_matrix: (13, 13), nonzero: 78
QAOA bitstring: 0001111011110 (8 ones)
Selected indices: [9, 8, 7, 6, 4, 3, 2, 1]
Selected: idx=8, pos=(14, 17), h=-23.65
Steps 22: (14, 17), dist: 47
Step: 23 - 11 candidates
H_values: [ -3.77564103 -8.45512821 86.19871795 -4.44230769 -7.96794872
100.6939946 -7.96794872 -13.80128205 -14.66025641 80.23076923
80.6474359 ]
J_matrix: (11, 11), nonzero: 55
QAOA bitstring: 11000100100 (4 ones)
Selected indices: [10, 9, 5, 2]
Selected: idx=9, pos=(15, 19), h=80.23
Steps 23: (15, 19), dist: 44
Step: 24 - 6 candidates
H_values: [ 2.05602564e+02 5.76923077e-01 8.97435897e-02 1.24358974e+00
-1.40737179e+01 7.95256410e+01]
J_matrix: (6, 6), nonzero: 15
QAOA bitstring: 001110 (3 ones)
Selected indices: [3, 2, 1]
Selected: idx=2, pos=(15, 17), h=0.09
Steps 24: (15, 17), dist: 46
Step: 25 - 11 candidates
H_values: [ -3.78846154 -8.46794872 86.18589744 65.46516165 61.23892774
89.82692308 -8.80128205 -7.98076923 -14.25641026 88.75457875
86.51923077]
J_matrix: (11, 11), nonzero: 55
QAOA bitstring: 00100001001 (3 ones)
Selected indices: [8, 3, 0]
Selected: idx=8, pos=(15, 18), h=-14.26
Steps 25: (15, 18), dist: 45
Step: 26 - 8 candidates
H_values: [ 96.28205128 96.28205128 -8.73076923 104.47610723 49.15105909
-14.57371795 -13.8525641 80.41346154]
J_matrix: (8, 8), nonzero: 28
QAOA bitstring: 11111100 (6 ones)
Selected indices: [7, 6, 5, 4, 3, 2]
Selected: idx=5, pos=(15, 20), h=-14.57
Steps 26: (15, 20), dist: 43
Step: 27 - 5 candidates
H_values: [104.0388796 64.43910256 96.1474359 -14.08653846 70.88782051]
J_matrix: (5, 5), nonzero: 10
QAOA bitstring: 01010 (2 ones)
Selected indices: [3, 1]
Selected: idx=3, pos=(16, 20), h=-14.09
Steps 27: (16, 20), dist: 42
Step: 28 - 6 candidates
H_values: [104.95192308 168.95192308 104.59294872 -15.09935897 70.54166667
70.875 ]
J_matrix: (6, 6), nonzero: 15
QAOA bitstring: 110000 (2 ones)
Selected indices: [5, 4]
Selected: idx=4, pos=(17, 22), h=70.54
Steps 28: (17, 22), dist: 39
Step: 29 - 10 candidates
H_values: [ 95.47115385 209.03846154 -7.73717949 -23.47115385 -23.98397436
96.09615385 -23.47115385 -28.78846154 -24.65064103 -29.99679487]
J_matrix: (10, 10), nonzero: 45
QAOA bitstring: 0000000000 (0 ones)
Selected indices: []
WARNING: No selection, fallback to best h
Selected: idx=0, pos=(15, 23), h=95.47
Steps 29: (15, 23), dist: 40
Step: 30 - 8 candidates
H_values: [105.71794872 1.19230769 -7.30769231 -14.875 -23.70833333
189.71153846 -24.22115385 70.76602564]
J_matrix: (8, 8), nonzero: 28
QAOA bitstring: 11110010 (5 ones)
Selected indices: [7, 6, 5, 4, 1]
Selected: idx=6, pos=(17, 23), h=-24.22
Steps 30: (17, 23), dist: 38
Step: 31 - 16 candidates
H_values: [ 97.19230769 103.93874644 95.25 105.27564103 -7.95833333
80.68269231 -8.23717949 60.89285714 -23.48397436 -24.33012821
-13.25 -23.81730769 -29.34294872 -19.65064103 -24.99679487
-29.34294872]
J_matrix: (16, 16), nonzero: 120
QAOA bitstring: 1100111100000101 (8 ones)
Selected indices: [15, 14, 11, 10, 9, 8, 2, 0]
Selected: idx=15, pos=(19, 24), h=-29.34
Steps 31: (19, 24), dist: 35
Step: 32 - 12 candidates
H_values: [105.38003663 -8.48397436 -13.70512821 -3.47115385 -7.78846154
-9.02564103 -8.87179487 -15.56410256 -23.73076923 -19.0224359
-23.82692308 -28.83974359]
J_matrix: (12, 12), nonzero: 66
QAOA bitstring: 000011101000 (4 ones)
Selected indices: [7, 6, 5, 3]
Selected: idx=7, pos=(19, 25), h=-15.56
Steps 32: (19, 25), dist: 34
Step: 33 - 12 candidates
H_values: [ -3.48397436 -8.70512821 86.90705128 -3.69230769 -8.21794872
-9.24679487 100.81078691 -14.25961538 -23.74358974 -18.82692308
-23.83974359 71.1474359 ]
J_matrix: (12, 12), nonzero: 66
QAOA bitstring: 111100111011 (9 ones)
Selected indices: [11, 10, 9, 8, 5, 4, 3, 1, 0]
Selected: idx=10, pos=(21, 25), h=-23.84
Steps 33: (21, 25), dist: 32
Step: 34 - 12 candidates
H_values: [ 65.00516956 103.39423077 -4.63461538 -8.49358974 81.35576923
-8.6474359 -7.82692308 -23.3525641 -23.65705128 -13.66025641
-23.3525641 79.28846154]
J_matrix: (12, 12), nonzero: 66
QAOA bitstring: 101001111000 (6 ones)
Selected indices: [11, 9, 6, 5, 4, 3]
Selected: idx=9, pos=(22, 23), h=-13.66
Steps 34: (22, 23), dist: 33
Step: 35 - 11 candidates
H_values: [ -9.50961538 -13.85576923 -3.83012821 -8.0224359 89.71670802
-9.17628205 -8.68910256 -14.83974359 -23.8525641 86.4775641
80.95192308]
J_matrix: (11, 11), nonzero: 55
QAOA bitstring: 11110000010 (5 ones)
Selected indices: [10, 9, 8, 7, 1]
Selected: idx=8, pos=(22, 25), h=-23.85
Steps 35: (22, 25), dist: 31
Step: 36 - 10 candidates
H_values: [ -3.98076923 -8.99358974 -3.6474359 60.66783217 81.34294872
100.07932692 0.66025641 -23.36538462 70.77564103 71.10897436]
J_matrix: (10, 10), nonzero: 45
QAOA bitstring: 0000011110 (4 ones)
Selected indices: [4, 3, 2, 1]
Selected: idx=1, pos=(20, 25), h=-8.99
Steps 36: (20, 25), dist: 33
Step: 37 - 12 candidates
H_values: [ -3.28846154 -8.71794872 -4.37179487 64.00534188 -9.38461538
-8.23076923 -13.5224359 45.12454212 71.34294872 -10.33974359
84.65501166 71.13461538]
J_matrix: (12, 12), nonzero: 66
QAOA bitstring: 100011001000 (4 ones)
Selected indices: [11, 7, 6, 3]
Selected: idx=6, pos=(21, 23), h=-13.52
Steps 37: (21, 23), dist: 34
Step: 38 - 14 candidates
H_values: [ 95.84935897 -9.49679487 54.32371795 96.18269231 -9.00961538
89.53337104 -8.83012821 -8.34294872 -23.32692308 44.58593209
-14.17628205 45.11752137 39.61172161 80.63141026]
J_matrix: (14, 14), nonzero: 91
QAOA bitstring: 10010011010110 (7 ones)
Selected indices: [13, 10, 7, 6, 4, 2, 1]
Selected: idx=10, pos=(22, 21), h=-14.18
Steps 38: (22, 21), dist: 35
Step: 39 - 13 candidates
H_values: [ -3.05448718 -8.69230769 -8.20512821 89.65018315 -8.69230769
-8.20512821 -23.93910256 44.58097166 -13.49679487 -23.5224359
-19.0224359 -24.03525641 -29.04807692]
J_matrix: (13, 13), nonzero: 78
QAOA bitstring: 1101011001111 (9 ones)
Selected indices: [12, 11, 9, 7, 6, 3, 2, 1, 0]
Selected: idx=12, pos=(24, 22), h=-29.05
Steps 39: (24, 22), dist: 32
Step: 40 - 12 candidates
H_values: [104.89316239 -9.18910256 154.42307692 -3.50961538 -8.36858974
-8.5224359 -8.03525641 -15.06089744 -13.57371795 71.12179487
91.6474359 70.58012821]
J_matrix: (12, 12), nonzero: 66
QAOA bitstring: 101000000101 (4 ones)
Selected indices: [11, 9, 2, 0]
Selected: idx=11, pos=(26, 23), h=70.58
Steps 40: (26, 23), dist: 29
REACHABILITY: (28, 23) not completed from (26, 23) !
Step: 41 - 13 candidates
H_values: [ 2.05085932e+02 -6.08974359e-02 -3.07371795e+00 1.05368590e+02
-7.65705128e+00 -1.90993590e+01 2.14743590e+00 4.26282051e-01
-2.41410256e+01 -2.49871795e+01 6.96666667e+01 8.15256410e+01
7.10833333e+01]
J_matrix: (13, 13), nonzero: 78
QAOA bitstring: 0000001000100 (2 ones)
Selected indices: [6, 2]
Selected: idx=2, pos=(24, 24), h=-3.07
Steps 41: (24, 24), dist: 30
Step: 42 - 8 candidates
H_values: [ 96.13141026 60.05128205 0.43910256 -23.37820513 70.88782051
89.40468961 -24.76602564 69.88782051]
J_matrix: (8, 8), nonzero: 28
QAOA bitstring: 11111011 (7 ones)
Selected indices: [7, 6, 5, 4, 3, 1, 0]
Selected: idx=6, pos=(26, 24), h=-24.77
Steps 42: (26, 24), dist: 28
Step: 43 - 14 candidates
H_values: [ 4.93910256e+00 1.05525641e+02 -7.87820513e+00 -1.91121795e+01
-7.37179487e-02 6.04967949e+01 -2.43621795e+01 -2.48750000e+01
8.64134615e+01 -2.43621795e+01 -3.02211538e+01 8.13044872e+01
-2.39166667e+01 -2.89294872e+01]
J_matrix: (14, 14), nonzero: 91
QAOA bitstring: 01011011001000 (6 ones)
Selected indices: [12, 10, 9, 7, 6, 3]
Selected: idx=10, pos=(27, 26), h=-30.22
Steps 43: (27, 26), dist: 25
Step: 44 - 15 candidates
H_values: [ -3.59935897 -8.61217949 -13.625 104.98397436 -8.75
-9.23717949 -8.95833333 -24.06730769 -15.87179487 -13.41666667
-23.44230769 -28.34294872 -9.40064103 -14.62179487 -19.21794872]
J_matrix: (15, 15), nonzero: 105
QAOA bitstring: 100010010001100 (5 ones)
Selected indices: [14, 10, 7, 3, 2]
Selected: idx=7, pos=(27, 27), h=-24.07
Steps 44: (27, 27), dist: 24
Step: 45 - 13 candidates
H_values: [ -3.61217949 -8.625 85.94551282 -4.36217949 -8.34615385
-9.70833333 100.18026892 -15.37179487 -13.42948718 -23.03846154
-9.62179487 -14.21794872 -17.0224359 ]
J_matrix: (13, 13), nonzero: 78
QAOA bitstring: 1011010101011 (8 ones)
Selected indices: [12, 10, 9, 7, 5, 3, 1, 0]
Selected: idx=9, pos=(28, 27), h=-23.04
Steps 45: (28, 27), dist: 23
Step: 46 - 10 candidates
H_values: [ -5. -9.34615385 -5.33333333 99.7779304 -8.67948718
-8.19230769 -22.84294872 -3.90064103 -13.71794872 93.88141026]
J_matrix: (10, 10), nonzero: 45
QAOA bitstring: 0001000101 (3 ones)
Selected indices: [6, 2, 0]
Selected: idx=6, pos=(28, 28), h=-22.84
Steps 46: (28, 28), dist: 22
Step: 47 - 7 candidates
H_values: [ 95.52884615 63.87606838 -0.49679487 -8.81730769 100.25126714
-4.12179487 -11.5224359 ]
J_matrix: (7, 7), nonzero: 21
QAOA bitstring: 1010111 (5 ones)
Selected indices: [6, 4, 2, 1, 0]
Selected: idx=6, pos=(29, 28), h=-11.52
Steps 47: (29, 28), dist: 21
Step: 48 - 7 candidates
H_values: [58.60117057 -6.49679487 -9.31730769 94.8502331 0.50320513 1.65705128
-0.61858974]
J_matrix: (7, 7), nonzero: 21
QAOA bitstring: 0100101 (3 ones)
Selected indices: [5, 2, 0]
Selected: idx=2, pos=(28, 26), h=-9.32
Steps 48: (28, 26), dist: 24
Step: 49 - 13 candidates
H_values: [ -4.73717949 -9.75 -14.09615385 -4.73717949 59.19551282
-11.12179487 -8.41666667 -7.92948718 44.82678669 44.32552954
-3.88782051 -14.12179487 84.82478632]
J_matrix: (13, 13), nonzero: 78
QAOA bitstring: 0100011011110 (7 ones)
Selected indices: [11, 7, 6, 4, 3, 2, 1]
Selected: idx=11, pos=(29, 26), h=-14.12
Steps 49: (29, 26), dist: 23
Step: 50 - 10 candidates
H_values: [-10.58333333 53.19551282 48.43269231 -8.91666667 94.85117057
44.17788462 1.11217949 1.59935897 -13.71794872 49.80114566]
J_matrix: (10, 10), nonzero: 45
QAOA bitstring: 1100011100 (5 ones)
Selected indices: [9, 8, 4, 3, 2]
Selected: idx=8, pos=(29, 27), h=-13.72
Steps 50: (29, 27), dist: 22
Step: 51 - 9 candidates
H_values: [ 57.94551282 53.18269231 -11.37179487 -9.17948718 54.29487179
0.97435897 103.57678669 50.27943485 -1.11858974]
J_matrix: (9, 9), nonzero: 36
QAOA bitstring: 101011010 (5 ones)
Selected indices: [8, 6, 4, 3, 1]
Selected: idx=3, pos=(28, 25), h=-9.18
Steps 51: (28, 25), dist: 25
Step: 52 - 12 candidates
H_values: [ 63.98397436 -9.73717949 -14.75 -9.58333333 48.43269231
-8.19551282 -7.91666667 44.80769231 43.79487179 -3.66666667
-13.90064103 82.80288462]
J_matrix: (12, 12), nonzero: 66
QAOA bitstring: 100101111000 (6 ones)
Selected indices: [11, 8, 6, 5, 4, 3]
Selected: idx=3, pos=(27, 25), h=-9.58
Steps 52: (27, 25), dist: 26
Step: 53 - 15 candidates
H_values: [ -3.37820513 -8.59935897 -13.61217949 164.37179487 -8.73717949
-19.34615385 -8.73717949 44.32051282 43.80769231 86.80448718
84.8307169 38.79487179 -9.38782051 -14.40064103 42.78506787]
J_matrix: (15, 15), nonzero: 105
QAOA bitstring: 111011110100100 (9 ones)
Selected indices: [14, 13, 12, 10, 9, 8, 7, 5, 2]
Selected: idx=5, pos=(26, 27), h=-19.35
Steps 53: (26, 27), dist: 25
Step: 54 - 13 candidates
H_values: [ -3.39102564 -8.40384615 86.16666667 -3.59935897 -8.125
80.64102564 -9.48717949 -9. 94.45833333 44.18269231
48.80769231 43.79487179 138.78205128]
J_matrix: (13, 13), nonzero: 78
QAOA bitstring: 0000011011110 (6 ones)
Selected indices: [7, 6, 4, 3, 2, 1]
Selected: idx=6, pos=(26, 25), h=-9.49
Steps 54: (26, 25), dist: 27
Step: 55 - 14 candidates
H_values: [169.88461538 86.60897436 -3.15705128 -8.09935897 -19.125
59.37179487 59.85897436 -24.25 84.3107089 44.68910256
38.80769231 -18.91666667 44.29221093 38.80769231]
J_matrix: (14, 14), nonzero: 91
QAOA bitstring: 11111110000000 (7 ones)
Selected indices: [13, 12, 11, 10, 9, 8, 7]
Selected: idx=7, pos=(26, 26), h=-24.25
Steps 55: (26, 26), dist: 26
Step: 56 - 14 candidates
H_values: [ -8.39102564 -13.40384615 -3.37820513 -8.11217949 80.44551282
59.35897436 100.32692308 44.79221093 -14.23717949 44.19551282
79.12820513 49.27505828 43.80769231 38.79487179]
J_matrix: (14, 14), nonzero: 91
QAOA bitstring: 10010011010000 (5 ones)
Selected indices: [13, 10, 7, 6, 4]
Selected: idx=13, pos=(28, 27), h=38.79
Steps 56: (28, 27), dist: 23
Step: 57 - 10 candidates
H_values: [104.05503145 59.27505828 63.9047619 59.18269231 59.07051282
59.55769231 44.28205128 -3.90064103 47.78205128 93.88141026]
J_matrix: (10, 10), nonzero: 45
QAOA bitstring: 1001000100 (3 ones)
Selected indices: [9, 6, 2]
Selected: idx=6, pos=(28, 28), h=44.28
Steps 57: (28, 28), dist: 22
Step: 58 - 7 candidates
H_values: [ 1.64134109e+02 6.33205128e+01 -4.96794872e-01 5.89326923e+01
5.32132835e+02 5.77948718e+01 4.97692308e+01]
J_matrix: (7, 7), nonzero: 21
QAOA bitstring: 1100110 (4 ones)
Selected indices: [6, 5, 2, 1]
Selected: idx=2, pos=(27, 28), h=-0.50
Steps 58: (27, 28), dist: 23
Step: 59 - 9 candidates
H_values: [ 96.375 164.52192982 58.94551282 59.68269231 54.30769231
516.73659674 52.28205128 49.26923077 93.88141026]
J_matrix: (9, 9), nonzero: 36
QAOA bitstring: 100011101 (5 ones)
Selected indices: [8, 4, 3, 2, 0]
Selected: idx=4, pos=(28, 26), h=54.31
Steps 59: (28, 26), dist: 24
Step: 60 - 13 candidates
H_values: [ 63.84615385 59.25706215 54.07051282 -4.73717949 59.19551282
92.49130037 -8.41666667 59.82051282 476.72590628 476.22064777
-3.88782051 47.79487179 44.26923077]
J_matrix: (13, 13), nonzero: 78
QAOA bitstring: 1001101000000 (4 ones)
Selected indices: [12, 9, 8, 6]
Selected: idx=6, pos=(28, 24), h=-8.42
Steps 60: (28, 24), dist: 26
Step: 61 - 13 candidates
H_values: [164.12179487 58.98397436 53.84615385 96.28846154 -9.23717949
48.19551282 -7.97435897 -7.69551282 44.32051282 516.2462888
-3.65384615 -13.88782051 42.29487179]
J_matrix: (13, 13), nonzero: 78
QAOA bitstring: 1010000111110 (7 ones)
Selected indices: [12, 10, 5, 4, 3, 2, 1]
Selected: idx=4, pos=(27, 24), h=-9.24
Steps 61: (27, 24), dist: 27
Step: 62 - 14 candidates
H_values: [ 96.84294872 -8.37820513 -13.59935897 104.92628205 59.85897436
48.83333333 44.20833333 43.69551282 87.02564103 84.76436782
471.23142112 90.83333333 -14.38782051 -19.40064103]
J_matrix: (14, 14), nonzero: 91
QAOA bitstring: 11000100000000 (3 ones)
Selected indices: [13, 12, 8]
Selected: idx=13, pos=(29, 25), h=-19.40
Steps 62: (29, 25), dist: 24
Step: 63 - 10 candidates
H_values: [ 98.64488266 53.08333333 48.07051282 -8.69551282 54.19551282
475.41987179 1.33333333 1.61217949 47.66987179 47.28205128]
J_matrix: (10, 10), nonzero: 45
QAOA bitstring: 1100110101 (6 ones)
Selected indices: [9, 8, 5, 4, 2, 0]
Selected: idx=9, pos=(29, 27), h=47.28
Steps 63: (29, 27), dist: 22
Step: 64 - 9 candidates
H_values: [ 9.94551282 5.18269231 3.79487179 10.57051282 12.29487179 55.09935897
15.04487179 49.76923077 -1.11858974]
J_matrix: (9, 9), nonzero: 36
QAOA bitstring: 001000000 (1 ones)
Selected indices: [6]
Selected: idx=6, pos=(29, 26), h=15.04
Steps 64: (29, 26), dist: 23
Step: 65 - 10 candidates
H_values: [10.20833333 5.19551282 0.43269231 11.22395833 12.30769231 1.65705128
1.11217949 15.71091811 42.19188735 -0.73076923]
J_matrix: (10, 10), nonzero: 45
QAOA bitstring: 0001110100 (4 ones)
Selected indices: [6, 5, 4, 2]
Selected: idx=2, pos=(27, 27), h=0.43
Steps 65: (27, 27), dist: 24
Step: 66 - 13 candidates
H_values: [-3.61217949 -8.625 85.94551282 16.22115385 11.82051282 11.08333333
11.57051282 -0.20512821 6.32051282 2.29487179 50.6980976 1.67887668
-5.73076923]
J_matrix: (13, 13), nonzero: 78
QAOA bitstring: 0000000001111 (4 ones)
Selected indices: [3, 2, 1, 0]
Selected: idx=1, pos=(25, 27), h=-8.62
Steps 66: (25, 27), dist: 26
Step: 67 - 14 candidates
H_values: [ 4.91346154 -8.59935897 -7.90384615 -19.47115385 -8.59935897
-8.11217949 -24.30448718 -24.48397436 5.97115385 -3.80448718
70.50320513 0.32051282 41.9545177 94.16987179]
J_matrix: (14, 14), nonzero: 91
QAOA bitstring: 01000111100011 (7 ones)
Selected indices: [12, 8, 7, 6, 5, 1, 0]
Selected: idx=7, pos=(25, 29), h=-24.48
Steps 67: (25, 29), dist: 24
Step: 68 - 13 candidates
H_values: [ -8.83333333 -14.17948718 -3.40384615 -8.34615385 -20.03846154
51.72395833 -8.67948718 -23.87179487 -24.71794872 106.32051282
-23.87179487 -29.18910256 79.7275641 ]
J_matrix: (13, 13), nonzero: 78
QAOA bitstring: 1011100010010 (6 ones)
Selected indices: [12, 10, 9, 8, 4, 1]
Selected: idx=8, pos=(25, 31), h=-24.72
Steps 68: (25, 31), dist: 22
Step: 69 - 14 candidates
H_values: [ -4.05448718 -8.85897436 -13.66346154 -3.84615385 -8.91346154
51.69230769 -8.37179487 -24.10576923 -24.61858974 -13.87179487
-23.68910256 -29.21474359 89.7275641 70.78525641]
J_matrix: (14, 14), nonzero: 91
QAOA bitstring: 11110010101001 (8 ones)
Selected indices: [13, 12, 11, 10, 7, 5, 3, 0]
Selected: idx=11, pos=(26, 33), h=-29.21
Steps 69: (26, 33), dist: 19
Step: 70 - 12 candidates
H_values: [ 95.32371795 56.41083916 -8.86858974 80.10576923 -8.68910256
-8.53525641 -24.06089744 -24.57371795 -23.7275641 -30.25320513
-23.40705128 -28.83653846]
J_matrix: (12, 12), nonzero: 66
QAOA bitstring: 000000111100 (4 ones)
Selected indices: [5, 4, 3, 2]
Selected: idx=2, pos=(25, 33), h=-8.87
Steps 70: (25, 33), dist: 20
Step: 71 - 10 candidates
H_values: [ 96.33653846 95.58653846 59.64969834 -8.60576923 -13.68910256
84.61672407 70.55128205 -19.21474359 -24.2275641 70.34294872]
J_matrix: (10, 10), nonzero: 45
QAOA bitstring: 0010011100 (4 ones)
Selected indices: [7, 4, 3, 2]
Selected: idx=7, pos=(27, 32), h=-19.21
Steps 71: (27, 32), dist: 19
Step: 72 - 10 candidates
H_values: [164.38919414 -9.35576923 94.37405732 96.32371795 -8.53525641
-19.56089744 -23.7275641 -24.90705128 71.16346154 83.12179487]
J_matrix: (10, 10), nonzero: 45
QAOA bitstring: 0100010110 (4 ones)
Selected indices: [8, 4, 2, 1]
Selected: idx=1, pos=(25, 32), h=-9.36
Steps 72: (25, 32), dist: 21
Step: 73 - 13 candidates
H_values: [ -3.85897436 -8.66346154 86.11538462 -4.06730769 -8.92628205
-8.87179487 60.1292735 44.61355311 -13.67628205 -23.91025641
70.56410256 84.10590858 -29.2275641 ]
J_matrix: (13, 13), nonzero: 78
QAOA bitstring: 1101001111011 (9 ones)
Selected indices: [12, 11, 9, 6, 5, 4, 3, 1, 0]
Selected: idx=12, pos=(27, 33), h=-29.23
Steps 73: (27, 33), dist: 18
Step: 74 - 12 candidates
H_values: [104.37637363 59.35363248 96.31089744 60.0860555 -19.57371795
60.09570242 -24.40705128 -25.25320513 -22.90705128 103.63461538
-11.87820513 -17.30769231]
J_matrix: (12, 12), nonzero: 66
QAOA bitstring: 110001000100 (4 ones)
Selected indices: [11, 10, 6, 2]
Selected: idx=6, pos=(27, 34), h=-24.41
Steps 74: (27, 34), dist: 17
Step: 75 - 14 candidates
H_values: [164.59424809 85.85576923 -3.91025641 -8.43589744 -19.66987179
59.5860555 100.08288191 -24.50320513 -25.01602564 -23.33653846
70.92948718 -6.87820513 -12.30769231 82.47115385]
J_matrix: (14, 14), nonzero: 91
QAOA bitstring: 10001000111010 (6 ones)
Selected indices: [13, 9, 5, 4, 3, 1]
Selected: idx=9, pos=(28, 34), h=-23.34
Steps 75: (28, 34), dist: 16
Step: 76 - 10 candidates
H_values: [ 63.99358974 -9.31089744 85.67628205 164.32692308 99.56517094
79.48397436 -7.40705128 109.13461538 -11.80769231 82.45833333]
J_matrix: (10, 10), nonzero: 45
QAOA bitstring: 1110001001 (5 ones)
Selected indices: [9, 8, 7, 3, 0]
Selected: idx=8, pos=(29, 34), h=-11.81
Steps 76: (29, 34), dist: 15
Step: 77 - 9 candidates
H_values: [ 58.68910256 53.43078656 79.37179487 94.42259396 75.17948718
14.13461538 4.12179487 -12.15384615 -12.66666667]
J_matrix: (9, 9), nonzero: 36
QAOA bitstring: 001100110 (4 ones)
Selected indices: [6, 5, 2, 1]
Selected: idx=6, pos=(29, 33), h=4.12
Steps 77: (29, 33), dist: 16
Step: 78 - 7 candidates
H_values: [158.11858974 53.43044456 48.17189609 -13.03205128 14.63461538
89.78014553 -12.90384615]
J_matrix: (7, 7), nonzero: 21
QAOA bitstring: 0110110 (4 ones)
Selected indices: [5, 4, 2, 1]
Selected: idx=4, pos=(29, 32), h=14.63
Steps 78: (29, 32), dist: 17
Step: 79 - 4 candidates
H_values: [148.10576923 143.15480353 90.03846154 49.27125506]
J_matrix: (4, 4), nonzero: 6
QAOA bitstring: 0100 (1 ones)
Selected indices: [2]
Selected: idx=2, pos=(29, 33), h=90.04
Steps 79: (29, 33), dist: 16
Step: 80 - 7 candidates
H_values: [158.11858974 53.10576923 47.84294872 -13.03205128 111.04689609
49.76282051 -12.90384615]
J_matrix: (7, 7), nonzero: 21
QAOA bitstring: 0010110 (3 ones)
Selected indices: [4, 2, 1]
Selected: idx=2, pos=(27, 34), h=47.84
Steps 80: (27, 34), dist: 17
Step: 81 - 14 candidates
H_values: [116.25641026 85.85576923 -3.91025641 -8.43589744 -19.66987179
11.24358974 11.73076923 -24.50320513 -25.01602564 -3.79487179
70.92948718 48.5215839 -0.49519231 82.47115385]
J_matrix: (14, 14), nonzero: 91
QAOA bitstring: 11010111000000 (6 ones)
Selected indices: [13, 12, 10, 8, 7, 6]
Selected: idx=8, pos=(27, 36), h=-25.02
Steps 81: (27, 36), dist: 15
Step: 82 - 16 candidates
H_values: [ -4.14423077 -9.36538462 -14.37820513 -3.93589744 -8.66987179
-19.90384615 57.53846154 -8.87820513 -24.73717949 -25.25
106.20512821 -23.57051282 -29.09615385 92.47115385 -12.54166667
-19.55448718]
J_matrix: (16, 16), nonzero: 120
QAOA bitstring: 1010000000011111 (7 ones)
Selected indices: [15, 13, 4, 3, 2, 1, 0]
Selected: idx=15, pos=(29, 37), h=-19.55
Steps 82: (29, 37), dist: 12
Step: 83 - 9 candidates
H_values: [ 50.38376339 -15.86217949 -20.875 -13.70833333 -24.73397436
2.97115385 3.45833333 -14.40064103 -14.91346154]
J_matrix: (9, 9), nonzero: 36
QAOA bitstring: 111100110 (6 ones)
Selected indices: [8, 7, 6, 5, 2, 1]
Selected: idx=2, pos=(27, 38), h=-20.88
Steps 83: (27, 38), dist: 13
Step: 84 - 15 candidates
H_values: [ -4.37820513 -9.18269231 -14.19551282 -4.16987179 -8.90384615
59.50094967 -9.11217949 -24.63782051 -24.94230769 -13.57051282
-23.59615385 -28.91346154 92.46634615 -14.77564103 -19.78846154]
J_matrix: (15, 15), nonzero: 105
QAOA bitstring: 000010110010100 (5 ones)
Selected indices: [10, 8, 7, 4, 2]
Selected: idx=8, pos=(27, 40), h=-24.94
Steps 84: (27, 40), dist: 11
Step: 85 - 13 candidates
H_values: [ 95.80448718 94.48717949 95.59615385 99.35030864 -9.26282051
-24.45512821 -24.55128205 -13.59615385 -23.41346154 -28.5224359
-9.78846154 -14.80128205 -19.81410256]
J_matrix: (13, 13), nonzero: 78
QAOA bitstring: 1000011101110 (7 ones)
Selected indices: [12, 7, 6, 5, 3, 2, 1]
Selected: idx=6, pos=(27, 42), h=-24.55
Steps 85: (27, 42), dist: 9
Step: 86 - 12 candidates
H_values: [109.98717949 87.12820513 80.14423077 102.69590369 -5.70512821
-26.8974359 -11.91346154 -25.5224359 67.16025641 -10.31410256
-16.91025641 -21.92307692]
J_matrix: (12, 12), nonzero: 66
QAOA bitstring: 100110100111 (7 ones)
Selected indices: [11, 8, 7, 5, 2, 1, 0]
Selected: idx=5, pos=(27, 43), h=-26.90
Steps 86: (27, 43), dist: 8
Step: 87 - 13 candidates
H_values: [101.47435897 -5.74679487 87.44871795 101.26602564 -5.25961538
79.71474359 -6.08012821 103.41658943 -11.92628205 -25.74358974
75.43910256 -9.91025641 -14.92307692]
J_matrix: (13, 13), nonzero: 78
QAOA bitstring: 1111001010111 (9 ones)
Selected indices: [12, 11, 10, 9, 6, 4, 2, 1, 0]
Selected: idx=9, pos=(28, 43), h=-25.74
Steps 87: (28, 43), dist: 7
Step: 88 - 12 candidates
H_values: [ -6.38461538 87.26923077 0.29487179 102.77518315 87.91025641
-5.05128205 -4.0224359 -25.33974359 -17.56089744 -2.81410256
-14.42307692 86.25961538]
J_matrix: (12, 12), nonzero: 66
QAOA bitstring: 000000100101 (3 ones)
Selected indices: [5, 2, 0]
Selected: idx=0, pos=(26, 43), h=-6.38
Steps 88: (26, 43), dist: 9
Step: 89 - 13 candidates
H_values: [ -6.06730769 -12.53846154 109.98717949 -5.24679487 -20.60576923
-26.35576923 -27.28525641 86.91987179 41.89326178 74.41025641
80.9775641 81.38386124 67.16025641]
J_matrix: (13, 13), nonzero: 78
QAOA bitstring: 0011111111100 (9 ones)
Selected indices: [10, 9, 8, 7, 6, 5, 4, 3, 2]
Selected: idx=6, pos=(26, 45), h=-27.29
Steps 89: (26, 45), dist: 7
Step: 90 - 13 candidates
H_values: [ 1.46153846 -6.09294872 86.89423077 1.25320513 -5.60576923
79.91025641 102.90608229 -4.85576923 155.88665501 -18.08974359
63.38461538 81.16025641 -17.56089744]
J_matrix: (13, 13), nonzero: 78
QAOA bitstring: 0100011100001 (5 ones)
Selected indices: [11, 7, 6, 5, 0]
Selected: idx=7, pos=(26, 44), h=-4.86
Steps 90: (26, 44), dist: 8
Step: 91 - 12 candidates
H_values: [ 0.68269231 -5.66346154 -13.34294872 101.34935897 -5.17628205
79.13141026 63.14947552 81.62709991 155.49038462 65.7724359
148.37064247 75.43910256]
J_matrix: (12, 12), nonzero: 66
QAOA bitstring: 111000100000 (4 ones)
Selected indices: [11, 10, 9, 5]
Selected: idx=9, pos=(27, 46), h=65.77
Steps 91: (27, 46), dist: 5
Step: 92 - 11 candidates
H_values: [100.76923077 87.41025641 209.88665501 78.63461538 3.41025641
-29.11538462 -28.58653846 88.66025641 65.02564103 100.25961538
75.31730769]
J_matrix: (11, 11), nonzero: 55
QAOA bitstring: 00011101110 (6 ones)
Selected indices: [7, 6, 5, 3, 2, 1]
Selected: idx=5, pos=(27, 47), h=-29.12
Steps 92: (27, 47), dist: 4
Step: 93 - 15 candidates
H_values: [100.75641026 -5.58974359 -3.06089744 169.73946886 -4.89423077
2.91025641 103.34500144 -28.08653846 -17.47435897 96.93910256
-28.29487179 -26.07051282 89.74679487 -17.68269231 -26.07051282]
J_matrix: (15, 15), nonzero: 105
QAOA bitstring: 001011111100100 (8 ones)
Selected indices: [12, 10, 9, 8, 7, 6, 5, 2]
Selected: idx=10, pos=(28, 47), h=-28.29
Steps 93: (28, 47), dist: 3
Step: 94 - 10 candidates
H_values: [ -5.76923077 -13.86538462 109.41025641 100.32905983
-10.47435897 -27.47435897 -19.07051282 107.75961538
-17.18269231 -1000. ]
J_matrix: (10, 10), nonzero: 45
QAOA bitstring: 1000110010 (4 ones)
Selected indices: [9, 5, 4, 1]
Selected: idx=9, pos=(29, 49), h=-1000.00
Steps 94: (29, 49), dist: 0
Completed in 94 steps
time: 23.9 sekund
sec/steps: 0.25
In [7]:
# === Visualization of found path ===
# Display complete path including QAOA steps and statistics
navigator.visualize_path(path)
