Failure Evasion: Statistically Solving the NP Complete Problem of Testing Difficult-toDetect Faults Muralidharan Venkatasubramanian PhD Final exam COMMITTEE D R . V I S H WA N I D. A G R AWA L ( C H A I R ) D R . A D I T D. S I N G H D R . V I C TO R P. N E L S O N D R . M I C H A E L C . H A M I LTO N D R . ROY J . H A R T F I E L D 4 November 2016 PhD Final Presentation 1 Outline Problem Statement Literature Review Proposed Algorithm Version 1 Version 2 Outline and Results Outline and Results Version 3 Working Example Results

Conclusion and Future Work 4 November 2016 PhD Final Presentation 2 Problem Statement Given a stuck-at fault, find a test. Specifically, find tests for hard to detect stuck-at faults. Rephrase the VLSI Testing problem as a database search problem. Need for research to harness potential of database search. Application of quantum search towards test generation. Improve the search bottleneck of hard to find tests. 4 November 2016 PhD Final Presentation 3 Literature Review 4 November 2016 PhD Final Presentation 4 Overview of ATPG Research Fault detection problem is NP complete [Ibarra and Sahni, 1975; Fujiwara and Toida, 1982; Seroussi and Bshouty, 1988].

Worst case computational complexity is an exponential function in circuit size. Nature of NP complexity problems. Generation of test vectors is a classic VLSI problem. Tackled by numerous algorithms. 4 November 2016 PhD Final Presentation 5 ATPG Research (contd..) Deterministic algorithms derived from structural description of circuits. D Algorithm [Roth, 1966]. PODEM [Goel, 1981]. FAN [Fujiwara and Shimono, 1983]. And various others... Test sets derived from functional description of circuits [Akers, 1972; Reddy, 1973]. Use of weighted random test generators. Heuristics like input switching activity and weight assignment [Schnurmann et al., 1972]. Skewing input probability to attain maximum output entropy [Agrawal, 1981]. Adaptive test generation Genetic algorithms [Saab et al. 1992; ODare and Arslan, 1994; Corno et al., 1996]. Anti-random test generators [Malaiya, 1995]. Using spectral properties of successful tests to generate new test vectors [Yogi and Agrawal, 2006]. 4 November 2016 PhD Final Presentation

6 ATPG Research (contd..) Redefinition as energy minimization problem [Chakradhar et al., 1991]. Converting digital circuit as a neural network. Concerns with test power. Reordering of test vectors [Girard et al., 1999]. Adaptive clock cycles [Venkataramani et al., 2014]. Dynamic voltage and frequency scaling [Sheshadri et al., 2013]. Utilization of SAT solvers [Drechsler et al., 2008]. Snapshot of VLSI Testing research over the past 50 years. 4 November 2016 PhD Final Presentation 7 ATPG and Database Search Connection Key elements show testing algorithms can be redefined as database search algorithms. Brute force search in vector combinations is analogous to linear search. Algorithmic ATPGs are forms of tree traversals. D algorithm a type of breadth-first search. PODEM and FAN forms of depth-first search. Weighted random generators, anti-random testing, spectral test generation are simulation based search methods. 4 November 2016 PhD Final Presentation

8 Interdisciplinary Connection Genetic algorithms and simulated annealing are also simulations based methods applied in VLSI Testing [Saab et al., 1992; ODare and Arslan, 1994; Corno et al, 1996]. Huge benefit if ATPG algorithm utilized one of the most efficient database search algorithms. Grovers algorithm for database search. Being a quantum algorithm, the speed-up is quite significant and mathematically most optimal [Boyer et al., 1998]. 4 November 2016 PhD Final Presentation 9 Quantum Computing The Future! Touted as a silver bullet to exponential complex research problems [Deutsch and Jozsa, 1992]. Wide ranging applications of quantum computing. Quantum communication [Kimble, 2008]. Quantum cryptography [Boyer et al., 1998; Gisin et al., 2002; Bernstein et al., 2009]. Shors factorization algorithm [Shor, 1997] a prominent quantum algorithm. Given an integer N, find its prime factors. Used to test D-wave machines. Grovers database search algorithm [Grover, 1996] another groundbreaking algorithm.

Complexity of O( is quadratically faster [Boyer et al., 1998]. 4 November 2016 PhD Final Presentation 10 Grovers Quantum Algorithm Finds the element in an unsorted database which can satisfy a particular function. Uses an "Oracle" to iteratively search for the qubits representing the element to be searched. Idea of Oracle key behind implementation of Grovers quantum search algorithm. Can recognize the solution to a database search without knowing the actual solution. Distinction between knowing the solution and recognizing the solution [Nielsen and Chuang, 2011]. Possible to do the latter without knowing the former. 4 November 2016 PhD Final Presentation 11 Average Search Effort ( Grovers Algorithm (contd..) 0 32

1024 32768 1048576 Database size (N) Average search effort vs. Database size comparison of Grovers Search and Linear Search. 4 November 2016 PhD Final Presentation 12 Proposed Concept 4 November 2016 PhD Final Presentation 13 Conceptual Outline Current algorithms hit a bottleneck when testing hard to detect faults. When testing these faults, we generally have many trial vectors that do not work. All known algorithms use previous successes to generate new test vectors. But, test generation has lots more failed attempts than successful ones. Current algorithms ignoring a lot of potentially valuable information. How to design a new test algorithm, which utilizes the information from failed attempts effectively? 4 November 2016

PhD Final Presentation 14 Algorithm Genesis How does one prosper in life?? Repeating steps from previous successes. As people say, do not change a successful formula. Learning from past failures and avoiding them. Main conjecture is to avoid vectors with properties similar to known failed vectors. The direction of search gets skewed towards the correct test vector. Proposed algorithm versions utilize both successful and failed vectors. Moving away from failed vectors will lead to solution in fewer iterations. 4 November 2016 PhD Final Presentation 15 Research Contribution Proposed work has three unique contributions: Avoidance of failed vectors and their properties.

Use of correlation among primary inputs (PIs). Classification of failed vectors in activation and propagation vectors. Proposed algorithm has three versions: Version 1 utilizes properties one and two listed above. Version 2 utilizes properties one and three listed above. Was presented in PhD General (proposal) exam (September 29, 2014). Was designed to overcome shortcomings of version 1. Version 3 utilizes all three properties and is the final result of this research. Combines the flavors of both version 1 and version 2. 4 November 2016 PhD Final Presentation 16 Version 1 Principle Current algorithms hit a bottleneck when testing hard to detect faults. Because we are testing hard-to-detect faults, we generally have many trial vectors that do not work. Quantify probabilities in an n x n probability matrix. n is the number of primary inputs. Diagonal represents independent probability of 1 at a primary input. An off-diagonal entry represents conditional probability of 1 at a column

primary input given a state of 1 at the row primary input. Probability matrix contains information from unsuccessful test vectors. 4 November 2016 PhD Final Presentation 17 Version 1 Results Algorithm applied to two stuck-at faults in c17 benchmark circuit that have minimum number of tests. X Stuck-at-1 (site 1) X Stuck-at-1 (site 2) 4 November 2016 PhD Final Presentation 18 C17: Version 1 Results Has 5 primary inputs. Has no hard to detect stuck-at faults. 6 test vectors can detect all possible stuck-at faults. The two target faults have the least number of tests. Test generation was conducted 100 times for each fault. C17 circuit Fault Sites Site 1 (stuck-at 1) Site 1 (stuck-at 1) Site 2 (stuck-at 1) Site 2 (stuck-at 1) 4 November 2016 Grovers quantum

Version 1 Random search () Algorithm Search Average number of iterations (out of 100 trials) Average number of iterations (out of 100 trials) <6 7 11 <6 7 11 <6 9 15 <6 9 15 PhD Final Presentation 19 Version 1 Issues Showed an important proof of concept that failure avoidance can theoretically work. Struggled with attaining speedup in larger circuits. Problem akin to searching for Needle in a haystack. Correct test vector got lost in all the noise of failed vectors. Failed vectors are too many but some of them contain useful information. Some of them contain activation or propagation vector information. Version 2 addresses these issues. 4 November 2016 PhD Final Presentation

20 Version 2 Principle Main conjecture is to avoid vectors with properties similar to known failed test vectors. The direction of search gets skewed towards the correct test vector. Also learn from failed vectors and glean information so as to make them a partial success. Test vectors in the vector space are classified into three categories: Activation vectors Propagation vectors Failed vectors 4 November 2016 PhD Final Presentation 21 Classification of Test Vectors Classification of vectors in three categories for stuck-at fault [Venkatasubramanian and Agrawal, 2015]. 4 November 2016 PhD Final Presentation 22 Implementation Initialize weighted probabilities of each PI bit being "1" to 0.50 and extract a vector. Use a fault simulator to check if the vector is a test. If it is, stop. Else, check if it is an activation or a propagation vector. Add test vector to the failed vector list if neither and recalculate weighted probabilities of all PIs.

Invert the weighted probability and extract a bit value from the new calculated probability. Operation performed till an activation or a propagation vector is extracted. 4 November 2016 PhD Final Presentation 23 Implementation (contd..) Derive new vectors using weights which extracted previous activation/propagation vector. Tweak the weights in smaller increments utilizing the failed vector weights for direction. Idea is move towards the intersection of activation and propagation vectors when inside "region of desirability". Avoid going back to failed vector region. 4 November 2016 PhD Final Presentation 24 Version 2 Results Benchmark Circuit Search space #PI size, N = 2#PI Test circuit Test (#PIcircuit = 6)

(#PI = 6) ALU control (#PIcontrol = 7) ALU (#PI = 7) Decoder (#PI = 8) Decoder (#PICounter = 8) Ones (#PI = 9) Ones Counter CAVL (#PI coder = 9) (#PI = 10) CAVL coder (#PI = 10) 64 64 8 8 14 14 34 34 128 128 256 256 512 11 11 16

16 23 15 15 24 24 76 62 62 133 133 288 512 1024 23 32 76 132 288 500 1024 32 132 500 4 November 2016 Grovers quantum Version 2 Random search search () algorithm

( ~ N/2) Average Average number number of of iterations iterations (out (out of of 100 100 trials) trials) PhD Final Presentation 25 CAVL Coder Results (#PIs = 10) (# iterations) Iterative search duration distribution to search for the correct test vector. 4 November 2016 PhD Final Presentation 26 Version 2 Algorithm Complexity Test vector search complexity: Average search iterations versus no. of primary inputs 4 November 2016 PhD Final Presentation 27 Version 2 Summary Step in the right direction. Use of activation and propagation properties have significant effect on search efficiency. We put all three properties into version 3.

Avoidance of failed vectors. Utilization of bit correlations among PIs. Classification of failed vectors into activation and propagation vectors. 4 November 2016 PhD Final Presentation 28 Version 3 Principle Combines the properties of version 1 and version 2. Utilizes the correlations like version 1. When a vector is identified as activation or propagation, search is skewed in the appropriate direction. Correlations are quantified in an n x n matrix (n is number of PIs). Diagonal values represent independent bit probabilities. Off-diagonal values represent the conditional probabilities. 4 November 2016 PhD Final Presentation 29 Types of Probabilities Independent Probabilities: P(A = 1) = P(A) P(A = 0) = 1 P(A)

Conditional probabilities: P(B = 1 | A = 1) = P(B|A) P(B = 1 | A = 0) = P(B|) P(B = 0 | A = 1) = 1 P(B|A) P(B = 0 | A = 0) = 1 P(B|) 4 November 2016 PhD Final Presentation 30 A Working Example Failed vector list: ABCDEF 001010 110101 010010 100111 100000 100001 010011 000000 100010 111100 4 November 2016 PhD Final Presentation 31 Working Example (contd..) Failed vector list: P(B = 1 | A = 1)

P(A = 1) ABCDEF I/P A B C D E F 001010 110101 010010 100111 100000 100001 010011 000000 100010 111100 A 0.60 0.33 0.17 0.50 0.33 0.50

B 0.50 0.40 0.25 0.50 0.50 0.75 C 0.50 0.50 0.20 0.50 0.50 0 D 1 0.67 0.33 0.30 0.33 0.67

E 0.40 0.40 0.20 0.20 0.50 0.40 F 0.75 0.50 0 0.75 0.50 0.40 P(A = 1 | B = 1) 4 November 2016 PhD Final Presentation P(C = 1 | D = 1) 32 Working Example (contd..) Failed vector list: ABCDEF 001010 110101

010010 100111 100000 100001 010011 000000 100010 1 1 1 1 0 0P(A = 1) = 0.60 4 November 2016 P(B = 1 | A = 0) I/P A B C D E F A 0 0.50 0.25 0 0.75 0.25 B

X 0.40 0.25 0.50 0.50 0.50 C X 0.50 0.20 0.50 0.50 0 D X 0.67 0.33 0.30 0.33 0.67 E

X 0.40 0.20 0.20 0.50 0.40 F X 0.50 0 0.75 0.50 0.40 Invert Prob. P(A = 1) = 0.40 PhD Final Presentation Generate sample A=0 33 Working Example (contd..) P(C = 1 | B = 1) P(C = 1 | A = 0)

Failed vector list: ABCDEF 001010 110101 010010 100111 100000 100001 010011 000000 100010 111100 I/P A B C D E F A 0 X 0.25 0 0.75 0.25

B X 1 0.25 0.50 0.50 0.50 C X X 0.20 0.50 0.50 0 D X X 0.33 0.30 0.33 0.67

E X X 0.20 0.20 0.50 0.40 F X X 0 0.40 0.60 0.40 Average P(B|) = 0.50 4 November 2016 Invert Prob.P(B|) PhD Final Presentation = 0.50 Generate B= sample

1 34 Working Example (contd..) Failed vector list: ABCDEF 001010 110101 010010 100111 100000 100001 010011 000000 100010 111100 I/P A B C D E F A 0 X X 0

0.75 0.25 B X 1 X 0.50 0.50 0.50 C X X 0 0.25 0.50 0.50 D X X X 0.30

0.33 0.67 E X X X 0.20 0.50 0.40 F X X X 0.40 0.60 0.40 Average P(C|, B) = 0.25 4 November 2016 Invert P(C|, Prob. PhD Final Presentation B) = 0.75

Generate C= sample 0 35 Working Example (contd..) Failed vector list: ABCDEF 001010 110101 010010 100111 100000 100001 010011 000000 100010 111100 I/P A B C D E F A 0 X

X X 0.75 0.25 B X 1 X X 0.50 0.50 C X X 0 X 0.50 0.50 D X X

X 1 0.33 0.67 E X X X X 0.50 0.40 F X X X X 0.60 0.40 Average P(D|, B, ) = 0.25 4 November 2016 Invert P(D|,

Prob. PhD Final Presentation B, ) = 0.75 Generate Dsample =1 36 Working Example (contd..) Failed vector list: ABCDEF I/P A B C D E F A 0 X X X X 0.25

X 1 X X X 0.50 X X 0 X X 0.50 X X X 1 X 0.67 X X X

X 0 0.40 X X X X X 0.40 001010 B 110101 010010 C 100111 D 100000 100001 E 010011 000000 F 100010 1 1 1 1 0 P(E|, 0 Average B, , D) = 0.52 4 November 2016 Invert P(E|, Prob.

B, , D) = 0.48 PhD Final Presentation Generate E=0 sample 37 Working Example (contd..) Failed vector list: ABCDEF I/P A B C D E F A 0 X X X X X X

1 X X X X X X 0 X X X X X X 1 X X X X X X

0 X X X X X X 0 001010 B 110101 010010 C 100111 100000 D 100001 E 010011 000000 F 100010 1 1P(F|, 1 1 0B,0 , D, ) = 0.464 Average 4 November 2016 Invert P(F|, Prob. B, , D, ) = 0.536

PhD Final Presentation F Generate = 0sample 38 Version 3 Results Benchmark Benchmark Circuit Circuit cm85a logic cm85a (#PI = logic 13) (#PI = 13) cu logic cu logic (#PI = 14) (#PI = 14) b12 logic (#PI 15) b12 =logic (#PI = 15) Parity logic (#PI =logic 16) Parity (#PI 16) vda =logic (#PI 17) vda =logic (#PI = 17) 4 November 2016

Search Search space space size, size, #PI N N == 2 2#PI Grovers quantum search () Random Random Version Version search Version 2 2 Version 3 3 search (( ~~ N/2) N/2) Average Average number number of of iterations iterations (out (out of of 100 100 trials) trials) 8192 8192 91 91

304 304 183 183 4100 4100 16384 16384 128 128 436 436 257 257 8203 8203 32768 32768 181 181 569 569 311 311 16367 16367 65536 65536 131072

131072 256 256 362 362 847 847 1569 1569 591 591 1201 1201 32751 32751 65516 65516 PhD Final Presentation 39 Results (contd..) Benchmark Benchmark Circuit Circuit Search Search space space #PI size, size, N N == 2 2#PI Grovers

quantum search () cmb logic cmb (#PI =logic 18) (#PI = 18) sct logic sct logic (#PI = 19) (#PI = 19) pm1 logic pm1 (#PI =logic 20) (#PI = 20) mux logic mux (#PI =logic 21) (#PI = 21) 262144 262144 512 512 2196 2196 1429 1429 131023 131023 524288 524288

724 724 3255 3255 2798 2798 262154 262154 1048756 1048756 1024 1024 4587 4587 4172 4172 524963 524963 2097512 2097512 1448 1448 6842 6842 5410 5410 1048753 1048753

4 November 2016 Random Random Version 2 Version 3 search Version 2 Version 3 search (( ~~ N/2) N/2) Average number of iterations (out of 100 trials) Average number of iterations (out of 100 trials) PhD Final Presentation 40 Test Circuit Histogram Comparison 4 November 2016 PhD Final Presentation 41 Results (contd..) Test vector search complexity: Average search iterations versus no. of primary inputs 4 November 2016 PhD Final Presentation 42 Conclusion Showed evolution of ATPG algorithms over the past 50 years. Redefined the testing problem as a database search problem.

ATPG algorithms are formulations of classic database search algorithms. Proposed work has three unique contributions. Avoidance of failed vectors and their properties. Use of correlation among primary inputs (PIs). Classification of failed vectors in activation and propagation vectors. This is a simulation-based learning method. Results show failure evasion is a good technique for finding test vectors for hard to detect stuck-at faults. Utilizing correlations between test vectors is very effective. Comparison with quantum search shows algorithm is on same order of search time or iteration time. 4 November 2016 PhD Final Presentation 43 Future Work Elaborates only one possible technique for utilizing correlations. Integrate current work with other testing algorithms. Creation of a Grand Unified ATPG to test all types of faults. Need to build an ATPG system which combines with other structural techniques like SOCRATES [Schulz et al., 1994] and recursive learning [Kunz and Pradhan, 1994]. Question of using Grovers quantum algorithm of database search for searching through the database of unordered test vectors is still unanswered.

Practical implementation of quantum search still needs to be found. Need to understand what an Oracle is and how it can be implemented. Might need to wait for a large-scale quantum computer to be practical. 4 November 2016 PhD Final Presentation 44 Success consists of going from failure to failure without loss of enthusiasm. - Sir Winston Churchill 4 November 2016 PhD Final Presentation 45 Publications M. Venkatasubramanian and V. Agrawal, Failures Guide Probabilistic Search for a Hardto-Find Test, in Proc. IEEE 25th North American Test Workshop, pp. 18 23, May 2016 (Jake Karrfalt Best Student Paper Award). M. Venkatasubramanian and V. Agrawal, Failure Evasion: Statistically Solving the NP Complete Problem of Testing Difficult-to-Detect Faults, E. J. McCluskey Best Doctoral Thesis 2016 Award Contest, IEEE VLSI Test Symposium, Apr. 2016. M. Venkatasubramanian and V. Agrawal, Database Search and ATPG Interdisciplinary Domains and Algorithms, in Proc. 29th IEEE International Conference on VLSI Design, pp. 38 43, Jan. 2016. M. Venkatasubramanian and V. Agrawal, Quest for a Quantum Search Algorithm for Testing Stuck-at Faults in Digital Circuits, in Proc. 29th IEEE International Symp. Defect and Fault Tolerance in VLSI and Nanotechnology Systems, pp. 127 132, Oct. 2015. M. Venkatasubramanian and V. Agrawal, A New Test Vector Search Algorithm for a Single Stuck-at Fault using Probabilistic Correlation, in Proc. IEEE 23rd North Atlantic Test Workshop, pp. 57 60, May 2014. 4 November 2016 PhD Final Presentation 46

References [1] O. H. Ibarra and S. Sahni, Polynomially complete fault detection problems, IEEE Trans. Computers, vol. 24, no. 3, pp. 242249, 1975. [2] H. Fujiwara and S. Toida, The complexity of fault detection problems for combinational logic circuits, IEEE Transactions on Computers, vol. 100, no. 6, pp. 555560, 1982. [3] G. Seroussi and N. H. Bshouty, Vector sets for exhaustive testing of logic circuits, IEEE Transactions on Information Theory, vol. 34, no. 3, pp. 513522, 1988. [4] J. P. Roth, Diagnosis of automata failures: A calculus and a method, IBM Journal of Research and Development, vol. 10, no. 4, pp. 278291, 1966. [5] P. Goel, An implicit enumeration algorithm to generate tests for combinational logic circuits, IEEE Transactions on Computers, vol. 100, no. 3, pp. 215222, 1981. [6] H. Fujiwara and T. Shimono, On the acceleration of test generation algorithms, IEEE Transactions on Computers, vol. 100, no. 12, pp. 11371144, 1983. [7] S. B. Akers, Universal test sets for logic networks, IEEE Conference Record of 13th Annual Symposium on Switching and Automata Theory, 1972, pp. 177184. [8] S. M. Reddy, Complete test sets for logic functions, IEEE Transactions on Computers, vol. 100, no. 11, pp. 10161020, 1973. 4 November 2016 PhD Final Presentation 47 References [9] H. D. Schnurmann, E. Lindbloom, and R. G. Carpenter, The weighted random test-pattern generator, IEEE Transactions on Computers, vol. 100, no. 7, pp. 695700, 1975. [10] V. D. Agrawal, An information theoretic approach to digital fault testing, IEEE Transactions on Computers, vol. 30, no. 8, pp. 582587, 1981. [11] D. G. Saab, Y. G. Saab, and J. A. Abraham, CRIS: A Test Cultivation Program for Sequential VLSI Circuits, in Proc. IEEE/ACM International Conference on Computer-Aided Design, 1992, pp. 216219. [12] M. ODare and T. Arslan, Generating Test Patterns for VLSI Circuits Using a Genetic Algorithm, Electronics Letters, vol. 30, no. 10, pp. 778779, 1994. [13] F. Corno, P. Prinetto, M. Rebaudengo, and M. S. Reorda, GATTO: A Genetic Algorithm for Automatic Test Pattern Generation for Large Synchronous Sequential Circuits, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 15, no. 8, pp. 9911000, 1996. [14] Y. K. Malaiya, Antirandom Testing: Getting The Most Out of Black-box Testing, in Proc. 6th IEEE International Symp. Software Reliability Engineering, 1995, pp. 8695. [15] N. Yogi and V. D. Agrawal, Spectral RTL test generation for gate-level stuck-at faults, Proc. 15 th IEEE Asian Test Symposium, 2006, pp. 8388. 4 November 2016

PhD Final Presentation 48 References [16] S. T. Chakradhar, V. D. Agrawal, and M. L. Bushnell, Neural Models and Algorithms for Digital Testing. Springer, 1991. [17] P. Girard, L. Guiller, C. Landrault, and S. Pravossoudovitch, A Test Vector Ordering Technique for Switching Activity Reduction During Test Operation, in Proc. 9th IEEE Great Lakes Symp. VLSI, 1999, pp. 2427. [18] P. Venkataramani, S. Sindia, and V. D. Agrawal, A Test Time Theorem and its Applications, Journal of Electronic Testing: Theory and Applications, vol. 30, no. 2, pp. 229236, 2014. [19] V. Sheshadri, V. D. Agrawal, and P. Agrawal, Power-aware SoC Test Optimization Through Dynamic Voltage and Frequency Scaling, in Proc. IFIP/IEEE 21st International Conference on Very Large Scale Integration (VLSI-SoC), 2013, pp. 102107. [20] R. Drechsler, S. Eggersglu, G. Fey, A. Glowatz, F. Hapke, J. Schloeffel, and D. Tille, On Acceleration of SAT-Based ATPG for Industrial Designs, IEEE Transactions on ComputerAided Design of Integrated Circuits and Systems, vol. 27, no. 7, pp. 13291333, July 2008. [21] S. Kirkpatrick, C. D. Gelatt, M. P. Vecchi, et al., Optimization by Simulated Annealing, Science, vol. 220, no. 4598, pp. 671 680, 1983. 4 November 2016 PhD Final Presentation 49 References [22] P. W. Shor, Polynomial-time Algorithms For Prime Factorization and Discrete Logarithms on a Quantum Computer, SIAM Journal on Computing, vol. 26, no. 5, pp. 14841509, 1997. [23] L. K. Grover, A Fast Quantum Mechanical Algorithm for Database Search, in Proc. 28th Annual ACM Symposium on Theory of Computing, pp. 212219, 1996. [24] M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information. New York: Cambridge University Press, 10th edition, 2011. [25] P. C. Mahalanobis, On the Generalized Distance in Statistics, Proceedings of the National Institute of Sciences (Calcutta), vol. 2, pp. 4955, 1936. [26] M. H. Schulz, E. Trischler, and T. M. Sarfert, "SOCRATES: A highly efficient automatic test pattern generation system." IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 7, pp. 126 137, 1988. [27] W. Kunz and D.K. Pradhan, "Recursive learning: a new implication technique for efficient solutions to CAD problems-test, verification, and optimization." IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 13, pp. 1143 1158, 1994.

4 November 2016 PhD Final Presentation 50 Thank You!!! Questions?? 4 November 2016 PhD Final Presentation 51