Transcript Functional and Delay Fault Testing for Systems-on-a-Chip

Projects on
Quantum Circuits Simulation
George F. Viamontes,
Igor L. Markov, and John P. Hayes
{gviamont,imarkov,jhayes}@umich.edu
Advanced Computer Architecture Laboratory
University of Michigan, EECS
EECS Department
University of Michigan,
Ann Arbor, MI 48109
Quantum Approaches to Logic Circuit Synthesis and Testing
The University of Michigan: John Hayes and Igor Markov
Quantum
domain
Parallelism
Microscale
Synthesis and test
algorithms
Classical
domain
Automation
Scalability
Practical logic
circuits
New Ideas
• Integrated approach to both quantum and
classical logic circuits
• Exploit quantum methods for classical
circuit synthesis and testing problems
• Scalable representation of quantum circuits
• Multiobjective optimization techniques
that are suited to automation (CAD)
Impact
• Quantum approaches promise more
efficient computation in critical
applications.
• Automation is key to large-scale quantum
circuit development
• Development of practical algorithms for
quantum circuit synthesis and test
• Use of quantum methods to improve
testing and synthesis of classical circuits
Ongoing Projects at U.Michigan
• Simulation of quantum circuits
– BDD-based QuIDDPro simulator
– Simulating Grover’s algorithm
• Synthesis of two-qubit circuits
– Bounds for gate counts in two-qubit circuits
• Quantum algorithms that improve
memory usage
– Quantum counters
Quantum Circuit Simulation
Using QuIDDs
• Motivation
– Need for a better way to simulate quantum circuits
• Quantum Information Decision Diagram (QuIDD)
– Novel data representation that uses Binary Decision
Diagrams (BDD) widely used in computer-aided circuit
design
– Captures some exponentially-sized matrices and vectors in a
form that grows polynomially with the number of qubits
– Multiplies matrices and vectors in compressed form
• QuIDDPro Simulator
– Our QuIDD-based simulator implemented in C++
– Experiments with Grover’s algorithm demonstrate fast
execution and low memory utilization
Problem
• Simulation of quantum computing on a
classical computer
– Requires exponentially growing time and memory
resources
• Goal: Improve classical simulation
• Their Solution: Quantum Information Decision
Diagrams (QuIDDs)
Operations on Multiple Qubits
• Tensor product of operators/qubits
1 / 2

1 / 2
1 / 2  1 / 2

 1 / 2  1 / 2

H
'

H
'
1 / 2

1 / 2  1 / 2

 1 / 2  1 / 2

1 / 2
1/ 2
1/ 2
1/ 2
1/ 2
1/ 2
1/ 2
1/ 2
1/ 2
H  H 
1/ 2 
 1 / 2
 1 / 2

1/ 2 
  ' '
Previous Work
• Traditional array-based representations
are insensitive to the values stored
• Qubit-wise multiplication
– 1-qubit operator and n-qubit state vector
– State vector requires exponential memory
• BDD techniques
– Multi-valued logic for q. circuit synthesis [1]
– Shor’s algorithm simulator (SHORNUF) [8]
Redundancy in
Quantum Computing
• Matrix/vector representation of
quantum gates/state vectors contains
block patterns
• The tensor product propagates block
patterns in vectors and matrices
Example of
Propagated Block Patterns
1 / 2 1 / 2  1 / 2 1 / 2 



1 / 2  1 / 2  1 / 2  1 / 2 
1 / 2 1 / 2 1 / 2 1 / 2 
1 / 2  1 / 2 1 / 2  1 / 2

 
1 / 2 1 / 2  1 / 2  1 / 2


1 / 2  1 / 2  1 / 2 1 / 2 
•QuIDD
Structure
Data Structure
that Exploits Redundancy
• Binary Decision Diagrams (BDDs) exploit repeated sub-structure
• BDDs have been used to simulate classical logic circuits efficiently
[6,2]
• Example: f = a AND b
f
a
Assign value of 1 to variable x
b
Assign value of 0 to variable x
1
0
BDDs in Linear Algebra
• Algebraic Decision Diagrams (ADDs)
treat variable nodes as matrix indices
[2], also MTBDDs
• ADDs encode all matrix elements aij
– Input variables capture bits of i and j
– Terminals represent the value of aij
• CUDD implements linear algebra for
ADDs (without decompression)
Quantum Information
Decision Diagrams (QuIDDs)
• QuIDDs: an application of ADDs
to quantum computing
• QuIDD matrices : row (i), column (j) vars
• QuIDD vectors: column vars only
• Matrix-vector multiplication
cij   aijb j
i 1 j 1
performed in terms of QuIDDs
QuIDD Vectors
f
C0
C1
1
0
0
0 + 0i
1
1 + 0i

 0 00
 0 01
 
 0 10
 11
1 
 11
Terminal value array
QuIDD Data Representation
f
R0
C0
R1
R1

00
01
10
11
C1
C1
00
01
1 / 2
1 / 2

1 / 2

1 / 2
1/ 2
1/ 2
1/ 2
1/ 2
1/ 2
1/ 2
1/ 2
1/ 2
0
0
1
1 / 2  0i
1 1/ 2  0i
10
11
1/ 2 
 1 / 2
 1 / 2

1/ 2 
QuIDDs and ADDs
• All dimensions are 2n
• Row and column variables are interleaved
R0  C0  R1  C1    Rn  Cn  T
• Terminals are integers which map
into an array of complex numbers

QuIDD Data Representation
f
R1,R0 \ C1, C0
R0
00
C0
01
10
R1
R1
11
C1
C1
00
01
1 / 2
1 / 2

1 / 2

1 / 2
1/ 2
1/ 2
1/ 2
1/ 2
1/ 2
1/ 2
1/ 2
1/ 2
0
0
1
10
11
1/ 2 
 1 / 2
 1 / 2

1/ 2 
1 / 2  0i
1 1/ 2  0i
•C0 = 1, R0=0, R1=1
•QuIDD
Operations
QuIDD Operations
• Based on the Apply algorithm [4,5]
– Construct new QuIDDs by traversing
two QuIDD operands based on variable ordering
– Perform “op” when terminals reached (op is *, +, etc.)
– General Form: f op g where f and g are QuIDDs, and x and y
are variables in f and g, respectively:
xi  yi
xi  yi
xi  yi
xi
yi
xi
f xi op g yi
f x op g y
i
i
xi op g yi
xi op g y
i
f xi op yi
f x op yi
i
Tensor Product
• Given A

B
– Every element of a matrix A
is multiplied by the entire matrix B
• QuIDD Implementation: Use Apply
– Operands are A and B
– Variables of operand B are shifted
– “op” is defined to be multiplication
Other Operations
• Matrix multiplication
– Modified ADD matrix multiply algorithm [2]
– Support for terminal array
– Support for row/column variable ordering
• Matrix addition
– Call to Apply with “op” set to addition
• Qubit measurement
– DFS traversal or measurement operators
•Simulation
Results
QuIDDPro Simulation Results
(Grover’s search algorithm) for Oracle 1
•Memory Usage
•Runtime
•Blitz++
•Matlab
•15 qubits
Linear Growth
using QuIDDPro
QuIDDPro Simulation of Grover’s Algorithm
•Memory Usage
•Runtime
Same results for any oracle that distinguishes a unique element
QuIDDPro Simulation of Grover’s Algorithm
•Memory Usage
•Runtime
O(n)
O(p(n)(√2)n)
Number of Iterations
• Use formulation from Boyer et al. [3]
• Exponential runtime
(even on an actual quantum computer)
• Actual Quantum Computer Performance:
~ O(1.41n) time and O(n) memory
Simulation Results for
Grover’s Algorithm
• Linear memory growth
(numbers of nodes shown)
Oracle 1: Runtime (s)
No. Qubits (n)
Octave
MATLAB
Blitz++
QuIDDPro
10
80.6
6.64
0.15
0.33
11
2.65e2
22.5
0.48
0.54
12
8.36e2
74.2
1.49
0.83
13
2.75e3
2.55e2
4.70
1.30
14
1.03e4
1.06e3
14.6
2.01
15
4.82e4
6.76e3
44.7
3.09
16
> 24 hrs
> 24 hrs
1.35e2
4.79
17
> 24 hrs
> 24 hrs
4.09e2
7.36
18
> 24 hrs
> 24 hrs
1.23e3
11.3
19
> 24 hrs
> 24 hrs
3.67e3
17.1
20
> 24 hrs
> 24 hrs
1.09e4
26.2
Oracle 1: Peak Memory Usage (MB)
No. Qubits (n)
Octave
MATLAB
Blitz++
QuIDDPro
10
2.64e-2
1.05e-2
3.52e-2
9.38e-2
11
5.47e-2
2.07e-2
8.20e-2
0.121
12
0.105
4.12e-2
0.176
0.137
13
0.213
8.22e-2
0.309
0.137
14
0.426
0.164
0.559
0.137
15
0.837
0.328
1.06
0.137
16
1.74
0.656
2.06
0.145
17
3.34
1.31
4.06
0.172
18
4.59
2.62
8.06
0.172
19
13.4
5.24
16.1
0.172
20
27.8
10.5
32.1
0.172
Linear Growth
using QuIDDPro
Validation of Results
• SANITY CHECK: Make sure that QuIDDPro
achieves highest probability of measuring the
item(s) to be searched using the number of iterations
predicted by Boyer et al. [3]
Consistency with Theory
Grover Results Summary
• Asymptotic performance
– QuIDDPro: ~ O(1.44n) time and O(n) memory
– Actual Quantum Computer
• ~ O(1.41n) time and O(n) memory
• Outperforms other simulation techniques
– MATLAB: (2n) time and (2n) memory
– Blitz++: (4n) time and (2n) memory
What about errors?
• Do the errors and mixed states that
are encountered in practical
quantum circuits cause QuIDDs to
explode and lose significant
performance?
NIST Benchmarks
• NIST offers a multitude of quantum circuit
descriptions containing errors/decoherence
and mixed states
• NIST also offers a density matrix C++
simulator called QCSim
• How does QuIDDPro compare to QCSim
on these circuits?
QCSim vs. QuIDDPro
• dsteaneZ: 13-qubit circuit with initial
mixed state that implements the Steane
code to correct phase flip errors
– QCSim: 287.1 seconds, 512.1MB
– QuIDDPro: 0.639 seconds, 0.516 MB
QCSim vs. QuIDDPro (2)
• dsteaneX: 12-qubit circuit with initial mixed
state that implements the Steane code to
correct bit flip errors
– QCSim: 53.2 seconds, 128.1MB
– QuIDDPro: 0.33 seconds, 0.539 MB
•Complexity
Analysis
Results
Recall the Tensor Product
Key Formula
• Given QuIDDs {Qi }in1 , the tensor product
QuIDD  n Q contains
i 1
i
| In(Q1 ) | i 2 | In(Qi ) || Term( ) |
n
 | Term( Qi ) | nodes
n
i 1
i 1
j 1
Persistent Sets
• A set  is persistent if and only if the set of n
pair-wise products of its elements is constant (i.e.
the pair-wise product n times)
• Consider the tensor product of two matrices whose
elements form a persistent set
– The number of unique elements in the resulting matrix
will be a constant with respect to the number of unique
elements in the operands
Relevance to QuIDDs
• Tensor products with n QuIDDs whose
terminals form a persistent set produce
QuIDDs whose sets of terminals do not
increase with n
Main Results
• Given a persistent set and a constant C, consider
n QuIDDs with at most C nodes each and terminal
values from .
• The tensor product of those QuIDDs has O(n)
nodes and can be computed in O(n) time.
• Matrix multiplication with QuIDDs A and B as
2
operands requires O(( AB) )time and produces a
2
result with O(( AB) ) nodes [2]
Applied to Grover’s Algorithm
• Since O(1.41n) Grover iterations are required,
and thus O(1.41n) matrix multiplications, does
Grover’s algorithm induce exponential
memory complexity when using QuIDDs?
• Answer: NO!
– The internal nodes of the state vector/density
matrix QuIDD are the same at the end of each
Grover iteration
– Runtime and memory requirements are therefore
polynomial in the size of the oracle QuIDD
Work in Progress:
On The Power of Grover’s Algorithm
• Database search with a black-box predicate p(x)=1
– Classical evaluation of p(x) on one input (queries)
– Quantum (parallel) evaluation of p(x) facilitates an implementation with
fewer queries
Non-trivial assumption
• We also assume that p(x) is given as a BDD/QuIDD
– BDDs are used to represent functions in practical CAD
– However, a BDD is not really a black-box
– BDD operations evaluate p(x) on multiple inputs at once
(no quantum computation is involved)
• Grover on QuIDDs: same query complexity as in the quantum case
– In practice this simulation is very fast and needs little memory
Ongoing Work
• Explore error/decoherence models
• Simulate Shor’s algorithm
– QFT and its inverse are exponential in size as
QuIDDs
– Other operators are linear in size as QuIDDs
– QFT and its inverse are an asymptotic
bottleneck
• Limitations of quantum computing
Relevant Work
G. Viamontes, I. Markov, J. Hayes, “Improving GateLevel Simulation of Quantum circuits,” Los Alamos
Quantum Physics Archive, Sept. 2003 (quantph/0309060)
G. Viamontes, M. Rajagopalan, I. Markov, J. Hayes,
“Gate-Level Simulation of Quantum Circuits,” Asia
South Pacific Design Automation Conference, pp. 295301, January 2003
G. Viamontes, M. Rajagopalan, I. Markov, J. Hayes,
‘Gate-Level Simulation of Quantum Circuits,” 6th Intl.
Conf. on Quantum Communication, Measurement, and
Computing, pp. 311-314, July 2002
References
[1] A. N. Al-Rabadi et al., “Multiple-Valued Quantum
Logic,” 11th Intl. Workshop on Post Binary ULSI,
Boston, MA, May 2002.
[2] R. I. Bahar et al., “Algebraic Decision Diagrams and
their Applications”, In Proc. IEEE/ACM ICCAD, pp.
188-191, 1993.
[3] M. Boyer et al., “Tight Bounds on Quantum
Searching”, Fourth Workshop on Physics and
Computation, Boston, Nov 1996.
[4] R. Bryant, “Graph-Based Algorithms for Boolean
Function Manipulation”, IEEE Trans. On Computers,
vol. C-35, pp. 677-691, Aug 1986.
[5] E. Clarke et al., “Multi-Terminal Binary Decision
Diagrams and Hybrid Decision Diagrams”, In T. Sasao
and M. Fujita, eds, Representations of Discrete
Functions, pp. 93-108, Kluwer, 1996.
References
[6] C.Y. Lee, “Representation of Switching
Circuits by Binary Decision Diagrams,” Bell
System Technical Jour., 38:985-999, 1959.
[7] D. Gottesman, “The Heisenberg Representation
of Quantum Computers,” Plenary Speech at the
1998 Intl. Conf. on Group Theoretic Methods in
Physics, http://xxx.lanl.gov/abs/quantph/9807006
[8] D. Greve, “QDD: A Quantum Computer
Emulation Library,”
http://home.plutonium.net/~dagreve/qdd.html