Priority-Centrality Token-Swap (PCTS) Compilation

[vivek-kumar9696]

1. How the technique works

The PCTS pass is aimed at static, gate-model quantum circuits whose two-qubit gates must respect a sparse, fixed coupling map—the common scenario for today’s NISQ-era superconducting (e.g., IBM, Rigetti) and neutral-atom machines. PCTS combines a centrality-aware placement with a token-swap routing heuristic, aiming to reduce both two qubit gate counts and number of required passes to generate final circuit.

High-level design (two overarching steps)
We have the coupling graph of the hardware and DAG of the logical circuit.

Step 1 – Mapping (Placement)

1. Interaction graph: build an adjacency matrix weighted by two-qubit-gate counts.
2. Priority stack: order logical qubits by total interaction weight.
3. Seed node: pop the top logical qubit and map it to the physical node with the highest Katz/eigenvector centrality in the coupling graph.
4. Neighbour growth loop:

• Choose an unmapped logical neighbour (highest residual priority).
• Place it on the highest-centrality adjacent physical qubit.
• Remove assigned qubit form priority stack.

5. Repeat 4 until the parent’s neighbourhood is exhausted.
6. Then pull the next parent from the stack, ie Step 3. Continue this process till all logical qubits are mapped.
7. Run gates that are now executable without swaps and according to their position in the DAG and status of their dependency.

Step 2 – Routing (Token-Swap)
When a scheduled two-qubit gate still involves distant qubits, I intend to insert Swap gates using a token-swap heuristic:

• treat qubit locations as tokens on the hardware graph,
• choose swap sequences that minimise parallel-depth rather than raw length,
• exploit edge-disjoint paths to schedule swaps in layers.

Status: the core idea for the Routing step is crystallised, but the exact heuristic (greedy vs look-ahead vs A* on token-swap cost) is still under ideation. Feedback from the community is welcome before locking the algorithm.

PS: Refer to PCTS repo for sample ipynb notebooks that explain this process. Please refer Manual_TokenSwap_Qubit_Routing.ipynb for detailed explanation about the workings of above proposal.

2. Performance expectations

a. What circuit types will this improve? (e.g., dynamic circuits, error correction)
Static, gate-model quantum circuits whose two-qubit gates must respect a sparse, fixed coupling map.

b. Which UCC metrics will it impact? (gate counts, errors, etc.)
This project was done with the aim of improving SABRE SWAP protocol Tackling the Qubit Mapping Problem for NISQ-Era Quantum Devices. It aims make some of its stochatic elements like the random initial map and the selection of a candidate swap, which is random if there are multiple candidates with identical minimum scores more deterministic. This stochasticity results in the original SABRE algorithm’s output quality being potentially very dependent on the random number generator, hence increasing required number of passes and trials.

Hence most of the metrics that I aim to improve are the ones mentioned in the paper. But I mainly wan't to eliminate the lookahead heuristic steps and the reverse traversal steps, thus reducing the time it takes for the compilation process to execute for larger, deeper circuits. How it will effect the gate count of final compiled circuit remains to be seen. When trying to solve manually for smaller coupling graphs I saw reduced gate count than SABRE compile pass, but the routing step did not follow the token swap algorithm process but rather manual solution.

Develop your compiler pass

Once the maintainers have given you the go-ahead, you can work on the next sections:

3. Create a fork of UCC to develop in: [link your fork here]
   Hint: We recommending syncing your fork with the main branch of UCC to stay up to date with changes.

4. Implement and Validate a Prototype of the Pass:
   A Jupyter notebook or a small script is sufficient for the prototype: [link prototype script/notebook here].
   Important: Make sure your compiler pass works as you expect on the circuits you defined in step 2a.

5. Implement the New Pass in the UCC Codebase:
   Documentation to guide you through this process is available in the user guide. For more detailed information and examples, refer to the Qiskit documentation.

Benchmark performance

UCC benchmarks live in the separate repo called ucc-bench. We have a suite of quantum circuits that we regularly benchmark UCC and other popular quantum compilers on. Several of the key metrics we track are:

• Compiling alone:

  • 2-qubit gate count after circuit compilation (lower is better)
  • Total runtime of compilation (lower is better)

• Simulating compiled circuits:

  • Relative errors in simulated expectation values for a defined set of observables (lower is better)

Your new pass should improve one or more of these metrics on our existing benchmark suite.

Note: If you are introducing a technique whose effect on performance is not currently measurable by our benchmark suite (e.g. a new qubit mapping pass that performs very well on sparsely connected qubit layouts), let us know and we can work with you to add the metric into ucc-bench.

When you are ready to run benchmarks...

6. Open a pull request (PR) to merge your fork of UCC in main (mark it as a Draft unless you are ready for final review), ping a UCC maintainer, and we will trigger the benchmarking suite to run. Alternately, you can also run the benchmarks locally by comparing your UCC version to main, as explained in the ucc-bench README.

---

Useful documentation

Contributing Guide
Setting up your Developer Environment
Writing a Custom Transpiler Pass
-We use "transpiler pass" to refer to transformations that act only on the Directed Acyclic Graph (DAG) representation of the quantum circuit. Higher or lower-level optimizations (e.g. algorithm-level or pulse-level, respectively), we call "compiler passes."

[jordandsullivan]

Hi @vivek-kumar9696, thanks for your proposal! :) I'm one of the UCC maintainers, and this sounds like a great direction to develop. If I understand correctly, you'd want to implement a separate mapping pass which gets used in ucc to replace the current mapping passes. I believe @Misty-W has done some previous working defining a set of different layout topologies to use as test cases.

You have our approval to go ahead with this pass. Let us know if you have any questions about defining benchmarks.

[vivek-kumar9696]

Hi @jordandsullivan,
Thanks for the reply. I aim to implement both the mapping and routing pass. That being said, I have not worked on the routing pass algorithm. If there are existing routing algorithms present in UCC, I think a good strategy will be to first couple the PCTS mapping pass with an existing routing pass of UCC. Any guidance in this direction will be appreciated.

Apart from that, if you could point me to any resources for the work done by @Misty-W, that will help a lot.

Thanks

[jordandsullivan]

Here is the script for generating layouts: https://github.com/unitaryfoundation/ucc-bench/blob/main/benchmarks/scripts/generate_layouts.py

[jordandsullivan]

The link above to our current mapping passes is a good place to start. They are currently unchanged from Qiskit's default behavior: https://docs.quantum.ibm.com/api/qiskit/transpiler_passes#layout-selection-placement

[jordandsullivan]

@vivek-kumar9696 Let us know if your have any questions or need any support on this compiler pass :)

[vivek-kumar9696]

Hi @jordandsullivan,
I have written the code and ran benchmarks using ucc_bench. I have seen a decrease in the compilation time compared to the compilation pass in UCCDefaults1 class. The results are as follows:

Whenever my proposed compiler pass (fdls) performs better, I have highlighted it in green. I have taken the best times out of multiple runs and it seemed fdls performed better consistently over all runs. But there is no improvement in the number of gates.

I needed help with benchmarking by applying different physical layouts . Can you direct me how I can use ucc-bench to benchmark using the Tilted square and heavy hex lattice that is generated using the generate_layouts.py code you mentioned earlier.
I also wanted to ask, whether ucc-bench takes the physical layout of the qubit lattice into consideration when doing the benchmarks, because src/ucc_bench/compilers/ucc_compiler.py does not pass any target_device to the compile function which completely bypasses the code in _add_map_passes() of ucc/transpilers/ucc_defaults.py and only runs _add_local_passes().

[vivek-kumar9696]

Hi @jordandsullivan,
I was able to run the ucc-bench benchmarks for layouts using FakeWashingtonV2 backend. It is a 127 qubit, heavy hex layout backend with the following structure:

The results that I got using ucc-bench were very encouraging and showed significant reduction in gate counts compared to the currently used SABRE routing algorithm in UCCDefaults1. The result are as follows:

The PCTS algorithm I was trying to implement did not yield good results, but I found out that the work done in Qubit Mapping Based on Subgraph Isomorphism and Filtered Depth-Limited Search may improve ucc's performance. The above results are for that algorithm and the reduction ratio closely resemble the reduction ratios achieved in the paper where they compared to SABRE swap algorithm.

Can you please assist with the next steps for vetting the results and proceed for further development?

[vivek-kumar9696]

okay, Thanks for the input.

[vivek-kumar9696]

I have created a new discussion, [New Pass] Filtered Depth-Limited Search (FDLS) compiler pass #407. Please refer it for details regarding the compiler pass. I will also open a PR with changes to the ucc code.

Should I also open PR for changes in the ucc_bench repo where I hardcoded the underlying target device for benchmarking?

[vivek-kumar9696]

PCTS did not work because, token swapping algorithm is only suited for smaller graphs (In our case, the coupling layout). It does not scale well with added edges and vertices and execution time is specially penalized by graphs which have clusters of nodes with high degree. It seemed too restrictive for various backends.

Apart from that the initial mapping algorithm of PCTS performed similar to SABRE algorithm's initial mapping algorithm. I am still using SABRE's initial mapping algorithm in FDLS. We can maybe later use the paper's intial mapping algorithm, but for now switching SABRE's routing algorithm with FDLS is already giving better results.

[jordandsullivan]

Should I also open PR for changes in the ucc_bench repo where I hardcoded the underlying target device for benchmarking?

I'd recommend working with my colleague @bachase, who just created an issue to add new benchmarks for multiple layouts/topologies: unitaryfoundation/ucc-bench#77 :)

[vivek-kumar9696]

Yes sure

[jordandsullivan]

Thanks so much @vivek-kumar9696

[vivek-kumar9696]

You're welcome!! @jordandsullivan