QROM with unary iterationΒΆ

Download Notebook - qrom_unary_iteration.ipynb

  • Unary iteration QROM implementation.

  • QROM is used to store classical data in a quantum circuit. It takes as input an index register and a data register, and for each possible value of the index register, it writes the corresponding data value to the data register.

from guppyalgos.algorithms.select.qrom import qrom_unary_iteration

from guppylang.decorator import guppy
from guppylang.std.builtins import array, output
from guppylang.std.quantum import measure_array, qubit, toffoli, x, h, collect_measurements

from guppyalgos.utils import int_to_bits, qarray

from guppylang import comptime

from guppyalgos.primitives.gate_decompositions.and_op import (
    temp_and_compute,
    temp_and_uncompute,
)

  • First we must build the input data

  • A list of lists of bools is used to represent the classical data to be stored in the QROM.

  • Currently only a single target register is supported.

import numpy as np
# build a random of list of list of bools

n_index_qubits = 4
n_state_qubits = 4
n_index_elements = 2**n_index_qubits  # check when this is not a power of 2

data_input = [np.random.choice([False, True], n_state_qubits).tolist() for _ in range(n_index_elements)]

  • We use a metaprogramming approach to build the QROM circuit where we use a python function to generate the guppy function

  • The QROM is has freedom to use different compute and uncompute functions for the AND operations

  • In this example function we initialize the index register to a specific value and check that the correct data is written to the data register by measuring the index register at the end of the circuit, which should still be in the same index.

def qrom_and_input(compute_and, uncompute_and, data_input, index):

    binary_index = int_to_bits(index, n_index_qubits)

    qrom = qrom_unary_iteration(data_input, comp_and_op=compute_and, uncomp_and_op=uncompute_and)

    @guppy
    def main() -> None:
        idx = binary_index
        index_qreg = qarray(n_index_qubits)
        state_qreg = qarray(n_state_qubits)

        for bit in range(n_index_qubits):
            if idx[bit]:
                x(index_qreg[bit])

        qrom(index_qreg, state_qreg)

        output("index", collect_measurements(measure_array(index_qreg)))
        output("state", collect_measurements(measure_array(state_qreg)))


    total_qubits = n_state_qubits + n_index_qubits + (n_index_qubits - 1)
    my_shots = main.emulator(n_qubits=total_qubits).with_seed(42).with_shots(1).run()

    print(f"Measured data {index}: ", my_shots.collated_shots()[0]["state"])
    print(f"Expected data {index}: ", data_input[index])

for i in range(4):
    print(f"--- Test {i} ---")
    qrom_and_input(toffoli, toffoli, data_input, i)

--- Test 0 ---
Measured data 0:  [[0, 0, 1, 1]]
Expected data 0:  [False, False, True, True]
--- Test 1 ---
Measured data 1:  [[1, 0, 1, 0]]
Expected data 1:  [True, False, True, False]
--- Test 2 ---
Measured data 2:  [[1, 0, 1, 1]]
Expected data 2:  [True, False, True, True]
--- Test 3 ---
Measured data 3:  [[0, 0, 0, 1]]
Expected data 3:  [False, False, False, True]

  • We can also use T gate efficient AND functions to reduce the T gate count of the QROM circuit.

  • Following the implementation from https://arxiv.org/abs/1805.03662 we can do the compute temporary and with 4 T gates and the uncompute with 0 T gates using measurement based computation.

qrom_and_input(temp_and_compute, temp_and_uncompute, data_input, 3)

Measured data 3:  [[0, 0, 0, 1]]
Expected data 3:  [False, False, False, True]

  • Here we can apply a uniform superposition to the index register by applying Hadamard gates to all qubits in the index register.

  • Each shot will give a uniformly random binary index and the corresponding data value.

from guppyalgos.utils import transversal

def qrom_h_transversal(compute_and, uncompute_and, data_input):

    qrom = qrom_unary_iteration(data_input, comp_and_op=compute_and, uncomp_and_op=uncompute_and)

    @guppy
    def main() -> None:
        index_qreg = qarray(n_index_qubits)
        state_qreg = qarray(n_state_qubits)

        transversal(h, index_qreg)

        qrom(index_qreg, state_qreg)

        output("index", collect_measurements(measure_array(index_qreg)))
        output("state", collect_measurements(measure_array(state_qreg)))


    total_qubits = n_state_qubits + n_index_qubits + (n_index_qubits - 1)
    my_shots = main.emulator(n_qubits=total_qubits).with_seed(42).with_shots(10).run()

    print(f"Measured data: ", my_shots.collated_shots())

qrom_h_transversal(toffoli, toffoli, data_input)

Measured data:  [{'index': [[1, 0, 0, 1]], 'state': [[0, 0, 0, 1]]}, {'index': [[0, 0, 1, 1]], 'state': [[0, 0, 0, 1]]}, {'index': [[0, 1, 1, 1]], 'state': [[1, 1, 1, 0]]}, {'index': [[0, 0, 0, 0]], 'state': [[0, 0, 1, 1]]}, {'index': [[1, 0, 0, 0]], 'state': [[0, 1, 0, 0]]}, {'index': [[0, 0, 0, 1]], 'state': [[1, 0, 1, 0]]}, {'index': [[1, 0, 0, 1]], 'state': [[0, 0, 0, 1]]}, {'index': [[0, 0, 0, 1]], 'state': [[1, 0, 1, 0]]}, {'index': [[0, 1, 0, 0]], 'state': [[0, 1, 0, 0]]}, {'index': [[0, 1, 1, 1]], 'state': [[1, 1, 1, 0]]}]