Intro to quantum read-only memory (QROM)¶

Select¶

Select is an operator that prepares quantum states associated with indices. It is defined as:

where $|\phi_i\rangle$ is the $i$-th state we want to encode, generated by a known unitary $U_i.$ QROM can be considered a special case of the Select operator where the encoded states are computational basis states. Then the unitaries $U_i$ can be simply products of $X$ gates satisfying:

We use BasisState as a useful template for implementing the gates $U_i.$ Let’s see how it could be written in code:

import pennylane as qml
import numpy as np
from functools import partial
import matplotlib.pyplot as plt


bitstrings = ["01", "11", "11", "00", "01", "11", "11", "00"]

control_wires = [0, 1, 2]
target_wires = [3, 4]

Ui = [qml.BasisState(int(bitstring, 2), target_wires) for bitstring in bitstrings]

dev = qml.device("default.qubit", shots=1)


# This line is included for drawing purposes only.
@partial(qml.transforms.decompose, max_expansion=1)

@qml.qnode(dev)
def circuit(index):
    qml.BasisState(index, wires=control_wires)
    qml.Select(Ui, control=control_wires)
    return qml.sample(wires=target_wires)


qml.draw_mpl(circuit, style="pennylane")(3)
plt.show()

Now we can check that all the outputs are as expected:

for i in range(8):
    print(f"The bitstring stored in index {i} is: {circuit(i)}")

The bitstring stored in index 0 is: [0 1]
The bitstring stored in index 1 is: [1 1]
The bitstring stored in index 2 is: [1 1]
The bitstring stored in index 3 is: [0 0]
The bitstring stored in index 4 is: [0 1]
The bitstring stored in index 5 is: [1 1]
The bitstring stored in index 6 is: [1 1]
The bitstring stored in index 7 is: [0 0]

The outputs match the elements of our initial data list: $[01, 11, 11, 00, 01, 11, 11, 00].$ Nice!

The QROM template can be used to implement the previous circuit using directly the bitstring without having to calculate the $U_i$ gates:

import warnings
# This line will suppress ComplexWarnings for output visibility
warnings.filterwarnings(action="ignore", category=np.ComplexWarning)

bitstrings = ["01", "11", "11", "00", "01", "11", "11", "00"]

control_wires = [0, 1, 2]
target_wires = [3, 4]


@partial(qml.compile, basis_set="CNOT")  # Line added for resource estimation purposes only.
@qml.qnode(dev)
def circuit(index):
    qml.BasisState(index, wires=control_wires)
    qml.QROM(bitstrings, control_wires, target_wires, work_wires=None)
    return qml.sample(wires=target_wires)


for i in range(8):
    print(f"The bitstring stored in index {i} is: {circuit(i)}")

The bitstring stored in index 0 is: [0 1]
The bitstring stored in index 1 is: [1 1]
The bitstring stored in index 2 is: [1 1]
The bitstring stored in index 3 is: [0 0]
The bitstring stored in index 4 is: [0 1]
The bitstring stored in index 5 is: [1 1]
The bitstring stored in index 6 is: [1 1]
The bitstring stored in index 7 is: [0 0]

Although this approach works correctly, the number of multicontrol gates is high — gates with a costly decomposition. Here we show the number of 1 and 2 qubit gates we use when decomposing the circuit:

print("Number of qubits: ", len(control_wires + target_wires))
print("One-qubit gates: ", qml.specs(circuit)(0)["resources"].gate_sizes[1])
print("Two-qubit gates: ", qml.specs(circuit)(0)["resources"].gate_sizes[2])

Number of qubits:  5
One-qubit gates:  495
Two-qubit gates:  240

You can learn more about these resource estimation methods in the PennyLane documentation. There are numerous works that attempt to simplify this, of which we highlight reference 1, which introduces an efficient technique using measurements in the middle of the circuit. Another clever approach was introduced in 2 , with a smart structure known as SelectSwap, which we describe below.

SelectSwap¶

The goal of the SelectSwap construction is to trade depth of the circuit for width. That is, using multiple auxiliary qubits, we reduce the circuit depth required to build the QROM. Before we get into how it works, let’s show you how easy it is to use: we simply add work_wires to the code we had previously.

bitstrings = ["01", "11", "11", "00", "01", "11", "11", "00"]

control_wires = [0, 1, 2]
target_wires = [3, 4]
work_wires = [5, 6]


@partial(qml.compile, basis_set="CNOT")
@qml.qnode(dev)
def circuit(index):
    qml.BasisState(index, wires=control_wires)
    #  added work wires below
    qml.QROM(bitstrings, control_wires, target_wires, work_wires, clean=False)
    return qml.sample(wires=control_wires + target_wires + work_wires)

print("Number of qubits: ", len(control_wires + target_wires + work_wires))
print("One-qubit gates: ", qml.specs(circuit)(0)["resources"].gate_sizes[1])
print("Two-qubit gates: ", qml.specs(circuit)(0)["resources"].gate_sizes[2])

Number of qubits:  7
One-qubit gates:  207
Two-qubit gates:  96

The number of 1 and 2 qubit gates is significantly reduced!

Internally, the main idea of this approach is to organize the $U_i$ operators into two dimensions, whose positions will be determined by a column index $c$ and a row index $r.$

Following this structure, for instance, the $U_5$ operator (or $101$ in binary) is in column $2$ and row $1$ (zero-based indexing):

In order to load the desired bitstring in the target wires, we use two building blocks in the construction:

• Select block: Loads the $c$-th column in the target and work wires.

• Swap block: Swaps the $r$-th row to the target wires.

Let’s look at an example by assuming we want to load in the target wires the bitstring with the index $5,$ i.e., $U_5|0\rangle = |b_5\rangle.$

Now we run the circuit with our initial data list: $[01, 11, 11, 00, 01, 11, 11, 00].$

index = 5
output = circuit(index)
print(f"control wires: {output[:3]}")
print(f"target wires: {output[3:5]}")
print(f"work wires: {output[5:7]}")

control wires: [1 0 1]
target wires: [1 1]
work wires: [0 1]

As expected, $|b_5\rangle = |11\rangle$ is loaded in the target wires. Note that with more auxiliary qubits we could make larger groupings of bitstrings reducing the depth of the Select operator. Below we show an example with two columns and four rows:

The QROM template will put as many rows as possible using the work_wires we pass. Let’s check how it looks in PennyLane:

bitstrings = ["01", "11", "11", "00", "01", "11", "11", "00"]

control_wires = [0, 1, 2]
target_wires = [3, 4]
work_wires = [5, 6, 7, 8, 9, 10, 11, 12]


# Line added for drawing purposes only
@partial(qml.transforms.decompose, max_expansion=2)
@qml.qnode(qml.device("default.qubit", shots=1))
def circuit(index):
    qml.BasisState(index, wires=control_wires)
    qml.QROM(bitstrings, control_wires, target_wires, work_wires, clean=False)
    return qml.sample(wires=target_wires), qml.sample(wires=target_wires)


qml.draw_mpl(circuit, style="pennylane")(0)
plt.show()

The circuit matches the one described above.

Reusable qubits¶

The above approach has a drawback. The work wires have been altered, i.e., after applying the operator they have not been returned to state $|00\rangle.$ This could cause unwanted behaviors, but in PennyLane it can be easily solved by setting the parameter clean = True.

bitstrings = ["01", "11", "11", "00", "01", "11", "11", "00"]

control_wires = [0, 1, 2]
target_wires = [3, 4]
work_wires = [5, 6]


@qml.qnode(dev)
def circuit(index):
    qml.BasisState(index, wires=control_wires)
    qml.QROM(bitstrings, control_wires, target_wires, work_wires, clean=True)
    return qml.sample(wires=target_wires + work_wires)


for i in range(8):
    print(f"The bitstring stored in index {i} is: {circuit(i)[:2]}")
    print(f"The work wires for that index are in the state: {circuit(i)[2:4]}\n")

The bitstring stored in index 0 is: [0 1]
The work wires for that index are in the state: [0 0]

The bitstring stored in index 1 is: [1 1]
The work wires for that index are in the state: [0 0]

The bitstring stored in index 2 is: [1 1]
The work wires for that index are in the state: [0 0]

The bitstring stored in index 3 is: [0 0]
The work wires for that index are in the state: [0 0]

The bitstring stored in index 4 is: [0 1]
The work wires for that index are in the state: [0 0]

The bitstring stored in index 5 is: [1 1]
The work wires for that index are in the state: [0 0]

The bitstring stored in index 6 is: [1 1]
The work wires for that index are in the state: [0 0]

The bitstring stored in index 7 is: [0 0]
The work wires for that index are in the state: [0 0]

All the work wires have been reset to the zero state.

To achieve this, we follow the technique shown in 3, where the proposed circuit (with $R$ rows) is as follows:

To see how this circuit works, let’s suppose we want to load the bitstring $b_{cr}$ in the target wires, where $b_{cr}$ is the bitstring whose operator $U$ is placed in the $c$-th column and $r$-th row in the two-dimensional representation shown in the Select block. We can summarize the idea in a few simple steps.

0. Initialize the state. We create the state:

1. A uniform superposition is created in the r-th register of the work wires. To do this, we put the Hadamards in the target wires and move it to the $r$-th row with the Swap block:

2. The Select block is applied. This loads the whole $c$-th column in the registers. Note that in the $r$-th position, the Select has no effect since the state $|+\rangle$ is not modified by $X$ gates:

3. The Hadamard gate is applied to the r-th register of the work wires. This returns that register to the zero state. The two Swap blocks and the Hadamard gate applied to the target wires achieve this:

4. Select block is applied. Thanks to this, we clean the used registers. That is because loading the bitstring twice in the same register leaves the state as $|0\rangle$ since $X^2 = \mathbb{I}.$ On the other hand, the bitstring $|b_{cr}\rangle$ is loaded in the $r$ register:

5. Swap block is applied. With this, we move $|b_{cr}\rangle$ that is encoded in the r-th row to the target wires:

The desired bitstring has been encoded in the target wires and the rest of the qubits have been left in the zero state.