跳转至

QFTDivider

QuICT.algorithm.arithmetic.divider.qft_divider.CCRk 

CCRk(k: int, name: str = None)

Bases: CompositeGate

Build two control qubit \(R_k\) gate according to the paper.

References

[1]: "Integer Numeric Multiplication Using Quantum Fourier Transform" by Joseph L Pachuau, Arnab Roy and Anish Kumar Saha https://doi.org/10.1007/s40509-021-00262-w.

Parameters:

  • k (int) –

    The value of 'k' in \(R_k\).

  • name (str, default: None ) –

    The name of this gate.

Source code in QuICT/algorithm/arithmetic/divider/qft_divider.py 
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
def __init__(
        self,
        k: int,
        name: str = None
):
    """
    Args:
        k (int): The value of 'k' in $R_k$.
        name (str, optional): The name of this gate.
    """
    super().__init__(name)
    if name is None:
        self.name = f"R_{k}"

    # init rotation angle
    if k < 0:
        theta = -pi / (1 << (-k))
    else:
        theta = pi / (1 << k)

    CU1(theta) | self([1, 2])
    CX | self([0, 1])
    CU1(-theta) | self([1, 2])
    CX | self([0, 1])
    CU1(theta) | self([0, 2])

QuICT.algorithm.arithmetic.divider.qft_divider.SUBModule 

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

Bases: CompositeGate

Implement a subtractor which is part of the following dividers. This module in total requires 2n qubits. $$ \vert{\Phi (a)}\rangle_n \vert{b}\rangle_n \to \vert{\Phi (a-b)}\rangle_n \vert{b}\rangle_n $$

References

[1]: "Quantum Division Circuit Based on Restoring Division Algorithm" by Alireza Khosropour, Hossein Aghababa and Behjat Forouzandeh https://ieeexplore.ieee.org/document/5945378.

Parameters:

  • qreg_size (int) –

    The register size for the operand which is same as the register size for the dividend in the following divider.

  • name (str, default: None ) –

    The name of this module.

Raises:

Source code in QuICT/algorithm/arithmetic/divider/qft_divider.py 
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
def __init__(
        self,
        qreg_size: int,
        name: str = None
):
    """
    Args:
        qreg_size (int): The register size for the operand
            which is same as the register size for the dividend in the following divider.
        name (str, optional): The name of this module.

    Raises:
        GateParametersAssignedError: If `qreg_size` is smaller than 2.
    """
    if qreg_size < 2:
        raise GateParametersAssignedError(
            f"{self.__class__.__name__} needs register size must to be at least 2 but given {qreg_size}."
        )

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

    sub, mapping = self._build_sub(qreg_size)

    self._implement_mapping = [0] * (2 * qreg_size)
    for idx, val in enumerate(mapping):
        self._implement_mapping[val] = idx
    sub = sub & self._implement_mapping

    for gate in sub:
        gate | self

QuICT.algorithm.arithmetic.divider.qft_divider.CtrlAddSubModule 

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

Bases: CompositeGate

Implement a control adder-subtractor module which is part of the following dividers. This module in total requires 2n + 1 qubits. $$ \vert{\text{ctrl}}\rangle \vert{\Phi (a)}\rangle_n \vert{b}\rangle_n \to \vert{\text{ctrl}}\rangle \vert{\Phi (a+(-1)^\text{ctrl}\times b)}\rangle_n \vert{b}\rangle_n $$

Parameters:

  • qreg_size (int) –

    The register size for two operands which is same as the register size for the dividend in the following dividers.

  • name (str, default: None ) –

    The name of this module.

Raises:

Source code in QuICT/algorithm/arithmetic/divider/qft_divider.py 
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
def __init__(
        self,
        qreg_size: int,
        name: str = None
):
    """
    Args:
        qreg_size (int): The register size for two operands
            which is same as the register size for the dividend in the following dividers.
        name (str): The name of this module.

    Raises:
        GateParametersAssignedError: If `qreg_size` is smaller than 2.
    """
    if qreg_size < 2:
        raise GateParametersAssignedError(
            f"{self.__class__.__name__} needs register size must to be at least 2 but given {qreg_size}."
        )

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

    # the meaning of each line
    ctrl = 0
    a_h2l = range(1, qreg_size + 1)
    b_h2l = range(qreg_size + 1, 2 * qreg_size + 1)

    # construct the module
    for i in range(qreg_size):
        for j in range(i + 1):
            CX | self([ctrl, b_h2l[i]])
            CU1(pi / (1 << (i - j))) | self([b_h2l[i], a_h2l[j]])
            CX | self([ctrl, b_h2l[i]])
            CU1(-pi / (1 << (i - j))) | self([ctrl, a_h2l[j]])

QuICT.algorithm.arithmetic.divider.qft_divider.CtrlADDModule 

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

Bases: CompositeGate

Implement a control adder which is part of the following dividers. This module in total requires 2n + 1 qubits. $$ \vert{\text{ctrl}}\rangle \vert{\Phi (a)}\rangle_n \vert{b}\rangle_n \to \vert{\text{ctrl}}\rangle \vert{\Phi (a+\text{ctrl}\times b)}\rangle_n \vert{b}\rangle_n $$

References

[1]: "Quantum Division Circuit Based on Restoring Division Algorithm" by Alireza Khosropour, Hossein Aghababa and Behjat Forouzandeh https://ieeexplore.ieee.org/document/5945378.

Parameters:

  • qreg_size (int) –

    The register size for the operand which is same as the register size for the dividend in the following dividers.

  • name (str, default: None ) –

    The name of this module.

  • Raises –

    GateParametersAssignedError: If qreg_size is smaller than 2.

Source code in QuICT/algorithm/arithmetic/divider/qft_divider.py 
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
def __init__(
        self,
        qreg_size: int,
        name: str = None
):
    """
    Args:
        qreg_size (int): The register size for the operand
            which is same as the register size for the dividend in the following dividers.
        name (str, optional): The name of this module.

        Raises:
             GateParametersAssignedError: If `qreg_size` is smaller than 2.
    """
    if qreg_size < 2:
        raise GateParametersAssignedError(
            f"{self.__class__.__name__} needs register size must to be at least 2 but given {qreg_size}."
        )

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

    ctrl_add, mapping = self._build_add(qreg_size)
    self._implement_mapping = [0] * (2 * qreg_size + 1)
    for idx, val in enumerate(mapping):
        self._implement_mapping[val] = idx
    ctrl_add = ctrl_add & self._implement_mapping

    for gate in ctrl_add:
        gate | self

QuICT.algorithm.arithmetic.divider.qft_divider.QFTDivider 

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

Bases: CompositeGate

Implement a quantum divider using non-restoring algorithm based on QFT that in total require 3n - 1 qubits. $$ \vert{0}\rangle_{n-1} \vert{b}\rangle_n \vert{a}\rangle_n \to \vert{b//a}\rangle_n \vert{b%a}\rangle_{n-1} \vert{a}\rangle_n $$ Note: The divisor's highest bit must be zero. If divisor is set to zero, the result of running this divider is:

$$
\vert{0}\rangle_{n-1} \vert{b}\rangle_n \vert{0}\rangle_n
\to
\vert{2^n-1}\rangle_n \vert{b_{n-2}...b_0}\rangle_{n-1} \vert{0}\rangle_n
$$
References

[1]: "Quantum Circuit Designs of Integer Division Optimizing T-count and T-depth" by Himanshu Thapliyal, Edgard Muñoz-Coreas, T.S.S.Varun and Travis S.Humble https://ieeexplore.ieee.org/document/8691552.

[2]: "Integer Numeric Multiplication Using Quantum Fourier Transform" by Joseph L Pachuau, Arnab Roy and Anish Kumar Saha https://doi.org/10.1007/s40509-021-00262-w.

[3]: "Quantum Division Circuit Based on Restoring Division Algorithm" by Alireza Khosropour, Hossein Aghababa and Behjat Forouzandeh https://ieeexplore.ieee.org/document/5945378.

Parameters:

  • qreg_size (int) –

    The register size for the dividend and divisor.

  • name (str, default: None ) –

    The name of the divider.

Raises:

Source code in QuICT/algorithm/arithmetic/divider/qft_divider.py 
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
def __init__(
        self,
        qreg_size: int,
        name: str = None
):
    """
    Args:
        qreg_size (int): The register size for the dividend and divisor.
        name (str): The name of the divider.

    Raises:
        GateParametersAssignedError: If `qreg_size` is smaller than 3.
    """
    if qreg_size < 3:
        raise GateParametersAssignedError(
            f"{self.__class__.__name__} needs register size must to be at least 3 but given {qreg_size}."
        )

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

    self._build_divider(qreg_size)