qqz.elementary

View Source

  1"""
  2Implementing [arXiv:quant-ph/9511018](https://arxiv.org/abs/quant-ph/9511018)
  3"""
  4
  5from typing import Optional
  6
  7import numpy as np
  8from qiskit import QuantumCircuit, QuantumRegister
  9from qiskit.circuit import Gate
 10
 11
 12def carry() -> Gate:
 13    """CARRY. It requires 4 qubits.
 14    
 15    Returns:
 16        its gate
 17    """
 18
 19    qc = QuantumCircuit(4)
 20    qc.ccx(1, 2, 3)
 21    qc.cx(1, 2)
 22    qc.ccx(0, 2, 3)
 23    return qc.to_gate()
 24
 25def qsum() -> Gate:
 26    """SUM. It requires 3 qubits.
 27    
 28    Returns:
 29        its gate
 30    """
 31
 32    qc = QuantumCircuit(3)
 33    qc.cx(1, 2)
 34    qc.cx(0, 2)
 35    return qc.to_gate()
 36
 37def adder(n: int) -> Gate:
 38    r"""ADDER: $a,b\to a,a+b$. It requires $3n+1$ qubits: $a$ uses $n$ qubits, $b$ uses $n+1$ qubits, and $c$ uses $n$ qubits.
 39
 40    Args:
 41      n (int): $n$ bits for representing $a$.
 42
 43    Returns:
 44        its gate
 45    """
 46
 47    qubits = QuantumRegister(n + (n + 1) + n)
 48    a = qubits[:n]
 49    b = qubits[n:n + (n + 1)]
 50    c = qubits[n + (n + 1):]
 51    qc = QuantumCircuit(qubits)
 52
 53    carry_gate = carry()
 54    carry_gate_dag = carry_gate.inverse()
 55    sum_gate = qsum()
 56
 57    for i in range(n - 1):
 58        qc.append(carry_gate, [c[i]] + [a[i]] + [b[i]] + [c[i + 1]])
 59    qc.append(carry_gate, [c[n - 1]] + [a[-1]] + [b[n - 1]] + [b[n]])
 60    qc.cx(a[-1], b[n - 1])
 61    qc.append(sum_gate, [c[n - 1]] + [a[-1]] + [b[n - 1]])
 62    for i in reversed(range(n - 1)):
 63        qc.append(carry_gate_dag, [c[i]] + [a[i]] + [b[i]] + [c[i + 1]])
 64        qc.append(sum_gate, [c[i]] + [a[i]] + [b[i]])
 65
 66    return qc.to_gate()
 67
 68def adder_modM(M: int, N_len: int) -> Gate:
 69    r"""ADDER MOD: $a,b\to a,a+b\mod M$. It requires $4N_\mathit{len}+2$ qubits: $a$ uses $N_\mathit{len}$ qubits, $b$ uses $N_\mathit{len}+1$ qubits, $c$ uses $N_\mathit{len}$ qubits, $M$ uses $N_\mathit{len}$ qubits, and $t$ uses 1 qubit.
 70
 71    Args:
 72        M (int): $N$ in the paper, but we uses $M$ instead.
 73        N_len (int): a number of bits for representing $a$.
 74
 75    Returns:
 76        its gate
 77    """
 78
 79    M_val = M
 80
 81    qubits = QuantumRegister(N_len + (N_len + 1) + N_len + N_len + 1)
 82    a, left_qubits = qubits[:N_len], qubits[N_len:]
 83    b, left_qubits = left_qubits[:N_len + 1], left_qubits[N_len + 1:]
 84    c, left_qubits = left_qubits[:N_len], left_qubits[N_len:]
 85    M, left_qubits = left_qubits[:N_len], left_qubits[N_len:]
 86    t = left_qubits[:1]
 87    qc = QuantumCircuit(qubits)
 88
 89    adder_gate = adder(N_len)
 90    adder_gate_dag = adder_gate.inverse()
 91
 92    for i, char in enumerate(bin(M_val)[2:][::-1]):
 93        if char == '1':
 94            qc.x(M[i])
 95
 96    qc.append(adder_gate, a + b + c)
 97    qc.append(adder_gate_dag, M + b + c)
 98    qc.x(b[-1])
 99    qc.cx(b[-1], t[0])
100    qc.x(b[-1])
101    for i, char in enumerate(bin(M_val)[2:][::-1]):
102        if char == '1':
103            qc.cx(t[0], M[i])
104    qc.append(adder_gate, M + b + c)
105    for i, char in enumerate(bin(M_val)[2:][::-1]):
106        if char == '1':
107            qc.cx(t[0], M[i])
108    qc.append(adder_gate_dag, a + b + c)
109    qc.cx(b[-1], t[0])
110    qc.append(adder_gate, a + b + c)
111
112    for i, char in enumerate(bin(M_val)[2:][::-1]):
113        if char == '1':
114            qc.x(M[i])
115
116    return qc.to_gate()
117
118def ctrl_multi_modM(a: int, M: int, N_len: int) -> Gate:
119    r"""Ctrl MULT MOD: $x,0\to x,ax\mod M$ if $c=1$, otherwise $x,0\to x,x$. It requires $9N_\mathit{len}-1$ qubits: $\mathit{ctrl}$ uses 1 qubit, $x$ uses $N_\mathit{len}$ qubits, $y$ uses $2N_\mathit{len}$ qubits, $\mathit{xx}$ (which is a register in the middle of Fig. 5 in the paper) uses $2N_\mathit{len}-1$ qubits, $c$ (which is $c$ for ADDER MOD) uses $2N_\mathit{len}-1$ qubits, $M$ (which is $M$ for ADDER MOD) uses $2N_\mathit{len}-1$ qubits, and $t$ (which is $t$ for ADDER MOD) uses 1 qubit.
120
121    Args:
122        a (int): $a$
123        M (int): $M$ (see `adder_modM`)
124        N_len (int): a number of bits for representing $x$
125
126    Returns:
127        its gate
128    """
129
130    M_val = M
131    N_len = N_len
132
133    qubits = QuantumRegister(9 * N_len - 1)
134    ctrl, left_qubits = qubits[:1], qubits[1:]
135    x, left_qubits = left_qubits[:N_len], left_qubits[N_len:]
136    y, left_qubits = left_qubits[:2 * N_len], left_qubits[2 * N_len:]
137    xx, left_qubits = left_qubits[:2 * N_len - 1], left_qubits[2 * N_len - 1:]
138    c, left_qubits = left_qubits[:2 * N_len - 1], left_qubits[2 * N_len - 1:]
139    M, left_qubits = left_qubits[:2 * N_len - 1], left_qubits[2 * N_len - 1:]
140    t, left_qubits = left_qubits[:1], qubits[1:]
141
142    qc = QuantumCircuit(qubits)
143
144    adder_modM_gate = adder_modM(M=M_val, N_len=2 * N_len - 1)
145
146    for i in range(N_len):
147        for j, char in enumerate(bin(2 ** i * a % M_val)[2:][::-1]):
148            if char == '1':
149                qc.ccx(ctrl[0], x[i], xx[j])
150        qc.append(adder_modM_gate, xx + y + c + M + t)
151        for j, char in enumerate(bin(2 ** i * a % M_val)[2:][::-1]):
152            if char == '1':
153                qc.ccx(ctrl[0], x[i], xx[j])
154    qc.x(ctrl[0])
155    for x_bit, y_bit in zip(x, y):
156        qc.ccx(ctrl[0], x_bit, y_bit)
157    qc.x(ctrl[0])
158
159    return qc.to_gate()
160
161def ax_modM(a: int, M: int, N_len: Optional[int] = None, x_0_at_first: bool = True) -> Gate:
162    r"""Modular exponentiation, $a^x\mod M$. It requires $10N_\mathit{len}-2$ qubits: $x$ uses $N_\mathit{len}$ qubits, $\mathit{x\ for\ Ctrl\ MULT\ MOD}$ uses $N_\mathit{len}$ qubits, $y$ uses $2N_\mathit{len}$ qubits, $\mathit{xx}$ uses $2N_\mathit{len}-1$ qubits, $c$ (which is $c$ for ADDER MOD) uses $2N_\mathit{len}-1$ qubits, $M$ (which is $M$ for ADDER MOD) uses $2N_\mathit{len}-1$ qubits, and $t$ (which is $t$ for ADDER MOD) uses 1 qubit.
163
164    Args:
165        a (int): $a$
166        M (int): $M$ (see `adder_modM`)
167        N_len (int): a number of bits for representing $x$
168        x_0_at_first (bool): if True, it adds 1 into the target register before calculating modular exponentiation
169
170    Returns:
171        its gate
172    """
173
174    M_val = M
175    if N_len is None:
176        N_len = int(np.ceil(np.log2(M)))
177
178    qubits = QuantumRegister(10 * N_len - 2)
179    x, left_qubits = qubits[:N_len], qubits[N_len:]
180    x_for_ctrl_multi_modM_gate, left_qubits = left_qubits[:N_len], left_qubits[N_len:]
181    y, left_qubits = left_qubits[:2 * N_len], left_qubits[2 * N_len:]
182    xx, left_qubits = left_qubits[:2 * N_len - 1], left_qubits[2 * N_len - 1:]
183    c, left_qubits = left_qubits[:2 * N_len - 1], left_qubits[2 * N_len - 1:]
184    M, left_qubits = left_qubits[:2 * N_len - 1], left_qubits[2 * N_len - 1:]
185    t, left_qubits = left_qubits[:1], qubits[1:]
186
187    qc = QuantumCircuit(qubits)
188
189    if x_0_at_first:
190        qc.x(x_for_ctrl_multi_modM_gate[0])
191    for i in range(N_len):
192        ctrl_multi_modM_gate = ctrl_multi_modM(pow(a, 2 ** i, M_val), M_val, N_len)
193        ctrl_multi_modM_gate_dag = ctrl_multi_modM(pow(a, -2 ** i, M_val), M_val, N_len).inverse()
194
195        qc.append(ctrl_multi_modM_gate, [x[i]] + x_for_ctrl_multi_modM_gate + y + xx + c + M + t)
196        for j in range(N_len):
197            qc.cswap(x[i], x_for_ctrl_multi_modM_gate[j], y[j])
198        qc.append(ctrl_multi_modM_gate_dag, [x[i]] + x_for_ctrl_multi_modM_gate + y + xx + c + M + t)
199
200    return qc.to_gate()

def carry() -> qiskit.circuit.gate.Gate: View Source

13def carry() -> Gate:
14    """CARRY. It requires 4 qubits.
15    
16    Returns:
17        its gate
18    """
19
20    qc = QuantumCircuit(4)
21    qc.ccx(1, 2, 3)
22    qc.cx(1, 2)
23    qc.ccx(0, 2, 3)
24    return qc.to_gate()

CARRY. It requires 4 qubits.

Returns:

its gate

def qsum() -> qiskit.circuit.gate.Gate: View Source

26def qsum() -> Gate:
27    """SUM. It requires 3 qubits.
28    
29    Returns:
30        its gate
31    """
32
33    qc = QuantumCircuit(3)
34    qc.cx(1, 2)
35    qc.cx(0, 2)
36    return qc.to_gate()

SUM. It requires 3 qubits.

Returns:

its gate

def adder(n: int) -> qiskit.circuit.gate.Gate: View Source

38def adder(n: int) -> Gate:
39    r"""ADDER: $a,b\to a,a+b$. It requires $3n+1$ qubits: $a$ uses $n$ qubits, $b$ uses $n+1$ qubits, and $c$ uses $n$ qubits.
40
41    Args:
42      n (int): $n$ bits for representing $a$.
43
44    Returns:
45        its gate
46    """
47
48    qubits = QuantumRegister(n + (n + 1) + n)
49    a = qubits[:n]
50    b = qubits[n:n + (n + 1)]
51    c = qubits[n + (n + 1):]
52    qc = QuantumCircuit(qubits)
53
54    carry_gate = carry()
55    carry_gate_dag = carry_gate.inverse()
56    sum_gate = qsum()
57
58    for i in range(n - 1):
59        qc.append(carry_gate, [c[i]] + [a[i]] + [b[i]] + [c[i + 1]])
60    qc.append(carry_gate, [c[n - 1]] + [a[-1]] + [b[n - 1]] + [b[n]])
61    qc.cx(a[-1], b[n - 1])
62    qc.append(sum_gate, [c[n - 1]] + [a[-1]] + [b[n - 1]])
63    for i in reversed(range(n - 1)):
64        qc.append(carry_gate_dag, [c[i]] + [a[i]] + [b[i]] + [c[i + 1]])
65        qc.append(sum_gate, [c[i]] + [a[i]] + [b[i]])
66
67    return qc.to_gate()

ADDER: $a,b\to a,a+b$. It requires $3n+1$ qubits: $a$ uses $n$ qubits, $b$ uses $n+1$ qubits, and $c$ uses $n$ qubits.

Arguments:

n (int): $n$ bits for representing $a$.

Returns:

its gate

def adder_modM(M: int, N_len: int) -> qiskit.circuit.gate.Gate: View Source

 69def adder_modM(M: int, N_len: int) -> Gate:
 70    r"""ADDER MOD: $a,b\to a,a+b\mod M$. It requires $4N_\mathit{len}+2$ qubits: $a$ uses $N_\mathit{len}$ qubits, $b$ uses $N_\mathit{len}+1$ qubits, $c$ uses $N_\mathit{len}$ qubits, $M$ uses $N_\mathit{len}$ qubits, and $t$ uses 1 qubit.
 71
 72    Args:
 73        M (int): $N$ in the paper, but we uses $M$ instead.
 74        N_len (int): a number of bits for representing $a$.
 75
 76    Returns:
 77        its gate
 78    """
 79
 80    M_val = M
 81
 82    qubits = QuantumRegister(N_len + (N_len + 1) + N_len + N_len + 1)
 83    a, left_qubits = qubits[:N_len], qubits[N_len:]
 84    b, left_qubits = left_qubits[:N_len + 1], left_qubits[N_len + 1:]
 85    c, left_qubits = left_qubits[:N_len], left_qubits[N_len:]
 86    M, left_qubits = left_qubits[:N_len], left_qubits[N_len:]
 87    t = left_qubits[:1]
 88    qc = QuantumCircuit(qubits)
 89
 90    adder_gate = adder(N_len)
 91    adder_gate_dag = adder_gate.inverse()
 92
 93    for i, char in enumerate(bin(M_val)[2:][::-1]):
 94        if char == '1':
 95            qc.x(M[i])
 96
 97    qc.append(adder_gate, a + b + c)
 98    qc.append(adder_gate_dag, M + b + c)
 99    qc.x(b[-1])
100    qc.cx(b[-1], t[0])
101    qc.x(b[-1])
102    for i, char in enumerate(bin(M_val)[2:][::-1]):
103        if char == '1':
104            qc.cx(t[0], M[i])
105    qc.append(adder_gate, M + b + c)
106    for i, char in enumerate(bin(M_val)[2:][::-1]):
107        if char == '1':
108            qc.cx(t[0], M[i])
109    qc.append(adder_gate_dag, a + b + c)
110    qc.cx(b[-1], t[0])
111    qc.append(adder_gate, a + b + c)
112
113    for i, char in enumerate(bin(M_val)[2:][::-1]):
114        if char == '1':
115            qc.x(M[i])
116
117    return qc.to_gate()

ADDER MOD: $a,b\to a,a+b\mod M$. It requires $4N_\mathit{len}+2$ qubits: $a$ uses $N_\mathit{len}$ qubits, $b$ uses $N_\mathit{len}+1$ qubits, $c$ uses $N_\mathit{len}$ qubits, $M$ uses $N_\mathit{len}$ qubits, and $t$ uses 1 qubit.

Arguments:

M (int): $N$ in the paper, but we uses $M$ instead.
N_len (int): a number of bits for representing $a$.

Returns:

its gate

def ctrl_multi_modM(a: int, M: int, N_len: int) -> qiskit.circuit.gate.Gate: View Source

119def ctrl_multi_modM(a: int, M: int, N_len: int) -> Gate:
120    r"""Ctrl MULT MOD: $x,0\to x,ax\mod M$ if $c=1$, otherwise $x,0\to x,x$. It requires $9N_\mathit{len}-1$ qubits: $\mathit{ctrl}$ uses 1 qubit, $x$ uses $N_\mathit{len}$ qubits, $y$ uses $2N_\mathit{len}$ qubits, $\mathit{xx}$ (which is a register in the middle of Fig. 5 in the paper) uses $2N_\mathit{len}-1$ qubits, $c$ (which is $c$ for ADDER MOD) uses $2N_\mathit{len}-1$ qubits, $M$ (which is $M$ for ADDER MOD) uses $2N_\mathit{len}-1$ qubits, and $t$ (which is $t$ for ADDER MOD) uses 1 qubit.
121
122    Args:
123        a (int): $a$
124        M (int): $M$ (see `adder_modM`)
125        N_len (int): a number of bits for representing $x$
126
127    Returns:
128        its gate
129    """
130
131    M_val = M
132    N_len = N_len
133
134    qubits = QuantumRegister(9 * N_len - 1)
135    ctrl, left_qubits = qubits[:1], qubits[1:]
136    x, left_qubits = left_qubits[:N_len], left_qubits[N_len:]
137    y, left_qubits = left_qubits[:2 * N_len], left_qubits[2 * N_len:]
138    xx, left_qubits = left_qubits[:2 * N_len - 1], left_qubits[2 * N_len - 1:]
139    c, left_qubits = left_qubits[:2 * N_len - 1], left_qubits[2 * N_len - 1:]
140    M, left_qubits = left_qubits[:2 * N_len - 1], left_qubits[2 * N_len - 1:]
141    t, left_qubits = left_qubits[:1], qubits[1:]
142
143    qc = QuantumCircuit(qubits)
144
145    adder_modM_gate = adder_modM(M=M_val, N_len=2 * N_len - 1)
146
147    for i in range(N_len):
148        for j, char in enumerate(bin(2 ** i * a % M_val)[2:][::-1]):
149            if char == '1':
150                qc.ccx(ctrl[0], x[i], xx[j])
151        qc.append(adder_modM_gate, xx + y + c + M + t)
152        for j, char in enumerate(bin(2 ** i * a % M_val)[2:][::-1]):
153            if char == '1':
154                qc.ccx(ctrl[0], x[i], xx[j])
155    qc.x(ctrl[0])
156    for x_bit, y_bit in zip(x, y):
157        qc.ccx(ctrl[0], x_bit, y_bit)
158    qc.x(ctrl[0])
159
160    return qc.to_gate()

Ctrl MULT MOD: $x,0\to x,ax\mod M$ if $c=1$, otherwise $x,0\to x,x$. It requires $9N_\mathit{len}-1$ qubits: $\mathit{ctrl}$ uses 1 qubit, $x$ uses $N_\mathit{len}$ qubits, $y$ uses $2N_\mathit{len}$ qubits, $\mathit{xx}$ (which is a register in the middle of Fig. 5 in the paper) uses $2N_\mathit{len}-1$ qubits, $c$ (which is $c$ for ADDER MOD) uses $2N_\mathit{len}-1$ qubits, $M$ (which is $M$ for ADDER MOD) uses $2N_\mathit{len}-1$ qubits, and $t$ (which is $t$ for ADDER MOD) uses 1 qubit.

Arguments:

a (int): $a$
M (int): $M$ (see adder_modM)
N_len (int): a number of bits for representing $x$

Returns:

its gate

def ax_modM( a: int, M: int, N_len: Union[int, NoneType] = None, x_0_at_first: bool = True) -> qiskit.circuit.gate.Gate: View Source

162def ax_modM(a: int, M: int, N_len: Optional[int] = None, x_0_at_first: bool = True) -> Gate:
163    r"""Modular exponentiation, $a^x\mod M$. It requires $10N_\mathit{len}-2$ qubits: $x$ uses $N_\mathit{len}$ qubits, $\mathit{x\ for\ Ctrl\ MULT\ MOD}$ uses $N_\mathit{len}$ qubits, $y$ uses $2N_\mathit{len}$ qubits, $\mathit{xx}$ uses $2N_\mathit{len}-1$ qubits, $c$ (which is $c$ for ADDER MOD) uses $2N_\mathit{len}-1$ qubits, $M$ (which is $M$ for ADDER MOD) uses $2N_\mathit{len}-1$ qubits, and $t$ (which is $t$ for ADDER MOD) uses 1 qubit.
164
165    Args:
166        a (int): $a$
167        M (int): $M$ (see `adder_modM`)
168        N_len (int): a number of bits for representing $x$
169        x_0_at_first (bool): if True, it adds 1 into the target register before calculating modular exponentiation
170
171    Returns:
172        its gate
173    """
174
175    M_val = M
176    if N_len is None:
177        N_len = int(np.ceil(np.log2(M)))
178
179    qubits = QuantumRegister(10 * N_len - 2)
180    x, left_qubits = qubits[:N_len], qubits[N_len:]
181    x_for_ctrl_multi_modM_gate, left_qubits = left_qubits[:N_len], left_qubits[N_len:]
182    y, left_qubits = left_qubits[:2 * N_len], left_qubits[2 * N_len:]
183    xx, left_qubits = left_qubits[:2 * N_len - 1], left_qubits[2 * N_len - 1:]
184    c, left_qubits = left_qubits[:2 * N_len - 1], left_qubits[2 * N_len - 1:]
185    M, left_qubits = left_qubits[:2 * N_len - 1], left_qubits[2 * N_len - 1:]
186    t, left_qubits = left_qubits[:1], qubits[1:]
187
188    qc = QuantumCircuit(qubits)
189
190    if x_0_at_first:
191        qc.x(x_for_ctrl_multi_modM_gate[0])
192    for i in range(N_len):
193        ctrl_multi_modM_gate = ctrl_multi_modM(pow(a, 2 ** i, M_val), M_val, N_len)
194        ctrl_multi_modM_gate_dag = ctrl_multi_modM(pow(a, -2 ** i, M_val), M_val, N_len).inverse()
195
196        qc.append(ctrl_multi_modM_gate, [x[i]] + x_for_ctrl_multi_modM_gate + y + xx + c + M + t)
197        for j in range(N_len):
198            qc.cswap(x[i], x_for_ctrl_multi_modM_gate[j], y[j])
199        qc.append(ctrl_multi_modM_gate_dag, [x[i]] + x_for_ctrl_multi_modM_gate + y + xx + c + M + t)
200
201    return qc.to_gate()

Modular exponentiation, $a^x\mod M$. It requires $10N_\mathit{len}-2$ qubits: $x$ uses $N_\mathit{len}$ qubits, $\mathit{x\ for\ Ctrl\ MULT\ MOD}$ uses $N_\mathit{len}$ qubits, $y$ uses $2N_\mathit{len}$ qubits, $\mathit{xx}$ uses $2N_\mathit{len}-1$ qubits, $c$ (which is $c$ for ADDER MOD) uses $2N_\mathit{len}-1$ qubits, $M$ (which is $M$ for ADDER MOD) uses $2N_\mathit{len}-1$ qubits, and $t$ (which is $t$ for ADDER MOD) uses 1 qubit.

Arguments:

a (int): $a$
M (int): $M$ (see adder_modM)
N_len (int): a number of bits for representing $x$
x_0_at_first (bool): if True, it adds 1 into the target register before calculating modular exponentiation

Returns:

its gate