# Estimating Algorithmic Information Using Quantum Computing for Genomics Applications
## Appendix A QPULBA Quantum Circuit  
An example quantum circuit for the 2 state 2 symbol 1 dimension taped QPULBA is presented here as a reference. While execution, the QPULBA is initialized and then undergoes the following unitary transformations for the pre-determined number of steps. These correspond to one step of a classical UTM, with the distinction of the computation now evolving in a superposition of all possible classical automata. 1. Read: \(\{q_{read}\}\gets U_{read}(\{q_{head},q_{tape}\})\)
2. Transition evaluation: \(\{q_{write},q_{ch},q_{move}\}\gets U_{\delta}(\{q_{read},q_{state},q_{ \delta}\})\)
3. Write: \(\{q_{tape}\}\gets U_{write}(\{q_{head},q_{write}\})\)
4. Move: \(\{q_{head}\}\gets U_{move}(\{q_{head},q_{move}\})\)
5. Reset  
The initialization and each of the QPULBA steps are shown in the following circuits. **Initialize**: For measuring the algorithmic probability or the universal distribution, all possible programs (represented by the transition table) need to be evolved in a superposition. All other qubits are kept at the ground or default state of \(|0\rangle\). The circuit is shown in Figure 11.  
**Read tape**: The quantum circuit for read implements a multiplexer with the tape as the input signals and the binary coded head position as the selector lines, as shown in Figure 12. The read head is the output. Figure 11: Initialization quantum circuit for QPULBA 2-2-1. **Wite tape**: The quantum circuit for write implements a de-multiplexer with the tape as the output signals and the head position as the selector lines, as shown in Figure 14. The write head is the input. **Move**: There are many choices for implementing the move, e.g., a looped tape (overflow or underflow is ignored and trimmed), error flag is raised and halts, overflow/underflow is ignored, etc. Here, a looped tape is implemented. The head is incremented or decremented using the move qubit as control. Figure 13: Transition function quantum circuit for QPULBA 2-2-1. The increment/decrement circuit is a special case of the quantum full adder [63] with the first register, \(a\) set to \(1\). For the QPULBA 2-2-1 case, the length of the circular tape is \(12\), thus, the increment and decrement needs to be modulo \(12\). For increment, when the \(q_{head}\) equals \(11\), it should increment to \((11+1)\bmod 12=0\), while for decrement, \((0-1)\bmod 12=11\). Thus, for these edge cases, we need to increment/decrement by \(5\) instead of \(1\). We set the \(a_{2}\) bit to change the effective value of \(a\) from \(1=0001_{2}\) to \(5=0101_{2}\) for the addition/subtraction. This operation is conditioned on the head value and move bit, and denoted as the overflow/underflow qubit \(|ovfw\rangle/|udfw\rangle\). The \(a_{2}\) bit is uncomputed based on the incremented value being \(0\) or the decremented value being \(11\). The carry (C), sum (S) and reverse carry (C\({}^{\dagger}\)) blocks are defined as follows:  
.sum.carry.reverse_carry  
cnot A0,S0 toffoli A0,B0,C1 toffoli C0,B0,C1  
cnot B0,S0 cnot A0,B0 cnot A0,B0  
toffoli C0,B0,C1 toffoli A0,B0,C1  
In this design, \(c_{3}c_{2}c_{1}=000\) are \(3\) ancilla (\(c_{0}\) is not required), \(a_{0}=q_{move}\), \(a_{3}a_{2}a_{1}=000\), \(b_{3}b_{2}b_{1}b_{0}=q_{head}^{3}q_{head}^{4}q_{head}^{1}q_{head}^{1}\) and \(b_{4}\) is ignored. The circuit in Figure A5 shows the \(4\)-bit modulo-\(12\) quantum increment circuit using the quantum adder blocks, while the decrement circuit is shown in Figure A6. Figure A5: Modulo-\(12\) quantum adder for implementing move tape head for QPULBA 2-2-1. Both the increment and decrement circuits can be simplified considering some of the control qubits are always in the 0 state, so those CNOT/Toffoli gates can be ignored. **Reset**: Quantum logic is universal and can implement any classical Boolean logic function using only the Toffoli (CCNOT) or Fredkin (CSWAP) gate. However, it is not always possible to uncompute all ancilla qubits. Specifically, if the function to be implemented is irreversible.