Eliminate multiple control layers on CX/CZ.controlled([0])

[daxfohl]

Describe your design idea/issue

All other cases of .controlled() in Cirq, as well as the ControlledGate constructor, do their best to flatten the layers of control where possible. The one exception is CX/CZ.controlled(...), where ... is a non-default set of control values.

    for cv in [1, 0]:
        for g in [cirq.X, cirq.CX, cirq.CCX, cirq.Z, cirq.CZ, cirq.CCZ]:
            print()
            for i in range(5):
                print(repr(g.controlled(i, [cv] * i)))

Output:

cirq.X
cirq.CNOT
cirq.TOFFOLI
cirq.ControlledGate(sub_gate=cirq.X, num_controls=3)
cirq.ControlledGate(sub_gate=cirq.X, num_controls=4)

cirq.CNOT
cirq.TOFFOLI
cirq.ControlledGate(sub_gate=cirq.X, num_controls=3)
cirq.ControlledGate(sub_gate=cirq.X, num_controls=4)
cirq.ControlledGate(sub_gate=cirq.X, num_controls=5)

cirq.TOFFOLI
cirq.ControlledGate(sub_gate=cirq.X, num_controls=3)
cirq.ControlledGate(sub_gate=cirq.X, num_controls=4)
cirq.ControlledGate(sub_gate=cirq.X, num_controls=5)
cirq.ControlledGate(sub_gate=cirq.X, num_controls=6)

cirq.Z
cirq.CZ
cirq.CCZ
cirq.ControlledGate(sub_gate=cirq.Z, num_controls=3)
cirq.ControlledGate(sub_gate=cirq.Z, num_controls=4)

cirq.CZ
cirq.CCZ
cirq.ControlledGate(sub_gate=cirq.Z, num_controls=3)
cirq.ControlledGate(sub_gate=cirq.Z, num_controls=4)
cirq.ControlledGate(sub_gate=cirq.Z, num_controls=5)

cirq.CCZ
cirq.ControlledGate(sub_gate=cirq.Z, num_controls=3)
cirq.ControlledGate(sub_gate=cirq.Z, num_controls=4)
cirq.ControlledGate(sub_gate=cirq.Z, num_controls=5)
cirq.ControlledGate(sub_gate=cirq.Z, num_controls=6)

cirq.X
cirq.ControlledGate(sub_gate=cirq.X, control_values=cirq.ProductOfSums(((0,),)),control_qid_shape=(2,))
cirq.ControlledGate(sub_gate=cirq.X, control_values=cirq.ProductOfSums(((0,), (0,))),control_qid_shape=(2, 2))
cirq.ControlledGate(sub_gate=cirq.X, control_values=cirq.ProductOfSums(((0,), (0,), (0,))),control_qid_shape=(2, 2, 2))
cirq.ControlledGate(sub_gate=cirq.X, control_values=cirq.ProductOfSums(((0,), (0,), (0,), (0,))),control_qid_shape=(2, 2, 2, 2))

cirq.CNOT
cirq.ControlledGate(sub_gate=cirq.CNOT, control_values=cirq.ProductOfSums(((0,),)),control_qid_shape=(2,))
cirq.ControlledGate(sub_gate=cirq.CNOT, control_values=cirq.ProductOfSums(((0,), (0,))),control_qid_shape=(2, 2))
cirq.ControlledGate(sub_gate=cirq.CNOT, control_values=cirq.ProductOfSums(((0,), (0,), (0,))),control_qid_shape=(2, 2, 2))
cirq.ControlledGate(sub_gate=cirq.CNOT, control_values=cirq.ProductOfSums(((0,), (0,), (0,), (0,))),control_qid_shape=(2, 2, 2, 2))

cirq.TOFFOLI
cirq.ControlledGate(sub_gate=cirq.X, control_values=cirq.ProductOfSums(((0,), (1,), (1,))),control_qid_shape=(2, 2, 2))
cirq.ControlledGate(sub_gate=cirq.X, control_values=cirq.ProductOfSums(((0,), (0,), (1,), (1,))),control_qid_shape=(2, 2, 2, 2))
cirq.ControlledGate(sub_gate=cirq.X, control_values=cirq.ProductOfSums(((0,), (0,), (0,), (1,), (1,))),control_qid_shape=(2, 2, 2, 2, 2))
cirq.ControlledGate(sub_gate=cirq.X, control_values=cirq.ProductOfSums(((0,), (0,), (0,), (0,), (1,), (1,))),control_qid_shape=(2, 2, 2, 2, 2, 2))

cirq.Z
cirq.ControlledGate(sub_gate=cirq.Z, control_values=cirq.ProductOfSums(((0,),)),control_qid_shape=(2,))
cirq.ControlledGate(sub_gate=cirq.Z, control_values=cirq.ProductOfSums(((0,), (0,))),control_qid_shape=(2, 2))
cirq.ControlledGate(sub_gate=cirq.Z, control_values=cirq.ProductOfSums(((0,), (0,), (0,))),control_qid_shape=(2, 2, 2))
cirq.ControlledGate(sub_gate=cirq.Z, control_values=cirq.ProductOfSums(((0,), (0,), (0,), (0,))),control_qid_shape=(2, 2, 2, 2))

cirq.CZ
cirq.ControlledGate(sub_gate=cirq.CZ, control_values=cirq.ProductOfSums(((0,),)),control_qid_shape=(2,))
cirq.ControlledGate(sub_gate=cirq.CZ, control_values=cirq.ProductOfSums(((0,), (0,))),control_qid_shape=(2, 2))
cirq.ControlledGate(sub_gate=cirq.CZ, control_values=cirq.ProductOfSums(((0,), (0,), (0,))),control_qid_shape=(2, 2, 2))
cirq.ControlledGate(sub_gate=cirq.CZ, control_values=cirq.ProductOfSums(((0,), (0,), (0,), (0,))),control_qid_shape=(2, 2, 2, 2))

cirq.CCZ
cirq.ControlledGate(sub_gate=cirq.Z, control_values=cirq.ProductOfSums(((0,), (1,), (1,))),control_qid_shape=(2, 2, 2))
cirq.ControlledGate(sub_gate=cirq.Z, control_values=cirq.ProductOfSums(((0,), (0,), (1,), (1,))),control_qid_shape=(2, 2, 2, 2))
cirq.ControlledGate(sub_gate=cirq.Z, control_values=cirq.ProductOfSums(((0,), (0,), (0,), (1,), (1,))),control_qid_shape=(2, 2, 2, 2, 2))
cirq.ControlledGate(sub_gate=cirq.Z, control_values=cirq.ProductOfSums(((0,), (0,), (0,), (0,), (1,), (1,))),control_qid_shape=(2, 2, 2, 2, 2, 2))

The CX and CZ in the nontrivial control value cases end up with ControlledGates that wrap CX/CZ, instead of having the ControlGate absorb the outer control layer like everywhere else. Beyond the inconsistency, multiple layers of control are futzy to work with, awkward to understand, and harder to decompose. (Hence the isinstance(subgate, CZ) in ControlledGate._decompose_).

Making this consistent seems worthwhile, and given the behavior of most cases, it seems like this was the original goal, but it just got lost in the special nontrivial control values cases.

I'm pretty sure this is just modifying the CX/CZPowGate.controlled methods and adding unit tests, so marking as good first issue.

[pavoljuhas]

csynque meeting - let us verify if this behavior was intended, ie, is expected elsewhere or should be changed as suggested.

[daxfohl]

@pavoljuhas sgtm. Also note there's an ulterior motive here: if we can do this, #7242, and #7238, it'll allow us to get rid of this ugly block that special-cases controlled CZ gates:

Cirq/cirq-core/cirq/ops/controlled_gate.py

Lines 190 to 221 in 50d7198

	if isinstance(self.sub_gate, common_gates.CZPowGate):
	z_sub_gate = common_gates.ZPowGate(exponent=self.sub_gate.exponent)
	num_controls = self.num_controls() + 1
	control_values = self.control_values & cv.ProductOfSums(((1,),))
	control_qid_shape = self.control_qid_shape + (2,)
	controlled_z = (
	z_sub_gate.controlled(
	num_controls=num_controls,
	control_values=control_values,
	control_qid_shape=control_qid_shape,
	)
	if protocols.is_parameterized(self)
	else ControlledGate(
	z_sub_gate,
	num_controls=num_controls,
	control_values=control_values,
	control_qid_shape=control_qid_shape,
	)
	)
	if self != controlled_z:
	result = controlled_z.on(*qubits)
	if self.sub_gate.global_shift == 0:
	return result
	# Reconstruct the controlled global shift of the subgate.
	total_shift = self.sub_gate.exponent * self.sub_gate.global_shift
	phase_gate = gp.GlobalPhaseGate(1j ** (2 * total_shift))
	controlled_phase_op = phase_gate.controlled(
	num_controls=self.num_controls(),
	control_values=self.control_values,
	control_qid_shape=self.control_qid_shape,
	).on(*control_qubits)
	return [result, controlled_phase_op]

It's not the end of the world if it can't be supported. But I tried to break that into three separate issues that each are improvements on existing behavior.

There's precedent for a similar change here: #5883 (comment), with rationale for it being non-breaking. cc @tanujkhattar