Quantum arithmetic operations
We demonstrate building some quantum arithmetic operations using basic gates. Some operations would be used in other quantum algorithms, such as Shor's algorithm.
Adder
We will present two quantum adders based on the ripple-carry approach, i.e., starting from low-order bits of the input and working our way up to the high-order bits. We assume the inputs are and , both with qubits and 0 is the lowest-order bit. The adder transfers
First, we show a basic design. It relies on two major components: a majority (MAJ) gate and an UnMajority and Add (UMA) gate. They make a 1-bit full-adder together.
These two components can be built with CNOT and Toffoli gates easily:
It follows that we can string together MAJ and UMA gates to build a ripple-carry adder. Below is a 3-bit adder
Note that the first qubit is ancillary. The isQ code implementing this adder is
/*
* Majority gate
*
* |a_i>|b_i>|c_i> -> |c_{i+1}>|b_i^a_i>|c_i^a_i>.
* when the inputs contain two or three 1s, c_{i+1} = 1; otherwise, 0.
*/
procedure maj(qbit a, qbit b, qbit c) {
CNOT(c, a);
CNOT(c, b);
Toffoli(a, b, c);
} deriving gate
/*
* UMA (UnMaj-and-Add) gate
*
* |c_i^a_i>|b_i^a_i>|c_{i+1}> -> |c_i>|s_i>|a_i>
* s_i is the addition result of a_i, b_i, and c_i.
*/
procedure uma(qbit ca, qbit ba, qbit c)
{
Toffoli(ca, ba, c);
CNOT(c, ca);
CNOT(ca, ba);
} deriving gate
/*
* 3-bit adder
* |a>|b> -> |a+b>|a>
*/
procedure adder3(qbit a0, qbit a1, qbit a2, qbit b0, qbit b1, qbit b2) {
qbit anc;
maj(anc, a0, b0);
maj(b0, a1, b1);
maj(b1, a2, b2);
uma(b1, a2, b2);
uma(b0, a1, b1);
uma(anc, a0, b0);
} deriving gate
The keyword deriving gate
transfers a procedure into a gate so that it can be decorated with ctrl
and inv
.
Above adder design can be optimized to improve scalability. One of the more efficient designs is shown below
Note that this design does not require any ancillary qubit. We write an isQ procedure for this design
procedure __add(qbit a[], qbit b[])
{
int len = a.length;
CNOT(a[1:len], b[1:]);
CNOT(a[len-2:0:-1], a[len-1:0:-1]);
Toffoli(a[0:], b, a[1:len]);
for i in len-1:0:-1 {
CNOT(a[i], b[i]);
Toffoli(a[i - 1], b[i - 1], a[i]);
}
CNOT(a[1:], a[2:len]);
CNOT(a, b);
}
We use two qbit
arrays as parameters. This procedure works with an array of any length. Many gates used in this procedure are bundle operations, i.e., operations applied to array elements. For example, CNOT(a[1:len], b[1:])
means applying CNOT
gates pair-wise to (a[1], b[1])
, (a[2], b[2])
, ..., (a[len-1], b[len-1])
. This feature of isQ makes programs concise. However, this feature and classical control flow conflict with deriving gate
because only pure quantum circuits can be decorated.
The second adder design has been adopted as the default adder in the current isQ compiler. It will be called with the form a += b;
where a
and b
are both qubit arrays. For example, the following program will print 3
, 6
, and 1
in sequence.
import std;
procedure main()
{
qbit p[3];
qbit q[3];
X(p[0:2]); // = X(p[0]); X(p[1]);
q += p;
print M(q); // should print 3
q += p;
print M(q); // should print 6
q += p;
print M(q); // should print 1
}
By setting an addend to a constant number, we can turn an adder into a constant adder. More formally, a constant adder maps where is a constant number.
We can implement the constant adder using a regular adder and a simple component SET (). The subscript represents the constant number. The set gate is simply some gates corresponding to the bit 1s in . Therefore, its reverse is itself.
For example, an increment gate can be seen as a constant adder where . We implement it in isQ:
procedure add1(qbit a0, qbit a1, qbit a2) {
qbit b0, b1, b2;
X(b0);
adder3(a0, a1, a2, b0, b1, b2);
X(b0);
} deriving gate
Note that is implemented with X(b0)
.
Subtractor
Subtraction is the dual operation of addition. Therefore, a subtractor is just the reverse of an adder. The following example demonstrates the way of subtracting using an adder.
import std;
import adder3;
procedure main()
{
qbit a[3], b[3];
// Set |a> = |7>
X(a);
// Set |b> = |1>
X(b[0]);
// |a>|b> -> |a-b>|b>
inv adder3(a[0], a[1], a[2], b[0], b[1], b[2]);
print M(a); // should be 6
print M(b); // should be 1
}
Similarly to addition, isQ supports using -=
as the short form of calling the subtraction procedure.
Carrier
A special gate named Carrier is helpful for gates such as the modular adder. It computes i.e., it only computes whether leads to a carry without changing the values of and . Therefore, we can use a circuit similar to the adder to implement the carrier gate.
Note that the gate on the right side of the figure is the inverse of . Thus, and change back to their initial values. The corresponding isQ code is
procedure carrier3(qbit a0, qbit a1, qbit a2, qbit b0, qbit b1, qbit b2, qbit c) {
qbit anc;
maj(anc, a0, b0);
maj(b0, a1, b1);
maj(b1, a2, b2);
// Copy out the result
CNOT(b2, c);
// Uncompute
inv maj(b1, a2, b2);
inv maj(b0, a1, b1);
inv maj(anc, a0, b0);
} deriving gate
Multiplier
We use isQ to build a naive multiplier in this section. It implements the following transformation:
where the lengths of , , and are , , and , respectively. The algorithm mimics the way of multiplying binary numbers on paper, e.g.,
We prepare an ancillary qubit array anc
as the scratchpad, i.e., the memory storing the shifted numbers shown between the two lines in the above figure. The shift operation is implemented using Toffoli
gates, which can also be seen as the multiplication of two bits. Next, anc
is added to c
using an adder. Finally, anc
is uncomputed to , so the computation continues. The complete program is shown below.
// |a>|b>|c> -> |a>|b>|c+a*b>
procedure mul(qbit a[], qbit b[], qbit c[])
{
// Check the length of qubit arrays
int len = a.length;
assert(len == b.length);
assert(len * 2 == c.length);
qbit anc[len * 2];
for i in 0:len {
// anc = b << i
for j in 0:len {
Toffoli(a[i], b[j], anc[i + j]);
}
c += anc;
// anc = 0
for j in 0:len {
Toffoli(a[i], b[j], anc[i + j]);
}
}
}
Modular adder
Let us consider a type of modular adder that computes where and are constant numbers.
One way to implement a modular adder is first to test whether the result is larger than or equal to . If , then . Therefore, this step can be done by setting ancillary qubits to and then applying the carrier gate. If , we need to add to and subtract . It equals adding . If , then we can add directly. Finally, we convert the carry bit back to by calling the carrier gate again. The overall circuit is shown as follows.
As all the components require at most quantum gates, the cost of a modular adder is .
We implement an example where and in isQ:
// |a> -> |a+1(mod 15)>
procedure add1mod15(qbit a0, qbit a1, qbit a2, qbit a3) {
qbit b0, b1, b2, b3, c;
// set b = |2>
X(b1);
// Test whether a + 1 >= 15
carrier4(a0, a1, a2, a3, b0, b1, b2, b3, c);
// If true, add 1 then subtract 15, i.e., subtract 14, i.e., add 2
ctrl add2(c, a0, a1, a2, a3);
// If false, add 1 directly
X(c);
ctrl add1(c, a0, a1, a2, a3);
// Uncompute
X(b0);
X(b2);
X(b3);
carrier4(a0, a1, a2, a3, b0, b1, b2, b3, c);
X(b3);
X(b2);
X(b1);
X(b0);
} deriving gate
Modular multiplier
Based on the modular adder, we can build a modular multiplier. That is, given an -qubit input , we calculate the result where and are constant numbers.
If we express in binary form , i.e., , we can see that i.e., modular multiplication is a series of modular addition chained together.
This observation motivates us to implement the modular multiplier using the following circuit.
As a modular multiplier contains modular adders, the overall cost is .
The following is an isQ implementation where and . Note that , , and .
// |a>|0> -> |a>|a*7(mod 15)>
procedure mul7mod15(qbit a3, qbit a2, qbit a1, qbit a0, qbit b3, qbit b2, qbit b1, qbit b0) {
ctrl add7mod15(a0, b0, b1, b2, b3);
ctrl add14mod15(a1, b0, b1, b2, b3);
ctrl add13mod15(a2, b0, b1, b2, b3);
ctrl add11mod15(a3, b0, b1, b2, b3);
} deriving gate
The above implementation keeps input unchanged. That is, gate maps However, a unitary gate is preferred sometimes. It can be built with the following circuit
The box in the middle of the figure represents a gate, i.e., Note that , and does not always exist for any . Also, it does not always possible to build the unitary form since the modular multiplication may not be reversible. This circuit is implemented with the following isQ program
// |a>|b> -> |b>|a>
procedure swap4(qbit a0, qbit a1, qbit a2, qbit a3, qbit b0, qbit b1, qbit b2, qbit b3) {
SWAP(a0, b0);
SWAP(a1, b1);
SWAP(a2, b2);
SWAP(a3, b3);
} deriving gate
// |a> -> |a*7(mod 15)>
procedure mul7mod15_u(qbit a3, qbit a2, qbit a1, qbit a0) {
qbit anc[4];
mul7mod15(a3, a2, a1, a0, anc[3], anc[2], anc[1], anc[0]);
swap4(a3, a2, a1, a0, anc[3], anc[2], anc[1], anc[0]);
inv mul13mod15(a3, a2, a1, a0, anc[3], anc[2], anc[1], anc[0]);
} deriving gate
Note that , i.e., .
Modular exponentiation
In a similar way, we can also build modular exponentiation () based on modular multiplication. Assume . Then, . The corresponding circuit is shown as follows.
As the above circuit contains modular multipliers, its cost is .
We implement such a gate where and with isQ:
// |p>|a> -> |a*7^p(mod 15)>
procedure pow7mod15(qbit p[], qbit a[4]) {
// 7^(2^0) = 7 (mod 15)
ctrl mul7mod15_u(p[0], a[3], a[2], a[1], a[0]);
// 7^(2^1) = 4 (mod 15)
ctrl mul4mod15_u(p[1], a[3], a[2], a[1], a[0]);
}
For bits other than the lowest two, the modular result is always 1, e.g., . Therefore, the corresponding modular multiplication gate would be a trivial identical gate.
Reference
-
Steven A. Cuccaro, Thomas G. Draper, et al. "A new quantum ripple-carry addition circuit." arXiv preprint quant-ph/0410184, 2004.
-
Y. Takahashi, S. Tani, and N. Kunihiro, "Quantum Addition Circuits and Unbounded Fan-Out." arXiv preprint 0910.2530, 2009.
-
D. Beckman, A. Chari, et al. "Efficient networks for quantum factoring." Physical Review A, 1996, 54: 1034-1063.