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

# Copyright 2026 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 implementation of the Incrementer template."""

from pennylane import capture, compiler, math
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.ops import CNOT, MultiControlledX, PauliX, X, adjoint, change_op_basis, cond
from pennylane.ops.op_math.adjoint2 import _adjoint_abstract
from pennylane.ops.op_math.change_op_basis2 import _change_op_basis_abstract
from pennylane.ops.op_math.controlled2 import flip_zero_control as flip_zero_control2
from pennylane.typing import Bool, Wire
from pennylane.wires import Wires, WiresLike, is_abstract_qubit

from ..multix import MultiX
from ..qrom import _interleave_controls
from .temporary_and import TemporaryAND


[docs] class Incrementer(Operator2): r""" Increment the input ``wires`` by one, using zeroed ``work_wires``. Args: wires (Wires): The wires that the incrementer acts on. work_wires (Wires): The auxiliary wires that the incrementer may use in its decomposition. **Example** Here we add :math:`2 + 1` to get :math:`3`, using the `Incrementer`. .. code-block:: python from pennylane import qnode, device, sample, BasisEmbedding, Incrementer import numpy as np wires = [0, 1, 2] work_wires = [3, 4] init_state = [0, 1, 0] # binary representation of 2 dev = device("default.qubit", wires=wires + work_wires) @qnode(dev, shots=1) def increment(wires, init_state, work_wires=None): BasisEmbedding(init_state, wires) Incrementer(wires, work_wires) return sample() result = increment(wires, init_state, work_wires)[0] >>> result[:len(wires)] array([0, 1, 1]) The result incremented the binary value in the non-work wires by 1: :math:`(010)_2 + (001)_2 = (011)_2`. .. details:: :title: Available decompositions .. decomposition-table:: qp.Incrementer :symbols: :math:`n \geq 2` ``wires`` and :math:`w` ``work_wires`` :example: :math:`n=4` .. decomposition-rule:: incrementer_elbow_ladder :image: /_static/decomposition_thumbnails/incrementer_elbow_ladder.svg :requires: :math:`w \geq n - 1` work wires :class:`~.TemporaryAND` | :math:`n - 2` | 2 :class:`Adjoint(TemporaryAND) <.TemporaryAND>` | :math:`n - 2` | 2 :class:`~.CNOT` | :math:`n - 1` | 3 :class:`~.X` | :math:`1` | 1 .. decomposition-rule:: incrementer_multicontrolledx :image: /_static/decomposition_thumbnails/incrementer_multi_controlled_x.svg :requires: :math:`w < n - 1` work wires :class:`~.MultiControlledX` with :math:`1, \dots, n-1` controls | :math:`n-1` | 3 :class:`~.X` | :math:`1` | 1 .. decomposition-rule:: adjoint_incrementer_bit_flips :image: /_static/decomposition_thumbnails/incrementer_adjoint.svg :region: adjoint :class:`~.MultiX` on :math:`n` wires | :math:`2` :class:`~.Incrementer` | :math:`1` .. decomposition-rule:: flip_zero_ctrl_values(ctrl_incrementer_elbow_ladder) :image: /_static/decomposition_thumbnails/incrementer_controlled.svg :region: controlled :requires: :math:`n + c - 1` work wires in total, from ``work_wires`` and the work wires of the controlled operator :where: :math:`c` is the number of control wires, each control wire with control value :math:`0` adds two :class:`~.PauliX` gates, not included in the counts, and the circuit shows :math:`c = 2` :class:`~.TemporaryAND` | :math:`n + c - 2` :class:`Adjoint(TemporaryAND) <.TemporaryAND>` | :math:`n + c - 2` :class:`~.CNOT` | :math:`n` .. details:: :title: Decomposition :href: decomposition We use a left elbow ladder together with a :class:`~.CNOT` + right :class:`~.TemporaryAND` uncompute ladder. This is a manually reduced decomposition of the standard incrementer via :class:`~.MultiControlledX` gates if work wires are available. Generic decomposition: .. code-block:: 0: ─╭X────────────────┤ 1: ─├●─╭X─────────────┤ 2: ─├●─├●─╭X──────────┤ 3: ─├●─├●─├●─╭X───────┤ 4: ─├●─├●─├●─├●─╭X────┤ 5: ─╰●─╰●─╰●─╰●─╰●──X─┤ Decompose all MCX gates into elbows and CNOTs: .. code-block:: 0 : ─────────────╭X──────────────────────────────────────────────────────────────────────────┤ 1 : ──────────╭●─│───●╮──────────────────────╭X──────────────────────────────────────────────┤ 2 : ───────╭●─│──│────│──●╮───────────────╭●─│───●╮───────────────╭X─────────────────────────┤ 3 : ────╭●─│──│──│────│───│──●╮────────╭●─│──│────│──●╮────────╭●─│───●╮────────╭X───────────┤ 4 : ─╭●─│──│──│──│────│───│───│──●╮─╭●─│──│──│────│───│──●╮─╭●─│──│────│──●╮─╭●─│───●╮─╭X────┤ 5 : ─├●─│──│──│──│────│───│───│──●┤─├●─│──│──│────│───│──●┤─├●─│──│────│──●┤─├●─│───●┤─╰●──X─┤ aux0: ─│──│──├⊕─├●─│───●┤──⊕┤───│───│─│──│──│──│────│───│───│─│──│──│────│───│─│──│────│───────┤ aux1: ─│──├⊕─╰●─│──│────│──●╯──⊕┤───│─│──├⊕─├●─│───●┤──⊕┤───│─│──│──│────│───│─│──│────│───────┤ aux2: ─╰⊕─╰●────│──│────│──────●╯──⊕╯─╰⊕─╰●─│──│────│──●╯──⊕╯─╰⊕─├●─│───●┤──⊕╯─│──│────│───────┤ aux3: ──────────╰⊕─╰●──⊕╯───────────────────╰⊕─╰●──⊕╯────────────╰⊕─╰●──⊕╯─────╰⊕─╰●──⊕╯───────┤ Cancel neighbouring right and left elbows (moving some work wire usage around in the process) .. code-block:: 0 : ─────────────╭X───────────────────────────────┤ 1 : ──────────╭●─│───●╮─╭X────────────────────────┤ 2 : ───────╭●─│──│────│─│──●╮──╭X─────────────────┤ 3 : ────╭●─│──│──│────│─│───│──│──●╮─╭X───────────┤ 4 : ─╭●─│──│──│──│────│─│───│──│───│─│───●╮─╭X────┤ 5 : ─├●─│──│──│──│────│─│───│──│───│─│───●┤─╰●──X─┤ aux0: ─│──│──├⊕─├●─│───●┤─╰●─⊕┤──│───│─│────│───────┤ aux1: ─│──├⊕─╰●─│──│────│────●╯──╰●─⊕┤─│────│───────┤ aux2: ─╰⊕─╰●────│──│────│───────────●╯─╰●──⊕╯───────┤ aux3: ──────────╰⊕─╰●──⊕╯───────────────────────────┤ We see a leading ladder of left elbows and a backwards ladder of CNOT+right elbow pairs. This circuit is derived, e.g., in `Gidney's blog <https://algassert.com/circuits/2015/06/12/Constructing-Large-Increment-Gates.html>`__, see "Incrementer from n-2 Zeroed bits". The ``Controlled(Incrementer)`` decomposition provided is a similar decomposition to the default, except that there is no ``X`` gate at the end of the circuit, and the ``MultiControlledX`` gates have one additional control. It is therefore 'cut-off', and we can follow the same logic as the default decomposition, excluding only the trivial X which is not decomposed into elbows and CNOTs or cancelled in any case. Generic decomposition: .. code-block:: 0: ─╭X────────────────┤ 1: ─├●─╭X─────────────┤ 2: ─├●─├●─╭X──────────┤ 3: ─├●─├●─├●─╭X───────┤ 4: ─├●─├●─├●─├●─╭X────┤ 5: ─├●─├●─├●─├●─├●─╭X─┤ 6: ─╰●─╰●─╰●─╰●─╰●─╰●─┤ Optimized controlled decomposition (controlled on wire 12): .. code-block:: 0 : ────────────────╭X────────────────────────────────────┤ 1 : ─────────────╭●─│───●╮─╭X─────────────────────────────┤ 2 : ──────────╭●─│──│────│─│───●╮─╭X──────────────────────┤ 3 : ───────╭●─│──│──│────│─│────│─│───●╮─╭X───────────────┤ 4 : ────╭●─│──│──│──│────│─│────│─│────│─│───●╮─╭X────────┤ 5 : ─╭●─│──│──│──│──│────│─│────│─│────│─│────│─│───●╮─╭X─┤ aux0: ─├⊕─├●─│──│──│──│────│─│────│─│────│─│───●┤─╰●──⊕┤─│──┤ aux1: ─│──╰⊕─├●─│──│──│────│─│────│─│───●┤─╰●──⊕╯──────│─│──┤ aux2: ─│─────╰⊕─├●─│──│────│─│───●┤─╰●──⊕╯─────────────│─│──┤ aux3: ─│────────╰⊕─├●─│───●┤─╰●──⊕╯────────────────────│─│──┤ aux4: ─│───────────╰⊕─╰●──⊕╯───────────────────────────│─│──┤ 12 : ─╰●─────────────────────────────────────────────●╯─╰●─┤ """ wire_argnames = ("wires", "work_wires") arg_specs = {"wires": Wire[-1], "work_wires": Wire[-1]} def __init__(self, wires: WiresLike, work_wires: WiresLike | None = None): work_wires = Wires([] if work_wires is None else work_wires) super().__init__(wires, work_wires=work_wires) @property def increment_wires(self): """The wires whose encoded integer is incremented, excluding ``work_wires``.""" return self.arguments["wires"] @property def wires(self): """All wires involved in the operation.""" return self.increment_wires + self.work_wires
def _core_incrementer_resources(num_wires): """Resources of the incrementer's core MCX ladder, as a function of the number of wires in the ladder (excluding work wires).""" resources = {X: 1} if num_wires > 1: # Forward ladder resources[TemporaryAND] = num_wires - 2 # Backward ladder and trailing CNOT resources[CNOT] = num_wires - 2 + 1 resources[_adjoint_abstract(TemporaryAND)] = num_wires - 2 return resources def _incrementer_resources(wires, work_wires=None): # pylint: disable=unused-argument return _core_incrementer_resources(len(wires)) def _has_dynamic_qubits(wires): """Whether any wire is a dynamically-allocated ``AbstractQubit`` handle (e.g. from ``qp.allocate``), which cannot be stacked into a numeric array for the dynamic-slicing ladder construction below. This forces the fallback decomposition; remove once dynamic-wire indexing is supported (shortcut.com/story/129521).""" return any(is_abstract_qubit(w) for w in wires) def _work_wire_condition(wires, work_wires): return (len(work_wires) + 1) >= len(wires) and not _has_dynamic_qubits(wires) def _ctrl_work_wire_condition(base, control_wires, work_wires, **_): num_wires = len(base.increment_wires) + len(control_wires) num_work_wires = len(base.work_wires) + len(work_wires) return (num_work_wires + 1) >= num_wires and not _has_dynamic_qubits(base.increment_wires) def _work_wire_inverse_condition(wires, work_wires): return not _work_wire_condition(wires, work_wires) def _decompose_mcxs(wires, work_wires, control_wires=None): if control_wires is None: wires = wires[::-1] num_controls = 0 else: if compiler.active() or capture.enabled() and control_wires.shape[0] > 0: wires = math.concatenate([wires, math.atleast_1d(control_wires)]) else: wires = wires + control_wires wires = wires[::-1] num_controls = len(control_wires) def _increment(): # Construct the wires on which the ladder will act. interleaved = _interleave_controls(wires, work_wires) triples = [interleaved[2 * i : 2 * i + 3] for i in range(len(wires) - 2)] if compiler.active() or capture.enabled(): interleaved = math.array(interleaved, like="jax") triples = math.array(triples, like="jax") # Forward ladder @for_loop(len(wires) - 2) def forward_ladder(k): TemporaryAND(triples[k]) forward_ladder() # pylint: disable=no-value-for-parameter # The backward ladder applies a CNOT in all iterations except for k < num_controls - 2 num_ladder_iters = len(wires) - 2 num_ladder_cnots = num_ladder_iters - max(num_controls - 2, 0) cnot_prob = num_ladder_cnots / num_ladder_iters if num_ladder_iters > 0 else 0.0 # Backward ladder @for_loop(len(wires) - 3, -1, -1) def backward_adder(k): cond(k >= num_controls - 2, hint(CNOT, {"branch-prob": cnot_prob}))( [interleaved[2 * k + 2], interleaved[2 * k + 3]] ) adjoint(TemporaryAND)(triples[k]) backward_adder() # pylint: disable=no-value-for-parameter if num_controls <= 1: # Trailing CNOT CNOT(wires[:2]) cond(len(wires) > 1, _increment)() def _incrementer_fallback_resources(wires, work_wires): num_wires = len(wires) num_work_wires = len(work_wires) resources = {} for i in range(num_wires, 1, -1): resources[MultiControlledX(Wire[i], work_wires=Wire[num_work_wires])] = 1 resources[PauliX] = 1 return resources @register_condition(_work_wire_inverse_condition) @register_resources(_incrementer_fallback_resources, name="incrementer_multicontrolledx") def _incrementer_multicontrolledx(wires, work_wires, **_): # This loop is intentionally a plain Python loop rather than a ``qp.for_loop``: each # iteration emits a ``MultiControlledX`` with a different number of controls (``i - 1``), # so the loop body has no fixed structure and cannot be traced as a dynamic loop. Keeping # it unrolled lets this fallback run under program capture without any extra gating. num_wires = len(wires) for i in range(num_wires, 1, -1): MultiControlledX( wires[num_wires - i :][::-1], [1] * (i - 1), work_wires=work_wires, ) X(wires[-1]) @register_condition(_work_wire_condition) @register_resources(_incrementer_resources, name="incrementer_elbow_ladder") def _incrementer_elbow_ladder(wires, work_wires, **_): if compiler.active() or capture.enabled(): wires = math.array(wires, like="jax") _decompose_mcxs(wires, work_wires) X(wires[-1]) def _controlled_incrementer_resources(base, control_wires, **_): num_control_wires = len(control_wires) resources = _core_incrementer_resources(len(base.increment_wires) + num_control_wires) resources[X] = 0 if num_control_wires > 2: resources[CNOT] -= num_control_wires - 2 resources[CNOT] -= num_control_wires > 1 return resources @register_condition(_ctrl_work_wire_condition) @register_resources(_controlled_incrementer_resources, name="ctrl_incrementer_elbow_ladder") def _ctrl_incrementer_elbow_ladder(base, control_wires, work_wires, **_): wires = base.increment_wires base_work_wires = base.work_wires if compiler.active() or capture.enabled(): wires, work_wires, control_wires = ( math.array(wires, like="jax"), math.array(work_wires, like="jax"), math.array(control_wires, like="jax"), ) base_work_wires = math.array(base_work_wires, like="jax") if base_work_wires.shape[0] > 0 and work_wires.shape[0] > 0: # Both arrays are already 1D at this point, guaranteed by the ``shape[0]`` check work_wires = math.concatenate([base_work_wires, work_wires]) elif base_work_wires.shape[0] > 0 and work_wires.shape[0] == 0: work_wires = base_work_wires else: work_wires = base_work_wires + Wires(work_wires) _decompose_mcxs(wires, work_wires, control_wires) def _adjoint_incrementer_resources(base): num_wires = len(base.increment_wires) multix = MultiX(Bool[num_wires], Wire[num_wires]) incrementer = Incrementer(Wire[num_wires], work_wires=Wire[len(base.work_wires)]) return {_change_op_basis_abstract(multix, incrementer, multix): 1} @register_resources(_adjoint_incrementer_resources, name="adjoint_incrementer_bit_flips") def _adjoint_incrementer_bit_flips(base): """Decompose a decrement into an increment conjugated by bit flips, ``x - 1 = ~(~x + 1)``.""" wires = base.increment_wires ones = [1] * len(wires) change_op_basis( MultiX(ones, wires), Incrementer(wires, work_wires=base.work_wires), MultiX(ones, wires), ) add_decomps(Incrementer, _incrementer_elbow_ladder, _incrementer_multicontrolledx) add_decomps("C(Incrementer)", flip_zero_control2(_ctrl_incrementer_elbow_ladder)) add_decomps("Adjoint(Incrementer)", _adjoint_incrementer_bit_flips)