Compiling: heuristic for compiling 2 qubits gates to the native gateset

[tanujkhattar]

Is your feature request related to a use case or problem? Please describe.
Approximate compilation to arbitrary target gatesets is a useful compilation primitive for the NISQ era. Currently, cirq only has GateTabulation method in cirq_google which supports approximate compilation to arbitrary target gatesets. However, being in cirq_google, GateTabulation is not very easily discoverable.

There are also other nice approximate compilation techniques like https://arxiv.org/pdf/2106.15490.pdf which should exist in cirq_core.

Describe the solution you'd like
Implement approximate compilation routine based on NuOps and bring GateTabulation to Cirq core

• The GateTabulation compilation technique is not specific to cirq_google and should exist in cirq_core. There have also been requests in the past to implement a generic optimizer based on GateTabulation (Add a generic Optimizer that makes use of GateTabulation #4059), which should also exist in cirq_core.
• The NuOps compilation method described https://arxiv.org/pdf/2106.15490.pdf is very similar to GateTabulation, but smarter in the sense that instead of first trying to tabulate the weyl chamber by generating random single qubit unitaries it rather considers the rotation angles of single qubit unitaries as optimization parameters and uses a numerical optimizer to find those angles for a given target unitary. This removes the heavy precomputation stage needed for GateTabulation and should potentially also improve the accuracy. It also allows for noise adoptability during gate compilation by enabling compilation to different base gates for different target unitaries (which is still possible by GateTabulation but would need a precomputation stage for each different base gate).

What is the urgency from your perspective for this issue? Is it blocking important work?
This work should be done as part of the gate compiling roadmap item (#3239) and we should eventually aim for a suit of approximate compilation methods similar to the various exact kak based analytical gate synthesis methods that exist today.

P2 - we should do it in the next couple of quarters

[Ashalynd]

Hi Tanuj. Would you mind if I have a look at this?

[tanujkhattar]

Sure! There are multiple smaller work items for this larger bug

1. Bring GateTabulation out of cirq-google to cirq-core
   2.Add a generic optimizer that makes use of GateTabulation
2. Implement the NuOps compiler, given in the linked paper, in cirq-core.

@chrischris96 had also reached out to me over email earlier expressing interest in this issue but I think the issue is large enough that more than one person can work on it in parallel.

Please let me know if you have any further questions.

[Ashalynd]

Thanks for the quick reply!

Is there a dependency between the first (GateTabulation refactoring + optimizer) and the second (NuOps implementation) tasks?

If not, would it help to split this issue into two or more separate ones?

[tanujkhattar]

No, there's no dependency.

There's already #4059 that talks about adding an optimizer that uses the GateTabulation method. Feel free to create new smaller sub-issues to track specific work items.

[chrischris96]

@Ashalynd I read the paper and don't have any preferences about which part to work on. Would you rather work on the optimizer or the NuOps implementation task?

[Ashalynd]

Hi @chrischris96,

Sure, I can take the first part (refactoring GateTabulation and creating an optimizer).

@tanujkhattar - that would correspond to issue #4059 plus may be a separate issue for refactoring, correct?

[tanujkhattar]

@Ashalynd Yes, that's correct.