Source code for pennylane.templates.subroutines.arithmetic.adder

# Copyright 2024 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.
"""
Contains the Adder template.
"""

from collections import defaultdict

from pennylane.core.operator import Operator2
from pennylane.decomposition import (
    add_decomps,
    register_resources,
)
from pennylane.decomposition.resources import resource_rep
from pennylane.ops import CNOT, MultiControlledX, X
from pennylane.ops.op_math import change_op_basis
from pennylane.ops.op_math.adjoint import adjoint
from pennylane.ops.op_math.change_op_basis2 import _change_op_basis_abstract
from pennylane.templates.subroutines.qft import QFT
from pennylane.typing import Wire
from pennylane.wires import Wires, WiresLike, concatenate_wires, validate_no_wire_overlaps

from .phase_adder import PhaseAdder


def _increment(wires, control=()):
    """Carry-ripple ``+1`` (mod ``2**len(wires)``) on big-endian ``wires``, optionally controlled.

    The bits are flipped from most to least significant so each control still sees the original
    values of the lower bits. Every multi-controlled ``X`` borrows the higher-significance wires
    (already processed in this ripple, hence uninvolved) as dirty work wires, which are left unchanged.
    """
    wires = Wires(wires)
    control = Wires(control)
    n = len(wires)
    for i in range(n):
        controls = wires[i + 1 :] + control
        if len(controls) == 0:
            X(wires[i])
        else:
            MultiControlledX(
                wires=controls + wires[i : i + 1],
                work_wires=wires[:i],
                work_wire_type="borrowed",
            )


def _add_constant(k, wires, control=()):
    """Add the constant ``k`` (mod ``2**len(wires)``) to big-endian ``wires``, optionally controlled.

    Each set bit of ``k`` at position ``j`` is a ``+1`` acting on the top ``len(wires) - j`` wires.
    A subtraction is requested by passing a negative ``k`` (added as its two's complement).
    """
    wires = Wires(wires)
    control = Wires(control)
    n = len(wires)
    k %= 2**n
    for j in range(n):
        if (k >> j) & 1:
            _increment(wires[: n - j], control)


[docs] class Adder(Operator2): r"""Performs the in-place modular addition operation. This operator performs the modular addition by an integer :math:`k` modulo :math:`mod` in the computational basis: .. math:: \text{Adder}(k, mod) |x \rangle = | x+k \; \text{mod} \; mod \rangle. Two decomposition rules are registered for this operator. The first is based on the quantum Fourier transform method presented in `arXiv:2311.08555 <https://arxiv.org/abs/2311.08555>`_. The second is a QFT-free arithmetic rule built from carry-ripple incrementers, which avoids the arbitrarily precise rotations of the QFT approach and whose multi-controlled gates reuse the remaining register wires as borrowed (dirty) work wires for a cheaper decomposition. Its modular-reduction structure follows the modular adder of Beauregard, 2.2 (`arXiv:quant-ph/0205095 <https://arxiv.org/abs/quant-ph/0205095>`_), with the Fourier additions replaced by computational-basis incrementers. When the graph-based decomposition system is enabled (via :func:`~pennylane.decomposition.enable_graph`), the cheaper rule is selected automatically. .. note:: To obtain the correct result, :math:`x` must be smaller than :math:`mod`. .. seealso:: :class:`~.PhaseAdder` and :class:`~.OutAdder`. Args: k (int): the number that needs to be added x_wires (Sequence[int]): the wires the operation acts on. The number of wires must be enough for encoding `x` in the computational basis. The number of wires also limits the maximum value for `mod`. mod (int): the modulo for performing the addition. If not provided, it will be set to its maximum value, :math:`2^{\text{len(x_wires)}}`. work_wires (Sequence[int]): the auxiliary wires to use for the addition. The work wires are not needed if :math:`mod=2^{\text{len(x_wires)}}`, otherwise at least two work wires should be provided. Defaults to empty tuple. **Example** This example computes the sum of two integers :math:`x=8` and :math:`k=5` modulo :math:`mod=15`. .. code-block:: python x = 8 k = 5 mod = 15 x_wires =[0,1,2,3] work_wires=[4,5] dev = qp.device("default.qubit") @qp.qnode(dev, shots=1) def circuit(): x_bin = qp.math.int_to_binary(x, len(x_wires)) qp.BasisEmbedding(x_bin, wires=x_wires) qp.Adder(k, x_wires, mod, work_wires) return qp.sample(wires=x_wires) >>> print(circuit()) [[1 1 0 1]] The result, :math:`[[1 1 0 1]]`, is the binary representation of :math:`8 + 5 \; \text{modulo} \; 15 = 13`. .. details:: :title: Usage Details This template takes as input two different sets of wires. The first one is ``x_wires``, used to encode the integer :math:`x < \text{mod}` in the Fourier basis. To represent :math:`x`, ``x_wires`` must include at least :math:`\lceil \log_2(x) \rceil` wires. After the modular addition, the result can be as large as :math:`\text{mod} - 1`, requiring at least :math:`\lceil \log_2(\text{mod}) \rceil` wires. Since :math:`x < \text{mod}`, :math:`\lceil \log_2(\text{mod}) \rceil` is a sufficient length for ``x_wires`` to cover all possible inputs and outputs. The second set of wires is ``work_wires`` which consist of the auxiliary qubits used to perform the modular addition operation. - If :math:`mod = 2^{\text{len(x_wires)}}`, there will be no need for ``work_wires``, hence ``work_wires=()``. This is the case by default. - If :math:`mod \neq 2^{\text{len(x_wires)}}`, at least two ``work_wires`` have to be provided. Note that the ``Adder`` template allows us to perform modular addition in the computational basis. However if one just wants to perform standard addition (with no modulo), that would be equivalent to setting the modulo :math:`mod` to a large enough value to ensure that :math:`x+k < mod`. """ compilable_argnames = ("k", "mod") wire_argnames = ("x_wires", "work_wires") arg_specs = {"x_wires": Wire[-1], "work_wires": Wire[-1]} def __init__(self, k, x_wires: WiresLike, mod=None, work_wires: WiresLike = ()): x_wires = Wires(x_wires) work_wires = Wires(() if work_wires is None else work_wires) num_works_wires = len(work_wires) if mod is None: mod = 2 ** len(x_wires) elif mod != 2 ** len(x_wires) and num_works_wires < 2: raise ValueError( f"If mod is not 2^{len(x_wires)}, at least two work wires should be provided" ) if not isinstance(k, int) or not isinstance(mod, int): raise ValueError("Both k and mod must be integers") if mod > 2 ** len(x_wires): raise ValueError( "Adder must have enough x_wires to represent mod. The maximum mod " f"with len(x_wires)={len(x_wires)} is {2 ** len(x_wires)}, but received {mod}." ) validate_no_wire_overlaps({"x_wires": x_wires, "work_wires": work_wires}) super().__init__(k, x_wires, mod, work_wires) @property def wires(self): """All wires involved in the operation.""" return self.x_wires + self.work_wires
def _adder_decomposition_resources( k: int, x_wires: WiresLike, mod: int, work_wires: WiresLike ) -> dict: # pylint: disable=unused-argument num_x_wires = len(x_wires) num_qft_wires = num_x_wires if mod == 2**num_x_wires else 1 + num_x_wires _compute_op = QFT(Wire[num_qft_wires]) resources = { _change_op_basis_abstract( _compute_op, resource_rep(PhaseAdder, num_x_wires=num_qft_wires, mod=mod), adjoint(_compute_op), ): 1, } return resources @register_resources(_adder_decomposition_resources) def _adder_decomposition(k: int, x_wires: WiresLike, mod: int, work_wires: WiresLike): if mod == 2 ** len(x_wires): change_op_basis(QFT(x_wires), PhaseAdder(k, x_wires, mod)) return qft_wires = concatenate_wires(work_wires[:1], x_wires) change_op_basis(QFT(qft_wires), PhaseAdder(k, qft_wires, mod, work_wires[1:2])) def _increment_resources(num_wires: int, num_control: int = 0) -> dict: """Gate counts for :func:`_increment` acting on ``num_wires`` wires.""" counts = defaultdict(int) for i in range(num_wires): num_controls = (num_wires - 1 - i) + num_control if num_controls == 0: counts[X] += 1 else: counts[MultiControlledX(Wire[num_controls + 1], work_wires=Wire[i])] += 1 return dict(counts) def _add_constant_resources(num_wires: int, num_control: int = 0) -> dict: """Upper-bound gate counts for an ``_add_constant`` on ``num_wires`` wires. The estimate is taken at the worst case where every bit is set, so it is independent of the actual constant and covers every gate type that any constant could emit. """ counts = defaultdict(int) for size in range(1, num_wires + 1): for rep, count in _increment_resources(size, num_control).items(): counts[rep] += count return dict(counts) def _adder_arithmetic_resources( k: int, x_wires: WiresLike, mod: int, work_wires: WiresLike ) -> dict: # pylint: disable=unused-argument num_x_wires = len(x_wires) counts = defaultdict(int) if mod == 2**num_x_wires: return dict(_add_constant_resources(num_x_wires)) # The general-modulus circuit augments the register with one extra high bit and uses four # uncontrolled add/subtract blocks, one flag-controlled addition of ``mod``, and a little # flag bookkeeping (see _adder_arithmetic_decomposition). aug = num_x_wires + 1 for rep, count in _add_constant_resources(aug).items(): counts[rep] += 4 * count for rep, count in _add_constant_resources(aug, num_control=1).items(): counts[rep] += count counts[CNOT] += 2 counts[X] += 2 return dict(counts) @register_resources(_adder_arithmetic_resources, exact=False) def _adder_arithmetic_decomposition(k: int, x_wires: WiresLike, mod: int, work_wires: WiresLike): x_wires = Wires(x_wires) work_wires = Wires(work_wires) n = len(x_wires) if mod == 2**n: _add_constant(k, x_wires) return # Modular reduction follows the modular adder of Beauregard, sec. 2.2 (arXiv:quant-ph/0205095), # with the Fourier additions replaced by computational-basis incrementers: augment the register # with a spare high bit so x + k cannot wrap, then use a flag wire to conditionally undo an # over-subtraction of ``mod`` (the flag is uncomputed via his identity (a+k) mod m >= k <=> a+k < m). aug = work_wires[:1] + x_wires flag = work_wires[1:2] msb = aug[:1] k %= mod _add_constant(k, aug) # aug <- x + k _add_constant(-mod, aug) # aug <- x + k - mod (msb is the sign bit) CNOT(wires=msb + flag) # flag = 1 iff x + k < mod _add_constant(mod, aug, control=flag) # add mod back when flag is set _add_constant(-k, aug) # re-expose the branch in msb ... X(msb[0]) CNOT(wires=msb + flag) # ... to reset flag to 0 X(msb[0]) _add_constant(k, aug) # aug <- (x + k) mod mod, work wires restored add_decomps(Adder, _adder_decomposition, _adder_arithmetic_decomposition)