problems.n_minus_1

1.0.0

The n_minus_1 package provides quantum computing solvers for the n-1 problem.

The N-1 problem arises in graph theory as a reconfigurational mathematical challenge. When a cut is introduced, or an edge is removed, in a given graph of nodes and edges, the N-1 problem seeks the most efficient method of reconfiguring the nodes using the fewest possible edges.

Example

This script below uses annealing based optimization to solve the N-1 problem for the small dataset (load_small_dataset()) with some additional edits.

Edge (1,4) is removed (this is the “broken” edge). Furthermore, the I_max attribute of Edge (1,5) is set to 0. In this way, there is exactly one solution: Turning edge (0,1) on, while all other edges are not toggled.

from tno.quantum.problems.n_minus_1 import QABasedNMinusOneSolver
from tno.quantum.problems.n_minus_1.quantum_annealing.datasets import load_small_dataset

graph = load_small_dataset()
graph.edges[1, 5]["I_max"] = 0
failing_edge = (1, 4)
solver_config = {
    "name": "simulated_annealing_solver",
    "options": {
        "num_reads": 100,
        "num_sweeps": 100000,
        "num_sweeps_per_beta": 100,
        "seed": 2024,
    },
}

solver = QABasedNMinusOneSolver(graph, failing_edge)
results = solver.run(solver_config=solver_config)

print(results)

This prints the following result:

k | count |        turned on        |       turned off
---+-------+-------------------------+-------------------------
1 |   4   |         (1, 5)          |
1 |   1   |         (0, 1)          |
3 |   1   |     (0, 1), (1, 5)      |         (5, 6)

Example

This script below uses the gate grover algorithm to solve the N-1 problem for a custom dataset.

import networkx as nx
from qiskit.visualization import plot_distribution

from tno.quantum.problems.n_minus_1 import GateBasedNMinusOneSolver

# Create a graph with edges: 0-1, 0-2, 0-3, 1-4, 2-4, 2-3, 3-4, 1-2, 0-5, 4-5.
graph = nx.Graph()
active_edges = [(0, 1), (0, 2), (0, 3), (1, 4), (0, 5)]
inactive_edges = [(2, 4), (2, 3), (3, 4), (1, 2), (4, 5)]
for node_n, node_m in active_edges:
    graph.add_edge(node_n, node_m, weight=1)
for node_n, node_m in inactive_edges:
    graph.add_edge(node_n, node_m, weight=-1)

load_flow_correctness = [[(0, 2), (0, 1), (0, 3), (4, 5), (3, 4)]]

# Run the algorithm
solver = GateBasedNMinusOneSolver(
    graph, (1, 4), load_flow_correctness, n_iter=8, n_toggles=2
)
executed_run = solver.run()

# Plot the results
counts = executed_run.result().results[0].data.counts
fig = plot_distribution(
    counts,
    title="Failed Edge (1,4) - Correct Toggles (0,5), (3,4), or (4,5)",
    bar_labels=True,
)
fig.savefig("grover_n-1.png")
class tno.quantum.problems.n_minus_1.GateBasedNMinusOneSolver(graph, failing_edge, load_flow_correctness, n_toggles=1, n_iter=1, quantum_backend=None, *, exact_superposition=False)[source]

Bases: object

Gate Based N-1 Solver.

The gate based N-1 solver uses Grover to search for grid configurations that have the specified number of toggles and are load flow compliant.

__init__(graph, failing_edge, load_flow_correctness, n_toggles=1, n_iter=1, quantum_backend=None, *, exact_superposition=False)[source]

Init GateBasedNMinusOneSolver.

Parameters:

  • graph (Graph) – A networkx graph representation of an electric network.

  • failing_edge (tuple[int, int]) – The edge that is currently failing i.e (1,4).

  • load_flow_correctness (Iterable[Iterable[tuple[Hashable, Hashable]]]) – A list of edges that are load flow compliant

  • n_toggles (SupportsInt) – Number of toggles possible.

  • n_iter (SupportsInt) – Number of iterations

  • quantum_backend (Optional[Backend]) – A ‘qiskit’ backend. Default is ‘qasm_simulator’.

  • exact_superposition (bool) – Choose if you want to use exact superposition with only useful states or an easier (superfluous) superposition with additional indices.

run()[source]

Run the algorithm.

Return type:

AerJob

class tno.quantum.problems.n_minus_1.QABasedNMinusOneSolver(graph, failing_edge)[source]

Bases: object

Quantum Annealing Based N-1 Solver.

The Quantum Annealing solver performs the following steps:

  1. Transform the problem to a Binary Quadratic Model, also known as a Quadratic Unconstrained Optimization (QUBO).

  2. Approximate a solution to this problem with the given QUBO solver. This solver can be a quantum solver.

  3. Decode the bitstrings returned by the solver.

__init__(graph, failing_edge)[source]

Init of the QABasedNMinusOneSolver.

Parameters:

  • graph (Graph) – Network represented as a graph. Each node should have the following attributes: type, U_ref, P_low, P_high, U_min and U_max. Each edge should have the following attributes: active, edge_idx, Z and I_max.

  • failing_edge (tuple[Hashable, Hashable]) – The edge that will fail in the scenario.

run(factory_arguments=None, qubo_arguments=None, solver_config=None)[source]

Run the algorithm.

Parameters:
Return type:

ResultsOverview

Returns:

Result overview object containing the results.