Efficient Adjoint Operations

Quantum Read-Only Memory (QROM) is a method to load a classical dataset into a quantum data register using an index register and possibly an auxiliary register. General implementations, including SelectSwap, can use many multicontrolled gates.

Here, the adjoint QROM can be implemented as in Figure 1 if the b-qubit data register must be set to be |0\rangle afterwards [2]. The n-qubit index register is unchanged. Observe that the multicontrolled gates are replaced by Hadamards, measurements, and a diagonal correction \Delta. Therefore, the adjoint QROM would be cheaper to implement. This is analogous to the previous example of the adjoint Elbow implemented without T gates if the target qubit must be set to |0\rangle afterwards.

Figure 1. Implementation of adjoint QROM with only Hadamards, measurements, and a diagonal correction matrix, \Delta, assuming the b-qubit data register must become state |0\rangle. \Delta represents a diagonal correction matrix consisting of \pm 1 terms on the diagonal.

Definitions of QROM and adjoint QROM

By definition, the index register contains n qubits while the data register contains b qubits. Given an arbitrary initial state \sum_i \alpha_i |i\rangle_{\text{index}} |0\rangle_{\text{data}}, the action of QROM is:

where |\phi_i\rangle is the i^{\text{th}} bitstring that we wish to load.

Then, adjoint QROM performs the reverse operation to ensure the data register is finally |0\rangle.

Here, we shall confirm that there exists a diagonal \Delta such that the circuit in Figure 1 is equivalent to adjoint QROM i.e., the target qubits are reset to |0\rangle.

Step-by-step walkthrough of the circuit

At a high level, this particular measurement-based adjoint QROM circuit applies Hadamard gates to the data register qubits that we then reset to |0\rangle with measurements and X gates, as needed. This potentially introduces a -1 phase error along elements of the diagonal of the control (i.e., index) qubits of QROM. We correct those errors by applying a diagonal \Delta matrix.

Applying the Hadamards

Given the initial state \sum_i \alpha_i |i\rangle_{\text{index}} |\phi_i\rangle_{\text{data}} , applying Hadamard gates to the data register yields:

where \odot represents bitwise multiplication such that v \odot u = v_0 u_0 \oplus v_1 u_1 \oplus \dots \oplus v_{n-1}u_{n-1}, and \oplus represents the XOR operation, or addition modulo 2. For example:

Indeed, when the 4-qubit Hadamard is applied to the state |1101\rangle, the output of the |0101\rangle basis is +1 before normalisation.

Resetting target qubits to |0\rangle

After measuring, we are going to get a bitstring |y\rangle from the data qubits, and the state will collapse to:

Knowing the bitstring |y\rangle, it is straightforward to classically apply X gates to reset the data register to |0\rangle.

Correcting any -1 phase error

The goal is to end up with the state \sum_i \alpha_i |i\rangle_{\text{index}} |0\rangle_{\text{data}}. However, we observe that the above equation contains coefficients of the form (-1)^{\phi_i \odot y}, which can only be \pm 1. To eliminate those -1 phases, we apply a diagonal matrix \Delta consisting of \pm 1 terms. The result is the desired outcome state.