跳转至

MuThCtrlAdder

QuICT.algorithm.arithmetic.adder.MuThCtrlAdder 

MuThCtrlAdder(qreg_size: int, name: str = None)

Bases: CompositeGate

A controlled ripple-carry in-place half adder that in total requires 2n + 3 qubits. For two n-qubit binary encoded integers a and b, calculate their sum and store the result on the second register only when the control bit is 1:

\[ \vert{\text{ctrl}}\rangle \vert{a}\rangle_n \vert{0}\rangle \vert{b}\rangle_n \vert{0}\rangle \to \vert{\text{ctrl}}\rangle \vert{a}\rangle_n \vert{\text{ctrl} * a + b}\rangle_{n+1} \vert{0}\rangle \]

Applying this gate on two 2-qubit sized register, \(a:=\vert{q_1q_2}\rangle\) and \(b:=\vert{q_4q_5}\rangle\) with the control bit on \(\vert{q_0}\rangle\), output carry on \(\vert{q_3}\rangle\) and one ancilla qubit on \(\vert{q_6}\rangle\) looks like:

q_0: |0>─────────■────────────────────■─────────────■─────────────■─────────
                 │   ┌─────┐          │             │   ┌─────┐   │
q_1: |0>──■──────■───┤ ccx ├───■──────┼──────■──────■───┤ ccx ├───┼─────■───
          │      │   └──┬──┘   │      │      │      │   └──┬──┘   │     │
q_2: |0>──┼──────┼──────■──────┼──────┼──────┼──────┼──────■──────■─────┼───
          │   ┌──┴──┐   │      │   ┌──┴──┐   │      │      │      │     │
q_3: |0>──┼───┤ ccx ├───┼──────┼───┤ ccx ├───┼──────┼──────┼──────┼─────┼───
        ┌─┴──┐└─────┘   │      │   └──┬──┘   │   ┌──┴──┐   │      │   ┌─┴──┐
q_4: |0>┤ cx ├──────────┼──────■──────┼──────■───┤ ccx ├───┼──────┼───┤ cx ├
        └────┘          │      │      │      │   └─────┘   │   ┌──┴──┐└────┘
q_5: |0>────────────────■──────┼──────┼──────┼─────────────■───┤ ccx ├──────
                            ┌──┴──┐   │   ┌──┴──┐              └─────┘
q_6: |0>────────────────────┤ ccx ├───■───┤ ccx ├───────────────────────────
                            └─────┘       └─────┘

Examples:

from QuICT.core import Circuit
from QuICT.algorithm.arithmetic import MuThCtrlAdder

circuit = Circuit(7)
MuThCtrlAdder(2) | circuit

Implementation Details(Asymptotic)

Parameter Info
Input Size \(n\)
num. ctrl \(1\)
Input carry \(0\)
Output carry \(1\)
num. ancilla \(1\)
Gate set \(CCX, CX\)
Width \(2n+3\)
Depth \(5n-1\)
Size \(7n-4\)
CX count \(4n-6\)
CCX count \(3n+2\)
References

[1]: "Quantum Circuit Design of a T-count Optimized Integer Multiplier" by Edgard Muñoz-Coreas and Himanshu Thapliyal https://ieeexplore.ieee.org/document/8543237.

Parameters:

  • qreg_size (int) –

    Input register size for both addends. Needs to be greater than or euqal to 2.

  • name (str, default: None ) –

    Name of the adder gate.

Raises: GateParametersAssignedError: If the qreg_size is smaller than 2.

Source code in QuICT/algorithm/arithmetic/adder/muth_ctrl_adder.py 
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
def __init__(
    self,
    qreg_size: int,
    name: str = None
):
    """
    Args:
        qreg_size (int): Input register size for both addends. Needs to be greater than or euqal to 2.
        name (str): Name of the adder gate.
    Raises:
        GateParametersAssignedError: If the `qreg_size` is smaller than 2.
    """
    if qreg_size < 2:
        raise GateParametersAssignedError(
            f"Register size must be greater than or equal to 2 but given {qreg_size}."
        )

    self._reg_size = qreg_size

    self._ctrl_bit = 0
    self._reg_a_list = list(range(1, 1 + qreg_size))
    self._reg_carry = 1 + qreg_size
    self._reg_b_list = list(range(qreg_size + 2, 2 * qreg_size + 2))
    self._anci_bit = 2 * qreg_size + 2

    super().__init__(name)
    if name is None:
        self.name = "CtrlAdder"

    # step 1
    for i in range(qreg_size - 1):
        CX | self([self._reg_a_list[i], self._reg_b_list[i]])

    # step 2
    CCX | self([self._ctrl_bit, self._reg_a_list[0], self._reg_carry])
    for i in range(qreg_size - 2):
        CX | self([self._reg_a_list[i + 1], self._reg_a_list[i]])

    # step 3
    for i in range(qreg_size - 1):
        CCX | self([
            self._reg_b_list[-1 - i],
            self._reg_a_list[-1 - i],
            self._reg_a_list[-2 - i]
        ])

    # step 4
    CCX | self([self._reg_b_list[0], self._reg_a_list[0], self._anci_bit])
    CCX | self([self._ctrl_bit, self._anci_bit, self._reg_carry])
    CCX | self([self._reg_b_list[0], self._reg_a_list[0], self._anci_bit])

    # step 5
    for i in range(qreg_size - 1):
        CCX | self([self._ctrl_bit, self._reg_a_list[i], self._reg_b_list[i]])
        CCX | self([
            self._reg_b_list[i + 1],
            self._reg_a_list[i + 1],
            self._reg_a_list[i]
        ])
    CCX | self([self._ctrl_bit, self._reg_a_list[-1], self._reg_b_list[-1]])

    # step 6
    for i in range(qreg_size - 2):
        CX | self([self._reg_a_list[-2 - i], self._reg_a_list[-3 - i]])

    # step 7
    for i in range(qreg_size - 1):
        CX | self([self._reg_a_list[i], self._reg_b_list[i]])