Support native compilation of any quantum unitary into 1/2-qubit gates

[briancylui]

Is your feature request related to a use case or problem? Please describe.

Use case: Given a unitary matrix representing a quantum circuit on n qubits, output a list of Cirq operations implemented with one-qubit and two-qubit gates.

This use case concerns the general compilation of a quantum circuit into a target gate set.

In Jan 2021 (https://arxiv.org/pdf/2101.02993.pdf), OpenQL authors compared different approaches (including CSD and QSD) and implemented QSD in OpenQL in C++ to dump QASM code as the best general unitary decomposition method so far (to {Ry, Rz, CNOT} gates). Qiskit also has a transpile method to compile a circuit into a target gate set.

Right now, Cirq has a variety of optimizers. To perform general unitary decomposition, users may import OpenQL and get a decomposed Cirq circuit from OpenQL's QASM output.

It would be good for Cirq users to be able to natively compile any unitary into one-qubit gates and two-qubit gates, without importing additional dependencies like OpenQL.

Describe the solution you'd like

• Implement QSD in Cirq or Scipy in Python, or port from a C++ implementation for speed.
• Implement a general compilation function including fallbacks for edge cases.

[optional] Describe alternatives/workarounds you've considered

[optional] Additional context (e.g. screenshots)

What is the urgency from your perspective for this issue? Is it blocking important work?

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

[balopat]

Discussed on Cirq Sync:

• it should be very clear for users that in small number of qubits this scales exponentially - and won't be feasible to run it on real hardware
• we should not depend on OpenQL but rather we prefer using scipy.linalg.cossin and generalizing the structure in cirq.three_qubit_matrix_to_operations

[mpharrigan]

@tanujkhattar

[mpharrigan]

@tanujkhattar can you update the status of this

[tanujkhattar]

General compilation of arbitrary k-qubit unitaries into 1/2 qubit gates currently doesn't exist in Cirq and is out of scope for our Cirq 1.0 roadmap. We will be happy to accept contributions from the community if someone is interested to work on it and add an analytical decomposer to Cirq for doing this decomposition.

Note that specific built-in multi qubit Cirq gates (like QFT) do end up compiling into native 1/2 qubit gates because they specify a _decompose_ protocol in terms of other "simpler" gates. But compiling arbitrary k-qubit unitaries is not supported right now.

[cognigami]

RFC proposed. @tanujkhattar to review RFC and PR. cc @uzzzzzz

[dstrain115]

@uzzzzzzz is this complete now? Can we close this issue? @cognigami