Quantum Machine Learning Based on Minimizing Kronecker-Reed-Muller Forms and Grover Search Algorithm with Hybrid Oracles

Published In

Digital System Design (DSD), 2016 Euromicro Conference on

Document Type


Publication Date



This paper formulates the generic Machine Learning (ML) problem into finding the simplest spectral transform form (i.e. one having as many zero coefficients as possible) for an (in)complete binary function. The classical binary logic synthesis problem can be modeled to minimize a single output Boolean function with a two-level structure consisting of an exclusive-OR (EXOR) of ANDs of literals. The innovative approach in this paper is to build and simulate an accelerator that reduces learning to find the exact minimum expression of all 3n Kronecker Reed Muller (KRO) forms of a Boolean function with n input variables. This is in contrast to the previously studied quantum algorithm for the Fixed Polarity Reed-Muller forms (FPRM) which only selects from 2n possible forms. The algorithm, based on repeated application of a ternary Grover's Quantum Search algorithm, was simulated to find the minimum KRO form using a hybrid ternary/binary quantum oracle. This hybrid quantum system was simulated in Matlab and proved to be correct. The method can be also used as a future Quantum EDA Tool for exact minimization of AND/EXOR circuits, including reversible and quantum circuits.



Persistent Identifier