.. _branching: Branching ********* In an ordinary ``quantum_kernel`` function, it is not possible to use classical ``if`` statements to decide what quantum operations to apply unless the condition can be resolved at compile-time. For example, the following code is not supported. .. code-block:: C++ quantum_kernel void conditional_qk_FAIL(qbit &q, bool b) { if (b) { H(q); } } Classical control *is* natively supported by quantum kernel expressions, however, via the *classical if* or ``cIf``. ``QExpr qexpr::cIf(bool b, QExpr condTrue, QExpr condFalse)`` If the classical boolean value ``b`` is true, execute the quantum instructions given by ``condTrue``; and otherwise execute the instructions given by ``condFalse``. The boolean value ``b`` may be dynamic (need not be resolvable at compile-time). Classical control is the first indication that the ``QExpr`` type does not just represent a simple gate sequence. As an example, the above invalid quantum kernel function can be achieved by evaluating the following ``QExpr`` function: .. code-block:: C++ QExpr conditional_qexpr_SUCCESS(qbit &q, bool b) { return qexpr::cIf(b, qexpr::_H(q), qexpr::identity()); } Though the condition argument ``b`` to ``cIf`` can be dynamic, care should be taken with unresolved conditionals. Due to compile-time constraints, the FLEQ compilation stage of IQC will combinatorally generate all possible QBBs from unresolved branches and insert classical branching instructions to select amongst them. As a result, the number of QBBs generated by an unresolved conditional can grow exponentially, especially when used alongside ``qexpr::join`` or recursion (see :ref:`recursion`). This exponential explosion can be overcome via separate evaluation calls or through the use of ``qexpr::bind``; see :ref:`bind`. Two additional variants of ``cIf`` are also added for convenience: ``QExpr qexpr::cIfTrue(bool b, QExpr condTrue)`` If the classical boolean value ``b`` is true, return ``condTrue``, and otherwise return the identity ``QExpr``; i.e. equivalent to ``qexpr::cIf(b, condTrue, qexpr::identity())``. ``QExpr qexpr::cIfFalse(bool b, QExpr condFalse)`` If the classical boolean value ``b`` is false, return ``condFalse``, and otherwise return the identity ``QExpr``; i.e. equivalent to ``qexpr::cIf(b, qexpr::identity(), condFalse)``. .. _recursion: Recursion ********* With the introduction of branching, function recursion is now possible by providing exit conditions for recursion, i.e. by acting as a *recursion guard*. These recursive calls are the FLEQ equivalent of loops in standard C++ and represent the single most powerful tool for modular code development with FLEQ. A quintessential example of a recursive ``QExpr`` function is one that iterates over all the qubits in a ``QList`` and applies one or more gates to each of them. For example, the following function applies a ``PrepZ`` gate to every qubit in a ``QList``. .. code-block:: C++ QExpr prepAll(qlist::QList qs) { return qexpr::cIf(qs.size() == 0, qexpr::identity(), // qs.size() == 0 qexpr::_PrepZ(qs[0]) + prepAll(qs + 1) // qs.size() > 0 ); } This function uses a conditional ``cIf`` to determine if the ``QList`` is empty. If it is, it will terminate by returning ``identity``. If the ``QList`` is non-empty, the condition resolves to the second branch, which applies ``_PrepZ`` on the first element and recursively calls ``prepAll`` to the tail of the ``QList``. For those familiar with imperative-style ``for`` and ``while`` loops, it may take some practice to master function recursion, but the results can be elegant and useful. A recursive function is best matched conceptually to a ``while`` loop with a "continue" condition. For example, the general structure of a ``while`` loop is .. code-block:: C++ while(cont){ cont = new_cont; } The analogous structure using FLEQ would be .. code-block:: C++ QExpr while_analog(bool cont, QExpr body) { bool new_cont = ...; return qexpr::cIf(cont, while_analog(new_cont, body) * body, //cont == true qexpr::identity() //cont == false ); } Like the ``while`` loop, the ``while_analog`` function first checks if the ``cont`` condition is ``true``, in which case it "executes" ``body``. Then, the ``while_analog`` continues the loop by making a recursive call with boolean guard ``new_cont``. This recursive call is parallel to the ``while`` loop implicitly looping back and rechecking the updated value of ``cont``. When the ``cont`` condition is ``false``, the ``while_analog`` function exits the recursion by returning ``qexpr::identity()``. A ``for`` loop can be translated into a recursive ``QExpr`` function in a similar way. For nested loops, each loop will require at least one function. For example, consider a function that applies a ``CNOT`` gate to every unique pair of qubits in a ``QList``. This will require two loops and thus two functions: .. code-block:: C++ // This function uses the fixed argument q as the control // and loops over each qubit in after_q as the target QExpr CNOTOnAll_helper(qbit & q, qlist::QList after_q){ return qexpr::cIf(after_q.size() > 0, qexpr::_CNOT(q, after_q[0]) + CNOTOnAll_helper(q, after_q + 1), // after_q.size() > 0 qexpr::identity() // after_q.size() == 0 ); } // This function loops over every qubit in qs, calling the helper // function on it and every qubit that comes after it QExpr CNOTOnAll(qlist::QList qs){ qlist::QList q_after = qs + 1; return qexpr::cIf(qs.size() > 0, CNOTOnAll_helper(qs[0], q_after) + CNOTOnAll(q_after), // qs.size() > 0 qexpr::identity() // qs.size() == 0 ); } Note that recursion does not require the function be called inside its body directly; rather, it is a matter of the function having a dependency on itself (see :ref:`compilation-overview`), which can occur through other functions called inside the body via mutual recursion. For example, consider the following pair of mutually recursive functions, one of which applies one sequence of gates to even qubits in a ``QList``, and the other of which applies another sequence to odd qubits. .. code-block:: C++ QExpr oddQubits(qlist::QList qs) { return qexpr::cIfFalse(qs.size() == 0, qexpr::_X(qs[0]) + evenQubits(qs+1) ); } QExpr evenQubits(qlist::QList qs) { return qexpr::cIfFalse(qs.size() == 0, qexpr::_H(qs[0]) + oddQubits(qs+1) ); } It is important to note that all recursion in quantum kernel expressions must be able to be unrolled at compile-time. This ensures that quantum kernel expressions can be compiled to quantum basic blocks as described in the :ref:`intro`. Practically, this means that the arguments to conditionals used as recursive guards must all be resolvable at compile-time through the FLEQ compilations unrolling mechanism. Examples of such compile-time guards include but are not limited to: * constant integers or boolean values; * the size of a ``QList``, as in ``prepAll`` above; or * the size or contents of a ``DataList`` (see :ref:`datalist`). Users can set the recursion limit via a command-line flag. ``-F recursion-limit-power=`` Sets the FLEQ recursion limit to scale as a power ```` of the number of global qubits; default = 1. ``-F recursion-limit=`` Sets the FLEQ recursion limit to a fixed number ````; default is the maximum of 1000 or ````, if set. The ``recursion-limit`` option overrides the ``recursion-limit-power`` option. FLEQ does not currently support repeat-until-success loops, although they can be implemented by evaluating a ``QExpr`` inside a classical loop. For example, consider a repeat-until-success (RUS) loop that applies a quantum kernel expression ``op`` over and over until its measurement result returns 1: .. code-block:: C++ QExpr op(double param, bool& result); double new_param(double old_param); int RUS(double initial_param) { double param = initial_param; bool result = false; while (!result) { qexpr::eval_release(op(param, result)); param = new_param(param); } } FLEQ may allow for runtime recursion in future versions.