Source code for pennylane.ops.op_math.decompositions.controlled_decompositions

# 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 defines functions to decompose controlled operations."""

from functools import partial
from typing import Literal

import numpy as np

import pennylane as qp
from pennylane import capture, compiler, control_flow, math, ops
from pennylane.core import queuing
from pennylane.core.apply import apply
from pennylane.core.operator import Operation, Operator
from pennylane.decomposition import register_condition, register_resources
from pennylane.ops.op_math.decompositions.unitary_decompositions import _qubit_unitary_two_qubit
from pennylane.typing import Complex, Float, Wire
from pennylane.wires import Wires, concatenate_wires


[docs] def ctrl_decomp_bisect(target_operation: Operator, control_wires: Wires): """Decompose the controlled version of a target single-qubit operation Not backpropagation compatible (as currently implemented). Use only with numpy. Automatically selects the best algorithm based on the matrix (uses specialized more efficient algorithms if the matrix has a certain form, otherwise falls back to the general algorithm). These algorithms are defined in sections 3.1 and 3.2 of `Vale et al. (2023) <https://arxiv.org/abs/2302.06377>`_. .. warning:: This method will add a global phase for target operations that do not belong to the SU(2) group. Args: target_operation (~.operation.Operator): the target operation to decompose control_wires (~.wires.Wires): the control wires of the operation Returns: list[Operation]: the decomposed operations Raises: ValueError: if ``target_operation`` is not a single-qubit operation **Example:** >>> from pennylane.ops.op_math import ctrl_decomp_bisect >>> op = qp.T(0) # uses OD algorithm >>> print(qp.draw(ctrl_decomp_bisect, wire_order=(0,1,2,3,4,5), show_matrices=False)(op, (1,2,3,4,5))) 0: ─╭X──U(M0)─╭X──U(M0)†─╭X──U(M0)─╭X──U(M0)†─╭GlobalPhase(-0.39)─┤ 1: ─├●────────│──────────├●────────│──────────├●──────────────────┤ 2: ─├●────────│──────────├●────────│──────────├●──────────────────┤ 3: ─╰●────────│──────────╰●────────│──────────├●──────────────────┤ 4: ───────────├●───────────────────├●─────────├●──────────────────┤ 5: ───────────╰●───────────────────╰●─────────╰●──────────────────┤ >>> op = qp.QubitUnitary([[0,1j],[1j,0]], 0) # uses MD algorithm >>> print(qp.draw(ctrl_decomp_bisect, wire_order=(0,1,2,3,4,5), show_matrices=False)(op, (1,2,3,4,5))) 0: ──H─╭X──U(M0)─╭X──U(M0)†─╭X──U(M0)─╭X──U(M0)†──H─┤ 1: ────├●────────│──────────├●────────│─────────────┤ 2: ────├●────────│──────────├●────────│─────────────┤ 3: ────╰●────────│──────────╰●────────│─────────────┤ 4: ──────────────├●───────────────────├●────────────┤ 5: ──────────────╰●───────────────────╰●────────────┤ >>> op = qp.Hadamard(0) # uses general algorithm >>> print(qp.draw(ctrl_decomp_bisect, wire_order=(0,1,2,3,4,5), show_matrices=False)(op, (1,2,3,4,5))) 0: ──U(M0)─╭X──U(M1)†──U(M2)─╭X──U(M2)†─╭X──U(M2)─╭X──U(M2)†─╭X──U(M1)─╭X──U(M0)† ··· 1: ────────│─────────────────│──────────├●────────│──────────├●────────│───────── ··· 2: ────────│─────────────────│──────────├●────────│──────────├●────────│───────── ··· 3: ────────│─────────────────│──────────╰●────────│──────────╰●────────│───────── ··· 4: ────────├●────────────────├●───────────────────├●───────────────────├●──────── ··· 5: ────────╰●────────────────╰●───────────────────╰●───────────────────╰●──────── ··· <BLANKLINE> 0: ··· ─╭GlobalPhase(-1.57)─┤ 1: ··· ─├●──────────────────┤ 2: ··· ─├●──────────────────┤ 3: ··· ─├●──────────────────┤ 4: ··· ─├●──────────────────┤ 5: ··· ─╰●──────────────────┤ """ if len(target_operation.wires) > 1: raise ValueError( "The target operation must be a single-qubit operation, instead " f"got {target_operation}." ) with queuing.AnnotatedQueue() as q: _controlled_unitary_bisect( target_operation.matrix(), control_wires + target_operation.wires, control_values=[True] * len(control_wires), ) # If there is an active queuing context, queue the decomposition so that expand works if queuing.QueuingManager.recording(): for op in q.queue: # pragma: no cover apply(op) return q.queue
[docs] def ctrl_decomp_zyz( target_operation: Operator, control_wires: Wires, work_wires: Wires | None = None, work_wire_type: str | None = "borrowed", ) -> list[Operation]: """Decompose the controlled version of a target single-qubit operation This function decomposes both single and multiple controlled single-qubit target operations using the decomposition defined in Lemma 4.3 and Lemma 5.1 for single ``controlled_wires``, and Lemma 7.9 for multiple ``controlled_wires`` from `Barenco et al. (1995) <https://arxiv.org/abs/quant-ph/9503016>`_. Args: target_operation (~.operation.Operator): the target operation or matrix to decompose control_wires (~.wires.Wires): the control wires of the operation. work_wires (~.wires.Wires): the work wires available for this decomposition work_wire_type (str): the type of work wires, either "zeroed" or "borrowed". Returns: list[Operation]: the decomposed operations Raises: ValueError: if ``target_operation`` is not a single-qubit operation **Example** We can create a controlled operation using ``qp.ctrl``, or by creating the decomposed controlled version using ``qp.ctrl_decomp_zyz``. .. code-block:: python dev = qp.device("default.qubit", wires=2) @qp.qnode(dev) def expected_circuit(op): qp.Hadamard(wires=0) qp.ctrl(op, [0]) return qp.probs() @qp.qnode(dev) def decomp_circuit(op): qp.Hadamard(wires=0) qp.ops.ctrl_decomp_zyz(op, [0]) return qp.probs() Measurements on both circuits will give us the same results: >>> op = qp.RX(0.123, wires=1) >>> expected_circuit(op) array([0.5 , 0. , 0.498..., 0.001...]) >>> decomp_circuit(op) array([0.5 , 0. , 0.498..., 0.001...]) """ if len(target_operation.wires) != 1: raise ValueError( "The target operation must be a single-qubit operation, instead " f"got {target_operation.__class__.__name__}." ) control_wires = Wires(control_wires) target_wire = target_operation.wires *rot_angles, global_phase = qp.single_qubit_zyz_angles(target_operation) with queuing.AnnotatedQueue() as q: all_wires = control_wires + target_wire if len(control_wires) > 1: _multi_control_zyz( *rot_angles, wires=all_wires, work_wires=work_wires, work_wire_type=work_wire_type ) else: _single_control_zyz(*rot_angles, wires=all_wires) ops.cond(_not_zero(global_phase), _ctrl_global_phase)( global_phase, control_wires, work_wires, work_wire_type, ) # If there is an active queuing context, queue the decomposition so that expand works if queuing.QueuingManager.recording(): for op in q.queue: # pragma: no cover apply(op) return q.queue
############################################## # ControlledQubitUnitary Decomposition Rules # ############################################## def _ctrl_decomp_bisect_condition(U, wires, *_, **__): num_target_wires = int(qp.math.log2(qp.math.shape(U)[-1])) num_control_wires = len(wires) - num_target_wires # This decomposition rule is only applicable when the target is a single-qubit unitary. # Also, it is not helpful when there's only a single control wire. return num_target_wires == 1 and num_control_wires > 1 # pylint: disable-next=unused-argument def _controlled_unitary_bisect_resources(U, wires, control_values, *_, **__): num_ctrl_wires = len(wires) - 1 len_k1 = (num_ctrl_wires + 1) // 2 len_k2 = num_ctrl_wires - len_k1 # this is a heuristic overestimate based on the resource requirement of the general case. mcx_k1 = ops.MultiControlledX(Wire[len_k1 + 1], work_wires=Wire[len_k2]) mcx_k2 = ops.MultiControlledX(Wire[len_k2 + 1], work_wires=Wire[len_k1]) mcx_reps = {mcx_k1: 6} if len_k1 == len_k2 else {mcx_k2: 4, mcx_k1: 2} return { ops.QubitUnitary(Complex[2, 2], wires=Wire[1]): 4, qp.adjoint(ops.QubitUnitary(Complex[2, 2], wires=Wire[1])): 4, # we only need Hadamard for the main diagonal case (see _ctrl_decomp_bisect_md), # but it still needs to be accounted for. ops.Hadamard: 2, ops.ctrl(ops.GlobalPhase(Float), Wire[num_ctrl_wires], work_wires=Wire[1]): 1, qp.X: num_ctrl_wires, # assume half the control values are 0s } | mcx_reps # Resources are not exact because rotations might be skipped for zero angles @register_condition(_ctrl_decomp_bisect_condition) @register_resources(_controlled_unitary_bisect_resources, exact=False, name="bisect") def _controlled_unitary_bisect(U, wires, control_values, *_, **__): """The decomposition rule for ControlledQubitUnitary from `Vale et al. (2023) <https://arxiv.org/abs/2302.06377>`_.""" if compiler.active() or capture.enabled(): wires = math.array(wires, like="jax") control_values = math.array(control_values, like="jax") @qp.for_loop(len(control_values)) def _x_flips(i): qp.cond(qp.math.logical_not(control_values[i]), qp.X)(wires[i]) su2_U, phase = math.convert_to_su2(U) imag_U = math.imag(su2_U) _x_flips() # pylint: disable=no-value-for-parameter real_main_diagonal = math.allclose(imag_U[0, 0], 0) & math.allclose(imag_U[1, 1], 0) ops.cond( math.allclose(imag_U[1, 0], 0) & math.allclose(imag_U[0, 1], 0), # Real off-diagonal specialized algorithm - 16n+O(1) CNOTs _ctrl_decomp_bisect_od, # General algorithm - 20n+O(1) CNOTs _ctrl_decomp_bisect_general, # Real main-diagonal specialized algorithm - 16n+O(1) CNOTs elifs=[(real_main_diagonal, _ctrl_decomp_bisect_md)], )(su2_U, wires) fn = partial(_ctrl_global_phase, work_wire_type="borrowed") ops.cond(_not_zero(phase), fn)(phase, wires[:-1], wires[-1]) _x_flips() # pylint: disable=no-value-for-parameter def _single_ctrl_decomp_zyz_condition(U, wires, *_, **__): num_target_wires = int(qp.math.log2(qp.math.shape(U)[-1])) num_control_wires = len(wires) - num_target_wires return num_target_wires == 1 and num_control_wires == 1 # pylint: disable-next=unused-argument def _controlled_unitary_single_control_zyz_resources(U, wires, **_): return { ops.RZ: 3, ops.RY: 2, ops.CNOT: 2, ops.ctrl(ops.GlobalPhase(Float), Wire[1]): 1, ops.X: len(wires) - 1, } # Resources are not exact because rotations might be skipped for zero angles @register_condition(_single_ctrl_decomp_zyz_condition) @register_resources( _controlled_unitary_single_control_zyz_resources, exact=False, name="single_control_zyz" ) # pylint: disable-next=unused-argument def _controlled_unitary_single_control_zyz(U, wires, control_values, work_wires, **_): """The decomposition rule for ControlledQubitUnitary from Lemma 5.1 of https://arxiv.org/pdf/quant-ph/9503016""" if capture.enabled() or compiler.active(): wires = qp.math.array(wires, like="jax") control_values = math.array(control_values, like="jax") @qp.for_loop(len(control_values)) def _x_flips(i): qp.cond(qp.math.logical_not(control_values[i]), qp.X)(wires[i]) phi, theta, omega, phase = math.decomposition.zyz_rotation_angles(U) _x_flips() # pylint: disable=no-value-for-parameter _single_control_zyz(phi, theta, omega, wires=wires) ops.cond(_not_zero(phase), _ctrl_global_phase)(phase, wires[:-1]) _x_flips() # pylint: disable=no-value-for-parameter def _multi_ctrl_decomp_zyz_condition(U, wires, *_, **__): num_target_wires = int(qp.math.log2(qp.math.shape(U)[-1])) num_control_wires = len(wires) - num_target_wires return num_target_wires == 1 and num_control_wires > 1 def _controlled_unitary_multi_control_zyz_resources( U, wires, control_values, work_wires, work_wire_type, **_ # pylint: disable=unused-argument ): num_ctrl_wires = len(wires) - 1 num_work_wires = len(work_wires) return { ops.CRZ: 3, ops.CRY: 2, ops.MultiControlledX( Wire[num_ctrl_wires], work_wires=Wire[num_work_wires], work_wire_type=work_wire_type, ): 2, ops.ctrl(ops.GlobalPhase(Float), Wire[num_ctrl_wires], work_wires=Wire[1]): 1, ops.X: num_ctrl_wires, } @register_condition(_multi_ctrl_decomp_zyz_condition) # Resources are not exact because rotations might be skipped for zero angle(s) @register_resources( _controlled_unitary_multi_control_zyz_resources, exact=False, name="multi_control_zyz" ) def _controlled_unitary_multi_control_zyz( U, wires, control_values, work_wires, work_wire_type, **_ ): """The decomposition rule for ControlledQubitUnitary from Lemma 7.9 of https://arxiv.org/pdf/quant-ph/9503016""" if compiler.active() or capture.enabled(): wires = math.array(wires, like="jax") control_values = math.array(control_values, like="jax") @qp.for_loop(len(control_values)) def _x_flips(i): qp.cond(qp.math.logical_not(control_values[i]), qp.X)(wires[i]) phi, theta, omega, phase = math.decomposition.zyz_rotation_angles(U) _x_flips() # pylint: disable=no-value-for-parameter _multi_control_zyz( phi, theta, omega, wires=wires, work_wires=work_wires, work_wire_type=work_wire_type, ) fn = partial(_ctrl_global_phase, work_wire_type="borrowed") ops.cond(_not_zero(phase), fn)(phase, wires[:-1], wires[-1]) _x_flips() # pylint: disable=no-value-for-parameter def _controlled_unitary_two_qubit_resources( U, wires, control_values, work_wires, work_wire_type, **_ # pylint: disable=unused-argument ): num_target_wires = int(qp.math.log2(qp.math.shape(U)[-1])) num_control_wires = len(wires) - num_target_wires num_work_wires = len(work_wires) base_resources = _qubit_unitary_two_qubit.compute_resources(num_wires=num_target_wires) gate_counts = { qp.ctrl( base_op_rep, Wire[num_control_wires], work_wires=Wire[num_work_wires], work_wire_type=work_wire_type, ): count for base_op_rep, count in base_resources.gate_counts.items() } # The impl applies X gates in pairs to flip any zero control values. With abstract inputs the # concrete control values (and thus the exact number of X gates) are unknown, so we declare a # heuristic of half the control wires using zero as their control values. This equates to # X_count = (num_control_wires // 2) * 2 ~= num_control_wires. This keeps X in the estimated # gate set (required even for exact=False rules) while the actual count is allowed to be lower. gate_counts[ops.X] = num_control_wires return gate_counts # Resources are not exact because rotations might be skipped for zero angle(s) @register_condition(lambda U, *_, **__: qp.math.ceil_log2(qp.math.shape(U)[0]) == 2) @register_resources(_controlled_unitary_two_qubit_resources, exact=False, name="two_qubit") def _controlled_unitary_two_qubit(U, wires, control_values, work_wires, work_wire_type, **_): """A controlled two-qubit unitary is decomposed by applying ctrl to the base decomposition.""" if compiler.active() or capture.enabled(): wires = math.array(wires, like="jax") control_values = math.array(control_values, like="jax") @qp.for_loop(len(control_values)) def _x_flips(i): qp.cond(qp.math.logical_not(control_values[i]), qp.X)(wires[i]) _x_flips() # pylint: disable=no-value-for-parameter ops.ctrl( _qubit_unitary_two_qubit._impl, # pylint: disable=protected-access control=wires[:-2], work_wires=work_wires, work_wire_type=work_wire_type, )(U, wires=wires[-2:]) _x_flips() # pylint: disable=no-value-for-parameter ######################################## # MultiControlledX Decomposition Rules # ######################################## def _wrap_mcx_rule_w_alloc(base_rule, num_work_wires, work_wire_type, name=""): """Given a MCX decomposition rule that takes explicit work wires, populate the same decomposition rule that uses dynamic work wire allocation instead.""" def _resource_fn(wires, control_values, *_, **__): return base_rule._compute_resources( # pylint: disable=protected-access wires, control_values, Wire[num_work_wires], work_wire_type=work_wire_type, ) def _condition_fn(wires, control_values, work_wires, work_wire_type): # The allocation-based rules are only considered if the operator does not # come with explicitly specified work wires. We've made the decision last # year that passing work wires to an operator is like explicitly saying # "use these work wires in the operator's decomposition" return len(work_wires) == 0 and base_rule.is_applicable( wires, control_values, Wire[num_work_wires], work_wire_type=work_wire_type, ) @register_condition(_condition_fn) @register_resources( _resource_fn, work_wires={work_wire_type: num_work_wires}, exact=base_rule.exact_resources, name=name or f"use_allocation({base_rule.name})", ) def _impl(wires, control_values, *_, **__): state = "zero" if work_wire_type == "zeroed" else "any" with qp.allocation.allocate(num_work_wires, state, restored=True) as work_wires: # pylint: disable-next=protected-access base_rule._impl(wires, control_values, work_wires, work_wire_type=work_wire_type) return _impl def _mcx_to_cnot_or_toffoli_resources(wires, *_, **__): # The PauliX may be required to flip any non-zero controlled bits # Each non-zero control value requires 2 PauliX gates to flip, but we count # only one for each control wire as an average case estimate. if len(wires) - 1 == 1: return {qp.CNOT: 1, qp.X: 1} return {qp.Toffoli: 1, qp.X: 2} @register_condition(lambda wires, *_, **__: len(wires) <= 3) @register_resources(_mcx_to_cnot_or_toffoli_resources, exact=False, name="to_cnot_or_toffoli") def _mcx_to_cnot_or_toffoli(wires, control_values, *_, **__): """A decomposition rule that decomposes an MCX to a CNOT or Toffoli""" if compiler.active() or capture.enabled(): wires = math.array(wires, like="jax") control_values = math.array(control_values, like="jax") # Case 1: Decompose to single CNOT if len(wires) == 2: qp.CNOT(wires=wires) qp.cond(math.logical_not(control_values[0]), qp.X)(wires[1]) return @qp.for_loop(0, len(wires) - 1) def _x_flips(i): qp.cond(math.logical_not(control_values[i]), qp.X)(wires[i]) _x_flips() # pylint: disable=no-value-for-parameter qp.Toffoli(wires=wires) _x_flips() # pylint: disable=no-value-for-parameter def _mcx_two_controls_elbows_resources(wires, *_, **__): num_ctrl_wires = len(wires) - 1 return {qp.Elbow: 1, qp.CNOT: 1, qp.adjoint(qp.Elbow(Wire[3])): 1, qp.X: num_ctrl_wires} # pylint: disable-next=unused-argument def _2cx_elbow_explicit_condition(wires, control_values, work_wires, work_wire_type="borrowed"): num_control_wires = len(wires) - 1 return len(work_wires) >= 1 and num_control_wires == 2 and work_wire_type == "zeroed" @register_condition(_2cx_elbow_explicit_condition) @register_resources(_mcx_two_controls_elbows_resources, exact=False, name="two_controls_elbows") def _mcx_two_controls_elbows(wires, control_values, work_wires, **_): """A decomposition rule for MCX that uses controlled Elbow.""" if compiler.active() or capture.enabled(): wires = math.array(wires, like="jax") control_values = math.array(control_values, like="jax") @qp.for_loop(len(control_values)) def _x_flips(i): qp.cond(qp.math.logical_not(control_values[i]), qp.X)(wires[i]) elbow_wires = [wires[0], wires[1], work_wires[0]] _x_flips() # pylint: disable=no-value-for-parameter qp.Elbow(elbow_wires) qp.CNOT([work_wires[0], wires[2]]) qp.adjoint(qp.Elbow)(elbow_wires) _x_flips() # pylint: disable=no-value-for-parameter # pylint: disable-next=unused-argument def _mcx_many_workers_condition(wires, control_values, work_wires, **_): num_control_wires = len(wires) - 1 num_work_wires = len(work_wires) return num_control_wires > 2 and num_work_wires >= num_control_wires - 2 # pylint: disable-next=unused-argument def _mcx_many_work_wires_resources(wires, control_values, work_wires, work_wire_type="borrowed"): num_control_wires = len(wires) - 1 num_used_work_wires = num_control_wires - 2 num_extra_work_wires = len(work_wires) - num_used_work_wires # The middle MCX retains the variable number of extra work wires. middle_toffoli = ops.MultiControlledX( Wire[3], work_wires=Wire[num_extra_work_wires], work_wire_type=work_wire_type, ) if work_wire_type == "borrowed": return { ops.Toffoli: 4 * num_used_work_wires - 1, middle_toffoli: 1, qp.X: num_control_wires, } return { qp.TemporaryAND: num_used_work_wires, qp.adjoint(qp.TemporaryAND(Wire[3])): num_used_work_wires, middle_toffoli: 1, qp.X: num_control_wires, } @register_condition(_mcx_many_workers_condition) @register_resources(_mcx_many_work_wires_resources, exact=False, name="many_work_wires") def _mcx_many_work_wires(wires, control_values, work_wires, work_wire_type="borrowed"): """Decomposes the multi-controlled PauliX gate using the approach in Lemma 7.2 of https://arxiv.org/abs/quant-ph/9503016, which requires a suitably large register of work wires""" # pylint: disable=no-value-for-parameter if compiler.active() or capture.enabled(): wires = math.array(wires, like="jax") work_wires = math.array(work_wires, like="jax") control_values = math.array(control_values, like="jax") @qp.for_loop(len(control_values)) def _x_flips(i): qp.cond(qp.math.logical_not(control_values[i]), qp.X)(wires[i]) target_wire, control_wires = wires[-1], wires[:-1] num_work_wires = len(control_wires) - 2 extra_work_wires = work_wires[num_work_wires:] work_wires = work_wires[:num_work_wires] if work_wire_type == "borrowed": up_gate = down_gate = ops.Toffoli else: down_gate = qp.TemporaryAND up_gate = ops.adjoint(qp.TemporaryAND) @control_flow.for_loop(1, len(work_wires), 1) def loop_up(i): up_gate(wires=[control_wires[i], work_wires[i], work_wires[i - 1]]) @control_flow.for_loop(num_work_wires - 1, 0, -1) def loop_down(i): down_gate(wires=[control_wires[i], work_wires[i], work_wires[i - 1]]) _x_flips() if work_wire_type == "borrowed": ops.Toffoli(wires=[control_wires[0], work_wires[0], target_wire]) loop_up() down_gate(wires=[control_wires[-1], control_wires[-2], work_wires[-1]]) loop_down() _wires = [control_wires[0], work_wires[0], target_wire] ops.MultiControlledX( _wires, work_wires=extra_work_wires, work_wire_type=work_wire_type, ) loop_up() up_gate(wires=[control_wires[-1], control_wires[-2], work_wires[-1]]) if work_wire_type == "borrowed": loop_down() _x_flips() # pylint: disable-next=unused-argument def _mcx_two_workers_condition(wires, control_values, work_wires, **_): num_ctrls = len(wires) - 1 num_work_wires = len(work_wires) return num_ctrls > 2 and (num_work_wires >= 2 or (num_work_wires == 1 and num_ctrls < 6)) # pylint: disable-next=unused-argument def _mcx_two_work_wires_resources(wires, control_values, work_wires, work_wire_type="borrowed"): num_control_wires = len(wires) - 1 is_small_mcx = num_control_wires < 6 n_adjoint_ladder = num_control_wires - 4 + is_small_mcx adjoint_toffoli = qp.adjoint(ops.Toffoli(Wire[3])) adjoint_x = qp.adjoint(ops.X(Wire[1])) if work_wire_type == "zeroed": n_ccx = 2 * num_control_wires - 3 n_temporary_ccx_pairs = 2 - is_small_mcx n_x = (n_ccx - 3 if is_small_mcx else n_ccx - 5) + num_control_wires return { ops.Toffoli: n_ccx - 2 * n_temporary_ccx_pairs - n_adjoint_ladder, adjoint_toffoli: n_adjoint_ladder, ops.X: n_x - n_adjoint_ladder, adjoint_x: n_adjoint_ladder, qp.TemporaryAND: n_temporary_ccx_pairs, qp.adjoint(qp.TemporaryAND(Wire[3])): n_temporary_ccx_pairs, } # Otherwise, we assume the work wires are borrowed n_ccx = 4 * num_control_wires - 8 n_x = (n_ccx - 4 if is_small_mcx else n_ccx - 8) + num_control_wires return { ops.Toffoli: n_ccx - 2 * n_adjoint_ladder, adjoint_toffoli: 2 * n_adjoint_ladder, ops.X: n_x - 2 * n_adjoint_ladder, adjoint_x: 2 * n_adjoint_ladder, } @register_condition(_mcx_two_workers_condition) @register_resources(_mcx_two_work_wires_resources, exact=False, name="two_work_wires") def _mcx_two_work_wires(wires, control_values, work_wires, work_wire_type="borrowed"): r""" Synthesise a multi-controlled X gate with :math:`k` controls using :math:`2` auxiliary qubits. It produces a circuit with :math:`2k-3` Toffoli gates and depth :math:`O(\log(k))` if using zeroed auxiliary qubits, and :math:`4k-8` Toffoli gates and depth :math:`O(\log(k))` if using borrowed auxiliary qubits as described in Sec. 5 of [1]. References: 1. Khattar and Gidney, Rise of conditionally clean ancillae for optimizing quantum circuits `arXiv:2407.17966 <https://arxiv.org/abs/2407.17966>`__ """ if compiler.active() or capture.enabled(): wires = math.array(wires, like="jax") control_values = math.array(control_values, like="jax") @qp.for_loop(len(control_values)) def _x_flips(i): qp.cond(qp.math.logical_not(control_values[i]), qp.X)(wires[i]) _x_flips() # pylint: disable=no-value-for-parameter # Unpack work wires for readability. There might just be one of them if it # is a "small" MCX (less than 6 controls) work0, *work1 = work_wires # First use the work wire to prepare the first two control wires as conditionally clean. left_elbow = ops.Toffoli if work_wire_type == "borrowed" else qp.TemporaryAND left_elbow([wires[0], wires[1], work0]) middle_ctrl_indices = _build_log_n_depth_ccx_ladder(wires[:-1]) # Apply the MCX in the middle. This is just a single Toffoli without work wires for "small" MCX if len(middle_ctrl_indices) == 1: ops.Toffoli([work0, wires[middle_ctrl_indices[0]], wires[-1]]) else: middle_wires = [wires[i] for i in middle_ctrl_indices] # No toggle detection needed for the inner MCX decomposition, even for borrowed work wires _mcx_one_worker_no_flips( [work0] + middle_wires + [wires[-1]], work_wires=work1, work_wire_type=work_wire_type, _skip_toggle_detection=True, ) # Uncompute the first ladder ops.adjoint(_build_log_n_depth_ccx_ladder)(wires[:-1]) right_elbow = ops.Toffoli if work_wire_type == "borrowed" else qp.adjoint(qp.TemporaryAND) right_elbow([wires[0], wires[1], work0]) if work_wire_type == "borrowed": # Perform toggle-detection if the work wire is borrowed middle_ctrl_indices = _build_log_n_depth_ccx_ladder(wires[:-1]) if len(middle_ctrl_indices) == 1: ops.Toffoli([work0, wires[middle_ctrl_indices[0]], wires[-1]]) else: middle_wires = [wires[i] for i in middle_ctrl_indices] _mcx_one_worker_no_flips( [work0] + middle_wires + [wires[-1]], work_wires=work1, work_wire_type=work_wire_type, _skip_toggle_detection=True, ) ops.adjoint(_build_log_n_depth_ccx_ladder)(wires[:-1]) _x_flips() # pylint: disable=no-value-for-parameter # pylint: disable-next=unused-argument def _mcx_one_worker_condition(wires, control_values, work_wires, **_): num_control_wires = len(wires) - 1 num_work_wires = len(work_wires) return num_control_wires > 2 and num_work_wires == 1 # pylint: disable-next=unused-argument def _mcx_one_work_wire_resources(wires, control_values, work_wires, work_wire_type="borrowed"): num_control_wires = len(wires) - 1 n_adjoint_ladder = num_control_wires - 3 adjoint_toffoli = qp.adjoint(ops.Toffoli(Wire[3])) adjoint_x = qp.adjoint(ops.X(Wire[1])) if work_wire_type == "zeroed": n_ccx = 2 * num_control_wires - 5 return { ops.Toffoli: n_ccx - n_adjoint_ladder, adjoint_toffoli: n_adjoint_ladder, qp.TemporaryAND: 1, qp.adjoint(qp.TemporaryAND(Wire[3])): 1, ops.X: n_ccx - 1 + num_control_wires - n_adjoint_ladder, adjoint_x: n_adjoint_ladder, } # Otherwise, we assume the work wire is borrowed n_ccx = 4 * num_control_wires - 8 return { ops.Toffoli: n_ccx - 2 * n_adjoint_ladder, adjoint_toffoli: 2 * n_adjoint_ladder, ops.X: n_ccx - 4 + num_control_wires - 2 * n_adjoint_ladder, adjoint_x: 2 * n_adjoint_ladder, } def _mcx_one_worker_no_flips(wires, work_wires, work_wire_type, _skip_toggle_detection=False): if work_wire_type == "zeroed": _skip_toggle_detection = True toffoli_type = qp.TemporaryAND if work_wire_type == "zeroed" else ops.Toffoli toffoli_type([wires[0], wires[1], work_wires[0]]) final_ctrl_index = _build_linear_depth_ladder(wires[:-1]) ops.Toffoli([work_wires[0], wires[final_ctrl_index], wires[-1]]) ops.adjoint(_build_linear_depth_ladder)(wires[:-1]) adj_toffoli_type = qp.adjoint(qp.TemporaryAND) if work_wire_type == "zeroed" else ops.Toffoli adj_toffoli_type([wires[0], wires[1], work_wires[0]]) if not _skip_toggle_detection: # Perform toggle-detection unless skipped explicitly. By default, toggle detection # is skipped for `work_wire_type="zeroed"` but not for `work_wire_type="borrowed"`. _build_linear_depth_ladder(wires[:-1]) ops.Toffoli([work_wires[0], wires[final_ctrl_index], wires[-1]]) ops.adjoint(_build_linear_depth_ladder)(wires[:-1]) @register_condition(_mcx_one_worker_condition) @register_resources(_mcx_one_work_wire_resources, exact=False, name="one_work_wire") def _mcx_one_work_wire(wires, control_values, work_wires, work_wire_type="zeroed"): r""" Synthesise a multi-controlled X gate with :math:`k` controls using :math:`1` auxiliary qubit. It produces a circuit with :math:`2k-3` Toffoli gates and depth :math:`O(k)` if the auxiliary is zeroed and :math:`4k-3` Toffoli gates and depth :math:`O(k)` if the auxiliary is borrowed as described in Sec. 5.1 of [1]. .. note:: The keyword argument ``_skip_toggle_detection`` is only supposed to be used when utilizing ``_mcx_one_worker`` as a subroutine within a decomposition rule, but not when using it as a decomposition rule itself. This is because ``_mcx_one_work_wire_resources`` does not support/take into account this keyword argument. References: 1. Khattar and Gidney, Rise of conditionally clean ancillae for optimizing quantum circuits `arXiv:2407.17966 <https://arxiv.org/abs/2407.17966>`__ """ if compiler.active() or capture.enabled(): wires = math.array(wires, like="jax") control_values = math.array(control_values, like="jax") @qp.for_loop(len(control_values)) def _x_flips(i): qp.cond(qp.math.logical_not(control_values[i]), qp.X)(wires[i]) _x_flips() # pylint: disable=no-value-for-parameter _mcx_one_worker_no_flips(wires, work_wires, work_wire_type) _x_flips() # pylint: disable=no-value-for-parameter def _mcx_no_work_wires_resources(wires, *_, **__): num_control_wires = len(wires) - 1 len_k1 = (num_control_wires + 1) // 2 len_k2 = num_control_wires - len_k1 mcx_k1 = ops.MultiControlledX(Wire[len_k1 + 1], work_wires=Wire[len_k2]) mcx_k2 = ops.MultiControlledX(Wire[len_k2 + 1], work_wires=Wire[len_k1]) mcx_reps = {mcx_k1: 4} if len_k1 == len_k2 else {mcx_k1: 2, mcx_k2: 2} return { ops.Hadamard: 2, ops.QubitUnitary(Complex[2, 2], wires=Wire[1]): 2, qp.adjoint(ops.QubitUnitary(Complex[2, 2], wires=Wire[1])): 2, ops.ctrl(ops.GlobalPhase(Float), Wire[num_control_wires]): 1, ops.X: num_control_wires, } | mcx_reps # pylint: disable-next=unused-argument def _mcx_no_worker_condition(wires, control_values, work_wires, **_): # With work wires present, one of the one-, two- or many-worker rules always applies, which # matches ``MultiControlledX.compute_decomposition``. Offering this rule as well pulls # ``C(GlobalPhase)`` and ``C(PhaseShift)`` with every number of controls into the # decomposition graph, and ``qjit(capture=True)`` traces and compiles all of them. return len(wires) > 3 and len(work_wires) == 0 @register_condition(_mcx_no_worker_condition) @register_resources(_mcx_no_work_wires_resources, exact=False, name="no_work_wires") def _mcx_no_work_wires(wires, control_values, *_, **__): """Use ctrl_decomp_bisect_md to decompose a multi-controlled X gate with no work wires.""" U = ops.RX.compute_matrix(np.pi) if compiler.active() or capture.enabled(): wires = math.array(wires, like="jax") control_values = math.array(control_values, like="jax") @qp.for_loop(len(control_values)) def _x_flips(i): qp.cond(qp.math.logical_not(control_values[i]), qp.X)(wires[i]) _x_flips() # pylint: disable=no-value-for-parameter _ctrl_decomp_bisect_md(U, wires) ops.ctrl(ops.GlobalPhase(-np.pi / 2), control=wires[:-1]) _x_flips() # pylint: disable=no-value-for-parameter #################### # Helper Functions # #################### def _not_zero(x): return math.logical_not(math.allclose(x, 0)) def _ctrl_decomp_bisect_general(U, wires): """Decompose the controlled version of a target single-qubit operation This function decomposes a controlled single-qubit target operation using the decomposition defined in section 3.2 of `Vale et al. (2023) <https://arxiv.org/abs/2302.06377>`_. Args: U (tensor): the target operation to decompose wires (WiresLike): the wires of the operation (control wires followed by the target wire) """ x_matrix = ops.X.compute_matrix() h_matrix = ops.Hadamard.compute_matrix() alternate_h_matrix = x_matrix @ h_matrix @ x_matrix d, q = math.linalg.eig(U) d = math.diag(d) q = _convert_to_real_diagonal(q) b = _bisect_compute_b(q) c1 = math.matmul(b, alternate_h_matrix) c2t = math.matmul(b, h_matrix) mid = len(wires) // 2 # for odd n, make control_k1 bigger ctrl_k1 = wires[:mid] ctrl_k2 = wires[mid:-1] # The component ops.QubitUnitary(c2t, wires[-1]) mcx_wires_k2 = concatenate_wires(ctrl_k2, wires[-1:]) ops.MultiControlledX(mcx_wires_k2, work_wires=ctrl_k1, work_wire_type="borrowed") ops.adjoint(ops.QubitUnitary(c1, wires[-1])) # Cancel the two identity controlled X gates _ctrl_decomp_bisect_od(d, wires, skip_initial_cx=True) # Adjoint of the component mcx_wires_k1 = concatenate_wires(ctrl_k1, wires[-1:]) ops.MultiControlledX(mcx_wires_k1, work_wires=ctrl_k2, work_wire_type="borrowed") ops.QubitUnitary(c1, wires[-1]) ops.MultiControlledX(mcx_wires_k2, work_wires=ctrl_k1, work_wire_type="borrowed") ops.adjoint(ops.QubitUnitary(c2t, wires[-1])) def _ctrl_decomp_bisect_od(U, wires, skip_initial_cx=False): """Decompose the controlled version of a target single-qubit operation This function decomposes a controlled single-qubit target operation using the decomposition defined in section 3.1, Theorem 1 of `Vale et al. (2023) <https://arxiv.org/abs/2302.06377>`_. The target operation's matrix must have a real off-diagonal for this specialized method to work. Args: U (tensor): the target operation to decompose wires (WiresLike): the wires of the operation (control wires followed by the target wire) """ a = _bisect_compute_a(U) mid = len(wires) // 2 # for odd n, make control_k1 bigger ctrl_k1 = wires[:mid] ctrl_k2 = wires[mid:-1] mcx_wires_k1 = concatenate_wires(ctrl_k1, wires[-1:]) mcx_wires_k2 = concatenate_wires(ctrl_k2, wires[-1:]) if not skip_initial_cx: ops.MultiControlledX(mcx_wires_k1, work_wires=ctrl_k2, work_wire_type="borrowed") ops.QubitUnitary(a, wires[-1]) ops.MultiControlledX(mcx_wires_k2, work_wires=ctrl_k1, work_wire_type="borrowed") ops.adjoint(ops.QubitUnitary(a, wires[-1])) ops.MultiControlledX(mcx_wires_k1, work_wires=ctrl_k2, work_wire_type="borrowed") ops.QubitUnitary(a, wires[-1]) ops.MultiControlledX(mcx_wires_k2, work_wires=ctrl_k1, work_wire_type="borrowed") ops.adjoint(ops.QubitUnitary(a, wires[-1])) def _ctrl_decomp_bisect_md(U, wires): """Decompose the controlled version of a target single-qubit operation This function decomposes a controlled single-qubit target operation using the decomposition defined in section 3.1, Theorem 2 of `Vale et al. (2023) <https://arxiv.org/abs/2302.06377>`_. The target operation's matrix must have a real main-diagonal for this specialized method to work. Args: U (tensor): the target operation to decompose wires (WiresLike): the wires of the operation (control wires followed by the target wire) """ h_matrix = ops.Hadamard.compute_matrix() mod_u = math.matmul(math.matmul(h_matrix, U), h_matrix) ops.H(wires[-1]) _ctrl_decomp_bisect_od(mod_u, wires) ops.H(wires[-1]) def _convert_to_real_diagonal(q): """ Change the phases of Q so the main diagonal is real, and return the modified Q. """ exp_angles = math.angle(math.diag(q)) return q * math.reshape(math.exp(-1j * exp_angles), (1, 2)) def _param_su2(ar, ai, br, bi=0): """ Create a matrix in the SU(2) form from complex parameters a, b. The resulting matrix is not guaranteed to be in SU(2), unless |a|^2 + |b|^2 = 1. """ return math.stack( [math.stack([ar + 1j * ai, -br + 1j * bi]), math.stack([br + 1j * bi, ar + 1j * -ai])] ) def _bisect_compute_a(u): """ Given the U matrix, compute the A matrix such that At x A x At x A x = U where At is the adjoint of A and x is the Pauli X matrix. """ x = math.real(u[0, 1]) z = u[1, 1] zr = math.real(z) zi = math.imag(z) def _compute_a(): ar = math.sqrt((math.sqrt((zr + 1) / 2) + 1) / 2) mul = 1 / (2 * math.sqrt((zr + 1) * (math.sqrt((zr + 1) / 2) + 1))) ai = zi * mul br = x * mul bi = 0 return _param_su2(ar, ai, br, bi) return math.cond( math.allclose(zr, -1), lambda: math.array([[1 + 0j, -1 + 0j], [1 + 0j, 1 + 0j]]) * 2**-0.5, _compute_a, (), ) def _bisect_compute_b(u): """ Given the U matrix, compute the B matrix such that H Bt x B x H = U where Bt is the adjoint of B, H is the Hadamard matrix, and x is the Pauli X matrix. """ w = math.real(u[0, 0]) s = math.real(u[1, 0]) t = math.imag(u[1, 0]) b = math.cond( math.allclose(s, 0), lambda: 0.0, lambda: math.cond( math.allclose(t, 0), lambda: (1 / 2 - w / 2) * math.sqrt(2 * w + 2) / s, lambda: math.sqrt(2) * s * math.sqrt((1 - w) / (s**2 + t**2)) * math.abs(t) / (2 * t), (), ), (), ) c = math.cond( math.allclose(s, 0), lambda: math.cond( math.allclose(t, 0), lambda: math.cond(w < 0, lambda: 0.0, lambda: math.sqrt(w), ()), lambda: math.sqrt(2 - 2 * w) * (-w / 2 - 1 / 2) / t, (), ), lambda: math.cond( math.allclose(t, 0), lambda: math.sqrt(2 * w + 2) / 2, lambda: math.sqrt(2) * math.sqrt((1 - w) / (s**2 + t**2)) * (w + 1) * math.abs(t) / (2 * t), (), ), (), ) d = math.cond( math.allclose(s, 0), lambda: math.cond( math.allclose(t, 0), lambda: math.cond(w < 0, lambda: math.sqrt(-w), lambda: 0.0, ()), lambda: math.sqrt(2 - 2 * w) / 2, (), ), lambda: math.cond( math.allclose(t, 0), lambda: 0.0, lambda: -math.sqrt(2) * math.sqrt((1 - w) / (s**2 + t**2)) * math.abs(t) / 2, (), ), (), ) return _param_su2(c, d, b, 0) def _single_control_zyz(phi, theta, omega, wires): """Implements Lemma 5.1 from https://arxiv.org/pdf/quant-ph/9503016""" # Operator A ops.cond(_not_zero(phi), ops.RZ)(phi, wires=wires[-1]) ops.cond(_not_zero(theta), ops.RY)(theta / 2, wires=wires[-1]) ops.CNOT(wires) # Operator B ops.cond(_not_zero(theta), ops.RY)(-theta / 2, wires=wires[-1]) ops.cond(_not_zero(phi + omega), ops.RZ)(-(phi + omega) / 2, wires=wires[-1]) ops.CNOT(wires) # Operator C ops.cond(_not_zero(omega - phi), ops.RZ)((omega - phi) / 2, wires=wires[-1]) # pylint: disable-next=too-many-arguments def _multi_control_zyz(phi, theta, omega, wires, work_wires, work_wire_type): """Implements Lemma 7.9 from https://arxiv.org/pdf/quant-ph/9503016""" # Operator A ops.cond(_not_zero(phi), ops.CRZ)(phi, wires=wires[-2:]) ops.cond(_not_zero(theta), ops.CRY)(theta / 2, wires=wires[-2:]) ops.MultiControlledX( concatenate_wires(wires[:-2], wires[-1:]), work_wires=work_wires, work_wire_type=work_wire_type, ) # Operator B ops.cond(_not_zero(theta), ops.CRY)(-theta / 2, wires=wires[-2:]) ops.cond(_not_zero(phi + omega), ops.CRZ)(-(phi + omega) / 2, wires=wires[-2:]) ops.MultiControlledX( concatenate_wires(wires[:-2], wires[-1:]), work_wires=work_wires, work_wire_type=work_wire_type, ) # Operator C ops.cond(_not_zero(omega - phi), ops.CRZ)((omega - phi) / 2, wires=wires[-2:]) def _ctrl_global_phase( phase, control_wires, work_wires=None, work_wire_type: Literal["zeroed", "borrowed"] = "borrowed", ): ops.ctrl( ops.GlobalPhase(-phase), control=control_wires, work_wires=work_wires, work_wire_type=work_wire_type, ) def _n_parallel_ccx_x(control_wires_x, control_wires_y, target_wires): r""" Construct a quantum circuit for creating n-condionally zeroed auxiliary qubits using 3n qubits. This implements Fig. 4a of [1]. Each wire is of the same size :math:`n`. Args: control_wires_x: The control wires for register 1. control_wires_y: The control wires for register 2. target_wires: The wires for target register. References: 1. Khattar and Gidney, Rise of conditionally clean ancillae for optimizing quantum circuits `arXiv:2407.17966 <https://arxiv.org/abs/2407.17966>`__ """ @control_flow.for_loop(0, len(control_wires_x), 1) def loop(i): ops.X(target_wires[i]) ops.Toffoli([control_wires_x[i], control_wires_y[i], target_wires[i]]) loop() # pylint: disable=no-value-for-parameter def _build_linear_depth_ladder(wires) -> int: r""" Helper function to create linear-depth ladder operations used in Khattar and Gidney's MCX synthesis. In particular, this implements Step-1 and Step-2 on Fig. 3 of [1] except for the first and last CCX gates. Preconditions: - The number of wires must be greater than 2. Args: wires: the list of wires. Returns: int: the index of the last unmarked wire. References: 1. Khattar and Gidney, Rise of conditionally clean ancillae for optimizing quantum circuits `arXiv:2407.17966 <https://arxiv.org/abs/2407.17966>`__ """ if len(wires) == 3: return 2 if len(wires) == 4: ops.Toffoli([wires[2], wires[3], wires[1]]) ops.X(wires[1]) return 1 i = -1 while i + 2 < len(wires) - 2: i += 2 ops.Toffoli([wires[i + 1], wires[i + 2], wires[i]]) ops.X(wires[i]) x, y = (i - 2, i) if i + 2 == len(wires) - 1 else (i, i + 3) k = x - 1 ops.Toffoli([wires[x], wires[y], wires[k]]) ops.X(wires[k]) for i in range(k, 1, -2): ops.Toffoli([wires[i - 1], wires[i], wires[i - 2]]) ops.X(wires[i - 2]) return 0 def _build_log_n_depth_ccx_ladder(control_wires) -> list: r""" Helper function to build a log-depth ladder compose of CCX and X gates as shown in Fig. 4b of [1]. Args: control_wires: The control wires. Returns: list: The list of unmarked wires to use as control wires. References: 1. Khattar and Gidney, Rise of conditionally clean ancillae for optimizing quantum circuits `arXiv:2407.17966 <https://arxiv.org/abs/2407.17966>`__ """ final_control_wires = [] # See Section 5.2 of [1] for what the following variables mean rightmost_marked = 1 timestep = 1 while rightmost_marked < len(control_wires) - 1: # At every time step, we aim to flip the next 2^i + 1 unmarked wires, but if # there are not enough wires available, we just flip all the remaining wires. n_to_flip = min(2**timestep + 1, len(control_wires) - rightmost_marked - 1) rightmost_ctrl = rightmost_marked + n_to_flip new_rightmost_marked = rightmost_ctrl leftmost_unmarked = rightmost_marked + 1 while n_to_flip > 1: ccx_n = n_to_flip // 2 ccx_t = control_wires[rightmost_marked + 1 - ccx_n : rightmost_marked + 1] ccx_y = control_wires[rightmost_ctrl + 1 - ccx_n : rightmost_ctrl + 1] ccx_x = control_wires[rightmost_ctrl + 1 - ccx_n * 2 : rightmost_ctrl + 1 - ccx_n] leftmost_unmarked = rightmost_marked + 1 - ccx_n _n_parallel_ccx_x(ccx_x, ccx_y, ccx_t) # The primitive used ccx_n target wires to flip the 2 * ccx_n control wires. The # total number of remaining wires to flip in this timestep is given by the original # number of wires minus the 2 * ccx_n wires that were flipped, plus the ccx_n # target wires that were unmarked as a result of this primitive. n_to_flip = n_to_flip - ccx_n rightmost_marked -= ccx_n rightmost_ctrl -= ccx_n * 2 final_control_wires.append(leftmost_unmarked) rightmost_marked = new_rightmost_marked timestep += 1 return final_control_wires