Quantum shannon decomposition fails for QFT with non-unitary matrix error

[doublehoon]

Description of the issue

I encountered an issue when attempting to decompose the unitary matrix of QFT(4) using the built-in quantum_shannon_decomposition function in Cirq.

According to the documentation, the quantum_shannon_decomposition function is supposed to decompose the unitary matrix into a sequence of CX, YPow, ZPow, and CNOT gates. However, it seems that the result of the decomposition contains a non-unitary matrix.

How to reproduce the issue

import cirq

qft4_qubits = cirq.NamedQubit.range(4, prefix="q")
qft4_op = cirq.qft(*qft4_qubits)
qft4_qc = cirq.Circuit(qft4_op)

qft4_utry = cirq.unitary(qft4_qc)

print(cirq.is_unitary(qft4_utry))   # True

qsd_qft4_qubits = cirq.NamedQubit.range(4, prefix="q")
qsd_qft4_op = cirq.quantum_shannon_decomposition(qsd_qft4_qubits, qft4_utry)
qsd_qft4_qc = cirq.Circuit(qsd_qft4_op)

qsd_qft4_utry = cirq.unitary(qsd_qft4_qc)

print(cirq.allclose_up_to_global_phase(qft4_utry, qsd_qft4_utry))

```shell True Traceback (most recent call last): File "/tmp/qsd_bug_cirq.py", line 11, in qsd_qft4_qc = cirq.Circuit(qsd_qft4_op) ^^^^^^^^^^^^^^^^^^^^^^^^^ File "/anaconda3/envs/qcs/lib/python3.11/site-packages/cirq/circuits/circuit.py", line 1771, in __init__ flattened_contents = tuple(ops.flatten_to_ops_or_moments(contents)) ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ File "/anaconda3/envs/qcs/lib/python3.11/site-packages/cirq/ops/op_tree.py", line 134, in flatten_to_ops_or_moments yield from flatten_to_ops_or_moments(subtree) File "/anaconda3/envs/qcs/lib/python3.11/site-packages/cirq/ops/op_tree.py", line 133, in flatten_to_ops_or_moments for subtree in root: File "/anaconda3/envs/qcs/lib/python3.11/site-packages/cirq/transformers/analytical_decompositions/quantum_shannon_decomposition.py", line 89, in quantum_shannon_decomposition yield from _msb_demuxer(qubits, v1, v2) File "/anaconda3/envs/qcs/lib/python3.11/site-packages/cirq/transformers/analytical_decompositions/quantum_shannon_decomposition.py", line 158, in _msb_demuxer yield from quantum_shannon_decomposition(demux_qubits[1:], W) File "/anaconda3/envs/qcs/lib/python3.11/site-packages/cirq/transformers/analytical_decompositions/quantum_shannon_decomposition.py", line 66, in quantum_shannon_decomposition raise ValueError( ValueError: Expected input matrix u to be unitary, but it fails cirq.is_unitary check ```

Cirq version 1.4.1

[NoureldinYosri]

@uzzzzzzz can you take a look? since you implemented this https://github.com/quantumlib/Cirq/pull/6020

[pavoljuhas]

csynque meeting - we need to confirm this fails due to significant difference rather than round-off errors.