Source code for pennylane.templates.subroutines.qrom

# 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(
    bitstrings, depth, target_wires, swap_wires, select_control_wires, select_work_wires
):  # pylint:disable=too-many-arguments
    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: 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, ): # pylint: disable=too-many-arguments,disable=too-many-positional-arguments 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, ) def _select_swap_condition(bitstrings, control_wires, target_wires, work_wires, clean): # pylint: disable=unused-argument """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 _select_swap_resources( bitstrings, control_wires, target_wires, work_wires, clean ): # pylint: disable=too-many-branches """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(_select_swap_resources) def _select_swap( bitstrings, control_wires, target_wires, work_wires, clean ): # pylint: disable=unused-argument, too-many-arguments 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): @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 _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. """ x_wires = [targets[i] for i, bit in enumerate(product) if bit == 1] m1 = pauli_measure("X" + "X" * len(x_wires), [work_wire, *x_wires]) 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) def _measurement_qrom_inner(controls, targets, bitstrings): """Inner binary recursion with measurement-based uncomputation. Each level opens a TemporaryAND, recurses into left/right halves, then uncomputes via measurement. The XOR product between subtree bases is absorbed into the measurement. Args: controls: interleaved [flag, sel, work, sel2, work2, ...] targets: target register wires bitstrings: The set of k strings to be loaded in the decomposition. They do not necessarily match the QROM input values. """ k = len(bitstrings) if k <= 1: return num_bits = ceil_log2(k) needed = 2 * num_bits + 1 controls = list(controls[:1]) + list(controls[-(needed - 1) :]) flag, sel, work = controls[0], controls[1], controls[2] child_controls = controls[2:] k_left = 2 ** (num_bits - 1) if k > 2: TemporaryAND([flag, sel, work], control_values=[1, 0]) _measurement_qrom_inner(child_controls, targets, bitstrings[:k_left]) CNOT(wires=[flag, work]) _measurement_qrom_inner(child_controls, targets, bitstrings[k_left:]) else: TemporaryAND([flag, sel, work], control_values=[1, 1]) product = math.bitwise_xor(bitstrings[0], bitstrings[k_left]) _measurement_uncompute(work, [flag, sel], targets, product) 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) --- for i, bit in enumerate(diff_q1): if bit == 1: CNOT(wires=[controls[2], targets[i]]) 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]) for i, bit in enumerate(diff_q2): if bit == 1: CNOT(wires=[sec_wires[2], targets[i]]) # --- 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, # one per inner-iterator split in the quarters, and up to ``num_targets`` for each of the # two explicit base corrections. num_ands = _count_tempAND_in_measurement_qrom(L) num_cnots = 3 + max(L // 2 - 4, 0) + 2 * num_targets resources = {load: 1, 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( bitstrings=None, control_wires=None, target_wires=None, work_wires=None, clean=None, base=None ): # pylint: disable=too-many-arguments,unused-argument 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(): 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) def _qrom_measurement_decomposition( bitstrings=None, control_wires=None, target_wires=None, work_wires=None, clean=None, base=None ): # pylint: disable=too-many-arguments,too-many-branches,unused-argument """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.zeros((2**num_control_wires_active, len(bitstrings[0])), dtype=int) padded[:L] = bitstrings 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( bitstrings, control_wires, target_wires, work_wires, clean=True, ): # pylint: disable=unused-argument,too-many-arguments 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)() # pylint: disable=no-value-for-parameter # 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) def _qrom_unary_iteration( bitstrings, control_wires, target_wires, work_wires, clean, **__ ): # pylint: disable=unused-argument, too-many-arguments """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, _select_swap, _qrom_unary_iteration, _qrom_measurement_decomposition, ) add_decomps("Adjoint(QROM)", _qrom_measurement_decomposition)