Thermodynamic optimization of quantum algorithms: On-the-go erasure of qubit registers

We consider two bottlenecks in quantum computing: limited memory size and noise caused by heat dissipation. Trying to optimize both, we investigate “on-the-go erasure” of quantum registers that are no longer needed for a given algorithm: freeing up auxiliary qubits as they stop being useful would facilitate the parallelization of computations. We study the minimal thermodynamic cost of erasure in these scenarios, applying results on the Landauer erasure of entangled quantum registers. For the class of algorithms solving the Abelian hidden subgroup problem, we find optimal on-the-go erasure protocols. We conclude that there is a trade-off: if we have enough partial information about a problem to build efficient on-the-go erasure, we can use it to instead simplify the algorithm, so that fewer qubits are needed to run the computation in the first place. We provide explicit protocols for these two approaches.

Figure 1

Class of algorithms considered. We consider quantum algorithms where a main register is used until the final measurement, but there can be auxiliary registers, which are needed for only part of the algorithm, for example, the period-finding algorithm and more generally algorithms for hidden subgroup problems are of this form.

Figure 2

On-the-go brute-force erasure. In order to free up memory space, the auxiliary register can be erased on the go. A brute-force erasure at temperature $T$ will have work cost $k_{B}Tln2$ per qubit due to Landauer's principle.

Figure 3

Bennett's uncomputing erasure. For Bennett's uncomputing, the original probabilistic algorithm is made essentially deterministic by running many copies of $(V\otimes \mathbb{1})\circ U$ in parallel together with a quantum implementation of the classical postprocessing, summarized as $\mathbf{U}$. The result of this calculation is coherently copied to an output register and $\mathbf{U}$ is uncomputed.

Figure 4

Optimized on-the-go erasure. We propose an optimized on-the-go erasure scheme which takes advantage of the entanglement between main and auxiliary register to reduce the work cost of erasure of the latter.

Figure 5

Abelian hidden subgroup algorithm [22, 23]. The quantum circuit above solves the Abelian hidden subgroup problem. Since it is of the same form as Fig. 4, we can use it as a candidate for optimizing the on-the-go erasure. The main register ${\mathcal{H}}_G$ encodes the group $G$ and the auxiliary register ${\mathcal{H}}_S$ encodes $S$. The function oracle acts on states of the joint register via $O_f|g,s\rangle =|g,s\oplus f\left(g\right)\rangle$, with $\oplus$ denoting the bitwise XOR operation. The algorithm performs the following sequence: (1) Generalized quantum Fourier transform $Q_G\otimes \mathbb{1}$ on $G$ register creates a superposition $\frac{1}{\left|G\right|}{\sum }_{g\in G}|g,0\rangle$. (2) Global oracle operation $O_f$ on both registers. At any later point we can erase $S$ with a map $\tilde{\mathcal{E}}$. (3) Quantum Fourier transform $Q_G$ on $G$ register. (4) Measurement of the $G$ register. (5) Classical postprocessing of the result.

Figure 6

The erasure process acting on an initial state ${\rho }_{GS}$ must leave the reduced state of the main register invariant, i.e., we require ${Tr}_S\left({\rho }_{GS}\right)={\rho }_{G^{\prime }}$ (the violet box in the circuit must act locally as the identity on $G$). This requirement is necessary to ensure that our on-the-go erasure procedure does not affect the outcome of the algorithm to which it is applied.

Figure 7

Optimized on-the-go erasure. The above circuit is a modified version of Fig. 5 implementing the optimized on-the-go erasure of $\ell$ qubits (see shaded part of the diagram). Here we know unitaries $U_G$ and $U_S$ which factor out part of the entanglement between the main and auxiliary register in the form of $\ell$ Bell pairs. The $\ell$ qubits belonging to the auxiliary register are then erased at temperature $T$ with $\tilde{\mathcal{E}}$ at a total average work cost of $-\ell k_{B}Tln2$. In the list below, the first steps 1–2 and last steps 3–5 of the modified algorithm displayed above are unchanged from the original. 1-2. Generalized quantum Fourier transform and oracle operation. 2a. Unitary transformation $U_G\otimes U_S\otimes {\mathbb{1}}_B$. 2b. Side information erasure $\mathcal{E}$ of $\ell$ qubits, standard erasure $\tilde{\mathcal{E}}$ of remaining $m-\ell$ qubits. 2c. Reverse transformation $U_G^{†}\otimes U_S^{†}\otimes {\mathbb{1}}_B$. 3-5. Quantum Fourier transform, measurement, and classical postprocessing.

Figure 8

Oracle simplification. If we have access to partial information about a subgroup $K$, the modified oracle ${\tilde{O}}_f$ (violet box in the circuit) can be used instead of the original oracle $O_f$. The $2\ell$ qubits inside the violet box are in the $|0\rangle$ state regardless of the input of the main and auxiliary qubits. All in all, the oracle ${\tilde{O}}_f$ has $2\ell$ fewer (variable) input qubits than $O_f$. If the function oracle $O_f$ is given with open circuit access (in contrast to a black box), the transformations $U_G$ and $U_S$ can be incorporated into $O_f$, giving a physical reduction of $2\ell$ qubits. In comparison to the standard algorithm (Fig. 5) the group $G$ has been replaced by $K$; henceforth, also the generalized quantum Fourier transforms $Q_G$ had to be replaced by $Q_K$. The remaining steps are as in Fig. 5; in the following enumeration they are steps 1 and 3–4, while steps $2{\mathrm{a}}^{\prime }$–$2{\mathrm{c}}^{\prime }$ are encapsulated by ${\tilde{O}}_f$ in the above circuit: 1. Generalized quantum Fourier transform $Q_K$ on ${\mathcal{H}}_K, 2{\mathrm{a}}^{\prime }$. Inverse transformation $U_G^{†}$ on ${\mathcal{H}}_K\otimes {\mathcal{H}}_{G/K}, 2{\mathrm{b}}^{\prime }$. Original oracle operation $O_f, 2{\mathrm{c}}^{\prime }$. Transformations $U_G\otimes U_S$, 3–4. Generalized quantum Fourier transform $Q_K$ on ${\mathcal{H}}_K$, and measurement of $K$ register.

Figure 9

Two-qubit on-the-go erasure for the period finding algorithm. Here the circuit describing the optimized on-the-go erasure of the least significant qubits in the period finding algorithm is shown. Given the Promise t11, the oracle $O_f$ fully entangles the least significant qubits of main and auxiliary register. The auxiliary qubit of this pair can then be erased at a negative average work cost of $-k_{B}Tln2$ if the erasure is performed at temperature $T$.

Figure 10

Two-qubit oracle simplification for the period finding algorithm. At equivalent thermodynamic costs as the on-the-go erasure in Fig. 9, the period finding algorithm can alternatively be simplified to an algorithm which uses two qubits fewer by keeping the least significant qubits of main and auxiliary register constantly in the ground state $|0\rangle$.

Figure 11

Qubit erasure energy diagram. Energy level diagram for the erasure setup of one qubit. From left to right are work storage, qubit system, and heat bath. The curved arrows visualize the swapping operation done by the unitary $U^{\left(3\right)}$ from Eq. (A1).

Figure 12

The first transformation brings the state ${\rho }_{GS}\otimes (\mathbb{1}/2)\otimes |0\rangle \langle 0|$ into a factorized form ${\rho }_{G^{\prime }{S}^{\prime }}\otimes |\chi \rangle \langle \chi |\otimes (\mathbb{1}/2)\otimes |0\rangle \langle 0|,$ in which the Bell pair $|\chi \rangle \langle \chi |$ is swapped with the partially erased state $(\mathbb{1}/2)\otimes |0\rangle \langle 0|$. After uncomputing $U_G$ and $U_S$, that is, ${\rho }_{G^{\prime }{S}^{\prime }}\otimes (\mathbb{1}/2)\otimes |0\rangle \langle 0|\otimes |\chi \rangle \langle \chi |$ is mapped to ${\tilde{\rho }}_{GS}\otimes |\chi \rangle \langle \chi |,$ the reduced states of the main register ${\tilde{\rho }}_G={Tr}_S\left({\tilde{\rho }}_{GS}\right)$ is the same as before the operation, ${\rho }_G={\tilde{\rho }}_G$, where ${\rho }_G={Tr}_S\left({\rho }_{GS}\right)$.