"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"matrix = mwpf.BasicMatrix()\n",
"initializer = example.initializer()\n",
"for vertex_index, edge_indicies in enumerate(example.incident_edges):\n",
" print(vertex_index, edge_indicies)\n",
" matrix.add_constraint(vertex_index, edge_indicies, vertex_index in example.defects)\n",
"matrix.show()"
]
},
{
"cell_type": "markdown",
"id": "c5ba8571-5fb1-4bdc-a4d2-47231c10d00a",
"metadata": {},
"source": [
"## 2. explain transformations on decoding hypergraph and parity matrix: XOR vertex $\\Leftrightarrow$ XOR row"
]
},
{
"cell_type": "markdown",
"id": "b4af3b13-b5b2-4e99-883a-438da32a050f",
"metadata": {},
"source": [
"Now we can manipulate the parity matrix by adding one row to another. For example, we can add row 4 to row "
]
},
{
"cell_type": "code",
"execution_count": 17,
"id": "1c3bb3e6-fe8e-41c4-ab14-cb332197b557",
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
"┌─┬─┬─┬─┬─┬─┬───┐\n",
"┊ ┊0┊1┊2┊3┊4┊ = ┊\n",
"╞═╪═╪═╪═╪═╪═╪═══╡\n",
"┊0┊1┊1┊1┊ ┊ ┊ ┊\n",
"├─┼─┼─┼─┼─┼─┼───┤\n",
"┊1┊ ┊ ┊1┊1┊ ┊ ┊\n",
"├─┼─┼─┼─┼─┼─┼───┤\n",
"┊2┊ ┊ ┊ ┊1┊1┊ ┊\n",
"├─┼─┼─┼─┼─┼─┼───┤\n",
"┊3┊ ┊1┊ ┊ ┊ ┊ 1 ┊\n",
"├─┼─┼─┼─┼─┼─┼───┤\n",
"┊4┊ ┊ ┊ ┊ ┊1┊ 1 ┊\n",
"└─┴─┴─┴─┴─┴─┴───┘\n",
"
"
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"text/html": [
"\n",
" "
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"matrix2 = matrix.clone()\n",
"matrix2.xor_row(3, 4)\n",
"matrix2.show()"
]
},
{
"cell_type": "code",
"execution_count": 19,
"id": "0b4ffe88-dea9-440e-aea2-29c2b3d8c85a",
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"text/html": [
"\n",
" "
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"example2 = Example()\n",
"example2.weighted_edges = [\n",
" mwpf.HyperEdge([0], 1),\n",
" mwpf.HyperEdge([0, 3], 1),\n",
" mwpf.HyperEdge([0, 1], 1),\n",
" mwpf.HyperEdge([1, 2], 1),\n",
" mwpf.HyperEdge([2, 4], 1),\n",
"]\n",
"example2.syndrome = [3, 4]\n",
"# example2.show()\n",
"\n",
"# print a colored version\n",
"visualizer = mwpf.Visualizer(positions=example2.positions)\n",
"initializer = example2.initializer()\n",
"solver = mwpf.Solver(initializer)\n",
"for edge_index in range(len(example2.weighted_edges)):\n",
" node = solver.create_node_hair_unchecked({edge_index})\n",
"solver.grow(mwpf.Rational(1))\n",
"solver.load_syndrome(mwpf.SyndromePattern(example2.syndrome))\n",
"visualizer.snapshot(\"hypergraph\", solver)\n",
"visualizer.show()"
]
},
{
"cell_type": "markdown",
"id": "d003227e-f4a4-494d-887d-013e34ecfde9",
"metadata": {},
"source": [
"## 3. explain the logic flow of the algorithm\n",
"\n",
"- we would like to find feasible primal and dual solutions with a small gap $\\sum w_e x_e - \\sum y_S$\n",
"- This involves two separate steps: increase the dual and decrease the primal\n",
"- However, neither of these tasks are easy.\n",
" - For dual problem, there are an exponential number of dual variables, and how to efficiently pick a small portion of them to constitute $\\sum y_S$ is challenging.\n",
" - For primal problem, although there is only linear number of variables with the number of physical error locations, finding the minimum-weighted one requires one to search over the exponential space especially with the high degeneracy in quantum error correction.\n",
"- We are inspired by the blossom algorithm, which solves the primal and dual problems leveraging each other's information. This is backed by the complementary slackness theorem that states the property of the optimal solution.\n",
" - The primal module uses the dual module information to select solutions: only tight edges can be selected\n",
" - The dual module uses the primal solution space to identify new dual variables, based on the single-hair rule\n",
"- More thoughts: since dual can be sometimes suboptimal due to the suboptimality of the disjoint single hair algorithm, it's probably beneficial to slightly break the law of the complementary slackness theorem\n",
" - Explore some more region in the primal graph?\n",
"- More thoughts: equivalent decoding graphs\n",
" - Indeed, we showed that there are multiple equivalent decoding hypergraphs, equivalent to each other via vertex manipulations. However, not all of them are created equal: some of them are sparse and some of them are dense. It would be much harder to reduce the primal-dual gap given a (equivalent) dense graph compared to a sparse graph."
]
},
{
"cell_type": "markdown",
"id": "feee3f62-619d-496d-ab3e-0888b2e84056",
"metadata": {},
"source": [
"Note:\n",
"\n",
"Single-hair algorithm could be divided into three levels:\n",
"1. ensure that for each non-zero dual variable, there exists one solution using the tight edges that only uses a single hair\n",
"2. ensure that for each non-zero dual variable, for each of its tight hair corresponds to a single hair solution of this dual variable\n",
"3. ensure that there exists a tight hair solution that is single-hair solution for all non-zero dual variables\n",
"\n",
"If an algorithm reaches level 3, it is an optimal solution."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "ab4410e3-d90f-4767-8a83-5e3b5c262ac5",
"metadata": {},
"outputs": [],
"source": []
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3 (ipykernel)",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.11.6"
}
},
"nbformat": 4,
"nbformat_minor": 5
}