Extended Quantum Computing Patterns

Remove entanglement that resulted from a previous computation

Quantum algorithms often use ancilla qubits as temporary qubits for their computations. After a computation, these qubits are often still entangled with the computational basis of the quantum register.
This prevents unrestricted access to the results of the computation.
This is especially problematic if the performed calculations are only intermediate steps within a larger algorithm. For example, assume a computation should produce a weighted superposition \(\newcommand{\state}[1]{{\left| #1 \right>}} \sum \alpha_i \state{\phi_i}\), but produces \(\newcommand{\state}[1]{{\left| #1 \right>}} \sum \alpha_i \state{\phi_i} \state{\psi_i}\) instead, where \(\newcommand{\state}[1]{{\left| #1 \right>}} \state{\psi_i}\) denotes the state of the ancilla qubits. The second part of the register containing the ancilla qubits cannot be discarded unless

holds, i.e., unless the two parts of the register are separable.

–

When computing a function \(f\), many algorithms map \(\newcommand{\state}[1]{{\left| #1 \right>}} \state{x}\state{0}\state{0}\) to \(\newcommand{\state}[1]{{\left| #1 \right>}} \state{x}\state{g(x)}\state{f(x)}\) (Derovic et al. 2018).
As a result, the second part of the register represents a workspace containing the byproduct \(g(x)\) of the computation of \(f(x)\), which is not needed anymore.
This garbage part of the register has to be reset, especially if the following parts of the algorithm expect a proper initialization of the workspace as \(\newcommand{\state}[1]{{\left| #1 \right>}} \state{0 \ldots 0}\).
More specifically, assume the following state to be the result of the computation \(U_f\):

with \(\newcommand{\state}[1]{{\left| #1 \right>}} \state{g(x)} = \sum \alpha_y \state{y}\) being the garbage state. Then, a fourth register is added and initialized as \(\newcommand{\state}[1]{{\left| #1 \right>}} \state{0}\). Then, CNOT is applied (bitwise) to this fourth register controlled by the third register containing the actual results of the computation. Thereby, \(f(x)\) is copied to the fourth register which results in \(\newcommand{\state}[1]{{\left| #1 \right>}} \sum \alpha_y \state{x} \state{y} \state{f(x)} \state{f(x)}\).
To reset the potentially entangled first three registers, the inverse operator \(U^{-1}_f\) is applied to them, resulting in \(\newcommand{\state}[1]{{\left| #1 \right>}} \state{x} \state{0} \state{0} \state{f(x)}\). By application of the SWAP operator, the entries of the last two registers are swapped: \(\newcommand{\state}[1]{{\left| #1 \right>}} \state{x} \state{0} \state{f(x)} \state{0}\). The fourth register is in the state \(\newcommand{\state}[1]{{\left| #1 \right>}} \state{0}\) again and can be discarded, leaving \(\newcommand{\state}[1]{{\left| #1 \right>}} \state{x} \state{0} \state{f(x)}\) as final result (see (Derovic et al. 2018) for a more detailed description). How a Uncompute operation can be realized in several other situations is described in (Proos and Zalka 2003).

The resulting register \(\newcommand{\state}[1]{{\left| #1 \right>}} \state{x} \state{0} \state{f(x)}\) contains the input \(x\) and the computed function values \(f(x)\).
The previous entanglement (caused by the computation) is no longer present.

–

Applying an Oracle often results in a state where ancilla qubits are entangled with other qubits, and therefore, requires the application of Uncompute. A Function Table can show the same behavior as a special case of an oracle.

Several algorithms like the Deutsch-Joza, the HHL algorithm (Harrow, Hassidim and Lloyd 2009), and quantum walks make use of Uncompute.

Grover's Algorithm (PlanQK) Shor's Algorithm (PlanQK) HHL Algorithm (PlanQK)