Implement two qubit unitary to operations algorithm from https://arxiv.org/abs/quant-ph/0406176

[NoureldinYosri]

The paper https://arxiv.org/abs/quant-ph/0406176 introduces an algorithm for performing quantum shannon decomposition. We have this algorithm implemented in Cirq in

Cirq/cirq-core/cirq/transformers/analytical_decompositions/quantum_shannon_decomposition.py

Line 44 in 351a08e

def quantum_shannon_decomposition(

However, one of the base cases of the algorithms is not implemented. Namely A.2 the base case for a two qubit unitary, instead cirq uses another decomposition

Cirq/cirq-core/cirq/transformers/analytical_decompositions/quantum_shannon_decomposition.py

Lines 101 to 113 in 351a08e

	if n == 4:
	operations = tuple(
	two_qubit_matrix_to_cz_operations(
	qubits[0], qubits[1], u, allow_partial_czs=True, clean_operations=True, atol=atol
	)
	)
	yield from operations
	i, j = np.unravel_index(np.argmax(np.abs(u)), u.shape)
	new_unitary = unitary_protocol.unitary(FrozenCircuit.from_moments(*operations))
	global_phase = np.angle(u[i, j]) - np.angle(new_unitary[i, j])
	if np.abs(global_phase) > 1e-9:
	yield ops.global_phase_operation(np.exp(1j * global_phase))
	return

Which is not as efficient as the decompositin described in A.2. It would be nice to implement A.2 and uses it in QSD.

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

[RahilJain1366]

Hi @NoureldinYosri, can I take this up too since I am trying to find a solution for #6770?

[senecameeks]

Cirq Cynq: This will improve the performance by reducing the number of rotations and depth of the circuit.

[senecameeks]

@RahilJain1366, thanks for offering, let's discuss after #6770 is complete

[ldi18]

Hi, I’m also interested in working on this if @RahilJain1366 hasn’t taken it up yet @senecameeks .

[codrut3]

I implemented the A.2 case. However, when comparing unoptimized circuit depth for the current Cirq package with my change, I didn't observe any improvement:

qubits = [3, 4, 5, 6, 7, 8]
cirq_package = [45, 219, 963, 4035, 16515, 66819]
with_my_change = [47, 221, 965, 4037, 16517, 66821]

To obtain these numbers I generated a random unitary for the given number of qubits and then ran Shannon decomposition.

Note that these numbers are the same as those here.

The reason for this is that the 3-qubit case already uses the A.2 optimization. The crux of A.2 was already implemented by @balopat in this method. Removing the 3-qubit base case and using A.2 for n=2 doesn't help.

However, when running the optimizer:
cirq.optimize_for_target_gateset(circuit, gateset=cirq.CZTargetGateset(preserve_moment_structure=False), max_num_passes=None)
I observed a substantial improvement in the current package (without A.2 base case):

qubits = [3, 4, 5, 6, 7, 8]
cirq_package = [41, 203, 899, 3779, 15491, 62723]

which is better than what was reported here.

Furthermore, I discovered that quantum Shannon decomposition is very slow. I traced this issue back to cleanup_operations in two_qubit_to_cz.py. merge_single_qubit_gates_to_phased_x_and_z is very slow, even for a small set of gates (size 7). I was able to optimize this substantially, reducing the time almost in half.

qubits = [3, 4, 5, 6, 7, 8]
time_sec_no_optimization = [0.05, 0.18, 0.76, 2.81, 11.22, 42.79]
time_sec_with_optimization = [0.04, 0.1, 0.39, 1.31, 5.43, 21.8]

You can see my code here.

To summarize:

• there is no need for the A.2 case as it's already part of the 3-qubit decomposition. I suggest this issue to be closed;
• the running time can be reduced sustantially by optimizing cleanup_operations. I am happy to submit my fix here. I suggest spending time to also fix merge_single_qubit_gates_to_phased_x_and_z, but this can be a different issue.

@NoureldinYosri @ACE07-Sev can you please have a look and let me know your thoughts?
@ACE07-Sev can you rerun your analysis and confirm the depth is better at the current package version?

[ACE07-Sev]

I implemented A.2 a few months ago for quick and it definitely improves depth.

I'll have a look soon but in the meantime kindly check yours with mine.

[codrut3]

@ACE07-Sev as I explain in the comment A.2 is already implemented here, but it's not obvious, because it's part of the n=3 base case. I ran my local analysis and didn't see any improvement from removing the n=3 base case and using n=2 and A.2. However, running the circuit through the optimizer substantially reduces depth: the issue is solved because the optimizer got better and is similar to the Qiskit one now.

If you have a colab or script to share, I'm happy to run it.

[ACE07-Sev]

@codrut3 I'm comparing with mine now. Can you run yours with transpile afterwards please? I want to compare the depths with mine.

Here are my results:

41
197
869
3653
14981
60677

This is the depth of a circuit with U3 and CX gates as done before (I don't have my old script anymore, but that one was the same).

[codrut3]

Are these Qiskit numbers? The Cirq numbers are:

qubits = [3, 4, 5, 6, 7, 8]
cirq_package = [41, 203, 899, 3779, 15491, 62723]

Would you consider this to be close enough?

[ACE07-Sev]

Yes, those are the qiskit numbers (after transpile). Did you run transpile on yours as well?