[NEW PASS] Parallelization of Commuting Gates

[gluonhiggs]

1. How the technique works

a. Provide a written abstract without too much jargon (cite arXiv paper/GitHub repo if applicable)
The "Parallelization of Commuting Gates" pass optimizes quantum circuits by identifying two-qubit gates (like CNOTs) that can run at the same time because they operate on separate qubits and don’t interfere with each other. Using Qiskit’s Commuting2qGateRouter, the pass reorganizes these gates into parallel layers, shortening the overall circuit depth. On quantum computers, especially NISQ devices with limited coherence times, shorter circuits can run faster and with fewer errors.
https://arxiv.org/abs/1204.4570
b. (Optional) Attach a diagram showing an example circuit transformation (you can add this later)

2. Performance expectations

a. What circuit types will this improve? (e.g., dynamic circuits, error correction)
Variational algorithms, circuits with operations on separate qubit groups that don’t overlap
b. Which UCC metrics will it impact? (gate counts, errors, etc.)
Circuit Depth: By running commuting gates in parallel, it reduces the number of layers in the circuit.
Runtime: Shorter circuits should execute faster on quantum hardware or simulators.
Relative Errors: On NISQ devices, shorter circuits experience less noise

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 @gluonhiggs , I'm one of the UCC maintainers :) Thanks for your proposal! So if I understand correctly, you'd like to incorporate the logic from this Commuting2qGateRouter pass into UCCDefault1, right?

[jordandsullivan]

If so, you can go ahead with development! We'd recommend starting by benchmarking the pass performance on a non-trivial layout, in addition to all-to-all. You can use this script developed by my colleague @Misty-W to generate different layouts: https://github.com/unitaryfoundation/ucc-bench/blob/main/benchmarks/scripts/generate_layouts.py

[gluonhiggs]

Thank you!

[jordandsullivan]

@gluonhiggs Let us know if your have any questions or need any support :)

[jordandsullivan]

@gluonhiggs glad you've got it working! So if your pass reduces the compilation time from UCC baseline, that's still worth considering! Have you compared the reduction in runtime for the different benchmark circuits to see if there are any trends there?

As for considering circuit depth as a metric, we generally consider the total number of 2 qubits gates as a proxy for this, but we could consider separating it out if you can demonstrate a test case where this reveals something that wouldn't be captured by total gate counts.

[gluonhiggs]

I have only compared the compilation time for some toy circuits, not benchmark suite circuits in ucc-bench. But the improvement seems to be random (some better, some worse). I'm still working on this.

As for considering circuit depth as a metric, we generally consider the total number of 2 qubits gates as a proxy for this, but we could consider separating it out if you can demonstrate a test case where this reveals something that wouldn't be captured by total gate counts.

Yeah, it sounds reasonable.

[Misty-W]

As long as the gate counts improve on average without incurring too much runtime cost (TBD), we generally don't worry about regressions on individual benchmarking circuits.

[jordandsullivan]

@gluonhiggs Can you run the official ucc-benchmarks as a next step?

[gluonhiggs]

@jordandsullivan
I can run the benchmarks with several variants of my simple pass. These variants improve the compilation time a little bit. However, when I run the simulation, they do not show any improvement in uncompiled_ideal,compiled_ideal,uncompiled_noisy,compiled_noisy.
For example,

Compilation

1. A new pass

compiler,benchmark_id,raw_multiq_gates,compile_time_ms,compiled_multiq_gates
ucc,qaoa,1176,181.3615,1176
ucc,qv,15000,906.2769,14856
ucc,qft,10050,350.3663,2740
ucc,square_heisenberg,2160,156.4589,540
ucc,prep_select,9744,723.6355,9702
ucc,qcnn,388,146.0646,388

2. Current pass

compiler,benchmark_id,raw_multiq_gates,compile_time_ms,compiled_multiq_gates
ucc,qaoa,1176,204.0268,1176
ucc,qv,15000,944.2042,14856
ucc,qft,10050,344.1111,2740
ucc,square_heisenberg,2160,156.9137,540
ucc,prep_select,9744,774.0786,9702
ucc,qcnn,388,152.1277,388

Simulation

1. A new pass

compiler,benchmark_id,measurement_id,uncompiled_ideal,compiled_ideal,uncompiled_noisy,compiled_noisy
ucc,qaoa,qaoa,5.5800,5.5800,3.6865,3.3136
ucc,qv,heavy_output,-0.4712,-0.6147,-0.6151,-0.6133
ucc,qft,computational_basis,0.0000,0.0000,0.0000,-0.0000
ucc,square_heisenberg,hamlib_heisenberg_pbc-qubitnodes_Lx_Ly_h-0.5,22.5000,22.5000,14.9739,19.8496
ucc,prep_select,computational_basis,-0.0000,0.0000,-0.0000,0.0000
ucc,qcnn,qcnn,-0.2273,-0.2273,-0.2075,-0.2054

2. Current pass

compiler,benchmark_id,measurement_id,uncompiled_ideal,compiled_ideal,uncompiled_noisy,compiled_noisy
ucc,qaoa,qaoa,5.5800,5.5800,3.6865,3.3012
ucc,qv,heavy_output,-0.6104,-0.6107,-0.5827,-0.6133
ucc,qft,computational_basis,0.0000,0.0000,0.0000,0.0000
ucc,square_heisenberg,hamlib_heisenberg_pbc-qubitnodes_Lx_Ly_h-0.5,22.5000,22.5000,14.9739,19.8496
ucc,prep_select,computational_basis,-0.0000,0.0000,-0.0000,0.0000
ucc,qcnn,qcnn,-0.2273,-0.2273,-0.2075,-0.2054

I have tried TemplateOptimization, however, Qiskit’s implementation is not very optimized for large circuits. My PC has 24 cores, but I had to stop the compilation when adding TemplateOptimization with some simple templates because there is a benchmark circuit of 15000 gates.
I have read a lot of papers and filtered out majority of them. What remains are Clifford Circuit Optimization with Templates and Symbolic Pauli Gates and Polynomial-time T-depth Optimization of Clifford+T circuits via Matroid Partitioning. I have a "gut feeling" that to implement the 2nd paper ideas, I would have to customize a lot. So, I'm diving into the first one, and hopefully it could be well integrated with TemplateOptimization. What do you think?
p/s: By the way, I have been working on Quantum Compilation using Deep RL, but that is not very easy to implement, and implement here. So I hope I will be able to submit it to the micro grant program.

[jordandsullivan]

Gotcha thanks @gluonhiggs ! Nice to see the runtimes down a bit. Can you rerun this plotting script with the your new pass data included, so we can compare the avg performance.

Script: https://github.com/unitaryfoundation/ucc-bench/blob/f18faf862c3160071c2d55a80b2ffd3daaa7a472/.github/scripts/plot_latest_benchmark.py#L4

[jordandsullivan]

Thanks for checking. So it doesn't look like the new pass reduces avg compile time by much.

In that case, I think your idea about working to implement the Clifford Circuit Optimization with Templates and Symbolic Pauli Gates paper sounds like a good instinct.

Please submit a new compiler pass proposal for that one if you'd like to work on it :)

[gluonhiggs]

Thank you for the info @jordandsullivan. Is that ok if my new proposal is only applied for Clifford circuits and it can't be check with the current existing benchmark circuits but the new one using this?

[Misty-W]

A pass that is only applied to Clifford circuits would be too narrow for UCC's range of use cases, but at least one of the techniques in Clifford Circuit Optimization with Templates and Symbolic Pauli Gates is already used to optimize Clifford unitaries. Groups of Clifford operations in a non-Clifford circuit can be optimized using "greedy" Clifford optimization, hence UCC's use of qiskit.transpiler.passes.CollectCliffords() in tandem with HighLevelSynthesis(hls_config=HLSConfig(clifford=["greedy"])). You might want to look at Qiskit/qiskit#11659 for some inspiration of how to improve beyond what we already have in UCC (no guarantees but could help point in the right direction).

[jordandsullivan]

@gluonhiggs If you'd still like to work on this after today, you are welcome to do so :) The deadline is only for the UnitaryHACK bounty.

[gluonhiggs]

@jordandsullivan Yeah thank you for the encouragement! I hadn't spent enough time on this issue, so it's late for recognizing which direction I should follow as @Misty-W commented above. The new pass implementation would be heavy, and ... tricky because underneath, Qiskit optimizes the passes using rust. I will be thinking about how to "pythonize" the optimization with the existing Python API passes.

[jordandsullivan]

Hi @gluonhiggs -- I wanted to reach out and let you know if you're still interested in developing on a compiler pass in UCC, contributions are now eligible for compensation year-round :)

Here's our blog post with the details it: https://unitary.foundation/posts/2025_merit_systems_uf/