# Quantum Circuit-Width Reduction through Parameterisation and Specialisation
## 7 Applying Circuit Transformations to a Quantum Integer Divider
### Design 1: Baseline Divider  
Figure 3 shows the quantum circuit design of an integer divider based on the long-division approach. The example shown divides a 7-qubit dividend by a 4-qubit divisor. The qubits in this circuit represent the following  
\[|out3|out2|out1|out0\rangle : n\text{ qubits defining output}\] \[|test\rangle :\text{ qubit defining comparator result}\] \[|q4d\rangle :\text{ additional qubit needed in 2's complement}\] \[|q3d|q2d|q1d|q0d\rangle : n\text{-qubit representation of divisor}\] \[|q3i|q2i|q1i|q0i\rangle : n\text{-qubit representation of dividend}\] \[|c\rangle :\text{ `carry' qubit in modulo adder}\] \[|qin2|qin1|qin0\rangle : n-1\text{ qubits used to create the 7-qubit}\] \[\text{ dividend along with }|q3i|q2i|q1i|q0i\rangle\]  
for the quantum circuit implementation illustrated in Figure 3 for the example \(n=4\), the circuit complexity in terms of required number of qubits as a function of \(n\) is,  
\[n+2+2n+1+(n-1)=4n+2 \tag{8}\]  
for \(n=4\), a minimum of 18 qubits is, therefore, needed, as shown in Figure 3. For \(n=5\), 22 qubits are required. For reference, when employing double-precision arithmetic in the simulators used in the present work, simulating circuits with 28 qubits typically requires 8 GB of memory. Increasing the dividend and divisor representation to \(n>6\) therefore means that computational resources on a desktop work station are challenged. The quantum circuit implementation of the comparator \(C\) and subtractor \(Sub\) used in the long-division steps are detailed in Figure 4.  
Design 1, presents the following challenges to'reducing out' one or more of the divisor qubits:  
* In the comparator \(C\) and its uncomputation \(U(C)\), the state of the divisor qubits can temporarily become changed before returning the their original state;
* The subtractor \(Sub\) involves a transformation to 2's complement formulation for divisor qubits at start and completes with a transformation from 2's complement to original representation. Along with the further temporary changes to divisor qubit states in the ripple-carry based modulo adder, this greatly complicates static analysis, as outlined previously in Section 4;
* The 'downward' movement of subtractor circuit toward less significant qubits of the dividend in successive long-division steps requires re-arrangement of qubits so that the modular addition on which the subtractor \(Sub\) is based can be performed. This further complicates qubit-reduction steps.  
The comparator circuit shown in Figure 4 can be reduced by specialisation of one or more (divisor) qubits. Reduction by two qubits is illustrated in Figure 12, while a further reduction by three and four divisor qubits is shown in Figure 13 and Figure 14, respectively. Note that, here, the divisor is represented in its original (4-qubit) form, not in 2's complement used in later designs. The reductions shown were performed manually, following the same principles outlined previously in Figure 5 for the example of ripple-carry modulo adders. The complexity of step-by-step reduction in these comparator circuits further supports the conclusion drawn in Section 4, that this type of reductions present a major challenge to automation and that, therefore, the alternative approach based on parameterised circuits is preferable.  
Figure 14: Reduction-by-specialisation of comparator circuit introduced by [PERSON] et al. [33]. Reduction by four qubits.  
Figure 12: Reduction-by-specialisation of comparator circuit introduced by [PERSON] et al. [33]. Reduction by two qubits.  
Figure 13: Reduction-by-specialisation of comparator circuit introduced by [PERSON] et al. [33]. Reduction by three qubits.