[NEW PASS] Global Phase Graph Optimizer

[q-inho]

1. How the technique works

The GPGO attempts two of the most expesnive resources, non-Clifford $T$ gates and two-qubit entangling gates in one sweep.

1. Alebebraic phase compression
   Every $T$ or controlled-phase gate is first recast as term in a phase-polynomial over bits. Optimizing that polynomial is mathematically the same as a minimum distance decoding problem in a Reed-Muller code. By solving this decoding task we remove redundant phase terms, cutting the $T$-count and $T$-depth often down to the provable minimum for Clifford $+$ T circuits. The idea follows the coding-theoretic from T-Count Optimization and Reed–Muller Codes and subsequent refinements Polynomial-Time T-Depth Optimization of Clifford+T Circuits Via Matroid Partitioning.

2. Graphical CNOT/ZZ clean-up
   In parallel, the circuit is converted to a ZX-diagram. Standard spider-fusion, pivoting and local-complementation rules, implemented in libraries like PyZx and recent reinforcement-learning engines, destroy chains of commuting CNOT/ZZ gates into the fewest possible entangling operations. The copleteness of the ZX guarantees the rewritten diagran is locally identical to the origin. Reinforcement Learning Based Quantum Circuit Optimization via ZX-Calculus

3. Re-synthesis
   The optimized phase-polynomial specifies the minimal set of $T$ gates and the simplifeid ZX graph dictates an entangling pattern with edge-coloring depth. Combinding the two yields a new DAG circuit that is functionally unchanged but globally smaler, shallower, and less error-prone.

I am expecting it as high-level pseudocode

class GlobalPhaseGraphPass(TransformationPass):
    def __init__(self):
        super().__init__()
    def run(self, dag: DAGCircuit) -> DAGCircuit:
        poly, linear_ops = extract_phase_polynomial(dag)
        zx_graph = extract_ZX_diagram(dag)
        optimized_poly = minimize_phase_polynomial(poly)  # solves decoding problem
        zx_graph.optimize()  # apply ZX rewrite rules iteratively
        new_dag = synthesize_from_poly_and_ZX(optimized_poly, linear_ops, zx_graph)
        return new_dag

2. Performance expectations

a. Circuit families that see the largest wins

• Variational-layered algorithms (QAOA, VQE, UCC ansatz).
  These circuits contain whole layers of commuting $ZZ$ or Pauli-exponential gates. So GPGO is expected to pack those interactions to the chromatic-index depth and merges repeated phase rotations, typically cutting two-qubit depth and CNOT count.
• Trotterised Hamiltonian simulation
  Global ZX rewriting cancels redundant entanglers arising between succeessive Trotter steps, while the phase-polynomial solver fusese smaller $R_z$ angles into a single minimal-T implementation.
• Arithmetic / Boolean-oracle blocks
  These are rich in linear-phase dependeices. So by decoding the associated Reed-Muller code the pass reduces $T$-count to theoretical rank bound of the phase matrix.

b. UCC benchmark metrics affected

• Compiled Gate Count Ratio is expected to redcue by Global ZX cancellations plus algebraic T-compression removing redundant entanglers.
• Observable under noise may increase by fewer two-qubit and $T$ gate cut physical error locations. Optionally tiny-rotation pruning further mitigates noise.
• Compilation Time might be increased based on the circuits. Solving a decoding problem and running graph rewrites is cosly, but performed once offline.

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."

[Misty-W]

I'm curious to see the benchmark results- feel free to post them here when ready @q-inho . And in the meantime, the UCC team is here to answer questions as needed :)

[jordandsullivan]

@q-inho How is development going for you? Do you need any support from the UCC team? :)

[jordandsullivan]

Okey doke! Thanks for the update. Let us know if we can help support!

[jordandsullivan]

@q-inho Do you need any pointers on other directions for development? :)

[q-inho]

Actually I am changing the strategy since this method does not look promising according to the tests

[jordandsullivan]

Makes sense. Feel free to submit a new proposal for the technique you'd like to pursue :)

[jordandsullivan]

You're also welcome to work on this outside of UnitaryHACK. It's just the bounty that has a deadline.