# Copyright 2018-2025 Xanadu Quantum Technologies Inc.
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
# http://www.apache.org/licenses/LICENSE-2.0
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.
"""
This submodule contains the template for QROM.
"""
import math as builtin_math
from collections.abc import Sequence
from functools import partial
import numpy as np
from pennylane import capture, compiler, math
from pennylane import ops as qp_ops
from pennylane.capture import hint
from pennylane.control_flow import for_loop
from pennylane.core.operator import Operator2
from pennylane.decomposition import (
add_decomps,
register_condition,
register_resources,
)
from pennylane.math import ceil_log2
from pennylane.ops import CNOT, CZ, MultiControlledX, X, Z, cond, ctrl, pauli_measure
from pennylane.ops.mid_measure.pauli_measure import PauliMeasure
from pennylane.typing import AbstractArray, Bool, TensorLike, Wire
from pennylane.wires import Wires, WiresLike, validate_no_wire_overlaps
from .arithmetic import TemporaryAND
from .multix import MultiX
def _select_ops( # pylint: disable=too-many-arguments
bitstrings, depth, target_wires, swap_wires, select_control_wires, select_work_wires
):
num_targets = len(target_wires)
num_bitstrings = bitstrings.shape[0]
num_columns = int(np.ceil(num_bitstrings / depth))
num_missing = (-num_bitstrings) % depth
if num_missing > 0:
bitstrings = math.vstack([bitstrings, math.zeros((num_missing, num_targets), dtype=int)])
num_targets_select = depth * num_targets
new_bitstrings = bitstrings.reshape((num_columns, num_targets_select))
# Make sure we do not create a QROM with Select-SWAP option, because that would yield invalid
# decompositions.
num_work_wires_select = max(0, len(select_control_wires) - 1)
QROM(
new_bitstrings,
control_wires=select_control_wires,
target_wires=swap_wires[:num_targets_select],
work_wires=select_work_wires[:num_work_wires_select],
clean=False,
)
def _swap_ops(swap_control_wires, swap_wires, target_wires, cswap_work_wires, adjoint=False):
n_targets = len(target_wires)
if capture.enabled() or compiler.active():
swap_wires = math.array(swap_wires, like="jax").reshape((-1, n_targets))
swap_control_wires = math.array(swap_control_wires, like="jax")
else:
# Need to work with nested list here in order to not coerce (deprecated) string wire labels
# to object-dtyped np.array. This forces manual "reshape" here and indexing via [j][k]
# instead of [j, k] below.
num_columns = len(swap_wires) // n_targets
swap_wires = [swap_wires[i * n_targets : (i + 1) * n_targets] for i in range(num_columns)]
n_iters = len(swap_control_wires)
outer_loop = for_loop(0, n_iters) if adjoint else for_loop(n_iters - 1, -1, -1)
def outer(i):
inner_loop = for_loop(0, 2**i) if adjoint else for_loop(2**i - 1, -1, -1)
def inner(j):
layer_loop = for_loop(n_targets - 1, -1, -1) if adjoint else for_loop(0, n_targets)
def swap_layer(k):
ctrl(
qp_ops.SWAP([swap_wires[j][k], swap_wires[j + 2**i][k]]),
control=swap_control_wires[-i - 1],
work_wires=cswap_work_wires,
work_wire_type="zeroed",
)
layer_loop(swap_layer)()
inner_loop(inner)()
outer_loop(outer)()
[docs]
class QROM(Operator2):
r"""Applies the QROM operator.
This operator encodes bitstrings associated with indexes:
.. math::
\text{QROM}|i\rangle|0\rangle = |i\rangle |b_i\rangle,
where :math:`b_i` is the bitstring associated with index :math:`i`.
Args:
bitstrings (TensorLike): the data to be encoded
control_wires (WiresLike):
The register that stores the index for the entry of the classical data we want to
read.
target_wires (Sequence[int]): the wires where the bitstring is loaded
work_wires (Sequence[int]): the auxiliary wires used for the computation
clean (bool): if True, the work wires are not altered by operator, default is ``True``
.. seealso:: :class:`~.BBQRAM`, :class:`~.QROMStatePreparation`
.. note::
QRAM and QROM, though similar, have different applications and purposes. QRAM is intended
for read-and-write capabilities, where the stored data can be loaded and changed. QROM is
designed to only load stored data into a quantum register.
**Example**
In this example, the QROM operator is applied to encode the third bitstring, associated with index 2, in the target wires.
.. code-block:: python
# a list of bitstrings is defined
bitstrings = [[0, 1, 0], [1, 1, 1], [1, 1, 0], [0, 0, 0]]
dev = qp.device("default.qubit")
@qp.qnode(dev, shots=1)
def circuit():
# the third index is encoded in the control wires [0, 1]
qp.BasisState([1, 0], wires = [0,1])
qp.QROM(bitstrings = bitstrings,
control_wires = [0,1],
target_wires = [2,3,4],
work_wires = [5,6,7])
return qp.sample(wires = [2,3,4])
>>> print(circuit())
[[1 1 0]]
.. details::
:title: Available decompositions
.. decomposition-table:: qp.QROM
:stacked:
:symbols: :math:`K` bitstrings of length :math:`b`, :math:`c \geq 2` control wires,
:math:`w` work wires and ``clean=True``
:example: :math:`K=4`, :math:`b=2`, :math:`c=2`, :math:`w=2`, bitstrings
``[[0, 0], [0, 1], [1, 0], [1, 1]]``
.. decomposition-rule:: select_swap
:image: /_static/decomposition_thumbnails/qrom_select_swap.svg
:requires: :math:`w \geq c - 1` work wires and :math:`\lambda \geq 2`
:where: :math:`\lambda` is the number of bitstrings loaded in parallel: the largest
power of 2 with :math:`\lambda \leq K`, :math:`b(\lambda - 1) \leq w` and
:math:`w - b(\lambda - 1) \geq c - \log_2 \lambda - 1`. The nested
:class:`~.QROM` loads :math:`\lceil K/\lambda \rceil` bitstrings of length
:math:`\lambda b`
:class:`~.QROM` | :math:`2` | 2
:class:`~.Hadamard` | :math:`2b` | 4
:class:`~.CSWAP` | :math:`4b(\lambda - 1)` | 8
.. decomposition-rule:: unary_iteration
:image: /_static/decomposition_thumbnails/qrom_unary_iteration.svg
:where: :math:`t = \min(c, w + 1)` control wires span the unary iteration tree and
the other :math:`e = c - t` are added as controls to each load,
:math:`B = \lceil K / 2^e \rceil`,
:math:`N = t + B - 2 - \mathrm{wt}(B-1) - [B > 2^{t-1}]`, with
:math:`\mathrm{wt}` the number of ones in the binary representation, and
:math:`[\cdot]` equal to 1 if the condition holds and 0 otherwise. With no work
wires (:math:`w = 0`), each bitstring is instead loaded by a :class:`~.MultiX`
with :math:`c` controls
:class:`~.TemporaryAND` | :math:`N` | 1
:class:`Adjoint(TemporaryAND) <.TemporaryAND>` | :math:`N` | 1
:class:`~.CNOT` | :math:`B - 1 + [B > 2^{t-1}]` | 4
:class:`~.X` | :math:`2[B > 2^{t-2}]` | 2
:class:`~.MultiX` with :math:`e + 1` controls | :math:`K` | 4
.. decomposition-rule:: measurement
:image: /_static/decomposition_thumbnails/qrom_measurement.svg
:requires: :math:`w \geq c - 1` work wires and compilation with :func:`~.qjit`
:where: :math:`L = 2^c` (the data is padded to :math:`L` entries, assuming
:math:`c = \lceil \log_2 K \rceil`) and :math:`A = L - 3`. Gates marked as
conditional are applied depending on mid-circuit measurement outcomes,
and the number of :class:`~.CNOT` gates depends on the bitstrings
:class:`~.MultiX` | :math:`1 + A` (:math:`A` conditional) | 2
:class:`~.TemporaryAND` | :math:`A` | 1
:class:`~.X` with 1 control on :math:`|0\rangle` | :math:`1` | 1
:class:`~.CNOT` | at most :math:`\max(3, L/2 - 1) + 2b` | 5
:func:`PauliMeasure <.pauli_measure>` (:math:`X`-type, :math:`\leq b + 1` wires) | :math:`A` | 1
:func:`PauliMeasure <.pauli_measure>` (:math:`Z`, 1 wire) | :math:`A` | 1
:class:`~.CZ` (conditional) | :math:`A` | 1
:class:`~.Z` (conditional) | :math:`A` | 1
:class:`~.X` (conditional) | :math:`A` | 1
.. details::
:title: Usage Details
This template takes as input three different sets of wires. The first one is ``control_wires`` which is used
to encode the desired index. Therefore, if we have :math:`m` bitstrings, we need
at least :math:`\lceil \log_2(m)\rceil` control wires.
The second set of wires is ``target_wires`` which stores the bitstrings.
For instance, if the bitstring is ``[0, 1, 1, 0]``, we will need four target wires. Internally,
the bitstrings are encoded using the :class:`~.MultiX` template.
The ``work_wires`` are auxiliary qubits used to reduce the gate complexity of the
operator. These wires are dynamically partitioned into two sets: one for the
:class:`~.Select` block and another to facilitate parallel data loading via a
`SWAP network <https://pennylane.ai/compilation/swap-network>`__.
The template determines the depth, :math:`\lambda` (a power of 2),
based on the available ``work_wires``. Let :math:`b` be the length of the bitstrings.
The number of wires allocated to the SWAP network is :math:`k_{swap} = b \cdot (\lambda - 1)`.
The remaining wires, :math:`k_{select}`, are assigned to the :class:`~.Select` block.
To ensure the decomposition is valid, the template guarantees that
:math:`k_{select} \geq c - \log_2(\lambda) - 1`, where :math:`c` is the number of
control wires, updating the depth if needed.
The QROM template has two variants. The first one (``clean = False``) is based on [`arXiv:1812.00954 <https://arxiv.org/abs/1812.00954>`__] that alternates the state in the ``work_wires``.
The second one (``clean = True``), based on [`arXiv:1902.02134 <https://arxiv.org/abs/1902.02134>`__], solves that issue by
returning ``work_wires`` to their initial state. This technique can be applied when the ``work_wires`` are not
initialized to zero.
.. note::
More ``control_wires`` than the minimum :math:`\lceil \log_2(m) \rceil` may be
provided. The extra wires are treated as the most-significant address bits: the data
is loaded only when they are all in :math:`|0\rangle`, and the operation acts as the
identity otherwise. This turns ``QROM`` into a *controlled* load gated by those extra
wires.
"""
dynamic_argnames = ("bitstrings",)
wire_argnames = ("control_wires", "target_wires", "work_wires")
compilable_argnames = ("clean",)
arg_specs = {
"bitstrings": Bool[-1, -1],
"control_wires": Wire[-1],
"target_wires": Wire[-1],
"work_wires": Wire[-1],
}
def __init__(
self,
bitstrings: TensorLike | Sequence[str],
control_wires: WiresLike,
target_wires: WiresLike,
work_wires: WiresLike,
clean=True,
):
control_wires = Wires(control_wires)
target_wires = Wires(target_wires)
work_wires = Wires(() if work_wires is None else work_wires)
if not isinstance(bitstrings, AbstractArray):
if isinstance(bitstrings[0], str):
bitstrings = [[int(bit) for bit in bitstring] for bitstring in bitstrings]
if isinstance(bitstrings, (list, tuple)):
bitstrings = math.array(bitstrings, dtype=bool)
else:
bitstrings = bitstrings.astype(bool)
wire_args = {
"control_wires": control_wires,
"target_wires": target_wires,
"work_wires": work_wires,
}
validate_no_wire_overlaps(wire_args)
if 2 ** len(control_wires) < bitstrings.shape[0]:
raise ValueError(
f"Not enough control wires ({len(control_wires)}) for the desired number of "
f"bitstrings ({bitstrings.shape[0]}). At least {ceil_log2(bitstrings.shape[0])} "
"control wires are required."
)
if bitstrings.shape[1] != len(target_wires):
raise ValueError("Bitstring length must match the number of target wires.")
super().__init__(bitstrings, control_wires, target_wires, work_wires, clean)
@property
def wires(self):
"""All wires involved in the operation."""
return self.control_wires + self.target_wires + self.work_wires
def _calculate_select_swap_sizes(
num_bitstrings, num_control_wires, num_targets, num_work_wires, **_
):
"""Calculates the register sizes for the Select-SWAP decomposition.
This utility function determines how many auxiliary wires from the total pool
should be allocated to the Select operation versus the SWAP network.
Args:
num_bitstrings (int): number of bitstrings/entries in the data
num_control_wires (int): number of control wires
num_targets (int): number of target wires (bitstring length)
num_work_wires (int): total number of available work wires
Returns:
tuple[int]: ``(num_control_wires_select, num_work_wires_select, num_work_wires_swap,
num_work_wires_cswap, depth)`` — control and work wires assigned to the Select component,
work wires assigned to the SWAP network, and the number of bitstrings loaded in parallel.
"""
if num_work_wires < num_control_wires - 1:
return num_control_wires, num_work_wires, 0, 0, 1
# Initialize available swap space using total work wires
num_work_wires_swap = num_work_wires
num_wires_swap = num_targets + num_work_wires_swap
# Calculate depth: how many bitstrings we can load in parallel (power of 2)
depth = num_wires_swap // num_targets
depth = 1 << math.floor_log2(min(depth, num_bitstrings))
# Recalculate actual wires used by SWAP and the remaining for Select
num_work_wires_swap = num_targets * depth - num_targets
num_work_wires_select = num_work_wires - num_work_wires_swap
# Adjust depth if Select doesn't have enough work wires for the required control logic
num_control_wires_select = num_control_wires - int(math.floor_log2(depth))
while num_work_wires_select < num_control_wires_select - 1:
depth = depth // 2
num_work_wires_swap = num_targets * (depth - 1)
num_work_wires_select = num_work_wires - num_work_wires_swap
num_control_wires_select = num_control_wires - int(math.floor_log2(depth))
# As soon as there is an excess work wire for Select, reroute it to the CSWAPs themselves.
num_work_wires_cswap = int(num_work_wires_select - max(0, num_control_wires_select - 1) >= 1)
return (
num_control_wires_select,
num_work_wires_select,
num_work_wires_swap,
num_work_wires_cswap,
depth,
)
# pylint: disable-next=unused-argument
def _select_swap_condition(bitstrings, control_wires, target_wires, work_wires, clean):
"""We use Select-SWAP only when there are enough work wires for unary iteration on the
nested select QROM and an actual SWAP network is used on top, i.e. for depth > 1."""
num_control_wires = len(control_wires)
num_work_wires = len(work_wires)
if num_control_wires == 0 or num_work_wires < num_control_wires - 1:
return False
*_, depth = _calculate_select_swap_sizes(
len(bitstrings), num_control_wires, len(target_wires), num_work_wires
)
return depth > 1
def _qrom_select_swap_resources(bitstrings, control_wires, target_wires, work_wires, clean):
"""Assumes depth computed below satisfies depth > 1, as guaranteed by _select_swap_condition."""
num_bitstrings = len(bitstrings)
num_control_wires = len(control_wires)
num_targets = len(target_wires)
num_work_wires = len(work_wires)
num_control_wires_select, _, _, num_work_wires_cswap, depth = _calculate_select_swap_sizes(
num_bitstrings, num_control_wires, num_targets, num_work_wires
)
num_work_wires_select = max(0, num_control_wires_select - 1)
num_columns = int(np.ceil(num_bitstrings / depth))
# Select block (implemented as a nested QROM over concatenated columns)
num_targets_select = depth * num_targets
bigger_qrom = QROM(
Bool[num_columns, num_targets_select],
Wire[num_control_wires_select],
Wire[num_targets_select],
Wire[num_work_wires_select],
False,
)
# Swap block
num_control_wires_swap = num_control_wires - num_control_wires_select
num_cswaps_per_block = num_targets * (2**num_control_wires_swap - 1)
cswap_rep = ctrl(
qp_ops.SWAP(Wire[2]),
control=Wire[1],
work_wires=Wire[num_work_wires_cswap],
work_wire_type="zeroed",
)
if not clean:
return {bigger_qrom: 1, cswap_rep: num_cswaps_per_block}
return {bigger_qrom: 2, cswap_rep: 4 * num_cswaps_per_block, qp_ops.H: 2 * num_targets}
@register_condition(_select_swap_condition)
@register_resources(_qrom_select_swap_resources, name="select_swap")
def _qrom_select_swap(bitstrings, control_wires, target_wires, work_wires, clean):
if len(control_wires) == 0:
MultiX(bitstrings[0, :], wires=target_wires)
return
num_control_wires_select, _, num_work_wires_swap, num_work_wires_cswap, depth = (
_calculate_select_swap_sizes(
len(bitstrings), len(control_wires), len(target_wires), len(work_wires)
)
)
swap_work_wires = work_wires[:num_work_wires_swap]
select_work_wires = work_wires[num_work_wires_swap : len(work_wires) - num_work_wires_cswap]
cswap_work_wires = work_wires[len(work_wires) - num_work_wires_cswap :]
swap_wires = Wires(target_wires) + Wires(swap_work_wires)
select_control_wires = control_wires[:num_control_wires_select]
swap_control_wires = control_wires[num_control_wires_select:]
if not clean:
_select_ops(
bitstrings, depth, target_wires, swap_wires, select_control_wires, select_work_wires
)
_swap_ops(swap_control_wires, swap_wires, target_wires, cswap_work_wires)
return
if capture.enabled() or compiler.active():
target_wires = math.array(target_wires, like="jax")
@for_loop(2)
def _select_swap_loop(i): # pylint: disable=unused-argument
@for_loop(len(target_wires))
def apply_h(i):
qp_ops.H(target_wires[i])
apply_h() # pylint: disable=no-value-for-parameter
cswaps = partial(_swap_ops, swap_control_wires, swap_wires, target_wires, cswap_work_wires)
cswaps(adjoint=True)
_select_ops(
bitstrings, depth, target_wires, swap_wires, select_control_wires, select_work_wires
)
cswaps()
_select_swap_loop() # pylint: disable=no-value-for-parameter
def _measure_masked_x(work_wire, targets, bit_mask):
"""Measure X on the work wire and on targets selected by an integer bit mask."""
if not math.is_tracer(bit_mask):
x_wires = [wire for wire, bit in zip(targets, bit_mask) if bit]
return pauli_measure("X" * (len(x_wires) + 1), [work_wire, *x_wires])
# A PauliMeasure has a static word and number of wires. Group the selected targets
# first, then choose a measurement of fixed width.
selected = math.array(targets, like="jax")[math.argsort(-bit_mask)]
weight = math.sum(bit_mask)
num_targets = len(bit_mask)
def measure_width(width):
return pauli_measure("X" * (width + 1), [work_wire, *selected[:width]])
return cond(
weight == 0,
partial(measure_width, 0),
partial(measure_width, num_targets),
elifs=tuple(
(weight == width, partial(measure_width, width)) for width in range(1, num_targets)
),
)()
@capture.subroutine
def _measurement_uncompute(work_wire, ctrl_wires, targets, product):
"""Measurement-based uncomputation from Fig 18a) https://arxiv.org/abs/2211.15465
Args:
work_wire: the AND output wire to uncompute. Third wire on the figure.
ctrl_wires: [ctrl0, ctrl1] -- the two AND control wires (for CZ correction). First and second qubit on the figure.
targets: target register wires.
product: bitstring indicating the X positions in the target register.
"""
m1 = _measure_masked_x(work_wire, targets, product)
cond(m1 == 1, CZ)(wires=ctrl_wires)
# Without this, the reset below would leave a global phase of -1 if both outcomes are 1
cond(m1 == 1, Z)(wires=work_wire)
m2 = pauli_measure("Z", [work_wire])
cond(m2 == 1, X)(wires=work_wire)
cond(m2 == 1, MultiX)(product, wires=targets)
@capture.subroutine
def _measurement_qrom_inner(controls, targets, bitstrings):
"""Iterate over pairs of rows with measurement-based uncomputation.
Each pair uses a TemporaryAND that is uncomputed with its XOR mask.
Between pairs, close and reopen only the ancestor levels whose address
bits change, absorbing the XOR between each subtree's bases into its
closing measurement.
Args:
controls: interleaved [flag, sel, work, sel2, work2, ...]
targets: target register wires
bitstrings: XOR-relative table, padded to a power-of-two number of rows.
"""
if len(bitstrings) <= 1:
return
num_bits = ceil_log2(len(bitstrings))
controls = list(controls[:1]) + list(controls[-2 * num_bits :])
triples = [controls[2 * i : 2 * i + 3] for i in range(num_bits)]
if compiler.active() or capture.enabled():
triples = math.array(triples, like="jax")
bitstrings = math.array(bitstrings, like="jax")
def load_pair(k):
TemporaryAND(triples[-1], control_values=[1, 1])
bit_mask = math.bitwise_xor(bitstrings[2 * k], bitstrings[2 * k + 1])
_measurement_uncompute(triples[-1][2], triples[-1][:2], targets, bit_mask)
def close_level(i, k):
# Align the current row to the subtree rooted at level i, then compare its
# left and right base rows. The table shape stays fixed throughout the loop.
half_size = 1 << (num_bits - i - 1)
start = (2 * k // (2 * half_size)) * (2 * half_size)
bit_mask = math.bitwise_xor(bitstrings[start], bitstrings[start + half_size])
_measurement_uncompute(triples[i][2], triples[i][:2], targets, bit_mask)
def open_level(i):
TemporaryAND(triples[i], control_values=[1, 0])
for i in range(num_bits - 1):
open_level(i)
num_pairs = len(bitstrings) // 2
if num_pairs > 1:
# Exclude the initial/final ladders and the leaf AND for each pair.
average_ladder_len = (num_pairs - num_bits) / (num_pairs - 1)
def loop(k):
load_pair(k)
# MSB-first index of the ancestor bit that changes between pairs k and k+1.
level = num_bits - 1 - math.bitwise_count(math.bitwise_xor(k, k + 1)).astype(int)
uncompute = for_loop(num_bits - 2, level, -1)(partial(close_level, k=k))
hint(uncompute, {"num-iters": average_ladder_len})()
CNOT(wires=triples[level][::2])
recompute = for_loop(level + 1, num_bits - 1)(open_level)
hint(recompute, {"num-iters": average_ladder_len})()
for_loop(num_pairs - 1)(loop)()
load_pair(num_pairs - 1)
for i in range(num_bits - 2, -1, -1):
close_level(i, num_pairs - 1)
def _measurement_qrom_outer(controls, targets, bitstrings, k):
"""Outer 4-quarter split with measurement-based uncomputation.
Splits k items into quarters [Q0, Q1 | Q2, Q3] and processes each.
Base corrections absorbed into measurements where possible (CLOSE).
Remaining corrections (diff_q1, diff_q2) are explicit CNOTs.
``k`` is always a power of two (the caller pads the data up to the next
power of two), so the middle split reduces to merging the close+open of
the two halves into two CNOTs.
"""
a = ceil_log2(k)
controls = list(controls[: 2 * a - 1])
and_wires = controls[:3]
child_controls = controls[2:]
k01 = 2 ** (a - 1)
k0 = k1 = 2 ** (a - 2)
l = k - k01
k2 = 2 ** (ceil_log2(l) - 1)
k3 = k - k01 - k2
# --- OPEN ---
TemporaryAND(and_wires, control_values=[0, 0])
# --- Q0 ---
_measurement_qrom_inner(child_controls, targets, bitstrings[:k0])
# --- Q0 -> Q1 transition ---
MultiControlledX([controls[0], controls[2]], control_values=[0])
diff_q1 = math.bitwise_xor(bitstrings[0], bitstrings[k0])
# --- Q1 ---
if k1 > 1:
_measurement_qrom_inner(child_controls, targets, bitstrings[k0:k01])
# --- MIDDLE: merge close+open into 2 CNOTs (no measurement here) ---
ctrl(MultiX(diff_q1, wires=targets), control=controls[2])
CNOT(wires=[and_wires[0], and_wires[2]])
CNOT(wires=[and_wires[1], and_wires[2]])
sec_wires = and_wires
sec_child = child_controls
# --- Q2 base correction (explicit, no measurement available here) ---
diff_q2 = math.bitwise_xor(bitstrings[0], bitstrings[k01])
ctrl(MultiX(diff_q2, wires=targets), control=sec_wires[2])
# --- Q2 ---
if k2 > 1:
_measurement_qrom_inner(sec_child, targets, bitstrings[k01 : k01 + k2])
# --- Q2 -> Q3 transition ---
CNOT(wires=[sec_wires[0], sec_wires[2]])
# --- Q3 ---
diff_q3 = math.bitwise_xor(bitstrings[0], bitstrings[k01 + k2])
if k3 > 1:
_measurement_qrom_inner(sec_child, targets, bitstrings[k01 + k2 :])
# --- CLOSE: absorb diff_q3 into measurement ---
_measurement_uncompute(sec_wires[2], [sec_wires[0], sec_wires[1]], targets, diff_q3)
def _count_tempAND_in_measurement_qrom(k):
"""Count TemporaryAND gates for the measurement-based decomposition."""
if k < 3:
return 0
if k > 3 / 4 * 2 ** ceil_log2(k):
return k - 3
return k - 2
def _qrom_measurement_resources( # pylint: disable=too-many-arguments,unused-argument
bitstrings=None, control_wires=None, target_wires=None, work_wires=None, clean=None, base=None
):
"""Resource estimate for the measurement-based QROM decomposition.
Each TemporaryAND is uncomputed via _measurement_uncompute which produces:
- 2 PauliMeasure (one X-type joint measurement, one Z measurement)
- 1 CZ and 1 Z (phase corrections conditioned on X measurement)
- conditional X gates on work + targets
Only the shape of ``bitstrings`` is known, so counts that depend on the bitstring data are
estimated: CNOTs use the worst case, and the widths of the X-type measurements follow the
distribution expected for uniformly random data.
"""
# When called for Adjoint(QROM), extract params from the base parameters
if base is not None:
num_bitstrings = len(base.bitstrings)
num_targets = len(base.target_wires)
num_control_wires = len(base.control_wires)
else:
num_bitstrings = len(bitstrings)
num_targets = len(target_wires)
num_control_wires = len(control_wires)
num_control_wires_extra = (
0 if num_control_wires is None else num_control_wires - ceil_log2(num_bitstrings)
)
# L = num_bitstrings
# TODO: allowing partial QROM will reduce this term
L = 2 ** ceil_log2(num_bitstrings)
load = MultiX(Bool[num_targets], Wire[num_targets])
if num_control_wires_extra > 0:
# Flag-gated load followed by the binary inner iterator over all ``L`` entries.
num_ands = L - 1
num_cnots = max(L // 2 - 1, 0)
resources = _flag_resources(num_control_wires_extra)
resources[ctrl(load, Wire[1])] = 1
elif L <= 1:
return {load: 1}
elif L == 2:
return {load: 1, ctrl(load, Wire[1]): 1}
else:
# Base load followed by the 4-quarter outer iterator. Its CNOTs are 3 structural ones
# and one per inner-iterator split in the quarters. Two controlled loads apply the
# explicit base corrections.
num_ands = _count_tempAND_in_measurement_qrom(L)
num_cnots = 3 + max(L // 2 - 4, 0)
resources = {
load: 1,
ctrl(load, Wire[1]): 2,
MultiControlledX(Wire[2], control_values=Bool[1]): 1,
}
# Each of the ``num_ands`` uncomputations performs one Z measurement on the work wire and
# one X-type joint measurement on the work wire plus the ``w`` target wires flipped by the XOR
# of two bitstrings. For uniformly random data, ``w`` is binomially distributed, so the
# measurements are spread over all widths accordingly. Rounding up makes every width appear
# and overestimates the total number of X-type measurements by at most ``num_targets``.
uncompute = {
TemporaryAND: num_ands,
PauliMeasure("Z", wires=Wire[1]): num_ands,
CZ: num_ands,
Z: num_ands,
X: num_ands,
load: num_ands,
CNOT: num_cnots,
}
for w in range(num_targets + 1):
x_measure = PauliMeasure("X" * (w + 1), wires=Wire[w + 1])
uncompute[x_measure] = -(-num_ands * builtin_math.comb(num_targets, w) // 2**num_targets)
for rep, count in uncompute.items():
if count:
resources[rep] = resources.get(rep, 0) + count
return resources
def _flag_resources(num_control_wires_extra):
"""Return the resources for building and uncomputing the flag on extra control wires.
A single extra wire is flipped with an X gate and restored with its adjoint; two or more use a
ladder of ``num_control_wires_extra - 1`` AND gates, all later uncomputed by the same number
of adjoints.
"""
if num_control_wires_extra == 1:
return {X: 1, qp_ops.adjoint(X(Wire[1])): 1}
return {
TemporaryAND: num_control_wires_extra - 1,
qp_ops.adjoint(TemporaryAND(Wire[3])): num_control_wires_extra - 1,
}
def _qrom_measurement_condition( # pylint: disable=too-many-arguments,unused-argument
bitstrings=None,
control_wires=None,
target_wires=None,
work_wires=None,
clean=None,
base=None,
):
if base is not None:
num_bitstrings = len(base.bitstrings)
num_work_wires = len(base.work_wires)
num_control_wires = len(base.control_wires)
else:
num_bitstrings = len(bitstrings)
num_work_wires = len(work_wires)
num_control_wires = len(control_wires)
if not (compiler.active() or capture.enabled()):
return False
num_control_wires = (
num_control_wires if num_control_wires is not None else max(1, ceil_log2(num_bitstrings))
)
if num_bitstrings <= 2 and num_control_wires <= 1:
return True
return num_work_wires >= num_control_wires - 1
def _interleave_controls(sel_wires, work_wires, head=None):
"""Build the interleaved control list consumed by the measurement iterators.
The iterators expect ``[head, sel0, work0, sel1, work1, ...]`` where ``head`` is either the
first selection wire (outer iterator, no flag) or the flag wire (flag-gated inner iterator).
When ``head`` is ``None`` the first selection wire is used as the head and is not repeated.
"""
if head is None:
controls = [sel_wires[0]]
sel_wires = sel_wires[1:]
else:
controls = [head]
for sel, work in zip(sel_wires, work_wires):
controls.append(sel)
controls.append(work)
return controls
def _build_flag(extra_wires, work_wires):
"""Build a flag wire that is 1 iff all extra control wires are 0.
A single extra wire is flipped in place so that ``flag == 1`` iff it was 0; two or more are
folded with a ladder of ``AND`` gates into an ancilla work wire. Returns ``(flag, core_work)``,
where ``core_work`` are the work wires left to drive the inner unary iterator.
"""
num_control_wires_extra = len(extra_wires)
if num_control_wires_extra == 1:
X(extra_wires[0])
return extra_wires[0], work_wires
anc_work, core_work = (
work_wires[: num_control_wires_extra - 1],
work_wires[num_control_wires_extra - 1 :],
)
# Each node is ``(wire, sat_value)``: the subtree rooted at ``wire`` reports "all extra wires
# zero" when ``wire == sat_value``. Raw extra wires are satisfied at 0; ancillas written by an
# ``AND`` are satisfied at 1. Combine nodes pairwise, level by level, into a balanced tree.
nodes = [(w, 0) for w in extra_wires]
anc_iter = iter(anc_work)
while len(nodes) > 1:
next_nodes = []
for i in range(0, len(nodes) - 1, 2):
(w0, v0), (w1, v1) = nodes[i], nodes[i + 1]
anc = next(anc_iter)
TemporaryAND([w0, w1, anc], control_values=[v0, v1])
next_nodes.append((anc, 1))
if len(nodes) % 2: # carry the unpaired node up to the next level
next_nodes.append(nodes[-1])
nodes = next_nodes
return nodes[0][0], core_work
@register_condition(_qrom_measurement_condition)
@register_resources(_qrom_measurement_resources, exact=False, name="measurement")
def _qrom_measurement( # pylint: disable=too-many-arguments,unused-argument
bitstrings=None,
control_wires=None,
target_wires=None,
work_wires=None,
clean=None,
base=None,
):
"""QROM decomposition using measurement-based uncomputation.
Uses L-3 (or L-2) TemporaryAND gates. All uncomputation is done via
PauliMeasure + conditional corrections instead of adjoint(TemporaryAND).
Work wires are always left clean (via measurement-based uncomputation).
Decomposition is based on Fig 18. https://arxiv.org/abs/2211.15465
Requires: len(work_wires) >= len(control_wires) - 1.
"""
# When called for Adjoint(QROM), extract params from the base operator
if base is not None:
bitstrings = base.bitstrings
control_wires = base.control_wires
target_wires = base.target_wires
work_wires = base.work_wires
# Bitstrings are manipulated with integer bitwise operations (math.bitwise_xor)
# below, but callers may pass float data (e.g. QROM(np.eye(b), ...)). Cast to
# int so the XOR-relative encoding works regardless of the input dtype.
bitstrings = math.cast(bitstrings, int)
L = len(bitstrings)
num_control_wires = len(control_wires)
# Extra control wires beyond ceil_log2(L) are the most-significant address bits: the data
# is loaded only when they are all zero, otherwise the operation is the identity (matching
# the non-partial ``Select``). We build a flag qubit that is 1 iff every extra wire is 0
# and control the whole load on it, reusing the unary iterator ``_measurement_qrom_inner``
# over the real 2**num_control_wires_active table.
#
# ``num_control_wires_extra == 0`` is intentionally handled by the branches below (the 4-quarter outer
# iterator), which is cheaper than the flag-gated inner iterator used here.
num_control_wires_active = ceil_log2(L)
num_control_wires_extra = num_control_wires - num_control_wires_active
if num_control_wires_extra > 0:
extra_wires, active_wires = (
control_wires[:num_control_wires_extra],
control_wires[num_control_wires_extra:],
)
# Fold the extra wires into a flag that is 1 iff all of them are 0, then run the whole
# load conditioned on that flag; the flag is uncomputed afterwards so work wires stay clean.
flag, core_work = _build_flag(extra_wires, work_wires)
# Gated base load, then the flag-gated unary iterator over the padded 2**num_control_wires_active table.
padded = math.concatenate(
[
bitstrings,
math.zeros((2**num_control_wires_active - L, len(bitstrings[0])), dtype=int),
]
)
base = padded[0]
# Fanout the base bitstring onto the target register, controlled on the flag.
ctrl(MultiX(base, wires=target_wires), control=flag)
bitstrings = math.bitwise_xor(padded, base)
controls = _interleave_controls(
active_wires[:num_control_wires_active], core_work, head=flag
)
_measurement_qrom_inner(controls, list(target_wires), bitstrings)
# Uncompute the flag by inverting the exact gate sequence queued by ``_build_flag``.
qp_ops.adjoint(_build_flag)(extra_wires, work_wires)
return
# TODO: allowing partial qrom will remove this padding
# Pad data up to the next power of 2 with all-zero bitstrings
next_pow2 = 1 << ceil_log2(L)
if L < next_pow2:
width = len(bitstrings[0])
bitstrings = math.concatenate([bitstrings, math.zeros((next_pow2 - L, width), dtype=int)])
L = next_pow2
if L == 1:
MultiX(bitstrings[0], target_wires)
return
if L == 2:
MultiX(bitstrings[0], target_wires)
diff = math.bitwise_xor(bitstrings[0], bitstrings[1])
ctrl(MultiX(diff, wires=target_wires), control=control_wires[0])
return
# Load base bitstring
MultiX(bitstrings[0], target_wires)
# Build interleaved controls: [in[0], in[1], work[0], in[2], work[1], ...]
controls = _interleave_controls(control_wires, work_wires)
# XOR-relative encoding: bitstrings[i] = bitstrings[i] XOR bitstrings[0]
bitstrings = math.bitwise_xor(bitstrings, bitstrings[0])
_measurement_qrom_outer(controls, list(target_wires), bitstrings, L)
def _unary_iteration_split(num_control_wires, num_work_wires):
"""Split the control register between the unary iteration tree and the data loads.
The tree spans the most-significant control wires and consumes one work wire per level, so
at most ``num_work_wires + 1`` control wires can be absorbed into it. The remaining,
least-significant control wires are attached as additional controls to each load.
Returns:
tuple[int]: ``(num_control_wires_tree, num_control_wires_extra)`` — control wires spanned
by the tree, and leftover control wires attached to each load.
"""
num_control_wires_tree = min(num_control_wires, num_work_wires + 1)
return num_control_wires_tree, num_control_wires - num_control_wires_tree
def _qrom_unary_iteration_resources( # pylint: disable=unused-argument
bitstrings,
control_wires,
target_wires,
work_wires,
clean=True,
):
c = len(control_wires)
K = len(bitstrings)
num_targets = len(target_wires)
basis_rep = MultiX(Bool[num_targets], Wire[num_targets])
if c == 0:
return {basis_rep: 1}
if c == 1:
cbasis_rep = ctrl(basis_rep, control=Wire[1])
if K == 1:
return {cbasis_rep: 1}
return {cbasis_rep: 1, basis_rep: 1}
num_control_wires_tree, num_control_wires_extra = _unary_iteration_split(c, len(work_wires))
# Each load is controlled on the ``num_control_wires_extra`` leftover control wires, plus the flag wire of
# the iteration tree if there is one.
load_rep = ctrl(basis_rep, control=Wire[1 + num_control_wires_extra])
if num_control_wires_tree == 1:
# No work wires, so there is no tree and every load is controlled on all control wires.
return {load_rep: K}
# The tree iterates over blocks of ``2**num_control_wires_extra`` bitstrings rather than over single
# bitstrings, so the elbow count below is in terms of the number of blocks.
num_blocks = -(-K // (1 << num_control_wires_extra))
# The number of elbows required for non-partial unary iteration over K slots with c control
# nodes is given by
# N(c, K) = c + K - 2 - ‖K-1‖_H - int(K>2^{c-1}),
# where ‖.‖_H denotes the Hamming weight, or bit count.
# To see this, note that adding a control node to a given unary iteration is done by using the
# given iteration, and replacing each "slot" (controlled unitary) by a construction that
# yields two new "slots" and requires one elbow. Consequently, the addition of a control
# node uses the given iteration with ⌈K/2⌉ slots, and ⌈K/2⌉ additional elbows, leading to the
# recursion relation
# N(c+1, K) = N(c, ⌈K/2⌉) + ⌈K/2⌉
# In addition, we know that for two control nodes, just a single elbow is required:
# N(2, K) = 1
# The formula at the top is the solution to this recursion relation. An alternative expression
# for the same is
# N(c,K)=1+∑_{j=1}^{c−2} ⌈K⋅2^{−j}⌉
more_than_half = int(num_blocks > 2 ** (num_control_wires_tree - 1))
num_elbows = (
num_control_wires_tree + num_blocks - 2 - (num_blocks - 1).bit_count() - more_than_half
)
return {
TemporaryAND: num_elbows,
qp_ops.adjoint(TemporaryAND(Wire[3])): num_elbows,
CNOT: num_blocks - 1 + more_than_half,
X: 2 * int(num_blocks > 2 ** (num_control_wires_tree - 2)),
load_rep: K,
}
def _load_block(block, address_wires, target_wires, flag=None):
"""Load one block of bitstrings into the target register.
The ``s``-th entry of ``block`` is loaded when the ``address_wires`` hold the value ``s``,
read most-significant bit first. If given, ``flag`` is an additional control wire that must
be in state 1, which is how the unary iteration selects the current block.
"""
num_address = len(address_wires)
controls = list(address_wires) if flag is None else [flag, *address_wires]
address_start = 0 if flag is None else (1 << num_address)
@for_loop(len(block))
def ctrl_sequence(s):
control_values = math.int_to_binary(s + address_start, len(controls))
ctrl(MultiX(block[s], target_wires), control=controls, control_values=control_values)
ctrl_sequence() # pylint: disable=no-value-for-parameter
def _flip_iteration_bit(a, triples, top_not_flipped, quarter_prob, mid_prob):
"""Update the unary iteration tree by flipping the most significant bit that differs between
subsequent addresses (the central remains of merging a temporary AND uncomputation
ladder and the next temporary AND computation ladder).
Args:
a (int): MSB-first index of least-significant 0 bit of k, the last loaded address
triples (TensorLike): wire triples for unary iteration, sliced from the interleaved
control and auxiliary wires.
top_not_flipped (bool): whether the last loaded address is in the first half of
the total capacity given by the number of control wires.
quarter_prob (float): probability for ``a == 1`` and ``top_not_flipped`` to be true
mid_prob (float): probability for ``a == 0`` to be true
"""
flip_first_control = math.logical_and(a == 1, top_not_flipped)
quarter_x = hint(X, {"branch-prob": quarter_prob})
mid_cnot = hint(CNOT, {"branch-prob": mid_prob})
non_mid_cnot = hint(CNOT, {"branch-prob": 1 - mid_prob})
cond(flip_first_control, quarter_x)(triples[0][0])
cond(a > 0, non_mid_cnot)(triples[a - 1][::2])
cond(flip_first_control, quarter_x)(triples[0][0])
cond(a == 0, mid_cnot)(triples[0][::2])
cond(a == 0, mid_cnot)(triples[0][1:])
def _main_unary_loop_monolithic(bitstrings, triples, target_wires, extra_control_wires):
c = len(triples) + 1
assert c >= 2
block_size = 1 << len(extra_control_wires)
# The iteration runs over blocks of bitstrings, all of which are full except for the last.
num_blocks = -(-len(bitstrings) // block_size)
# An explicit trailing dimension is required because ``num_blocks - 1`` may be zero.
blocks = math.reshape(
bitstrings[: (num_blocks - 1) * block_size], (num_blocks - 1, block_size, len(target_wires))
)
last_block = bitstrings[(num_blocks - 1) * block_size :]
# last work wire in use acts as the flag qubit for data loading.
flag = triples[-1][2]
concrete_load = partial(
_load_block, address_wires=extra_control_wires, target_wires=target_wires, flag=flag
)
TemporaryAND(triples[0], (0, 0))
for i in range(1, len(triples)):
TemporaryAND(triples[i], (1, 0))
# Loop over all blocks but the last one. Skip entirely when there is only one block:
# ``blocks`` then has shape ``(0, ...)``, and Catalyst's ``for_loop(0)`` still traces the
# body, which would index into that empty axis.
if num_blocks > 1:
# Average length of the elbow ladders below, which is min(t, c - 2) for t trailing ones in k
# ladder_lens = [min((k ^ (k + 1)).bit_count() - 1, c - 2) for k in range(num_blocks - 1)]
# est_ladder_len = sum(ladder_lens) / (num_blocks - 1)
# Compute total elbow count, subtract the leading ones outside of `loop`, and divide by
# outer iteration count.
more_than_half = int(num_blocks > 2 ** (c - 1))
num_elbows = c + num_blocks - 2 - (num_blocks - 1).bit_count() - more_than_half
average_ladder_len = (num_elbows - len(triples)) / (num_blocks - 1)
# Out of all k, a single one leads to a == 1 within the first half, if it is reached, and
# a single one leads to a == 0, if the second half is reached.
quarter_prob = int(num_blocks > 2 ** (c - 2)) / (num_blocks - 1)
mid_prob = more_than_half / (num_blocks - 1)
def loop(k):
# 1. load the k-th block, controlled on the flag circuit
concrete_load(blocks[k])
# 2. transition address k -> k+1
# a is the MSB-first index of least-significant 0 bit of k
a = c - math.bitwise_count(math.bitwise_xor(k, k + 1)).astype(int)
# 2a. right-elbow ladder: uncompute levels c-2 .. max(a,1) (top-down)
lower_bound = math.max(math.array([a, 1], like=a))
@hint({"num-iters": average_ladder_len})
@for_loop(c - 2, lower_bound - 1, -1)
def uncompute(i):
qp_ops.adjoint(TemporaryAND)(wires=triples[i])
uncompute() # pylint: disable=no-value-for-parameter
# 2b. merge gate(s) at the boundary
# Whether we are in the first half of the iteration, so that the top bit
# has not been flipped yet
top_not_flipped = k < (1 << (c - 1))
_flip_iteration_bit(a, triples, top_not_flipped, quarter_prob, mid_prob)
# 2c. left-elbow ladder: recompute levels max(a,1) .. c-2 (bottom-up)
@hint({"num-iters": average_ladder_len})
@for_loop(lower_bound, c - 1)
def recompute(i):
TemporaryAND(triples[i], (1, 0))
recompute() # pylint: disable=no-value-for-parameter
for_loop(num_blocks - 1)(loop)()
# Load the last block, which may be partially filled
concrete_load(last_block)
# closing ladder of right elbows for address num_blocks-1; control values depend on the bits of num_blocks-1
closing_bits = [(num_blocks - 1 >> (c - 1 - b)) & 1 for b in range(c)]
# levels i=c-2 .. 1 close with cvals (1, closing_bits[i+1]); level 0 closes with
# cvals closing_bits[:2]
for i in range(len(triples) - 1, 0, -1):
qp_ops.adjoint(TemporaryAND(wires=triples[i], control_values=(1, closing_bits[i + 1])))
qp_ops.adjoint(TemporaryAND(wires=triples[0], control_values=tuple(closing_bits[:2])))
@register_resources(_qrom_unary_iteration_resources, name="unary_iteration")
# pylint: disable-next=unused-argument
def _qrom_unary_iteration(bitstrings, control_wires, target_wires, work_wires, clean, **__):
"""Unary iteration decomposition of QROM.
The unary iteration tree is grown over the most-significant control wires, one level per
available work wire. Any control wire that is left over becomes an additional control of the
``MultiX`` loads, so that each slot of the unary iteration tree loads a block of bitstrings.
With no work wires at all this reduces to one multi-controlled load per bitstring, with
at least ``len(control_wires)-1`` work wires, we obtain classic unary iteration.
"""
num_control_wires = len(control_wires)
if num_control_wires == 0:
# Simply load unique bit string
MultiX(bitstrings[0], target_wires)
return
if num_control_wires == 1:
if len(bitstrings) == 1:
# One bit string to be applied
ctrl(MultiX(bitstrings[0], target_wires), control=control_wires, control_values=[0])
return
# Two bit strings to be applied. Load the first unconditionally and control-load the diff
MultiX(bitstrings[0], target_wires)
ctrl(MultiX(bitstrings[0] ^ bitstrings[1], target_wires), control=control_wires)
return
num_control_wires_tree, num_control_wires_extra = _unary_iteration_split(
num_control_wires, len(work_wires)
)
if num_control_wires_tree == 1:
# Without work wires there is no unary iteration tree to build and the full control
# register controls each bitstring to be loaded.
_load_block(bitstrings, control_wires, target_wires)
return
# We are guaranteed num_control_wires_tree > 1 from here on, because num_control_wires_tree >= 1 initially.
tree_wires, extra_control_wires = (
control_wires[:num_control_wires_tree],
control_wires[num_control_wires_tree:],
)
# Compute unary iteration wires
interleaved = _interleave_controls(tree_wires, work_wires, head=None)
triples = [interleaved[2 * i : 2 * i + 3] for i in range(num_control_wires_tree - 1)]
if compiler.active() or capture.enabled():
bitstrings = math.array(bitstrings, like="jax")
triples = math.array(triples, like="jax")
if num_control_wires_extra > 0:
extra_control_wires = math.array(extra_control_wires, like="jax")
_main_unary_loop_monolithic(bitstrings, triples, target_wires, extra_control_wires)
add_decomps(
QROM,
_qrom_select_swap,
_qrom_unary_iteration,
_qrom_measurement,
)
add_decomps("Adjoint(QROM)", _qrom_measurement)