Transcript Seminar (PPT, 903.0 kibibytes)

Cost Metrics for
Reversible and Quantum
Logic Synthesis
Dmitri Maslov1
D. Michael Miller2
1Dept.
of ECE, McGill University
2Dept. of CS, University of Victoria
1
Outline
•
•
•
•
Introduction (background, motivation)
Motivation for our research
Definitions and Problem Statement
Our solution: Pruned Prioritized Breadth-first
Search
• Results and Conclusions
2
Introduction
Quantum bit could be a state of a single proton in a
static magnetic field (magnetic spin). For a fixed
proton state of a magnetic spin is known to be
probabilistic, in other words, only the measurement
tells what was the state.
a|0>+b|1> - state of a proton.
|a| - probability of finding the
proton in a lower energy state
|b| - probability of finding the
proton in a higher energy state
.
.
3
Introduction
Quantum n-bit system is described by a vector of
length 2n with complex coefficients, called amplitudes.
a 00... 0 0,0,...,0  a 00... 01 0,0,...,0,1  ...  a11... 1 1,1,...,1
Quantum computation is done through multiplication
of the state vector by 2nx2n unitary matrices.
Rather than working with huge matrices, we consider a
circuit computation model. This saves space and
illustrates what happens better.
4
Introduction
Quantum computation features:
1. Quantum errors. At any time state |0> can spontaneously
change to the state |1> and vice versa.
2. Measurement kills the system.
3. Copying is impossible. No fan outs.
4. Computation lifetime is limited by approximately 2 sec.
5. Limited number of basic (elementary) gates.
5.5. All the computations are reversible.
6. Scaling is difficult.
7. Quantum superposition. Quantum system with n qubits is
associated with presence of 2n complex numbers.
8. Quantum parallelism. It is possible to compute a Boolean
function on all the possible inputs simultaneously.
5
Introduction
IBM research group, 2001: 7-qubit quantum processor.
6
Introduction
Quantum key distribution.
Quantum random number
generator.
Main features
Main features
•First commercial quantum key
distribution system
• PCI card
• random bit rate of up to 16Mbps
•Key distribution distance: up to 100 km
7
www.idquantique.com
Problem Statement
• Find optimal NCV circuits for the 8! 3-variable
quantum Boolean (reversible) functions.
• Optimal can be based on gate count or on total gate
cost for some costing model.
• Gate count is just a cost model where all gates have
cost 1.
8
Motivation
• NOT, CNOT, controlled-V and controlled-V+ (NCV) gates are
elementary and well studied blocks.
• We are interested in the direct synthesis of small circuits
composed of NCV gates (rather than of libraries with macros).
• Observing optimal circuits for small cases often will shed light
on good (if not optimal) synthesis approaches.
• Since we know the optimal results for 3-line Toffoli circuits, it
is of interest to know what the optimal NCV circuits might
look like.
• It is in its own right a challenging problem
(2116=1,430,568,690,241,985,328,321 ~ 1021).
9
Definitions
• A Boolean function f:{0,1}n  {0,1}n is reversible if
it maps each input pattern to a unique output pattern
(it is a bijection).
• There are 2n! n-variable reversible functions.
• For n=3, this yields 8! = 40,320 functions.
10
Definitions
• A quantum circuit is a sequence of quantum gates
(cascade), linked by “wires”
• The circuit has fixed “width” corresponding to the
number of qubits being processed
• Logic design (classical and quantum) attempts to
find circuit structures for needed operations that are
– Functionally correct
– Independent of physical technology
– Low-cost, e.g., use the minimum number of qubits or
gates
• Quantum logic design is not at all well developed.
11
Definitions
In Out
NOT
0 1 
1 0 


0
1
1
0
CNOT
1
0

0

0
In
Out
00
01
10
11
00
01
11
10
0 0 0
1 0 0 
0 0 1

0 1 0
12
Definitions
a
b
c
Toffoli
1
0

0

0
0

0
0

0
0 0 0 0 0 0 0
1 0 0 0 0 0 0 
0 1 0 0 0 0 0

0 0 1 0 0 0 0
0 0 0 1 0 0 0

0 0 0 0 1 0 0
0 0 0 0 0 0 1

0 0 0 0 0 1 0 
In
abc
000
001
010
011
100
101
110
111
Out
abc
000
001
011
010
100
101
111
110
13
Definitions
V
Controlled-V
1
0


0

0

0
0
1
0
1 1
 i
2 2
1 1
0
 i
2 2
0

0 
1 1 
 i
2 2 
1 1 
 i
2 2 
0
In
00
01
10
11
0 v0
0 v1
1 v0
1 v1
Out
00
01
1 v0
1 v1
0 v0
0 v1
11
10
14
Definitions
V+
Controlled-V+
1
0


0

0

0
0
1
0
1 1
 i
2 2
1 1
0
 i
2 2
0

0 
1 1 
 i
2 2 
1 1 
 i
2 2 
0
In
00
01
10
11
0 v0
0 v1
1 v0
1 v1
Out
00
01
1 v1
1 v0
0 v0
0 v1
10
11
15
Definitions
V V+
V V+ V+
V
Example of a quantum circuit (3-bit full adder)
16
Problem Statement
• Find optimal NCV circuits for the 8! 3-variable
quantum Boolean functions.
• Optimal can be based on gate count or on total gate
cost for some costing model.
• Gate count is just a cost model where all gates have
cost 1.
17
Our solution
identity
gate
choices (21)
depth
(16)
Every path represents a circuit.
How large is the search tree? 1021
How can we search it efficiently?
- works well for ‘small’ trees but pruning is often required for large problems
- should work for gate count cost but what about other cost models?
18
Our solution
• Issues:
• How to code the functions accounting for Boolean and
quantum values?
• How to limit the search space?
• How to search the tree efficiently?
• How to account for different gate costs?
• Assumption: never use a ‘quantum’ line as a control
for a V or V+ gate.
19
Our solution
How to code functions?
• The Boolean and quantum values can be treated as
follows:
V
A V gate is a quarter
turn counter-clockwise
1
0
A V+ gate is a quarter
turn clockwise
V+
20
Our solution
0
V
1
V+
A simple coding is sufficient
00
01
10
11
We can think of a quantum function as having a base
Boolean function (reversible parent) with a quantum
signature added.
a
0
0
0
0
1
1
1
1
b
0
0
1
1
0
0
1
1
c
0
1
0
1
0
1
0
1
A
0
0
0
0
1
1
1
1
B
0
0
1
1
0
0
1
1
C
0
1
V
V+
V
V+
1
0
a
0
0
0
0
1
1
1
1
b
0
0
1
1
0
0
1
1
c
0
1
0
1
0
1
0
1
A
00
00
00
00
10
10
10
10
B
00
00
10
10
00
00
10
10
C
00
10
01
11
11
01
10
00
21
Our solution
How to limit the search space?
Theorem. A circuit realizing a Boolean reversible
function realizes the same function if controlled-V
gates are replaced by controlled-V+ gates and
controlled-V+ gates are replaced by controlled-V
gates.
Proof: Obvious from circle of values.
Hint 1: during the search it is always enough to use
gate controlled-V as the first quantum gate.
22
Our solution
The number of gate choices is 21:
•
•
•
•
3 NOT
6 CNOT
6 controlled-V
6 controlled-V+
But not all gate choices are applicable in all situations.
Hint 2: Don’t follow a gate with another gate with the
same control and target – such a pair can always be
reduced to one gate regardless of the gate types.
Assumes no gate type is realizable by a lower cost
composition of other gates types.
23
Our solution
Hint 3: Once an optimal implementation of a function is
found, we have also found an optimal implementation
for all functions that differ from this one only by their
input-output labeling.
Hint 4: don’t consider a circuit (tree node) if we have
already found a cheaper realization for that function.
Hint 5 (not used): once G1G2…Gk is an optimal circuit
for a reversible function f , Gk1Gk11...G11 is an
optimal circuit for f 1.
24
Our solution
• There are 40,320 3-line Boolean reversible functions.
• We don’t know how many quantum function will
have to be considered.
• In the breadth-first search we want to visit the
cheaper circuits first. For gate count cost, this is easy
and can be done with one queue.
• But for a cost model with different costs for different
gate types, multiple queues are required.
25
Our solution
NQ = max gate cost +1
a circuit of cost C is queued in
queue C mod NQ
This is a prioritized
breadth-first search.
26
Our solution
• A reversible parent is readily mapped to an index
(integer) and vice versa (see p. 161 in Combinatorial
Algorithms, by Reingold, Nievergelt and Deo).
0
Boolean
index
1
2
quantum
signature
24 bits
40319
27
Results
NCV-111 cost model
– average gate count: 10.03
– average cost: 10.03
– Boolean functions queued: 6,828
– Boolean function cost reductions: 0
– Quantum functions queued: 206,410
– Quantum function cost reductions: 0
– user time: 61 seconds on a fairly fast UNIX
box
28
Results
0 :
5167 :
11536 :
23616 :
0 1 2 3 4 5 6 7 : 0 : ;
1 0 3 2 5 4 7 6 : 0 : N(1,0);
2 3 0 1 6 7 4 5 : 1 : N(2,0);
4 5 6 7 0 1 2 3 : 2 : N(3,0);
121
1565
3109
7
16
592
:
:
:
:
:
:
0
0
0
0
0
0
1
3
5
1
1
1
3
2
2
2
2
6
2
1
7
3
3
7
4
4
4
5
6
4
5
7
1
4
7
5
7
6
6
7
4
2
6
5
3
6
5
3
:
:
:
:
:
:
0
1
2
3
4
5
:
:
:
:
:
:
N(1,2);
N(2,1);
N(3,1);
N(1,3);
N(2,3);
N(3,2);
5046
10814
21410
5160
:
:
:
:
1
2
4
1
0
1
1
0
2
0
6
3
3
3
3
2
5
6
0
4
4
5
5
5
6
4
2
6
7
7
7
7
:
:
:
:
0
1
2
3
:
:
:
:
N(1,0).N(1,2);
N(2,0).N(2,1);
N(3,0).N(3,1);
N(1,0).N(1,3);
29
Results
28024 : 5 3 7 2 4 6 0 1 : 2 :
N(3,1).V(1,3).N(1,0).V(1,2).N(2,3).VP(1,2).V(3,1)
.VP(3,2).N(2,1).V(3,2).V(2,3).VP(2,1).N(1,3).VP(2,1);
37137 : 7 2 4 3 1 5 6 0 : 0 :
N(1,2).V(3,1).V(3,2).N(2,1).V(3,2).V(1,2).N(2,3).
VP(1,2).VP(1,3).V(3,1).N(2,0).N(1,2).V(3,1).V(3,2);
38337 : 7 4 1 3 2 5 6 0 : 0 :
N(1,2).V(3,1).V(3,2).N(2,1).V(3,2).V(1,2).N(2,3).
VP(1,2).VP(1,3).V(3,1).N(2,0).N(1,2).V(3,1).V(3,2);
36209 : 7 1 2 5 4 6 3 0 : 0 :
V(1,2).N(2,3).V(1,3).VP(1,2).V(2,1).V(2,3).N(3,1)
.VP(2,3).V(1,2).N(3,0).N(3,2).N(2,3).VP(1,2).VP(1,3);
36231 : 7 1 2 6 4 3 5 0 : 0 :
V(1,2).N(2,3).V(1,3).VP(1,2).V(2,1).V(2,3).N(3,1)
.VP(2,3).V(1,2).N(3,0).N(3,2).N(2,3).VP(1,2).VP(1,3);
30
Results
NCV Cost 1-1-1 Gate Count
12000
10000
# Functions
8000
6000
4000
2000
0
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
Gates
31
Results
Opt. NCT
Cost
GC
0
1
1
12
2
102
3
625
4
2780
5
8921
6
17049
7
10253
8
577
9
0
10
0
11
0
12
0
Opt. NCV
NCV-111 NCV-111
1
1
9
9
51
51
187
187
392
417
475
714
259
1373
335
3176
1300
4470
3037
4122
3394
10008
793
5036
929
1236
13
14
15
16
17
18
19
20
21
22
23
24
27
28
WA
0
0
0
0
0
0
0
0
0
0
0
0
0
0
5.8655
4009
8340
8318
1180
4385
0
255
0
1297
0
4626
0
4804
0
475
0
106
0
503
0
357
0
4
0
17
0
2
0
14.0548 10.0319
Conclusion 1: small Toffoli gate count is not an
effective illustration of the implementation cost.
32
Results
NCV-155 cost model
–
–
–
–
–
–
average gate count: 10.03
average cost: 46.35
Boolean functions queued: 6,878
Boolean function cost reductions: 50
quantum functions queued: 232,406
Quantum function cost reductions:
19,038
– user time: 68 seconds
33
Results
NCV Cost 1 - 5 - 5 Cost
10000
9000
8000
7000
5000
4000
3000
2000
1000
66
63
60
57
54
51
48
45
42
39
36
33
30
27
24
21
18
15
12
9
6
3
0
0
# Functions
6000
Cost
34
Results
Distribution of controlled-V/controlled-V+ gates.
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
0
2
9
51
187
393
474
215
14
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
3
0
0
0
0
24
240
1158
3162
4110
714
0
0
0
0
0
0
4
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
5
6
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
360
0 3408
0 10008
0 5036
0
4
0
0
0
0
0
0
7
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
8
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
9
0
0
0
0
0
0
0
0
0
0
0
0
1232
8340
1180
0
10
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
Conclusion 2: number of controlled-V/controlled-V+
gates in optimal implementations is divisible by 3.
35
Results
Interchangeability chart.
Conclusion 3: for small functions, it does not matter
much in which metric to minimize a circuit. NCV-111
metric, however, seems to be more useful.
36
Results
Conclusion 4: multiple control Toffoli gates with some
but not all negations are no more expensive than Toffoli
gates with all positive controls.
37
Acknowledgements
• Gerhard Dueck, Faculty of Computer Science,
University of New Brunswick
• Natural Sciences and Engineering Research
Council of Canada
• NB IEEE
38
Thank you!
Comments,
Questions,
Critiques?
39