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(  # 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)