search

Qiskit / rustworkx

A high performance Python graph library implemented in Rust.
https://www.rustworkx.org
Apache License 2.0
1.04k stars 145 forks source link

heavy hex graph generators from number of nodes #573

Open ajavadia opened 2 years ago

ajavadia commented 2 years ago

What is the expected enhancement?

Currently the heavy hex graphs accept a d which is the code distance for the quantum error correction code that can run on them. Since retworkx is supposed to be a standalone library, I think it would be useful to allow building generic heavy hex graphs that are not explicitly tied to quantum error correction. The other motivation is that with the current d parameter the number of qubits rise very rapidly, i.e. they go 19, 57, 115, 193, 291, 409, 547, .... This makes it hard for example to build a 27-node graph in the heavy-hex style.

So the request is to expose another parameter (n) which is number of nodes. From that one could find the appropriate number of heavy-hex tiles and the maximum d that can fit in that n. Any outstanding nodes can just be added to the periphery (in a way that it becomes a subset of the graph for the next d).

enavarro51 commented 1 year ago

I can take a look at this one.

enavarro51 commented 1 year ago

@mtreinish @ajavadia Since I'm not sure of the application here, I see several ways to do this. Assuming the idea above of determining the highest d value that creates a heavy hex graph with node count (c) less than n,

  1. A simple path graph can be added onto the last node of the heavy hex with d.
  2. Regarding the 'periphery' idea, simply adding an edge from the last nodes on the heavy hex to the extra nodes. If n < 2c, (n-1, c-1), (n-2, c-2), ... (n-c, 2c-n-1). If n >= 2c, then double up edge sources from the heavy hex nodes.
  3. If the goal is to make the additional nodes have edges that are a subset of the heavy hex with d+2, then the node indices would have to be discontinuous. For this, here are the edge lists for d=3, EdgeList[(0, 13), (1, 13), (1, 14), (2, 14), (3, 15), (4, 15), (4, 16), (5, 16), (6, 17), (7, 17), (7, 18), (8, 18), (0, 9), (3, 9), (5, 12), (8, 12), (10, 14), (10, 16), (11, 15), (11, 17)] and d=5, EdgeList[(0, 37), (1, 37), (1, 38), (2, 38), (2, 39), (3, 39), (3, 40), (4, 40), (5, 41), (6, 41), (6, 42), (7, 42), (7, 43), (8, 43), (8, 44), (9, 44), (10, 45), (11, 45), (11, 46), (12, 46), (12, 47), (13, 47), (13, 48), (14, 48), (15, 49), (16, 49), (16, 50), (17, 50), (17, 51), (18, 51), (18, 52), (19, 52), (20, 53), (21, 53), (21, 54), (22, 54), (22, 55), (23, 55), (23, 56), (24, 56), (0, 25), (5, 25), (9, 30), (14, 30), (10, 31), (15, 31), (19, 36), (24, 36), (26, 38), (26, 42), (27, 40), (27, 44), (28, 41), (28, 45), (29, 43), (29, 47), (32, 46), (32, 50), (33, 48), (33, 52), (34, 49), (34, 53), (35, 51), (35, 55)] The smallest target node is 25 for d=5, which means none of the added nodes could have an index between 19 and 24, etc. With Petgraph, this would require creating all the nodes for the d=5 graph and then removing those not connecting to the d=3 graph.