Find an independent set before choosing an algorithm¶
Start with the three-node path a — b — c. An independent set contains no pair joined by an edge. A maximum independent set (MIS) is an independent set with the largest possible number of nodes. In this lesson, define the graph, decode candidates and exhaust all eight bitstrings to establish a classical reference.
You need installation and basic Python dictionaries. No quantum simulation or variational optimizer runs in this lesson. Understanding bit order helps when reading the candidate strings.
Decide what each bit means¶
The graph explicitly contains edges (a, b) and (b, c). Its recorded variable order is ["a", "b", "c"]. In this order, 101 selects a and c; 110 selects a and b. Only the first is independent.
Positions at 0, 5 and 10 um are geometric information. GraphProblemIR.from_edges uses the supplied edges; it does not infer another edge list or establish that the graph can be implemented exactly by a physical interaction. Keep the optimization problem and its later physical mapping separate.
Predict the largest feasible set and whether it is unique. Also find a maximal set that is not maximum: maximal means you cannot add another node while keeping feasibility, not that its size is globally best.
Decode and enumerate¶
"""Describe and decode a small graph optimization problem.
This lesson starts before a variational optimizer: define a typed graph,
inspect its stable variable order, and decode one candidate bitstring. Keeping
problem semantics separate from an algorithm makes later QAOA results auditable.
"""
from __future__ import annotations
import json
from cascaqit.problems import GraphProblemIR, decode_graph_bitstring
def main() -> None:
"""Create a path graph and decode one independent-set candidate."""
# Positions are explicit problem facts; they are not inferred hardware placement.
graph = GraphProblemIR.from_edges(
problem_id="lesson.optimization.beginner",
positions={"a": (0.0, 0.0), "b": (5.0, 0.0), "c": (10.0, 0.0)},
edges=(("a", "b"), ("b", "c")),
)
# The candidate uses the graph's frozen variable order.
decoded = decode_graph_bitstring(graph, "101")
candidates = [decode_graph_bitstring(graph, f"{value:03b}") for value in range(8)]
feasible = [item for item in candidates if item["is_independent"]]
maximum_size = max(item["selection_size"] for item in feasible)
payload = {
"track": "optimization_researcher",
"level": "beginner",
"lesson": "graph_problem",
"facts": {
"node_order": list(graph.nodes),
"edges": [list(edge) for edge in graph.edges],
"bitstring": decoded["bitstring"],
"selected_nodes": list(decoded["selected_nodes"]),
"feasible": decoded["is_independent"],
"candidates": [
{
"bitstring": item["bitstring"],
"size": item["selection_size"],
"feasible": item["is_independent"],
"violating_edges": item["violating_edges"],
}
for item in candidates
],
"maximum_independent_set_size": maximum_size,
"optimal_bitstrings": [
item["bitstring"]
for item in feasible
if item["selection_size"] == maximum_size
],
},
"boundaries": {
"hardware_execution": False,
"cloud_execution": False,
"network_accessed": False,
"credentials_loaded": False,
},
}
print(json.dumps(payload, sort_keys=True))
if __name__ == "__main__":
main()
python3 examples/user/tracks/optimization_researcher/01_beginner_graph_problem_en.py
{
"boundaries": {
"cloud_execution": false,
"credentials_loaded": false,
"hardware_execution": false,
"network_accessed": false
},
"facts": {
"bitstring": "101",
"candidates": [
{
"bitstring": "000",
"feasible": true,
"size": 0,
"violating_edges": []
},
{
"bitstring": "001",
"feasible": true,
"size": 1,
"violating_edges": []
},
{
"bitstring": "010",
"feasible": true,
"size": 1,
"violating_edges": []
},
{
"bitstring": "011",
"feasible": false,
"size": 2,
"violating_edges": [
[
"b",
"c"
]
]
},
{
"bitstring": "100",
"feasible": true,
"size": 1,
"violating_edges": []
},
{
"bitstring": "101",
"feasible": true,
"size": 2,
"violating_edges": []
},
{
"bitstring": "110",
"feasible": false,
"size": 2,
"violating_edges": [
[
"a",
"b"
]
]
},
{
"bitstring": "111",
"feasible": false,
"size": 3,
"violating_edges": [
[
"a",
"b"
],
[
"b",
"c"
]
]
}
],
"edges": [
[
"a",
"b"
],
[
"b",
"c"
]
],
"feasible": true,
"maximum_independent_set_size": 2,
"node_order": [
"a",
"b",
"c"
],
"optimal_bitstrings": [
"101"
],
"selected_nodes": [
"a",
"c"
]
},
"lesson": "graph_problem",
"level": "beginner",
"track": "optimization_researcher"
}
Read candidates as a table of feasible and infeasible proposals. Among eight strings, five describe independent sets. 101 is the only feasible size-two set, so maximum_independent_set_size is 2 and optimal_bitstrings is ["101"]. 010 is maximal because both remaining nodes touch b, but it is smaller than the maximum.
111 selects three nodes but violates both edges. Counting selected nodes without checking feasible would declare an invalid solution the winner. A candidate decoder explains a string; it does not search for the optimum. The loop over eight strings provides the exhaustive reference here.
Write down the objective you will compare¶
One possible minimization cost is E(x) = −(x_a + x_b + x_c) + λ(x_a x_b + x_b x_c). The first term rewards selection, while the second penalizes an occupied edge. For this exercise choose λ = 2: E(101) = −2, E(110) = 0, and E(111) = 1.
This equation is a hand-calculated exercise, not an additional field returned by the script or a claim about every compiler's default penalty. When using a compiler later, inspect its actual objective, weights and sign convention. An expected energy, a feasible fraction and the size of the best sampled feasible set answer different questions.
Modify the problem¶
- Add
(a, c)to make a triangle, rerun and list all optimal bitstrings. - Leave only edge
(a, b). What is the maximum size and how many solutions attain it? - In the original path, use
λ = 0.5in the hand-calculated cost. Does minimizing this cost still distinguish the valid maximum from every invalid candidate?
Check your reasoning
A triangle has maximum size one, attained by 001, 010 and 100. With only (a, b), select c plus either endpoint: 011 and 101 both have size two. For λ = 0.5, E(111) = −2, tied with the feasible 101; the cost alone no longer selects only feasible optima. Always check constraint violations even when a reported objective looks favorable.
A wrong string length raises ValueError. Check the variable order before decoding; do not assume a display label or a later circuit uses the same order. Exhaustive enumeration costs 2^n candidates, so this three-node reference is deliberately small and says nothing about scaling advantage.
Continue with the optimization route to map QUBO and Ising costs, then study QAOA and VQE. Retain this graph and its exact answer as a test problem when learning a new algorithm.