Controlled QROM with unary iterationΒΆ
Download Notebook - controlled_qrom_unary_iteration.ipynb
Unary iteration controlled 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.controlled_qrom_unary_iteration import cntrl_qrom_unary_iteration
import pytest
from guppylang.decorator import guppy
from guppylang.std.builtins import array, output
from guppylang.std.quantum import measure_array, qubit, toffoli, x, h, discard, 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 = 3
n_state_qubits = 2
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)]
print(f" There are {len(data_input)} data input bitstrings, each of length {n_state_qubits}.")
print(f"Data input bitstrings: {data_input}")
There are 8 data input bitstrings, each of length 2.
Data input bitstrings: [[True, False], [True, True], [False, False], [True, False], [False, True], [True, True], [True, False], [False, False]]
We use a metaprogramming approach to build the QROM circuit where we use a python function to generate the guppy function
The QROM 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.
from guppylang.std.qsystem.helios import collect_measurements
def qrom_and_input(compute_and, uncompute_and, data_input, index):
binary_index = int_to_bits(index, n_index_qubits)
print(f"Binary index: {binary_index}")
qrom = cntrl_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)
control = qubit()
x(control)
for bit in range(n_index_qubits):
if idx[bit]:
x(index_qreg[bit])
qrom(control, index_qreg, state_qreg)
output("index", collect_measurements(measure_array(index_qreg)))
output("state", collect_measurements(measure_array(state_qreg)))
discard(control)
total_qubits = n_state_qubits + n_index_qubits + n_index_qubits + 1 # state + index + work + control
my_shots = main.emulator(n_qubits=total_qubits).with_seed(42).with_shots(1).run()
#print(f"Measured index {index}:" , my_shots.collated_shots())
print(f"Measured data {index}: ", my_shots.collated_shots()[0]["state"])
print(f"Expected data {index}: ", data_input[index])
for i in range(n_index_elements):
print(f"--- Test {i} ---")
qrom_and_input(toffoli, toffoli, data_input, i)
--- Test 0 ---
Binary index: [False, False, False]
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, 1)
Binary index: [False, False, True]
Measured data 1: [[0, 0]]
Expected data 1: [0, 0]
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.
Example:
We want to load the following list of data with 4 elements:
\([[0,0,1], [1,1,0], [1,0,1], [1,0,0]]\).We prepare 2 index qubits in uniform superposition:
\(\frac{1}{2} (\ket{00} + \ket{01} + \ket{10} + \ket{11})\)then we expect the following correspondence upon measuring the index qubits and data qubits:
index result
data result
00
001
01
110
10
101
11
100
from guppyalgos.utils import transversal
def cntrl_qrom_h_transversal(compute_and, uncompute_and, data_input):
qrom = cntrl_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)
control = qubit()
x(control)
transversal(h, index_qreg)
qrom(control, index_qreg, state_qreg)
output("index", collect_measurements(measure_array(index_qreg)))
output("state", collect_measurements(measure_array(state_qreg)))
discard(control)
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()
return my_shots
results = cntrl_qrom_h_transversal(toffoli, toffoli, data_input)
for shot in results.collated_shots():
print(f"Measured index is {shot['index']}, and measured state is {shot['state']}")
Measured index is [[1, 0, 0]], and measured state is [[1, 1]]
Measured index is [[0, 0, 1]], and measured state is [[0, 0]]
Measured index is [[0, 1, 1]], and measured state is [[0, 0]]
Measured index is [[0, 0, 0]], and measured state is [[0, 1]]
Measured index is [[1, 0, 0]], and measured state is [[1, 1]]
Measured index is [[0, 0, 0]], and measured state is [[0, 1]]
Measured index is [[1, 0, 0]], and measured state is [[1, 1]]
Measured index is [[0, 0, 0]], and measured state is [[0, 1]]
Measured index is [[0, 1, 0]], and measured state is [[0, 0]]
Measured index is [[0, 1, 1]], and measured state is [[0, 0]]