# Depth-Optimized Quantum Circuit of Gauss-Jordan Elimination
## 3 Parallel Implementation for Quantum Circuit of Gauss-Jordan Elimination
### Parallel Implementation of Elimination  
The methods presented earlier (Copying Pivot, Section 3.2; Exponential Copy, Section 3.2.2; Reuse Technique, Section 3.2.3) are also applied to the parallel implementation of the elimination stage. Compared to the parallel implementation of the swap stage, more ancilla qubits for copying are allocated in the parallel implementation of the elimination stage. Figure 4 shows the parallel implementation of the elimination stage in Gauss-Jordan elimination. Recall that in the swap stage, to perform Toffoli gates between the \(H_{0\sim 4,0}\) and \(H_{0\sim 4,2}\) rows, the previous Toffoli gates between the \(H_{0\sim 4,0}\) and \(H_{0\sim 4,1}\) rows must be completed. In contrast, in the elimination stage, there is no dependency between all of the rows since the targets of the change are the elements, not the pivot. Thus, in the elimination stage, we do not need to change the pivot as in the swap stage. Figure 3: Exponential copy. If we sufficiently copy elements used for the Toffoli gates, high parallelism can be achieved. In the elimination stage, elimination operations (i.e., changing \(|1\rangle\) to \(|0\rangle\)) are performed between rows based on the elements (\(H_{0,1}\), \(H_{0,2}\), \(H_{0,3}\) for \(i=0\), except for the pivot) in the column containing the pivot. As we performed in the swap stage, we copy each element with reduced repetitions. In Figure 4, each of \(|anc_{0,1}\rangle\), \(|anc_{0,2}\rangle\), and \(|anc_{0,3}\rangle\) contains three qubits but is illustrated as a single line for simplicity. In the same context, each of \(|anc_{1,0}\rangle\), \(|anc_{2,0}\rangle\), \(|anc_{3,0}\rangle\), and \(|anc_{c,0}\rangle\) contains two qubits \((n-1-i,n=4,i=0)\). Unlike in the swap stage, we can omit the actual operations on the \(i\)-th column (i.e., \(H_{0,1\smallsetminus 3}\)) in Gaussian elimination, reducing the number of copies by \(1\). In [9] (Section 3.2), the authors proposed this optimization method, called _Avoid Clearing Piot Column_. Additionally, we can utilize the elements of the \(i\)-th column as control qubits, further reducing the number of copies by \(1\). As mentioned before, we can achieve more parallelism in the elimination stage compared to the swap stage. Recall that in the swap stage, swap operations are only possible between two rows, but in the elimination stage, elimination operations can be performed on all of the rows. To achieve high parallelism, we also copy the elements of the row containing the pivot (i.e., \(H_{1,0}\), \(H_{2,0}\), \(H_{3,0}\), \(H_{4,0}\) (\(c_{0}\))). Conceptually, the matrix is copied at once (although, strictly speaking, not all elements in the matrix) in the elimination stage, whereas in the swap stage, only the pivot is copied. Finally, using the copied elements, all of the Toffoli gates in the elimination stage (shown in red in Figure 4) is executed simultaneously (i.e., Toffoli depth one). After the Toffoli gate operations, the reuse technique (described  
Figure 4: Quantum circuit implementation of the elimination stage (where \(|H_{0,0}\rangle\) is the pivot); red and blue lines have no dependency. in Section 3.2.3) is used to initialize ancilla qubits (shown in blue in Figure 4) and to reuse them in the subsequent elimination stages (i.e., the \(i\)-th stage where \(i>0\)). In contrast to the swap stage, all of the ancilla qubits are initialized to \(|0\rangle\). Finally, Algorithm 2 summarizes our parallel implementation of the Gauss-Jordan elimination quantum circuit.