Changes specific to the simulator:
I use the following heuristic to permute the gates before the simple DP:
Each qubit is assigned a cumulative weight, initially 0.
When doing topological sort, invoke a gate chooser each time we choose a gate (even if there is only one choice), so there are guaranteed to be num_gates iterations.
In each iteration:
Compute the weight of each gate to be the average of the weight of each qubit.
Choose a gate with probability proportional to exp(weight).
Multiply the weight of each qubit by 0.9. (Discounting old weights.)
For each qubit q the gate operates on, increase the weight of each other qubit j by pow(0.5, abs(j - q)), i.e., weight[q] += 1, weight[q - 1] += 0.5, weight[q + 1] += 0.5, weight[q - 2] += 0.25, weight[q + 2] += 0.25, .... Intuition: people tend to write circuits with space locality (i.e., if we use q, it is likely that q + 1 will be used next).
Benchmark: qft, 33 qubits, 28 local qubits:
Before:
Changes specific to the simulator: I use the following heuristic to permute the gates before the simple DP:
num_gatesiterations.qthe gate operates on, increase the weight of each other qubitjbypow(0.5, abs(j - q)), i.e.,weight[q] += 1, weight[q - 1] += 0.5, weight[q + 1] += 0.5, weight[q - 2] += 0.25, weight[q + 2] += 0.25, .... Intuition: people tend to write circuits with space locality (i.e., if we useq, it is likely thatq + 1will be used next).Benchmark: qft, 33 qubits, 28 local qubits: Before:
After (repeat=10):
(each invocation:)
After (repeat=100):
Recall the complicated DP: