# Optimizing Multidimensional Pooling for Variational Quantum Algorithms
## 4 Materials and Methods
### Quantum Average Pooling via Quantum Haar Transform
#### 4.1.3 Multilevel Multidimensional Quantum Haar Transform  
For the multidimensional QHT, we can assume the input data are \(d\)-dimensional, where each dimension has a data size of \(N_{i}:0\leq i<d\) for a total data size of \(N=\prod_{i=0}^{d-1}N_{i}\). We can denote the largest dimension of data as \(N_{\text{max}}=\max_{i=0}^{d-1}N_{i}\), where it is encoded by \(n_{\text{max}}\) qubits. Similarly, the smallest dimension of data is denoted as \(N_{\text{min}}=\min_{i=0}^{d-1}n_{i}\) and is encoded by \(n_{\text{min}}\) qubits. Similar to the 1-D case, the data are encoded as an \(n\)-qubit quantum state \(|\psi\rangle\), such that each dimension \(i\) of data requires \(n_{i}=\lceil\log_{2}N_{i}\rceil\) qubits and \(\ell_{i}\) decomposition levels. It is worth mentioning that the total number of required qubits is \(n=\sum_{i=0}^{d-1}n_{i}\) qubits and the final size of each data dimension \(i\) is \(\left\lceil\frac{N_{i}}{2^{\ell_{i}}}\right\rceil\). Based on the nature of the encoding scheme (amplitude encoding) and quantum circuit structures, the multidimensional QHT can be performed by parallel application of \(d\) 1-D QHT circuits. Thus, the transformation of each data dimension can be performed independently of the other data dimensions. More specifically, using a column-major vectorization of the multidimensional data, the \(i^{\text{th}}\) dimension of the data is represented by the contiguous region of qubits \(q_{\sum_{j=0}^{i-1}n_{j}}^{\text{c}}\) to \(q_{\sum_{j=0}^{i}n_{j}-1}^{\text{c}}\). In other words, the multidimensional \(d\)-D QHT can be performed by stacking \(d\) 1-D QHT circuits in parallel, each of which performs the transformation on the respective contiguous region/data dimension, as shown in Figure 9. For the interested reader, more details about the multilevel multidimensional (\(d\)-D) QHT can be found in [6]. Haar Wavelet Operation on Multidimensional Data  
Exploiting the parallelization offered by stacking, the multilevel \(d\)-D QHT wavelet operation can also be performed with constant circuit depth; see (24) and Figure 9.  
\[U_{\text{Haar}}^{d\text{-D}}=\bigotimes_{i=d-1}^{0}\left(I^{\otimes n_{i}- \ell_{i}}\otimes H^{\otimes\ell_{i}}\right) \tag{24}\]  
The multilevel \(d\)-D QHT data rearrangement operation is given by (25) and shown in Figure 9.  
\[U_{\text{rearrangement}}^{d\text{-D}}=\bigotimes_{i=d-1}^{0}\prod_{j=\ell_{i}- 1}^{0}\text{RoR}(n_{i}) \tag{25}\]  
Since the multidimensional QHT can be parallelized across dimensions, the circuit depth is determined by the dimension with the largest total data size and number of decomposition levels, as shown in (26). \[ \begin{split}\Delta_{d\text{-D QHT}}(n,\ell)&= \max_{i=0}^{d-1}(\Delta_{\text{H}}+\Delta_{\text{RoR}}(n_{i})+3(2(\ell_{i}-1)) )\\ &=1+3(n_{\text{max}}-1)+3(2(\ell_{\text{max}}-1))=3(n_{\text{max}} +2\ell_{\text{max}})-8\\ &=\mathcal{O}(n_{\text{max}}+\ell_{\text{max}})\end{split}  \tag{26}\]  
If data rearrangement can be performed in the classical post-processing of Q2C data decoding, as discussed in Section 4.1.1, the wavelet operation is completely parallelized for the multilevel multidimensional QHT, resulting in an optimal, constant circuit depth; see (27). \[ \begin{split}\Delta_{d\text{-D QHT}}^{\text{opt}}&= \max_{i=0}^{d-1}(\Delta_{\text{H}})=1\\ &=\mathcal{O}(1)\end{split}  \tag{27}\]Figure 9: Multilevel Multidimensional (\(d\)-D) QHT circuit.