# Quantum Calculi--From Theory to Language Design
## 4 Foundational Quantum Programming Languages
### qPCF and IQu
#### 4.5.3 Programming Quantum Algorithms: Three Higher-Order Examples  
In this section, we use qPCF and lQu to provide three higher-order examples of quantum circuit family encodings. The examples are parametric, whereas the majority of the examples proposed in the literature are linear: this means that a term (the program) represents an entire (infinite) quantum circuit family. When fed with the input dimension, the evaluation of the program morally first yieldsthe description of the circuit of the right size among the whole family and then returns to the user the evaluation of the circuit on the quantum state provided as the input of the computation. We show the encodings of the well-known Deutsch-Jozsa and [PERSON]'s algorithms. We implement the circuit representing the Deutsch-Jozsa procedure in qPCF and IQu, to see at work the main peculiarities of the languages and the different solutions we chose in the definition of the syntax, the type and the reduction systems. Finally, we propose the encoding of the circuit family implementing [PERSON]'s quantum subroutine in IQu, exploiting its partial measurement operator and the quantum store. **Example 2** (Deutsch-Jozsa Circuit in qPCF). : _Figure 2 represents, up to the last phase (measurement of the output state), the circuit implementing the well-known Deutsch-Josza algorithm (the generalization of the [PERSON]'s algorithm) [9], that considers a function \(f:\{0,1\}^{n}\to\{0,1\}\) which acts on many input bits:_  
_Given a classical input state of the form \(|0\ldots 01\rangle\), the circuit returns a state that, once measured, reveals in the first \(n-1\) bits if the function \(f\) is constant or balanced. If all \(n-1\) measurement results are \(0\), we can conclude that the function is constant. Otherwise, if at least one of the measurement outcomes is \(1\), we conclude that the function is balanced._  
_In qPCF, unitary gates of arity \(k+1\) are typed with the (dependent) type \(\text{circ}(\underline{\Bbbk})\), where the dependency parameter \(\underline{\text{i}}\) in type \(\text{circ}(\underline{\text{i}})\) is the numerical representation of the integer \(i\). Moreover, the special type \(\text{Idx}\) is reserved for strongly normalizing expressions that represent dimensions of operation on circuits, such as sequentialization and parallelization. Sequential composition of two circuits \(C_{1}\) and \(C_{2}\) (of \(\text{th}\) same arity \(k\)) is denoted as \(C_{1}\)\(\mathfrak{s}\)\(C_{2}\). The qPCF term \(\text{iter}\,\text{put}\) in parallel an arbitrary number of quantum gates of arbitrary arity: for example, \(\text{iter}\,\underline{\Bbbk}UV\) create a parallel composition of \(k\) copies of the gate \(V\) and a copy of the gate \(U\)._  
_Let \(\text{H}:\text{circ}(\underline{\text{o}})\) and \(\text{I}:\text{circ}(\underline{\text{o}})\) be the (unary) Hadamard and Identity gates respectively. Suppose \(\text{M}^{B_{f}}:\text{circ}(\underline{\text{n}})\) is given for some \(n\) such that \(\text{M}^{B_{f}}\)\(\text{M}^{B_{f}}\)\(\text{U}_{f}\) where \(\text{U}_{f}:\text{circ}(\underline{\text{n}})\) is the qPCF-circuit that represents the the black-box function \(f\) having arity \(n+1\) and \(\text{M}^{\underline{\text{o}}}\) represents the evaluation labelled with its probability (in this case, \(\alpha=1\))._  
_The term \(\lambda\text{x}^{\text{Idx}}\). \(\text{iter}\,\,\,\text{xHH}:\Pi\text{x}^{\text{Idx}}\). \(\text{circ}(\underline{\text{x}})\) generates \(x+1\) parallel copies of Hadamard gates \(\text{h}\) and \(\lambda\text{x}^{\text{Idx}}\). \(\text{iter}\,\,\,\text{xIH}:\Pi\text{x}^{\text{Idx}}\). \(\text{circ}(\underline{\text{x}})\) concatenates in parallel \(x\) copies of Hadamard gates \(\text{h}\) and one copy of the identity gate \(\text{I}\). Notice that we abstract on types by means of the standard abstraction \(\Pi\) of dependent types.