Transcript 1 - Electrical & Computer Engineering

Search for Universal
Ternary Quantum Gate Sets
with Exact Minimum Costs
Normen Giesecke, Dong Hwa Kim*, Sazzad
Hossain and Marek Perkowski
Department of Electrical Engineering, Portland State University,
FAB 160-05, 1900 SW Fourth Avenue,
Portland, Oregon, USA, E-mail: [email protected]
* Dept. of Instrumentation and Control Engn., Hanbat National University,
16-1 San Duckmyong-Dong Yuseong-Gu, Daejon, Korea, 305-719.E-mail:
[email protected]
Hierarchical Decomposition and
Synthesis of Ternary gates
Synthesis using Logic Blocks and Gates
Design of Logic Blocks and Gates
Mozammel
Khan, ISMVL
2007
This paper
Ternary Quantum Multiplexers
Ternary Muthukrishnan-Stroud Gates
Single-Qubit Rotation gates and 2-qubit Interaction gates
Soonchil Lee
et al, MVL J
2006
Circuit Structures for Ternary Logic
extend the structures for binary logic
a
b
c
d
0
e
a
FG ab
c
FG cd
-1
FG
-1
FG
Galois
Product
FG
(Galois
Product)-1
b
c
d
0
F = f (a,b,c,d)e
Binary Multi-Cube gate
Multivalued counterpart of the Multi-Cube gate
for any radix. FG is Feynman-Galois gate.
CD
AB 00
00 0
01 0
11 0
10 0
a
01 11 10
0 0 0
1
1
1
Symbol  stands for exor.
1
(ab)(cd) = acadbcbd
Kmap of function f(a,b,c,d) realized by the gate F = f(a,b,c,d) from above.
Toffoli-like 3-controlled gate
structure for Galois Field Sum of
Product Circuits
a
b
a
b
c
c
0
0
d
Galois
Product
Galois
Product
x
x
FG xd
(Galois
Product)-1
(Galois
Product)-1
0
0
A cascade of two 2-controlled Toffoli-like
gates for Modulo sum of minima type of
circuits
a
b
a
b
c
c
0
d
min-1
min
+1
0
min-1
min
(01)
0
Ternary Wave Cascade (Modsum
of ternary Maitra cascades)
a
a
a
b
b
b
0
c
F
0
-1
min
min
0
-1
max
max
c
c
0
d
max-1
max
modsum
c
min-1
min
modsum
Because these structures are used again and again, it
is definitely worthy to optimize their components
very well, even spending months of computer time.
0
0
0
Quantum Reversible Cascades with Ternary Quantum Multiplexers
Op. 4
A
A’
Op. 5
Operations for a
ternary system
Op. 6
B
Op. 1
0
Op. 7
Op. 2
1
Op. 8
Op. 3
2
Op. 9
B’
+0
+1
+2
01
02
12
Time

Reversible cascades are used to represent logic gates. The gates
themselves are realizable via quantum technologies.

Reversible cascades are not schematics; instead of being physical
representations, they are chronological.



Time flows from left to right
Gates are not physical gates; instead, they are electromagnetic pulses
applied to some group of quantum particles that change their bit
representation
This means that there cannot be a “feedback”; Gates cannot be
controlled by previous states that have changed.
Wire
Modulo Shift +1
Modulo Shift +2
Swap 0
1
Swap 0
2
Swap 1
2
The Muthukrishnan-Stroud Gate
A’=A
A
Operations for a
ternary system
+0
+1
+2
01
02
12
wire
B’
B
Wire
Modulo Shift +1
Modulo Shift +2
Swap 0
1
Swap 0
2
Swap 1
2
wire
operation
Two views of MS gate

A
B
2
operation
P
Q
Multi-valued representation is based on the Muthukrishnan-Stroud gate




It acts essentially as a multi-valued multiplexer
There is one control line, one input line, and one output line
When the control line qubit is at its highest order value (i.e., |2> in a
ternary system of |0>, |1>, |2>), it selects an operation to apply to the
input line
If the control line is at any other value, not the highest order value, the
multiplexer acts as a quantum wire and passes the input directly to output
Quantum Reversible Cascades cont.
A’=A
A
Operation 1
B
Operation 2
Operation 3
Time

+0
+1
+2
01
02
12
Wire
Modulo Shift +1
Modulo Shift +2
Swap 0
1
Swap 0
2
Swap 1
2
Based on the Muthukrishnan-Stroud gate, we use a generalized
multi-valued gate which we can implement via macros of the
Muthukrishnan-Stroud gate



B’
Operations for a
ternary system
It is similar to the Muthukrishnan-Stroud gate, except it can select
different operations for different control line values, rather than a
multiplexer that only operates when the control line is the highest
value
Ultimately we expect to see direct implementation of the generalized
ternary gate (GTG)
The operations used are multi-valued operators. The operators for
a ternary system are listed
Muthukrishnan-Stroud Gate
 Internally,
built from
Interaction gates and
rotations
What are the internals of the MS
Gate?
Sequence of X, Y and Z rotations
Schematic view of Muthukrishnan-Stroud Gate as
a controlled sequance of rotations in X, Y and Z
axes by arbitrary angles
X rotation
Y rotation
Z rotation
Use of interaction gate
X rotation
Y rotation
Z rotation
General case
rotations
Z
rotations
Z
rotations
Special cases are
cheaper
X rotation
Z
Y rotation
Z
General view of cascade for Dlevel circuits
rotations
rotations
rotations
Z
rotations
rotations
Z
rotations
Every multi-valued
quantum multiplexer can
be build like this
First two structures based on
cascaded quantum multiplexers
A
P
f3
f0
B
Q
f1
f4
f2
f5
f3
A
P
f4
f5
f0
f6
f1
f7
f2
f8
B
Q
One more structure based on
cascaded quantum multiplexers
A
fd
PA
fe
B
ff
fa
PB
fb
Z
fa11
|0>
PZ
fc
fb
fc
fg
fj
fm
fq
fh
fk
fn
fr
fi
fl
fp
fs
PR
Problem Formulation/Motivation

The system in ternary logic
A ternary output is specified

Goals:




Find a (quasi)-minimum circuit in a form of a cascade,
given input/output specification.
Introduction of minimal number of ancilla bits
(garbage/constant input)
Gates:

Only Generalized Ternary Gates (GTG) in series are used
for synthesis
Exhaustive Search: Why?




No experience and knowledge about the
space to search. Nothing was published
when this work started
To get a feeling what GTG are capable for
Straight forward process
A breadth-first search seemed a good start
Breadth first search (BFS)

BFS is a tree search algorithm used
for searching a tree, tree structure,
or graph.
1
2
5

The breadth-first-search begins at
the root node and explores all the
neighboring nodes. Then for each of
those nearest nodes, it explores their
unexplored neighbor nodes, and so
on, until it finds the goal.

There are 216 different GTG realizations
(63 operation combinations)
3
4
6
7
8
9
10
11
Breadth first search (BFS) cont.

216 different GTG realizations
A’
A
|0>
+0
+0
12
+0
+0
12
+0
+1
12
1. GTG Gate
2. GTG Gate
216. GTG Gate
A
B
|0>
A
B
+0
+0
+0
+0
+0
+0
+0
+0
+0
A
B
|0>
R
R
1.GTG - 1.GTG - 1.GTG
A
B
+0
+0
+0
+0
+0
+0
+0
+0
+1
R
1.GTG - 1.GTG - 2.GTG
…
A
B
|0>
A
B
12
12
12
12
12
12
12
12
12
R
216.GTG - 216.GTG - 216.GTG
Exhaustive Search: Example

A
B
B
A


This example gives the
implementation of a 2-qudit
ternary SWAP Gate
The example begins on the first
multiplexer and ensue the first
truth table. Continuing that way,
the last of the truth tables shows
the results of the multiplication of
the truth tables of the current
multiplexer with the one before
The third truth table shows the
solution of the 2-qudit ternary
SWAP
Exhaustive Search: Example cont.

2-qudit SWAP gate
+1
+2
A
B
B
+2
02
+1
12
A
01
A
0
0
0
1
1
1
2
2
2
A
B
0
1
2
0
1
2
0
1
2
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
2
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
1
0
0
0
1
1
0
0
0
1
0
0
0
0
0
1
2
0
0
0
0
1
0
0
0
0
2
0
0
0
0
0
0
0
1
0
0
2
1
0
0
0
0
0
0
0
1
0
2
2
0
0
0
0
0
0
0
0
1
A
0
0
0
1
1
1
2
2
2
A
B
0
1
2
0
1
2
0
1
2
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
1
0
0
0
0
0
0
2
1
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
1
0
1
2
0
0
0
0
1
0
0
0
0
2
0
0
0
0
0
0
1
0
0
0
2
1
0
0
1
0
0
0
0
0
0
2
2
0
0
0
0
0
0
0
0
1
A
0
0
0
1
1
1
2
2
2
A
B
0
1
2
0
1
2
0
1
2
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
2
0
0
0
0
0
0
1
0
0
1
0
0
1
0
0
0
0
0
0
0
1
1
0
0
0
0
1
0
0
0
0
1
2
0
0
0
0
0
0
0
1
0
2
0
0
0
1
0
0
0
0
0
0
2
1
0
0
0
0
0
1
0
0
0
2
2
0
0
0
0
0
0
0
0
1
Ternary Quantum Logic:
Exhaustive Search
Iterative deepening search
Iterative deepening search l =0
Iterative deepening search l =1
Iterative deepening search l =2
Iterative deepening search l =3
Iterative deepening search

Number of nodes generated in a depth-limited search to depth
d with branching factor b:
NDLS = b0 + b1 + b2 + … + bd-2 + bd-1 + bd


Number of nodes generated in an iterative deepening search to
depth d with branching factor b:
NIDS = (d+1)b0 + d b^1 + (d-1)b^2 + … + 3bd-2 +2bd-1 + 1bd
For b = 10, d = 5,



NDLS = 1 + 10 + 100 + 1,000 + 10,000 + 100,000 = 111,111
NIDS = 6 + 50 + 400 + 3,000 + 20,000 + 100,000 = 123,456
Overhead = (123,456 - 111,111)/111,111 = 11%
Properties of iterative
deepening search
Complete? Yes
 Time? (d+1)b0 + d b1 + (d-1)b2 + …

+ bd = O(bd)
 Space? O(bd)

Optimal? Yes, if step cost = 1
Summary of algorithms
Multiplexer Implementation

Multiplexer implementation for two variables is in fact
straightforward

Here we also introduce the idea of mirroring





After a constant input line performed its operation, it can be reused.
But for before it needs to be reset
Mirroring serves this purpose well, at the cost of some additional
gates.
By introducing N additional gates, where N is the number of gates
required for implementation, an inverse set of gates can be
implemented to realize the original set of inputs on the output
Notice that each and every operation (both swap and shift
operations) have a “conservative” map or inverse operation
Inverse Gates

Realization of the ternary Toffoli Gate as an example for
mirroring:
Mirroring gates
A
R=A
B
S=B
|0>
|0>
+1
+1
+2
+2
Z
C
Q
where Z{+1,+2,01,02,12}
Operations for a
ternary system
Conservative or Inverse
Operations
+0
+1
+2
01
02
12
+0
+2
+1
01
02
12
Wire
Modulo Shift +1
Modulo Shift +2
Swap 0
1
Swap 0
2
Swap 1
2
Wire
Modulo Shift +2
Modulo Shift +1
Swap 0
1
Swap 0
2
Swap 1
2
Limitations on the Goal Function
Balanced function
A\B
0
1
2
0
0
1
2
1
1
2
0

2
2
0
1

Unbalanced function
A\B
0
1
2
0
0
0
0
1
0
1
2
Because the operation of a GTG gives outputs
that are always conservative, the goal function
must be conservative with respect to the input
variable
Functions that are NOT balanced cannot be
directly implemented; they can, however, be
implemented if we introduce an ancilla bit

2
0
2
1

n
( p )!
A
[( p n 1 )!)] p

An ancilla bit is simply an input line that is a
known constant e.g. “|0>”
Also referred to as “garbage input.” Unless
restored using the property of reversibility, it will
result in a “garbage output”
Formula to calculate the number of balanced
functions for a given radix and number of
qudits (p=radix; n=number of qudits)
Implementation with more Input
Variables

A
RA
B
SB
C
 NOT C , if A  2  B  2
Q
C otherwise




In the previous examples, the input
was two variables.
Here we see an example of a 3variable problem, the ternary
Toffoli Gate
The Realization uses MS Gates and
needs the minimum cost of 4 single
qudit operations.
The Toffoli gate is a balanced gate and
therefore no ancilla bit is needed.
Karnaugh map and realization of the ternary Toffoli gate:
AB\C
00
01
02
10
11
12
20
21
22
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
2
2
0
2
1
0
2
1
0
2
0
A
B
A
B
C
C
+2
01
+1
01
Results – The MIN and MAX Gate



The following two gates are the MIN and MAX gates
They can be used to build up a PLA like structure (using Mod-Sum)
Their drawback is the required ancilla qudit, but contemporary circuit CAD
systems may be reused to start building quantum circuits out of MIN/MAX
gates
2-qudit ternary MAX gate
A
B
A
MAX
A
B
B
B
MAX (A,B)
|0>
A
+1
12
+1
+1
|0>
+1
R
12
2-qudit ternary MIN gate
A
B
|0>
A
MIN
A
A
B
B
B
MIN (A,B)
+1
|0>
02
01
+2
12
R
+2
Results – The Feynman Gate



The Feynman Gate was found to be universal to construct complete
quantum circuits.
There is a second version, which is called ternary Feynman Galois gate
Their realizations using GTG are shown below on the right-hand side
2-qudit ternary Feynman gate (Controlled-NOT)
A
B
R
 NOT B, if A  2
S 
 B otherwise
A
R
B
 NOT B, if A  2
S 
 B otherwise
+1
2-qudit ternary Feynman (Galois) gate
A
A
R
B
A 3 B
B
R=A
+1
+2
S=
A B
Results – 2-qudit SWAP Gate



The SWAP gate exchanges a pair of inputs to the output.
It has no counterpart in the classical binary logic because the
crossing of electrical wires, for instance within 2 layers of
metallization, is applied wherever it is needed and no special gate
is required for this action.
There are no real wires and thus a “copying” or “cloning” gate is
required to perform this
2-qudit ternary SWAP gate; Symbol (a), Input/Output table (b), Realization (c)
A
B
B
A
(a)
A
0
0
0
1
1
1
2
2
2
B
0
1
2
0
1
2
0
1
2
A’ B’
0 0
1 0
2 0
0 1
1 1
2 1
0 2
1 2
2 2
(b)
+1
A
B
A’
+2
+2
02
+1
12
01
(c)
B’
Results – 2-qudit Inverse SWAP Gate



Similar to the SWAP gate is the Inverse SWAP gate that we proposed
The pairs of inputs and outputs are also exchanged but in addition
the order of the output is flipped around.
It is expected that it is universal as the 2-qudit SWAP gate.
B
B
A
(a)
B
0
1
2
0
1
2
0
1
2
A’ B’
0 0
1 0
2 0
0 1
1 1
2 1
0 2
1 2
2 2
(b)
Flipping
A
A
0
0
0
1
1
1
2
2
2
Swapping
NEW 2-qudit ternary Inverse SWAP gate; Symbol (a), Input/Output table (b), Realization (c)
A’ B’
2 2
1 2
0 2
2 1
1 1
0 1
2 0
1 0
0 0
+2
A
A‘
+1
01
B
+1
12
+2
02
(c)
B‘
Results – Ternary Toffoli Gate





Toffoli is viewed as universal, and thus another important gate.
Its realization using GTG is possible without an ancilla qudit.
From the Toffoli gate, which is a 2 - Controlled-Not, it is
possible to build up an n-qudit – Controlled-Not.
The realization requires only 4 segments and 4 single qudit
operations. It seems to be the best realization found so far,
compared to the literature
No mirroring is needed.
3-qudit ternary Toffoli gate (2-Controlled-NOT); Symbol (a), Realization (b)
A
R
B
S
C
 NOT C , if A  2 and B  2
Q
C otherwise

A
B
A‘
B‘
C
C‘
+2
(a)
+1
01
(b)
01
Some New Gates Invented by
Exhaustive Search

Using the exhaustive program I found the
following:
1. all 2-qudit gates can be realized within 4 segments
(4 quantum multiplexers).
2. 1680 out of the 19683 2-qudit gates need no additional
ancilla qudit to be realized, the rest do
3. the number of single qudit operations at the multiplexers
is not higher than 6 for all of the 2-qudit gates
4. The exhaustive algorithm produced a library where the
realization of all 2-qudit gates, their structure and single
qudit operations are stored. This data can be used for a
CAD system for quantum logic circuits.
Gates used in GA



Not all 216 Generalized Ternary Gates (GTG) were
used
Yen et al. showed that 12 Generalized Ternary
Gates (GTG) out of the 216 GTG are universal and
sufficient to realize quantum gates
The Genetic algorithm used only those 12 GTG,
and the single qudit operations (+1,+2,01,02,12)
What was invented – 2-qudit Feynman

The solutions found by the GA have higher cost
2-qudit ternary Feynman gate (Controlled-NOT)
A
B
R
 NOT B, if A  2
S 
 B otherwise
A
R
B
S
+2
+2
2-qudit ternary Feynman (Galois) gate
A
R
A
02
02
R
B
S  A 3 B
B
+2
+2
S
+1
+2
Results – 2-qudits SWAP


The nature of the GA can be seen again. The solution that were
found are not optimal
The found result can be minimized.
2-qudit ternary SWAP gate; Symbol (a) and Realization found by the GA (b)
(a)
A
B
B
A
(b)
+1
12
A
+1
B
+1
+1
+2
+1
+1
+2
B
+1
+1
+1
+1
A
+1
+1
+1
Results – 2-qudits Inverse SWAP

The GA found a realization for the new proposed Inverse
SWAP gate
2-qudit ternary Inverse SWAP gate; Symbol (a) and GA realization (b)
(a)
A
B
B
A
(b)
+1
A +2
B
02
^
A
E
+2
V
+2
+2
+2
+1
+1
+2
+2
+1
+1
W
A
C
+2
N
+2
+2
T
R
+2
+2
+2
+2
+1
+2
+1
P
]
+1
P
G
N
A
+1
+1
I
+2
+2
I
L
Q
P
B
T
Genotype: p^ppAEppVppWppACppNppTppRppPpp]ppIppPppGppNppIppLppQppPppTp
Results cont.
The 3-qudit SWAP gate was not possible to find with the
exhaustive search and therefore indicates the ability of the GA
The 3-qudit SWAP exchanges the 3 input to the output
There are Ns Number of SWAP gates for Nq qudits



N S  Nq 1
3-qudit ternary SWAP gate; Realization (a) and Symbol (b)
A
B
B
C
C
A
(a)
(b)
+1
+2
A
+1
B
+1
B
02
+1
12
+1
+1
+1
+2
01
C
+1
+1
C
+1
02
+1
A
12
01
Improvements on the GA

The GA is restricted to an small number of
the 216 different GTGs

Therefore analyze the GTGs in the 2-qudit
library and use those for the GA

Automation of the GA:

e.g. If diversity of the population goes down:


Change of the mutation ratio (erasure/addition/flipping)
or increase the mutation probability
Conclusion
Exhaustive Search
Benefits







Toffoli Gate is realized in 4 GTGs
An algorithmic method was given to implement ternary quantum
logic gates using the principles of MS gates and GTG
Exhaustive search for 2-variable goal functions results in maximum of
4 levels of multiplexer, and one ancilla bit.
Realizations of well known universal quantum gates for 2- and 3qudit were found and verified.
Formula to calculate the number of balanced functions for a given
radix and number of qudits was presented.
Results for all 2-qudit quantum gates are now available.
The gates discovered in this thesis can be used as building block in
higher-level synthesis methods, as presented in the literature.
Drawbacks

Limitations with respect to number of levels and qudits are given.
Genetic Algorithm
Benefits




A realization for a 3-qudit SWAP gate was found
A second algorithmic method was given to implement ternary
quantum logic gates using the principles of MS gates and 12 GTGs
It supports the search for quantum gates where the exhaustive
search is not applicable anymore
Serves as a foundation for future research
Drawbacks


There is no guarantee to find a solution
If a solution was found it may not need to be minimal with respect
to the number of levels and single qudit operations
In Conclusion

Presented today were two software
programs for logic synthesis for quantum
realizable gates:
Exhaustive Search
 Genetic Algorithm


We believe now that the best method is
combining Iterative Deepening Depth First with
A* Algorithm and recognizing “easy functions”
on lower levels of the tree.
References






Ch. H. Bennett and R. Landauer, "The Fundamental Limits of
Computation", Scientific American, July 1985, pp. 38-46.
R. Landauer, "Irreversibility and heat generation in the
computational process"; I.B.M. Journal of Research and
Development, 5 (1961), pp. 183-191.
A. Muthukrishnan and C R. Stroud, Jr., “Multivalued Logic
Gates for Quantum Computation”, Physical Review A, vol. 62,
no. 5, 2000, pp. 052309/1-8
Edward Fredkin, “A physicist’s Model of Computation”,
Proceedings of the XXVIth RENCONTRE DE MORIOND, 1991
Savoie, France
http://www.waters.com
http://aemc.jpl.nasa.gov/activities/mms.cfm
Outline
Introduction
Why Quantum Logic?
 Reversible Logic
 A Brief Background

Quantum Logic Gate Synthesis Method
Exhaustive Search
 Comparison to GA

Conclusion
Why Quantum Computing?

Moore’s law will reach fundamental limits within the
coming future





Transistor size approaching single atom
Power density problem
Quantum phenomenon (tunneling, etc.)
Many other issues..
Computationally, quantum computing is exponentially
more powerful

Due to quantum phenomenon, for N ternary qudits (a “quantum
bit” with three states), 3^N states can be computed simultaneously.
Reversible Logic and
Quantum Computing

How does reversible logic relate?


In addition to being a method of power reduction,
reversibility is an intrinsic property of quantum
computing.
What is Reversible Logic?



Logic where no information is lost between input
and output.
Given an output, a the single distinct input can
be derived.
A special case is the “permutative” logic where the
outputs are simply some permutation of the inputs.
What is Reversible Logic?



Logic where no information is lost between input and output.
Given an output, a the single distinct input can be derived.
A special case is the “permutative” logic where the outputs are
simply some permutation of the inputs.
Reversible Logic
Input
A
0
0
1
1

Output
A’
0
0
1
1
B
0
1
0
1

B’
0
1
1
0
Non-Reversible Logic
Input
A
0
0
1
1
B
0
1
0
1

Output
?
Example: Permutative logic
Non-Reversible Logic

R
0
1
Reversible Logic
Example: Standard
AND/OR/EXOR Logic
Can you give example of reversible logic
that is not permutative? This would require
different numbe of input and output signals,
we discussed the interaction gate in my
class.
What is Reversible Logic?
Reversible Logic
Input
A
0
0
1
1
AB A’B AB’
0 0 0
0 1 0
0 0 1
1 0 0
B
0
1
0
1
Permutative Logic
Input
A
0
0
1
1
Output
A
0
0
1
1
B
0
1
0
1


Output

?
Example: Feynman Gate
One-to-One mapping
between input and output
(so called bijectiv function)
Non-Reversible Logic

R
0
1
Example: Interaction Gate
(2-input, 4 output)
One can derive the input by
knowing the output
Permutative Logic


Non-Reversible Logic
Reversible Logic

AB
0
0
0
1
A’ B’
0 0
0 1
1 1
1 0
B
0
1
0
1
Input

Output

Example: Standard
AND/OR/EXOR Logic
It is not possible to derive
the input only from the
output
Quantum Logic Synthesis
Logic synthesis for quantum computing can be divided into
two main categories:
 Synthesis using Purely Quantum Gates



Takes into account the effects of quantum phenomenon such as
superposition, entanglement, etc.
It is due to quantum phenomenon that for N qudits, 3^N states can be
computed simultaneously in case of ternary quantum circuits.
Synthesis of Permutative functions, Binary or Multiple-valued




This area has stronger ties with existing logic synthesis methods, as it
deals solely with basic quantum states |0> and |1> (for binary).
Ultimately, the Hilbert space transformations and quantum logical
manipulations from purely quantum gate logic must be related to some
basic state forms for data input and output.
Binary logic is a solution, but because of the nature of quantum
technology, it is possible to directly realize gates that are characterized
in multi-valued logic.
Permutative functions are similar to an identity matrix, where the rows
are permutated
Quantum Logic Synthesis
Logic synthesis for quantum computing can be divided into
two main categories:
Synthesis using Purely Quantum Gates


Takes into account the effects of quantum phenomenon such as
superposition, entanglement, etc.
It is due to quantum phenomenon that for N qubits, 2^N states can be
computed simultaneously in case of binary quantum circuits.
Synthesis of Permutative functions, Binary, Ternary or Multiple-valued



This area has stronger ties with existing logic synthesis methods, as it
deals solely with basic quantum states |0>, |1>.
Ultimately, the Hilbert space transformations and quantum logical
manipulations from purely quantum gate logic must be related to some
basic state forms for data input and output.
Binary logic is a solution, but because of the nature of quantum
technology, it is possible to directly realize gates that are characterized in
multi-valued logic.
Additional Slides in case of questions
Ternary Quantum Logic:
Synthesis using a Genetic
Algorithm
Genetic Algorithm: Why?



Exhaustive Search was a good starting
point for synthesis
However, the limits were the amount of
cascaded multiplexers, the number of
qudits and the exhaustive time
Quantum gates with more than 2-qudits
inputs are possible e.g. 3-qudit SWAP
Definition of Genetic Algorithm

GA is another search technique used in various fields e.g.







Mobile communications infrastructure optimization
Electronic circuit design and
many more…
To find approximate solutions to optimization and search
problems
GA is one of the evolutionary algorithms and is based on
biological evolution theory.
It is implemented as a computer simulation in which a
population of abstract representations (called chromosomes)
of candidate solutions (called individuals) to an optimization
problem evolves toward better solutions.
Individuals can be represented as strings of 0s and 1s or
strings of characters
011001101010
ACGHIKL
Pseudo Code of GA


The Pseudo code shows the general structure of a
GA with
After the initialization and first evaluation begins
the life cycle
01:
02:
03:
04:
05:
06:
07:
08:
09:
10:
t ← 0;
initialize(P(t));
evaluate(P(t));
/* initial population */
/* evaluate population */
while (not termination-condition) do /*begin of the life cycle*/
t ← t + 1;
(t) ← select(P(t − 1));
/* selection operator */
(t) ← recombine((t));
/* crossover operator */
P(t) ← mutate((t));
/* mutation operator */
evaluate(P(t));
/* evaluate fitness */
end while
Selection methods – Roulette Wheel



Three fitness proportional selection methods are
implemented
The individuals get a fitness value and upon this
they get a larger or smaller section on the roulette
wheel
A random number is generated (the ball on the
roulette wheel) and the section the is hit by the
ball is chosen for recombination
S7:
13%
S8:
8%
S1:
23%
S6:
14%
S5:
12%
S4:
16%
S3:
S2: 5%
9%
Selection method –
Stochastic Universal Sampling




Second selection method is SUS
It is similar to the Roulette Wheel. Every individuals gets a
section on the roulette wheel related to their fitness
Another wheel is laid above the Roulette Wheel and it is
turned around by a random value
The individuals selected by the second wheel are chosen for
recombination
S8:
8%
S7:
13%
S1:
23%
S6:
14%
S5:
12%
S4:
16%
S3:
S2: 5%
9%
S7:
13%
S8:
8%
S1:
23%
S6:
14%
S5:
12%
S4:
16%
S3:
S2: 5%
9%
Selection method –
Tournament Selection


The last implemented selection method is the
Tournament Selection
Individuals are chosen randomly for a tournament
(with k individuals) and the one with the highest
fitness of the Tournament is chosen for
recombination
Population
S8
S1 S4
S7
S6 S5
S2


S3
k Tournament
individuals
Individual with
highest fitness
S1
S6
S3
If k is chosen to big  high selection pressure
 “good” individuals are preferred to much
S3
Implemented crossover methods





Crossover is the primary operator in the GA
New Individuals are produced out of selected parents
Fragments of chromosomes are exchanged and thus information is
exchanged between potential solutions
The location were the crossover is applied is chosen randomly.
Two methods are implemented:


1- point crossover
0 1 0 1 1 0 1
0 1 1 1 1 0 0
0 1 0 1 0 0
0 1 1 1 1 1 0 1
2- point crossover
0 1 0 1 1 0 1
0 1 1 1 1 0 0
0 1 1 1 1 10 0
0 1 01 0 1
Two Mutation methods
The secondary operator is the mutation. It inserts new
or lost information into the population. It is performed
seldom otherwise the GA degenerated to a complete
random search.
Three
method are implemented:
Flip mutation
Erasure of a gene
Addition of a gene
0 1 0 1 1 0 1 0 0
0 1 0 1 1 0 1 0 0
0 1 0 1 1 0 1 0 0
0 1 1 1 1 0 1 0 0
0 1 0 1 1 1 0 0
0 1 0 1 1 1 0 1 0 0
Extra Slide – Structure of an Ion Trap
ION TRAP realization
End Cap
End Cap
Detection
Ion Injection
Ring electrode
V
The principle of the trap is to store the ions in a device
consisting of a ring electrode and two end cap electrodes.
The ions are stabilized in the trap by applying a RF voltage
on the ring electrode. For maximum efficiency, the ions
must be focused near the centre where the trapping fields
are closest to the ideal and the least distorted - maximizing
resolution and sensitivity. This is achieved by introducing a
damping gas (99.998% helium) that collisionally cools
injected ions, damping down their oscillations until they
stabilize.
Make it to3 or 4 slides,
letters are too small here
~
1)
2)
Ions, or charged atomic particles, can be confined and suspended in free
space using electromagnetic fields. Qubits are stored in stable electronic
states of each ion, and quantum information can be processed and
transferred through the collective quantized motion of the ions in the trap
(interacting through the Coulomb force). Lasers are applied to induce
coupling between the qubit states (for single qubit operations) or coupling
between the internal qubit states and the external motional states (for
entanglement between qubits). The fundamental operations of a quantum
computer have been demonstrated experimentally with high accuracy (or
"high fidelity" in quantum computing language) in trapped ion systems, and a
strategy has been developed for scaling the system to arbitrarily large
number of qubits by shuttling ions in an array of ion traps. This makes
trapped ion system one of the most promising architectures for a scalable,
universal quantum information processor.
1)
=http://www.waters.com
2)
=http://aemc.jpl.nasa.gov/activities/mms.cfm
Extra Slide – How does Logic Loss
introduce Power Loss?
Billiard Ball Model

In the “Billiard Ball Model” of reversible
computing, logic operations are
represented by collisions between billiard
balls.

Suppose we have two billiard balls with
some velocity vectors that will collide, as
shown.

At some given time later, knowing their
positions and velocities, one can derive the
original state of the system. This is an
example of reversible logic.

In contemporary irreversible logic, some
information is lost, preventing the
reversibility of the system. This also results
in a loss of energy to the system.
reversible
irreversible
Extra Slide – Bloch Sphere
z
z
|0>
|0>
120°
180°
|1>
120°
y
180°
y
120°
x
x
|2>
|1>

Dirac Notation Quantum logic states are often represented in Dirac notation:





i.e., A|0> + B|1> + C|2>
where quantum states |0>, |1> and |2> are representative of superpositional states as
weighted by A, B and C, such that |a|2, |b|2 and |c|2 are the probabilities of measurement
of basic quantum state |0>, |1> or |2> (and |a|2 + |b|2 + |c|2 = 1).
A multi-valued Bloch sphere can be described as a Bloch sphere for which more
than two states have been defined as additional logic states, such as given by
Figure b.
It is important to understand that the number of values of the logic is formally
related to the measurement process and not to what happens in Hilbert space.
Similarly as one can create a base of measurement of |0> and |1>, a base of |0>,
|1> and |2> can be created by measuring at angles 120° apart. This may be
difficult to achieve for particular technologies, but is possible in principle and does
not contradict principles of quantum mechanics.
Structure of an Ion Trap
•The principle of the trap is to store
the ions in a device consisting of a
ring electrode and two end cap
electrodes.
ION TRAP realization
End Cap
End Cap
Detection
Ion Injection
Ring electrode
V
~
1)
•The ions are stabilized in the trap
by applying a RF voltage on the ring
electrode.
•For maximum efficiency, the ions
must be focused near the centre
where the trapping fields are closest
to the ideal and the least distorted maximizing resolution and
sensitivity.
2)
•This is achieved by introducing a
damping gas (99.998% helium) that
collisionally cools injected ions,
damping down their oscillations until
they stabilize.
• Ions, or charged atomic particles, can be confined
and suspended in free space using electromagnetic
fields.
Structure of
an Ion Trap
• Qubits are stored in stable electronic states of each
ion, and quantum information can be processed and
transferred through the collective quantized motion of
the ions in the trap (interacting through the Coulomb
force).
• Lasers are applied to induce coupling between the
qubit states (for single qubit operations) or coupling
between the internal qubit states and the external
motional states (for entanglement between qubits).
• The fundamental operations of a quantum computer
have been demonstrated experimentally with high
accuracy (or "high fidelity" in quantum computing
language) in trapped ion systems, and a strategy has
been developed for scaling the system to arbitrarily
large number of qubits by shuttling ions in an array of
ion traps.
• This makes trapped ion system one of the most
promising architectures for a scalable, universal
quantum information processor.
1)
=http://www.waters.com
2)
=http://aemc.jpl.nasa.
gov/activities/mms.cfm
Conclusions on GA

A second algorithmic method was given to implement
ternary quantum logic gates using principle MS gates, GTG
and single qudit operations

Limitations with respect to the small amount of principle
gates are given.

The GA showed that solutions on 3 qudits (3-qudit SWAP)
can be realized.

Realizations for some universal well known quantum gates
for 2- and 3 qudits were presented
Conclusion on Exhaustive Search

An algorithmic method was given to implement ternary quantum
logic gates using the principles of MS gates and GTG

Limitations with respect to number of levels and qudits are given.

Exhaustive search for 2-variable goal functions results in maximum
of 4 levels of multiplexer, and one ancilla bit.

Realizations of well known universal quantum gates for 2- and 3qudit were found and verified.

Formula to calculate the number of balanced functions for a given
radix and number of qudits was presented.

The gates discovered in this thesis can be used as building block in
higher-level synthesis methods, as presented in the literature.
References
Ch. H. Bennett and R. Landauer, "The
Fundamental Limits of Computation", Scientific
American, July 1985, pp. 38-46.
reversibility

R. Landauer, "Irreversibility and heat generation
in the computational process"; I.B.M. Journal of
Research and Development, 5 (1961), pp. 183191.
Reversibility and
thermodynamic

A. Muthukrishnan and C R. Stroud, Jr.,
“Multivalued Logic Gates for
Quantum Computation”, Physical Review A, vol.
62, no. 5, 2000, pp. 052309/1-8
Multi-valued
quantum gates in
ion trap
technology
