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))

True

Traceback (most recent call last):
  File "/tmp/qsd_bug_cirq.py", line 11, in <module>
    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 #6020

[pavoljuhas]

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

[NoureldinYosri]

related to #6725

@pavoljuhas it seems that quantum_shannon_decomposition is indeed buggy

[ACE07-Sev]

@NoureldinYosri I would say this is a good opportunity to rewrite how cirq does QSD for two reasons:

1. It doesn't work as is.
2. Compared to Qiskit's QSD, it's 14 percent more expensive in terms of depth. This is an extremely important compilation which would directly dictate the size of problems you can meaningfully map to actual hardware.

It would be great if you can just replicate what Qiskit has for your QSD. I'd be more than happy to help where I can.

Here's a reference for QSD through qiskit vs through cirq (let's assume it's fixed):

Cirq's depth: (7, 49, 235, 1027, 4291, 17539, 70915, 285185)
Qiskit's depth: (7, 41, 197, 869, 3653, 14981, 60677, 244229)

[ACE07-Sev]

I think it would be worthwhile to add two qubit decomposition function as I mentioned before. Looking at Qiskit's version VS Cirq's version:


There's a considerable difference. Besides that, the rest is the same from what I can infer.

[NoureldinYosri]

@ACE07-Sev QSD was a recent addition to Cirq and we welcome help with this and other issues. if you (or someone else) would like to help fix this, feel free to assign the issue to yourself and we would be very grateful. otherwise we will discuss this issue in the next cirq-sync.

[ACE07-Sev]

May I ask how I can get added to the meeting for this? I had a look at the cirq-dev google group, but I can't see any scheduled meetings there.

[NoureldinYosri]

@ACE07-Sev when you join https://groups.google.com/g/cirq-dev, you get automatic invitation to the meeting