For several circuits of medium width 7-20ish qubits, GPU-enhanced QFactor allows us to run instantiation quickly in order to do a large-block ScanningGate removal. For these workflows, there are very few blocks, which limits our parallelism. In order to fix this, this PR adds a tree structure to ScanningGate removal. The TreeScan works as follows:
Split the circuit operations into chunks of size tree_depth
At every iteration:
a. Look at the next chunk of operations
b. Generate 2 ^ tree_depth circuits. Each circuit corresponds to every combination of whether or not to include one of the operations in the chunk.
c. Instantiate in parallel all 2^tree_depth circuits
d. Choose the circuit that has the least number of operations and move on to the next chunk of operations.
This optimization is less greedy than the current ScanningGate removal, which we see can offer much better quality circuits than ScanningGate. In very rare occasions, ScanningGate may be able to outperform TreeScan (since it is still greedy), but in general we can expect TreeScan to almost always outperform ScanningGate.
For several circuits of medium width 7-20ish qubits, GPU-enhanced QFactor allows us to run instantiation quickly in order to do a large-block ScanningGate removal. For these workflows, there are very few blocks, which limits our parallelism. In order to fix this, this PR adds a tree structure to ScanningGate removal. The TreeScan works as follows:
This optimization is less greedy than the current ScanningGate removal, which we see can offer much better quality circuits than ScanningGate. In very rare occasions, ScanningGate may be able to outperform TreeScan (since it is still greedy), but in general we can expect TreeScan to almost always outperform ScanningGate.