A Reversible Ternary Adder for Quantum Computation
Takahiko Satoh1 ∗ Shota Nagayama 2 † Rodney Van Meter 1 ‡1Faculty of Environment and Information Studies, Keio University
5322 Endo, Fujisawa, Kanagawa, 252-8520, Japan2
Faculty of Policy Management Studies, Keio University
5322 Endo, Fujisawa, Kanagawa, 252-8520, JapanAbstract. We present the design of a reversible ternary carry-ripple adder suitable for use with qutrits. Our designis based on the binary reversible adder of Vedral, Barenco and Ekert, and uses 3n + 1 qutrits to add two n-trit
numbers, with carry in and carry out. We assume a “rotor” gate as our basic gate.

1Introduction

Qutrits, ternary analogs to binary qubits, have been proposed for quantum communication, including quantum key
distribution (QKD), and have been recognized as giving good
spatial density for information storage [1, 2, 3]. Qutrits are
three-state elementary quantum systems, defined by a basis
set of three vectors. Much as qubits are defined using a basis
set commonly written as |0i and |1i, we define the basis set
for ternary arithmetic to be |0i, |1i, and |2i.
For any sort of complex computation on qutrits, we expect arithmetic subroutines to be an important component.
Building blocks, including a full adder, have been defined [4],but larger, more complete circuits are also necessary. Therefore, we have designed a reversible ternary adder, based on
the structure of the VBE carry-ripple adder circuit by Vedral,
Barenco and Ekert [5]. Our circuit involves no uniquely quantum operations, and would be usable in a classical ternary
logic context, which has a long if not exactly mainstream history [6, 7].

2We need a reversible ternary gate as our basic logic gate.
We define a gate R we call the rotor. It takes 0 → 1, 1 → 2,and 2 → 0. Applying this gate three times to any trit will bringits state back to its original position. The unitary transformand graphical symbol for R are shown in Figure 1.
We also need a two-qutrit gate. The C-R gate, or control-Rgate, rotates the second qutrit (the target qutrit) only if the firstqutrit (the control qutrit) is 2, as shown in Figure 2. Similarly,
the C-C-R gate rotates the third qutrit (the target qutrit) only
if both of the control qutrits are 2.
2.1

SUM gate

The purpose of the ternary SUM gate, or block of gates, isthe same as the purpose of the VBE binary SUM gate. Thisgate takes (aj , bj , cj → (a, cj + aj + bj , cj ). aj and cj are
undisturbed, while bj becomes the sum of the three, modulo 3.
cj will be used as the carry from qutrit to qutrit in our overall
circuit. The circuit for SUM is shown in Figure 3.

1 0 0 0 0 0 0 0 00 1 0 0 0 0 0 0 00 0 1 0 0 0 0 0 00 0 0 1 0 0 0 0 00 0 0 0 1 0 0 0 00 0 0 0 0 1 0 0 00 0 0 0 0 0 0 1 00 0 0 0 0 0 0 0 10 0 0 0 0 0 1 0 0

Concepts and Building Blocks

Our goal is to make a circuit that takes two n-qutrit numbersa and b and outputs a and a + b. In the following, we write thestate of an n-qutrit register as a = an−1 3n−1 + an−2 3n−2 +... + a1 3 + a0 . Here, a0 is the lowest-order qutrit, and an−1is the highest-order qutrit. Because our work is independentof the quantum nature of the trits, we dispense with the ket
notation for the rest of this paper.

RC−R gate figure

C−R gate matrix∗satoh@sfc.wide.ad.jp† kurosagi@sfc.wide.ad.jp‡ rdv@sfc.wide.ad.jp

10001

100

R matrix

RR figure

Figure 1: The rotor gate.

S U M
57/

0

Figure 2: The control-rotor gate.

cj

RR

R

aj

R

R

Rbj

R

R

R

R

Figure 3: The SUM gate.

RR

cj

R

RR



CARRYajR

R

R

bj



R

;

c j+1R

R

R

R

R

R

R

R

R

R

R

R

Figure 4: The CARRY gate.

c 0 =0c 1 =0b1c 2 =0

a1
aaan

b1

ADDER

CARRY

SUM

b2an

a0

C 2 =0
CARRY

a2

SUM

a1

C 1 =0CARRY

a1CARRY

a0SUM

CARRY

b0

C 0 =0
CARRY

a0b1

b2

b2c P=0c P=0
R

R

R

R

R

R

R

R

SUM

b P

bn
C n =0

CARRY

a P

a+ba+bSUM

CARRYbP

bn

CARRY

a P

C n−1=0b P =0

Figure 5: The complete ternary carry-ripple adder.
2.2

CARRY gate

ical Review Letters, 92(9):097901, 2004.

The purpose of the ternary CARRY gate is also the same as
the purpose of the binary CARRY gate. CARRY outputs thecarry cj+1 which is calculated when cj , aj and bj are added.

[2] Carlton M. Caves and Gerard J. Milburn. Optics Communications, 179(1):439–446, 2000.

3[3] S.J. Devitt, A.D. Greentree, and L.C.L. Hollenberg.
Quantum Information Processing, 2007. Arxiv preprint
quant-ph/0511084; to appear.

The Reversible Ternary AdderOur complete adder involves two n-qutrit registers, a andb, and n ancillae c, used to hold the intermediate carry values
during the computation, and an additional qutrit bn+1 whichholds the carry out, or new high digit of the b register. Theadder leaves a undisturbed and takes b → a+b. The c ancillae
must be returned to their original zero state. As in the original
VBE adder, the registers are interleaved, and the CARRY andSUM are arranged so that the carry qutrits are calculated inascending order, a structure known as a carry-ripple adder.
The depth and total complexity of our circuit are both O(n).
Both the CARRY and SUM blocks for ternary logic are substantially longer than their binary equivalents. The exact performance will depend on the construction of three-qutrit gates.

References[1] Andrew D. Greentree, S. G. Schirmer, F. Green, Lloyd
C. L. Hollenberg, A. R. Hamilton, and R. G. Clark. Phys-[4] D. M. Miller, G. W. Dueck, and D. Maslov. Proceedings of 34th International Symposium on Multiple-Valued
Logic, pages 74–80, 2004.
[5] Vlatko Vedral, Adriano Barenco, and Artur Ekert. Phys.
Rev. A, 54:147–153, 1996.
[6] Brian Hayes. American Scientist, 89(6):490–495, 2001.
[7] Roy D. Merrill Jr. In DAC ’65: Proceedings of the SHARE
design automation project, pages 6.1–6.17, New York,NY, USA, 1965. ACM Press.