Paper introduces a new spectral expansion of ternary-input binary-output functions that generalizes the binary Kronecker-Reed-Muller forms. Two binary Davio Expansions are generalized to 27 Ternary-Input Davio Expansions. New KRM spectrum has 28nexpansions for n ternary variables. By creating an oracle for this problem we generalize the quantum Grover-based algorithms presented for the binary FPRM and KRM forms in the past. Because the method finds solutions also to incompletely specified functions, it can be used to both quantum circuit design and Machine Learning classifier design.
Paper introduces a new spectral expansion of ternary-input binary-output functions that generalizes the binary Kronecker-Reed-Muller forms. Two binary Davio Expansions are generalized to 27 Ternary-Input Davio Expansions. New KRM spectrum has 28nexpansions for n ternary variables. By creating an oracle for this problem we generalize the quantum Grover-based algorithms presented for the binary FPRM and KRM forms in the past. Because the method finds solutions also to incompletely specified functions, it can be used to both quantum circuit design and Machine Learning classifier design.
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.
Optimization problems in machine-learning (ML) applications can be computationally challenging for classical methods, particularly when they involve large, unstructured search spaces. Quantum computing offers a promising approach to combinatorial optimization by utilizing quantum superposition and amplitude amplification. This paper presents a new methodology using logic-based quantum machine learning (QML) as a complete framework for employing a multi-solution ternary Grover’s algorithm to minimize incomplete binary functions represented by Pseudo-Kronecker Reed–Muller (PKRO) expansions, consistent with Occam’s razor principle. Unlike previous quantum approaches based on Kronecker Reed–Muller (KRO) or fixed-polarity Reed–Muller (FPRM) representations, our work introduces the first Grover-based optimization framework for PKRO forms. This framework formulates logic minimization as a quantum search problem to identify minimum-cost AND-XOR representations with the fewest nonzero coefficients. A hybrid binary–ternary quantum architecture is developed to explore the enlarged PKRO search space, enabling optimization of both completely and incompletely specified binary functions. Owing to the greater flexibility of PKRO expansions, our framework produces more compact AND–XOR representations than KRO- and FPRM-based approaches. Across all 256 3-variable binary functions, PKRO provides less nonzero coefficients for 4.688% of functions compared with KRO and for 37.5% compared with FPRM, with average reductions of 0.047 and 0.484 nonzero coefficients, respectively. Our multi-solution ternary Grover search reduces the number of Grover iterations by more than 91% compared with the single-solution approach.
Previous work has provided methods for decomposing unitary matrices to series of quantum multiplexers, but the multiplexers created in this way are highly non-minimal. This paper presents a new approach for optimizing quantum multiplexers with arbitrary single-qubit quantum target functions. For quantum multiplexers, we define standard forms and two types of new forms: fixed polarity quantum forms (FPQF) and Kronecker quantum forms (KQF), which are analogous to Minterm Sum of Products forms, Fixed Polarity Reed-Muller (FPRM) forms, and Kronecker Reed-Muller (KRM) forms, respectively, for classical logic functions. Drawing inspiration from the usage of butterfly diagrams for FPRM and KRM forms, we devise a method to exhaustively construct all FPQF and KQF forms. Thus, the new forms can be used to optimize quantum circuits with arbitrary target unitary matrices, rather than only multi-controlled NOT gates such as CNOT, CCNOT, and their extensions. Experimental results on FPQF and KQF forms, as well as FPRM and KRM classical forms, applied to various target gates such as NOT, V, V+, Hadamard, and Pauli rotations, demonstrate that FPQF and KQF forms greatly reduce the gate cost of quantum multiplexers in both randomly generated data and FPRM benchmarks.
This paper introduces a new logic structure for reversible quantum circuit synthesis. Our synthesis method aims to minimize the quantum cost of reversible quantum circuits with decoders. In this method, multi-valued input, binary output (MVI) functions are utilized as a mathematical concept only, but the circuits are binary. We introduce the new concept of ``Multi-Valued Input Fixed Polarity Reed-Muller (MVI-RM)" forms. Our decoder-based circuit uses three logical levels in contrast to commonly-used methods based on Exclusive-or Sum of Products (ESOP) with two levels (AND-XOR expressions), realized by Toffoli gates. In general, the high number of input qubits in the resulting Toffoli gates is a problem that greatly impacts the quantum cost. Using decoders decreases the number of input qubits in these Toffoli gates. We present two practical algorithms for three-level circuit synthesis by finding the MVI-FPRM: products-matching and the newly developed butterfly diagrams. The best MVI-FPRM forms are factorized and reduced to approximate Multi-Valued Input Generalized Reed-Muller (MVI-GRM) forms.
We describe the use of Grover’s algorithm as implemented in a quantum logic circuit that produces a solution for a classical switching circuit design problem. The particular application described here is to determine a Fixed Polarity Reed-Muller (FPRM) form that satisfies a threshold value constraint, thus we find a particular FPRM form among all 2^n FPRM forms that has a number of terms less than or equal to the threshold value. Grover’s algorithm is implemented in a quantum logic circuit that also contains a subcircuit that expresses all possible FPRM solutions of a given function. This approach illustrates how fast transforms as known from spectral theory can be combined with quantum computing as a part of an oracle.
The article describes the method of design of quantum circuit specifications, based on tabulated Boolean functions data. The method is considered as an example of building a set of new Boolean quantum circuits synthesized based on Reed – Muller polarized polynomials (FPRM) to have the best polynomial forms on the basis of preliminary statistical analysis of certain FPRM characteristics at all polarities. Matrix entry and software implementation of basic quantum converters is described, includind: NOT, C1NOT, C2NOT, SWAP. An example of the construction of a set of quantum circuits for quantum Boolean function for a given 1–0 table presented. The article shows, that the problem of synthesis and optimization of quantum circuits can be reduced to the traditional logical decisions. Illustrations, demonstrating transitions from automatically synthesized quantum circuits for different polarities of the Reed-Muller polynomials to quantum circuits with the least number of converters, presented.