# Operations and Functions in Q#

## Defining New Operations

Operations are the core of Q#. Once declared, they can either be called from classical .NET applications, for example, using a simulator or by other operations within Q#. Each operation defined in Q# can call any number of other operations, including the built-in intrinsic operations defined by the language. The particular way in which Q# defines these intrinsic operations depends on the target machine. When compiled, each operation is represented as a .NET class type that can be provided to target machines.

Each Q# source file can define any number of operations. Operation names must be unique within a namespace and can not conflict with type or function names.

An operation declaration consists of the keyword `operation`

, followed by the symbol that is the operation's name, a typed identifier tuple that defines the arguments to the operation, a colon `:`

, a type annotation that describes the operation's result type, optionally an annotation with the operation characteristics, an open brace, and then the body of the operation declaration, enclosed in braces `{ }`

.

Each operation takes an input, produces an output, and specifies the implementation for one or more operation specializations. The possible specializations, and how to define and call them, are detailed in the different sections of this article. For now, consider the following operation, which defines only a default body specialization and takes a single qubit as its input, then calls the built-in X operation on that input:

```
operation BitFlip(target : Qubit) : Unit {
X(target);
}
```

The keyword `operation`

begins the operation definition, followed by the name; here, `BitFlip`

.
Next, the type of input is defined (`Qubit`

), along with a name, `target`

, for referring to the input within the new operation.
Lastly, `Unit`

defines that the operation's output is empty.
`Unit`

is used similarly to `void`

in C# and other imperative languages and is equivalent to `unit`

in F# and other functional languages.

Operations can also return more interesting types than `Unit`

.
For instance, the M operation returns an output of type `Result`

, representing having performed a measurement. You can pass it from an operation to another operation or use it with the `let`

keyword to define a new variable.

This approach allows for representing classical computation that interacts with quantum operations at a low level, such as in superdense coding:

```
operation DecodeSuperdense(here : Qubit, there : Qubit) : (Result, Result) {
CNOT(there, here);
H(there);
let firstBit = M(there);
let secondBit = M(here);
return (firstBit, secondBit);
}
```

Note

Each operation in Q# takes exactly one input and returns exactly one output.
Multiple inputs and outputs are represented using *tuples*, which collect multiple values together into a single value.
In this regard, Q# is a "tuple-in tuple-out" language.
Following this concept, a set of empty parentheses, `()`

, should then be read as the "empty" tuple, which has the type `Unit`

.

## Controlled and Adjoint Operations

If an operation implements a unitary transformation, as is the case for many operations in Q#, then it is possible to define how the operation acts when *adjointed* or *controlled*.
An *adjoint* specialization of an operation specifies how the "inverse" of the operation acts, while a *controlled* specialization specifies how an operation acts when its application is conditioned on the state of a particular quantum register.

Adjoints of quantum operations are crucial to many aspects of quantum computing. For an example of one such situation discussed alongside a useful Q# programming technique, see Control Flow: Conjugations. The controlled version of an operation is a new operation that effectively applies the base operation only if all of the control qubits are in a specified state. If the control qubits are in superposition, then the base operation is applied coherently to the appropriate part of the superposition. Thus, controlled operations are often used to generate entanglement.

Naturally, a *controlled adjoint* specialization could exist as well, specifying the controlled application of an operation's adjoint.

Note

If $U$ is the unitary transformation implemented by an operation `U`

, then `Adjoint U`

represents the unitary transformation $U^\dagger$, which is the complex conjugate transpose.
Successively applying an operation and then its adjoint to a state leaves the state unchanged, as illustrated by the fact that $UU^\dagger = U^\dagger U = \id$, the identity matrix.
The unitary representation of a controlled operation is slightly more nuanced, but you can find more details at Quantum computing concepts: multiple qubits.

The following section describes how to call these various specializations in your Q# code, and how to define operations to support them.

### Calling operation specializations

A *functor* in Q# is a factory that defines a new operation from another operation.
The two standard functors in Q# are `Adjoint`

and `Controlled`

.

Functors have access to the implementation of the base operation when defining the implementation of the new operation. Thus, functors can perform more complex functions than traditional higher-level functions. Functors do not have a representation in the Q# type system. It is thus currently not possible to bind them to a variable or pass them as arguments.

Use a functor by applying it to an operation, which returns a new operation.
For example, applying the `Adjoint`

functor to the `Y`

operation returns the new operation `Adjoint Y`

. You can invoke the new operation like any other operation.
For an operation to support the application of the `Adjoint`

or `Controlled`

functors, its return type necessarily needs to be `Unit`

.

`Adjoint`

functor

Thus, `Adjoint Y(q1)`

applies the `Adjoint`

functor to the `Y`

operation to generate a new operation, and applies that new operation to `q1`

.
The new operation has the same signature and type as the base operation `Y`

.
In particular, the new operation also supports `Adjoint`

, and supports `Controlled`

if and only if the base operation did.
The `Adjoint`

functor is its own inverse; that is, `Adjoint Adjoint Op`

is always the same as `Op`

.

`Controlled`

functor

Similarly, `Controlled X(controls, target)`

applies the `Controlled`

functor to the `X`

operation to generate a new operation, and applies that new operation to `controls`

and `target`

.

Note

In Q#, controlled versions always take an array of control qubits, and the controlling is always based on all of the control qubits being in the computational (`PauliZ`

) `One`

state, $\ket{1}$.
Controlling based on other states is achieved by applying the appropriate unitary operation to the control qubits before the controlled operation, and then applying the inverses of the unitary operation after the controlled operation.
For example, applying an `X`

operation to a control qubit before and after a controlled operation causes the operation to control on the `Zero`

state ($\ket{0}$) for that qubit; applying an `H`

operation before and after controls on the `PauliX`

`One`

state, that is -1 eigenvalue of Pauli X, $\ket{-} \mathrel{:=} (\ket{0} - \ket{1}) / \sqrt{2}$ rather than the `PauliZ`

`One`

state.

Given an operation expression, you can form a new operation expression by using the `Controlled`

functor.
The signature of the new operation is based on the signature of the original operation.
The result type is the same, but the input type is a two-tuple with a qubit array that holds the control qubit(s) as the first element and the arguments of the original operation as the second element.
The new operation supports `Controlled`

, and will support `Adjoint`

if and only if the original operation did.

If the original operation took only a single argument, then singleton tuple equivalence comes into play here.
For instance, `Controlled X`

is the controlled version of the `X`

operation.
`X`

has type `(Qubit => Unit is Adj + Ctl)`

, so `Controlled X`

has type `((Qubit[], (Qubit)) => Unit is Adj + Ctl)`

; because of singleton tuple equivalence, this is the same as `((Qubit[], Qubit) => Unit is Adj + Ctl)`

.

If the base operation took several arguments, remember to enclose the corresponding arguments of the controlled version of the operation in parentheses to convert them into a tuple.
For instance, `Controlled Rz`

is the controlled version of the `Rz`

operation.
`Rz`

has type `((Double, Qubit) => Unit is Adj + Ctl)`

, so `Controlled Rz`

has type
`((Qubit[], (Double, Qubit)) => Unit is Adj + Ctl)`

.
Thus, `Controlled Rz(controls, (0.1, target))`

would be a valid invocation of `Controlled Rz`

(note the parentheses around `0.1, target`

).

As another example, `CNOT(control, target)`

can be implemented as `Controlled X([control], target)`

.
If a target should be controlled by two control qubits (CCNOT), use a `Controlled X([control1, control2], target)`

statement.

`Controlled Adjoint`

The `Controlled`

and `Adjoint`

functors commute, so there is no difference between applying `Controlled Adjoint Op`

or `Adjoint Controlled Op`

.

## Defining Controlled and Adjoint Implementations

In the first operation declaration in the previous examples, the operations `BitFlip`

and `DecodeSuperdense`

were defined with signatures `(Qubit => Unit)`

and `((Qubit, Qubit) => (Result, Result))`

, respectively.
As `DecodeSuperdense`

includes measurements, it is not a unitary operation, and therefore neither controlled not adjoint specializations could exist (recall the related requirement that such an operation return `Unit`

).
However, as `BitFlip`

simply performs the unitary X operation, you could have defined it with both specializations.

This section details how to include the existence of specializations in your Q# operation declarations, hence giving them the ability to called in conjunction with the `Adjoint`

or `Controlled`

functors.
For more information about some of the situations in which it is either valid or not valid to declare certain specializations, see Circumstances for validly defining specializations in this article.

Operation characteristics define what kinds of functors you can apply to the declared operation, and what effect they have.
The existence of these specializations can be declared as part of the operation signature, specifically through an annotation with the operation characteristics: either `is Adj`

, `is Ctl`

, or `is Adj + Ctl`

.
The actual implementation of each specialization can either be *implicitly* or *explicitly* defined.

### Implicitly specifying implementations

In this case, the body of the operation declaration consists solely of the default implementation. For example:

```
operation PrepareEntangledPair(here : Qubit, there : Qubit) : Unit
is Adj + Ctl { // implies the existence of an adjoint, a controlled, and a controlled adjoint specialization
H(here);
CNOT(here, there);
}
```

Here, the corresponding implementation for each such implicitly declared specialization is automatically generated by the compiler, to be performed if the `Adjoint`

or `Controlled`

functors are used.

So, a call of `Adjoint PrepareEntangledPair`

would result in the compiler implementing the adjoint of `CNOT`

and then the adjoint of `H`

.
These individual operations are both self-adjoint, so the resulting `Adjoint PrepareEntangledPair`

operation would simply consist of applying `CNOT(here, there)`

and then `H(here)`

.
Hence you can use this to write the `DecodeSuperdense`

in the previous example more compactly, by using the adjoint of `PrepareEntangledPair`

to transform the entangled state back into an unentangled pair of qubits:

```
operation DecodeSuperdense(here : Qubit, there : Qubit) : (Result, Result) {
Adjoint PrepareEntangledPair(there, here);
let firstBit = M(there);
let secondBit = M(here);
return (firstBit, secondBit);
}
```

The annotation with the operation characteristics in the declaration is useful to ensure that the compiler auto-generates other specializations based on the default implementation.

There are several important limitations to consider when designing operations for use with functors.
Most critically, specializations for an operation that uses the output value of any other operation *cannot* be auto-generated by the compiler, as it is ambiguous how to reorder the statements in such an operation to obtain the same effect.

Therefore, it is often useful to explicitly specify the various implementations.

### Explicitly specifying implementations

In the case where the compiler cannot generate the implementation, you can specify it explicitly.
Such explicit specialization declarations can consist of a suitable *generation directive* or a user-defined implementation.
Following are the full range of possibilities, with some examples of explicit specialization.

#### Explicit specialization declarations

Q# operations can contain the following explicit specialization declarations:

- The
`body`

specialization specifies the implementation of the operation with no functors applied. - The
`adjoint`

specialization specifies the implementation of the operation with the`Adjoint`

functor applied. - The
`controlled`

specialization specifies the implementation of the operation with the`Controlled`

functor applied. - The
`controlled adjoint`

specialization specifies the implementation of the operation with both the`Adjoint`

and`Controlled`

functors applied. This specialization can also be named`adjoint controlled`

, since the two functors commute.

An operation specialization consists of the specialization tag (for example, `body`

or `adjoint`

) followed by one of:

- An explicit declaration as described in the following.
- A
*directive*that tells the compiler*how*to generate the specialization, one of:`intrinsic`

, which indicates that the target machine provides the specialization.`distribute`

, used with the`controlled`

and`controlled adjoint`

specializations. When used with`controlled`

, it indicates that the compiler should compute the specialization by applying`Controlled`

to all of the operations in the`body`

. When used with`controlled adjoint`

, it indicates that the compiler should compute the specialization by applying`Controlled`

to all of the operations in the`adjoint`

specialization.`invert`

, which indicates that the compiler should compute the`adjoint`

specialization by inverting the`body`

, for example, reversing the order of operations and applying the adjoint to each one. When used with`adjoint controlled`

, this indicates that the compiler should compute the specialization by inverting the`controlled`

specialization.`self`

, to indicate that the adjoint specialization is the same as the`body`

specialization. Using`self`

is legal for the`adjoint`

and`adjoint controlled`

specializations. For`adjoint controlled`

,`self`

implies that the`adjoint controlled`

specialization is the same as the`controlled`

specialization.`auto`

, to indicate that the compiler should select an appropriate directive to apply. You cannot use`auto`

for the`body`

specialization.

The directives and `auto`

all require a closing semi-colon `;`

.
The `auto`

directive resolves to the following generated directive if an explicit declaration of the `body`

is provided:

- The
`adjoint`

specialization generates according to the directive`invert`

. - The
`controlled`

specialization generates according to the directive`distribute`

. - The
`adjoint controlled`

specialization generates according to the directive`invert`

if an explicit declaration for`controlled`

is given but not one for`adjoint`

, and`distribute`

otherwise.

Tip

If an operation is self-adjoint, explicitly specify either the adjoint or the controlled adjoint specialization via the generation directive `self`

to allow the compiler to make use of that information for optimization purposes.

A specialization declaration containing a user-defined implementation consists of an argument tuple followed by a statement block with the Q# code that implements the specialization.
In the argument list, `...`

is used to represent the arguments declared for the operation as a whole.
For `body`

and `adjoint`

, the argument list should always be `(...)`

; for `controlled`

and `adjoint controlled`

, the argument list should be a symbol that represents the array of control qubits, followed by `...`

, enclosed in parentheses; for example, `(controls,...)`

.

### Examples

An operation declaration might be as simple as the following, which defines the primitive Pauli X operation:

```
operation X (qubit : Qubit) : Unit
is Adj + Ctl {
body intrinsic;
adjoint self;
}
```

Note that the adjoint of the Pauli X operation is defined with the directive `self`

because by definition `X`

is its own inverse.

In the earlier `PrepareEntangledPair`

example, the code is equivalent to the following code containing explicit specialization declarations:

```
operation PrepareEntangledPair(here : Qubit, there : Qubit) : Unit
is Ctl + Adj {
body (...) { // default body specialization
H(here);
CNOT(here, there);
}
adjoint auto; // auto-generate adjoint specialization
controlled auto; // auto-generate controlled specialization
controlled adjoint auto; // auto-generate controlled adjoint specialization
}
```

The keyword `auto`

indicates that the compiler should determine how to generate the specialization implementation.

#### User-defined specialization implementation

If the compiler cannot generate the implementation for a certain specialization automatically, or if a more efficient implementation can be given, then you can manually define the implementation.

```
operation PrepareEntangledPair(here : Qubit, there : Qubit) : Unit
is Ctl + Adj {
body (...) { // default body specialization
H(here);
CNOT(here, there);
}
controlled (cs, ...) { // user-defined implementation for the controlled specialization
Controlled H(cs, here);
Controlled X(cs + [here], there);
}
adjoint invert;
controlled adjoint invert;
}
```

In the previous example, `adjoint invert;`

indicates that the adjoint specialization is to be generated by inverting the body implementation, and `controlled adjoint invert;`

indicates that the controlled adjoint specialization is to be generated by inverting the given implementation of the controlled specialization.

If one or more specializations besides the default body need to be explicitly declared, then the implementation for the default body needs to be wrapped into a suitable specialization declaration as well:

```
operation CountOnes(qubits: Qubit[]) : Int {
body (...) // default body specialization
{
mutable n = 0;
for (qubit in qubits) {
set n += M(q) == One ? 1 | 0;
}
return n;
}
...
```

### Circumstances for validly defining specializations

#### Operation declarations with adjoint/controlled

It is legal to specify an operation with no adjoint or controlled versions. For instance, measurement operations have neither because they are not invertible or controllable.

An operation supports the `Adjoint`

and `Controlled`

functors if its declaration contains an implicit or explicit declaration of the respective specializations.

An explicitly declared adjoint/controlled specialization implies the existence of an adjoint/controlled specialization.

For an operation whose body contains repeat-until-success loops, set statements, measurements, return statements, or calls to other operations that do not support the `Adjoint`

functor, auto-generating an adjoint specialization following the `invert`

or `auto`

directive is not possible.

For an operation whose body contains calls to other operations that do not support the `Controlled`

functor, auto-generating a controlled specialization following the `distribute`

or `auto`

directive is not possible.

#### Controlled Adjoint

The controlled adjoint version of an operation specifies how to implement a quantum-controlled version of the adjoint of the operation. It is legal to specify an operation with no controlled adjoint version; for instance, measurement operations have no controlled adjoint version because they are neither controllable nor invertible.

A controlled adjoint specialization for an operation needs to exist if and only if both an adjoint and a controlled specialization exist. In that case, the existence of the controlled adjoint specialization is inferred. If no implementation is explicitly defined, the compile generates an appropriate specialization.

For an operation whose body contains calls to other operations that do not have a controlled adjoint version, auto-generating an adjoint specialization following the `invert`

, `distribute`

, or `auto`

directive is not possible.

### Type Compatibility

Use an operation with additional functors supported anywhere you use an operation with fewer functors but the same signature. For instance, use an operation of type `(Qubit => Unit is Adj)`

anywhere you use an operation of type `(Qubit => Unit)`

.

Q# is *covariant* with respect to callable return types: a callable that returns a type `'A`

is compatible with a callable with the same input type and a result type that is compatible with `'A`

.

Q# is *contravariant* with respect to input types: a callable that takes a type `'A`

as input is compatible with a callable with the same result type and an input type that is compatible with `'A`

.

That is, given the following definitions,

```
operation Invert(qubits : Qubit[]) : Unit
is Adj {...}
operation ApplyUnitary(qubits : Qubit[]) : Unit
is Adj + Ctl {...}
function ConjugateInvertWith(
inner : (Qubit[] => Unit is Adj),
outer : (Qubit[] => Unit is Adj))
: (Qubit[] => Unit is Adj) {...}
function ConjugateUnitaryWith(
inner : (Qubit[] => Unit is Adj + Ctl),
outer : (Qubit[] => Unit is Adj))
: (Qubit[] => Unit is Adj + Ctl) {...}
```

you can

- Invoke the function
`ConjugateInvertWith`

with an`inner`

argument of either`Invert`

or`ApplyUnitary`

. - Invoke the function
`ConjugateUnitaryWith`

with an`inner`

argument of`ApplyUnitary`

, but not`Invert`

. - Return a value of type
`(Qubit[] => Unit is Adj + Ctl)`

from`ConjugateInvertWith`

.

Important

Q# 0.3 introduced a significant difference in the behavior of user-defined types.

User-defined types are treated as a wrapped version of the underlying type, rather than as a subtype. This means that a value of a user-defined type is not usable where you expect a value of the underlying type is.

## Defining New Functions

Functions are purely deterministic, classical routines in Q#, which are distinct from operations in that they are not allowed to have any effects beyond calculating an output value.
In particular, functions cannot call operations; act on, allocate, or borrow qubits; sample random numbers; or otherwise depend on state beyond the input value to a function.
As a consequence, Q# functions are *pure*, in that they always map the same input values to the same output values.
This behavior allows the Q# compiler to safely reorder how and when to call functions when generating operation specializations.

Each Q# source file can define any number of functions. Function names must be unique within a namespace and cannot conflict with operation or type names.

Defining a function works similarly to defining an operation, except that no adjoint or controlled specializations can be defined for a function. For instance:

```
function Square(x : Double) : (Double) {
return x * x;
}
```

or

```
function DotProduct(a : Double[], b : Double[]) : Double {
if (Length(a) != Length(b)) {
fail "Arrays are not compatible";
}
mutable accum = 0.0;
for (i in 0..Length(a)-1) {
set accum += a[i] * b[i];
}
return accum;
}
```

### Classical logic in functions == good

Whenever it is possible to do so, it is helpful to write out classical logic in terms of functions rather than operations so that operations can more readily use it. For example, if you had written the earlier `Square`

declaration as an *operation*, then the compiler would not have been able to guarantee that calling it with the same input would consistently produce the same outputs.

To underscore the difference between functions and operations, consider the problem of classically sampling a random number from within a Q# operation:

```
operation U(target : Qubit) : Unit {
let angle = RandomReal()
Rz(angle, target)
}
```

Each time that `U`

is called, it has a different action on `target`

.
In particular, the compiler cannot guarantee that if you add an `adjoint auto`

specialization declaration to `U`

, then `U(target); Adjoint U(target);`

acts as identity (that is, as a no-op).
This violates the definition of the adjoint defined in Vectors and Matrices, such that allowing the compiler to auto-generate an adjoint specialization in an operation where you call the operation RandomReal would break the guarantees provided by the compiler; RandomReal is an operation for which no adjoint or controlled version exists.

On the other hand, allowing function calls such as `Square`

is safe, and assures the compiler that it only needs to preserve the input to `Square`

to keep its output stable.
Thus, isolating as much classical logic as possible into functions makes it easy to reuse that logic in other functions and operations alike.

## Generic (Type-Parameterized) Callables

Many functions and operations that you might wish to define do not actually heavily rely on the types of their inputs, but rather only implicitly use their types via some other function or operation.
For example, consider the *map* concept common to many functional languages; given a function $f(x)$ and a collection of values ${x_1, x_2, \dots, x_n}$, map returns a new collection ${f(x_1), f(x_2), \dots, f(x_n)}$.
To implement this in Q#, take advantage of the fact that functions are first class.
Here is a quick example of `Map`

, using `T`

as a placeholder while you figure out what types you need.

```
function Map(fn : (T -> T), values : T[]) : T[] {
mutable mappedValues = new T[Length(values)];
for (idx in 0..Length(values) - 1) {
set mappedValues w/= idx <- fn(values[idx]);
}
return mappedValues;
}
```

Note that this function looks very much the same no matter what actual types you substitute in. A map from integers to Paulis, for instance, looks much the same as a map from floating-point numbers to strings:

```
function MapIntsToPaulis(fn : (Int -> Pauli), values : Int[]) : Pauli[] {
mutable mappedValues = new Pauli[Length(values)];
for (idx in 0..Length(values) - 1) {
set mappedValues w/= idx <- fn(values[idx]);
}
return mappedValues;
}
function MapDoublesToStrings(fn : (Double -> String), values : Double[]) : String[] {
mutable mappedValues = new String[Length(values)];
for (idx in 0..Length(values) - 1) {
set mappedValues w/= idx <- fn(values[idx]);
}
return mappedValues;
}
```

In principle, you could write a version of `Map`

for every pair of types that you encounter, but this introduces several difficulties.
For instance, if you find a bug in `Map`

, then you must ensure that the fix is applied uniformly across all versions of `Map`

.
Moreover, if you construct a new tuple or UDT, then you must now also construct a new `Map`

to go along with the new type.
While this is tractable for a small number of such functions, as you collect more and more functions of the same form as `Map`

, the cost of introducing new types becomes unreasonably large in fairly short order.

However, much of this difficulty results from the fact that you have not given the compiler the information it needs to recognize how the different versions of `Map`

are related.
Effectively, you want the compiler to treat `Map`

as some kind of mathematical function from Q# *types* to Q# functions.

Q# formalizes this notion by allowing functions and operations to have *type parameters*, as well as their ordinary tuple parameters.
In the previous examples, you wish to think of `Map`

as having type parameters `Int, Pauli`

in the first case and `Double, String`

in the second case.
For the most part, use these type parameters as though they were ordinary types. Use values of type parameters to make arrays and tuples, call functions and operations, and assign to ordinary or mutable variables.

Note

The most extreme case of indirect dependence is that of qubits, where a Q# program cannot directly rely on the structure of the `Qubit`

type but **must** pass such types to other operations and functions.

Returning to the earlier example, then, you see that `Map`

needs to have type parameters, one to represent the input to `fn`

and one to represent the output from `fn`

.
In Q#, this is written by adding angle brackets (that's `<>`

, not brakets $\braket{}$!) after the name of a function or operation in its declaration, and by listing each type parameter.
The name of each type parameter must start with a tick `'`

, indicating that it is a type parameter and not a ordinary type (also known as a *concrete* type).
Thus, `Map`

, is written:

```
function Map<'Input, 'Output>(fn : ('Input -> 'Output), values : 'Input[]) : 'Output[] {
mutable mappedValues = new 'Output[Length(values)];
for (idx in 0..Length(values) - 1) {
set mappedValues w/= idx <- fn(values[idx]);
}
return mappedValues;
}
```

Note that the definition of `Map<'Input, 'Output>`

looks extremely similar to the previoius versions.
The only difference is that you have explicitly informed the compiler that `Map`

doesn't directly depend on what `'Input`

and `'Output`

are, but works for any two types by using them indirectly through `fn`

.
Once you have defined `Map<'Input, 'Output>`

in this way, you can call it as though it was an ordinary function:

```
// Represent Z₀ Z₁ X₂ Y₃ as a list of ints.
let ints = [3, 3, 1, 2];
// Here, assume IntToPauli : Int -> Pauli
// looks up PauliI by 0, PauliX by 1, so forth.
let paulis = Map(IntToPauli, ints);
```

Tip

Writing generic functions and operations is one place where "tuple-in tuple-out" is a very useful way to think about Q# functions and operations.
Since every function takes exactly one input and returns exactly one output, an input of type `'T -> 'U`

matches *any* Q# function whatsoever.
Similarly, you can pass any operation to an input of type `'T => 'U`

.

As a second example, consider the challenge of writing a function that returns the composition of two other functions:

```
function ComposeImpl(outerFn : (B -> C), innerFn : (A -> B), input : A) : C {
return outerFn(innerFn(input));
}
function Compose(outerFn : (B -> C), innerFn : (A -> B)) : (A -> C) {
return ComposeImpl(outerFn, innerFn, _);
}
```

Here, you must specify exactly what `A`

, `B`

, and `C`

are, hence severely limiting the utility of our new `Compose`

function.
After all, `Compose`

only depends on `A`

, `B`

, and `C`

*via* `innerFn`

and `outerFn`

.
As an alternative, then, you can add type parameters to `Compose`

that indicate that it works for *any* `A`

, `B`

, and `C`

, so long as these parameters match those expected by `innerFn`

and `outerFn`

:

```
function ComposeImpl<'A, 'B, 'C>(outerFn : ('B -> 'C), innerFn : ('A -> 'B), input : 'A) : 'C {
return outerFn(innerFn(input));
}
function Compose<'A, 'B, 'C>(outerFn : ('B -> 'C), innerFn : ('A -> 'B)) : ('A -> 'C) {
return ComposeImpl(outerFn, innerFn, _);
}
```

The Q# standard libraries provide a range of such type-parameterized operations and functions to make higher-order control flow easier to express. These are discussed further in the Q# standard library guide.

## Callables as First-Class Values

One critical technique for reasoning about control flow and classical logic using functions rather than operations is to utilize that operations and functions in Q# are *first-class*.
That is, they are each values in the language in their own right.
For instance, the following is perfectly valid Q# code, if a little indirect:

```
operation FirstClassExample(target : Qubit) : Unit {
let ourH = H;
ourH(target);
}
```

The value of the variable `ourH`

in the previous snippet is then the operation H, such that you can call that value like any other operation.
With this ability, you can write operations that take operations as a part of their input, forming higher-order control flow concepts.
For instance, you could imagine wanting to "square" an operation by applying it twice to the same target qubit.

```
operation ApplyTwice(op : (Qubit => Unit), target : Qubit) : Unit {
op(target);
op(target);
}
```

### Returning operations from a function

It's important to emphasize that you can also return operations as a part of outputs, such that you can isolate some kinds of classical conditional logic as a classical function, which returns a description of a quantum program in the form of an operation. As a simple example, consider the teleportation example, in which the party receiving a two-bit classical message needs to use the message to decode their qubit into the proper teleported state. You could write this in terms of a function that takes those two classical bits and returns the proper decoding operation.

```
function TeleporationDecoderForMessage(hereBit : Result, thereBit : Result)
: (Qubit => Unit is Adj + Ctl) {
if (hereBit == Zero && thereBit == Zero) {
return I;
} elif (hereBit == One && thereBit == Zero) {
return X;
} elif (hereBit == Zero && thereBit == One) {
return Z;
} else {
return Y;
}
}
```

This new function is indeed a function, in that if you call it with the same values of `hereBit`

and `thereBit`

, you always get back the same operation.
Thus, the decoder can safely run inside operations without having to reason about how the decoding logic interacts with the definitions of the different operation specializations.
That is, the classical logic inside a function is isolated, guaranteeing to the compiler that the function call can be reordered with impunity so long as the input is preserved.

## Partial Application

You can do significantly more with functions that return operations by using *partial application*, in which you provide one or more parts of the input to a function or operation without actually calling it. In the earlier `ApplyTwice`

example, you can indicate that you don't want to specify, right away, to which qubit the input operation should apply:

```
operation PartialApplicationExample(op : (Qubit => Unit), target : Qubit) : Unit {
let twiceOp = ApplyTwice(op, _);
twiceOp(target);
}
```

In this case, the local variable `twiceOp`

holds the partially applied operation `ApplyTwice(op, _)`

, where `_`

indicates parts of the input that have not yet been specified.
When you call `twiceOp`

in the next line, you pass as input to the partially applied operation all of the remaining parts of the input to the original operation.
Thus, the previous snippet is effectively identical to having called `ApplyTwice(op, target)`

directly, save for that you have introduced a new local variable so you can delay the call while providing some parts of the input.

Since an operation that has been partially applied is not actually called until its entire input has been provided, you can safely partially apply operations even from within functions.

```
function SquareOperation(op : (Qubit => Unit)) : (Qubit => Unit) {
return ApplyTwice(op, _);
}
```

In principle, the classical logic within `SquareOperation`

could have been much more involved, but it is still isolated from the rest of an operation by the guarantees that the compiler can offer about functions.
The Q# standard library uses this approach throughout for expressing classical control flow in a way that quantum programs can readily use.

## Recursion

Q# callables are allowed to be directly or indirectly recursive. That is, an operation or function can call itself, or it can call another callable that directly or indirectly calls the callable operation.

There are two important comments about the use of recursion, however:

- The use of recursion in operations is likely to interfere with certain optimizations. This interference can have a substantial impact on the run time of the algorithm.
- When running on an actual quantum device, stack space might be limited, and so deep recursion can lead to a runtime error. In particular, the Q# compiler and runtime do not identify and optimize tail recursion.

## Next steps

Learn about Variables in Q#.