Returns a circuit for a target gate controlled by
    a collection of control qubits. [Barenco1995]_

    Uses a number of gates quadratic in the number of control qubits.

    .. [Barenco1995] A. Barenco, C. Bennett, R. Cleve (1995) Elementary Gates
        for Quantum Computation`<https://arxiv.org/abs/quant-ph/9503016>`_
        Sec 7.2

def control_circuit(controls: Qubits, gate: Gate) -> Circuit:
    """
    Returns a circuit for a target gate controlled by
    a collection of control qubits. [Barenco1995]_

    Uses a number of gates quadratic in the number of control qubits.

    .. [Barenco1995] A. Barenco, C. Bennett, R. Cleve (1995) Elementary Gates
        for Quantum Computation`<https://arxiv.org/abs/quant-ph/9503016>`_
        Sec 7.2
    """
    # Kudos: Adapted from Rigetti Grove's utility_programs.py
    # grove/utils/utility_programs.py::ControlledProgramBuilder

    circ = Circuit()
    if len(controls) == 1:
        q0 = controls[0]
        if isinstance(gate, X):
            circ += CNOT(q0, gate.qubits[0])
        else:
            cgate = control_gate(q0, gate)
            circ += cgate
    else:
        circ += control_circuit(controls[-1:], gate ** 0.5)
        circ += control_circuit(controls[0:-1], X(controls[-1]))
        circ += control_circuit(controls[-1:], gate ** -0.5)
        circ += control_circuit(controls[0:-1], X(controls[-1]))
        circ += control_circuit(controls[0:-1], gate ** 0.5)
    return circ