# Optimizing Multidimensional Pooling for Variational Quantum Algorithms
## 4 Materials and Methods
### Quantum Average Pooling via Quantum Haar Transform
#### 4.1.1 Single-Level One-Dimensional Quantum Haar Transform  
For the single-level one-dimensional (1-D) QHT, we will assume a 1-D input data of size \(N\) data points. The aforementioned data would be encoded into the quantum circuit using amplitude encoding [18] as an \(n\)-qubit quantum state \(|\psi\rangle\), where \(n=\lceil\log_{2}N\rceil\).  
The quantum circuit for single-level decomposition of the 1-D QHT is shown in Figure 7, where \(|\psi_{H}\rangle\) represents the quantum state after the wavelet operation and \(|\psi_{\text{out}}\rangle\) represents the quantum state after data rearrangement.  
Haar Wavelet Operation on Single-Level One-Dimensional Data  
The Haar wavelet is performed using the H gate; see Figure 7. For example, a single-level decomposition of the 1-D QHT can be performed on a state vector \(|\psi\rangle\) as described by (2) by applying a single H gate to the least-significant qubit of \(|\psi\rangle\), designated \(q_{0}\) in Figure 7. This operation replaces the data value of the pairs \((c_{2j},c_{2j+1}):0\leq j<\frac{N}{2}\) with their sum and difference, as shown in (16). It is worth mentioning that the sum terms represent the low-frequency terms and the difference terms represent the high-frequency terms for a single level of decomposition.  
\[|\psi_{H}\rangle=\left(I^{\otimes n-1}\otimes H\right)|\psi\rangle=\frac{1}{ \sqrt{2}}\left[\begin{array}{c}c_{0}+c_{1}\\ c_{0}-c_{1}\\ \vdots\\ c_{z_{j}}+c_{z_{j+1}}\\ c_{z_{j}}-c_{z_{j+1}}\\ \vdots\\ c_{N-2}+c_{N-1}\\ c_{N-2}-c_{N-1}\\ \end{array}\right],\text{where }0\leq j<\frac{N}{2} \tag{16}\]  
The data rearrangement operation congregates the low- or high-frequency fragmented terms after decomposition. For instance, the low- and high-frequency terms are segregated after wavelet decomposition, as expressed in (16). The low- and high-frequency terms exist at the even indices \((|q_{n-1}\ldots q_{1}\rangle|q_{0}=0\rangle)\) and odd indices \((|q_{n-1}\ldots q_{1}\rangle|q_{0}=1\rangle)\), respectively. Ideally, the state vector is formed in a way such that the low-frequency terms should be merged into a contiguous half of the overall state vector \((|q_{0}=0\rangle|q_{n-1}\ldots q_{1}\rangle)\), while the rest of the state vector consists of the high-frequency terms \((|q_{0}=1\rangle|q_{n-1}\ldots q_{1}\rangle)\). This data rearrangement operation can be performed using the qubit rotation \(|q_{n-1}\ldots q_{1}q_{0}\rangle\Rightarrow|q_{0}q_{n-1}\ldots q_{1}\rangle\) using a RoR operation; see Figure 7 and (17).  
\[|\psi_{\text{out}}\rangle=\text{rotate-right (RoR)}|\psi_{H}\rangle=\frac{1}{\sqrt{2}}\left[ \begin{array}{c}c_{0}+c_{1}\\ \vdots\\ c_{2j}+c_{z_{j+1}}\\ \vdots\\ c_{N-2}+c_{N-1}\\ c_{0}-c_{1}\\ \vdots\\ c_{z_{j}}-c_{z_{j+1}}\\ \vdots\\ c_{N-2}-c_{N-1}\\ \end{array}\right]\left[\begin{array}{c}2^{n-1}\\ \downarrow\\ \downarrow\\ 2^{n},\text{where }0\leq j<\frac{N}{2}\\ \end{array}\right] \tag{17}\]  
Figure 7: Single-level 1-D QHT circuit.  
The depth of the single-level 1-D QHT operation can be considered in terms of 1 H gate and 1 perfect-shuffle (RoR) gate. An RoR gate can be decomposed into \((n-1)\) SWAP gates or \(3(n-1)\) controlled-NOT (CNOT) gates. Accordingly, the total circuit depth can be expressed in terms of the number of consecutive single-qubit and CNOT gates, as shown in (18).  
\[\begin{split}\Delta_{\text{1-D QHT}}(n,\ell=1)&= \Delta_{\text{H}}+\Delta_{\text{RoR}}(n)=1+3(n-1)=3n-2\\ &=\mathcal{O}(n)\end{split} \tag{18}\]  
In many common quantum computing libraries, including Qiskit[19], it is possible to leverage arbitrary mapping of quantum registers to classical registers [35] to perform data rearrangement during quantum-to-classical (Q2C) data decoding without increasing circuit depth. Accordingly, the circuit depth of the optimized single-level 1-D QHT circuit can be expressed as shown in (19).  
\[\begin{split}\Delta_{\text{1-D QHT}}^{\text{opt}}(n,\ell=1)& =\Delta_{\text{H}}=1\\ &=\mathcal{O}(1)\end{split} \tag{19}\]