[Question] NoiseAwarePlacement for single-qubit gates

[1tnguyen]

When using NoiseAwarePlacement, if I only have circuits with one-qubit gates, it seems like the NoiseAwarePlacement module doesn't work.

For example, in the below example, I'd have expected it to map the two H gates to qubits 1 and 2 (much lower node errors) but it'd return unplaced.

How should I use NoiseAwarePlacement in these scenarios?

std::vector<std::pair<unsigned, unsigned>> edges = {{0, 1}, {1, 2}, {0, 2}};
Architecture architecture(edges);
Circuit circuit(2);
circuit.add_op<unsigned>(OpType::H, {0});
circuit.add_op<unsigned>(OpType::H, {1});

avg_node_errors_t op_node_errors;
op_node_errors[Node(0)] = 0.25;
op_node_errors[Node(1)] = 0.01;
op_node_errors[Node(2)] = 0.01;

DeviceCharacterisation characterisation(op_node_errors, {}, {});
NoiseAwarePlacement placement(architecture);
placement.set_characterisation(characterisation);
auto map = placement.get_placement_map(circuit);

[sjdilkes]

Hello,

In TKET, when "Mapping" a virtual quantum Circuit to a physical quantum circuit for some Architecture we use two stages:

1. "Placement", i.e. deciding a mapping between a Circuit virtual Qubit and a Architecture physical Node.
2. "Routing", i.e. adding gates such as SWAP to permute virtual Qubit on Architecture Node and so make the full circuit valid for the given Architecture.

I mention this to try and motivate why a Placement method might leave a Qubit labelled as Placement::unplaced_reg(). Routing is able to dynamically assign virtual Qubit to a physical Node as a Circuit is routed: If a virtual Qubit first undergoes a 2-qubit gate deep into the Circuit structure, then it can be dynamically assigned to the closest unassigned physical Node in the Architecture to the other Qubit (assuming it is placed, else both are placed) it is interacting with. In general we find this helps with compilation. Note that if a virtual Circuit Qubit has no edges, we don't want to assign it to an Architecture Node that is better placed for some dynamic assignment later, so instead we leave it.

Therefore, if there is no physically motivated reason for assigning a virtual Qubit to an Architecture Node then it is left unassigned. Or in terms of subgraph monomorphism, if a vertex in the Circuit "pattern graph" has no edges, then it is not assigned.

However, while this logic is sound for non-noise-aware instances, as you point out in this case, it is not assigning Qubit to the low noise Node in a simple circumstance. If there was a 2-qubit gate between two the Circuit qubits it would be fine.

As it's unlikely algorithm circuits will have Qubit with no 2-qubit gates, it seems that the downside of assigning isolated Qubit in the noise-aware case (worse routing) does not outweigh better qubit assignment. For the case where there are no two-qubit maps, i.e. the "pattern graph" is empty, I will add a catch case to assign virtual Qubit to lowest noise physical Qubit.

[yitchen-tim]

I also see the same behavior of the noise aware placement when a qubit has no gate, from some corner cases that the qubit does initially have gates, but the gates are compiled away for certain angles.

I will add a catch case to assign virtual Qubit to lowest noise physical Qubit.

Is there any timeline about this catch case?

[yitchen-tim]

@sjdilkes Is there any timeline about catching the cases for qubits with only 1-qubit gate and no gate?

[sjdilkes]

Really sorry for the slow reply and fix here - I have moved the catch case described above int our imminent work and should hopefully have a fix in the next release.

[sjdilkes]

The catch previously mentioned here for Circuit where no Qubit have 2-qubit gates has been added with 1165.

[yitchen-tim]

Hi @sjdilkes, thanks for updating the code about this issue! In the latest version of pytket, I indeed now see the test case of three H gates works as expected. However, in the case where there are mixed use of one- and two-qubit gates (like CX(0,1) and then H(2)), the qubit 2 is still unplaced.

[sjdilkes]

Hi @sjdilkes, thanks for updating the code about this issue! In the latest version of pytket, I indeed now see the test case of three H gates works as expected. However, in the case where there are mixed use of one- and two-qubit gates (like CX(0,1) and then H(2)), the qubit 2 is still unplaced.

Hi @yitchen-tim, this is intended behaviour. When routing, we don't always assign every virtual Qubit in a Circuit to a physical Qubit of a Device when completing placement, as we find that allowing some virtual Qubit's to be dynamically assigned during the routing process can improve compilation results. If routing finds any qubits unassigned once it is finished routing for all two-qubit gates, it will assign them to remaining free physical Qubit's (or reassign them to ancilla qubits used during routing). Though this process isn't noise aware - so qubit 2 in your example maybe ends up on a physical Qubit that reports worse fidelity.

For the case we discussed previously where the Circuit has no two-qubit gates, we can safely assign all virtual Qubit's to physical Qubit's as we know this won't effect later routing (as there is no routing to be done). For the mixed case you've shared, if we were to assign qubit 2 then we risk a drop in routing performance.

However this is our current thinking - we can try to find a new solution that works for your case. I have a couple of a suggestions on which your input would be appreciated:

1. We could add a new argument to NoiseAwarePlacement such as "assign_all_qubits", which if True completes the assignment as usual and then assigns the remaining virtual Qubit to the remaining physical Qubit with best reported fidelity. This would satisfy your use case, though the risk is routing producing a circuit with more SWAP gates.

2. We could add a new Compilation pass to apply after the Placement and Routing passes have been applied, which reassigns Qubit with only single-qubit gates to other physical Qubit with better reported Fidelity (if possible).

[github-actions]

This issue has been automatically marked as stale.

[yitchen-tim]

thanks @sjdilkes, I think the second method sounds better, given the first maybe suboptimal for routing. Ideally, a user would apply the reassign pass at the end.

[github-actions]

This issue has been automatically marked as stale.