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.
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.
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.
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.
Cardinality-constrained binary optimization is a fundamental computational primitive with broad applications in machine learning, finance, and scientific computing. In this work, we introduce a Grover-based quantum algorithm that exploits the structure of the fixed-cardinality feasible subspace under a natural promise on solution existence. For quadratic objectives, our approach achieves O(M(kn)) Grover rotations for any fixed cardinality k and degeneracy of the optima M, yielding an exponential reduction in the number of Grover iterations compared with unstructured search over {0,1}n. Building on this result, we develop a hybrid classical--quantum framework based on the alternating direction method of multipliers (ADMM) algorithm. The proposed framework is guaranteed to output an ε-approximate solution with a consistency tolerance ε+δ using at most $ {O}\left(\sqrt{\binom{n}{k}}\frac{n^{6}k^{3/2} }{ \sqrt{M}ε^2 δ}\right)$ queries to a quadratic oracle, together with O(ε2δn6k3/2) classical overhead. Overall, our method suggests a practical use of quantum resources and demonstrates an exponential improvements over existing Grover-based approaches in certain parameter regimes, thereby paving the way toward quantum advantage in constrained binary optimization.
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.
The K-SAT problem is a fundamental challenge in computational theory, widely used in artificial intelligence, cryptography, and optimization. Classical algorithms struggle with exponential time complexity, making them inefficient for large-scale instances. In this research, we propose an efficient quantum computing approach based on Grover’s algorithm to enhance the search process for satisfiable solutions in K-SAT problems. Our implementation leverages quantum superposition and amplitude amplification to explore multiple possible solutions simultaneously, reducing the search complexity from O (2ⁿ) in classical methods to O(√2ⁿ) in quantum computing. We design a quantum oracle that encodes the K-SAT clauses and integrates it into Grover’s iterative search framework. The performance is evaluated through Qiskit simulations, demonstrating a significant improvement in search efficiency compared to classical brute-force techniques. The results highlight the potential of quantum algorithms in solving complex combinatorial problems with enhanced speed and accuracy. This study contributes to the development of quantum-accelerated optimization methods, paving the way for real-world applications in machine learning, cryptanalysis, and large-scale data processing.