Marek A. Perkowski

FLAP Journal 2023 Journal Article

Quantum Algorithms for Unate and Binate Covering Problems with Application to Finite State Machine Minimization.

• Abdirahman Alasow
• Marek A. Perkowski

Covering problems find applications in many areas of computer science and engineering, such that numerous combinatorial problems can be formulated as covering problems. Combinatorial optimization problems are generally NP- hard problems that require an extensive search to find the optimal solution. Exploiting the benefits of quantum computing, we present a quantum oracle design for covering problems, taking advantage of Grover’s search algorithm to achieve quadratic speedup. This paper also discusses applications of the quan- tum counter in unate covering problems and binate covering problems with some important practical applications, such as finding prime implicants of a Boolean function, implication graphs, and minimization of incompletely specified Finite State Machines.

FLAP Journal 2022 Journal Article

Quantum Machine Learning, Logic Minimization, and Circuit Design by Optimizing Ternary-Input Binary-Output Kronecker Reed-Muller Forms.

• Maggie Bao
• Cole Powers
• Marek A. Perkowski

This paper introduces a new spectral transform for ternary-input binaryoutput functions that generalizes the well-known binary Kronecker Reed-Muller forms. The two binary Davio Expansions are generalized to 27 ternary-input Davio Expansions. The new Hybrid Kronecker Reed-Muller spectrum has 28n expansions for n ternary variables. By creating an oracle for this problem, we generalize past quantum Grover-based algorithms presented for the binary Fixed-Polarity Reed-Muller and Kronecker Reed-Muller transforms. Our quantum algorithm is for different variants of ternary-input binary-output forms realized on Grover’s Algorithms with either binary or binary/ternary control variables. We create several variants of expansions including binary and ternary control variables, which leads to a modification of Grover’s Algorithm for term minimization in the new expressions. The algorithm can be applied to incompletely specified functions, thus, introducing a new approach to quantum Machine Learning. The results of the binary Grover’s Algorithm simulation in Qiskit are presented.

FLAP Journal 2020 Journal Article

A Polarity-based Approach for Optimization of Multivalued Quantum Multiplexers with Arbitrary Single-qubit Target Gates.

• Kevin Jin
• Tahsin Saffat
• Justin Morgan
• Marek A. Perkowski

TCS Journal 2011 Journal Article

Realization and synthesis of reversible functions

• Guowu Yang
• Fei Xie
• William N.N. Hung
• Xiaoyu Song
• Marek A. Perkowski

Reversible circuits play an important role in quantum computing. This paper studies the realization problem of reversible circuits. For any n -bit reversible function, we present a constructive synthesis algorithm. Given any n -bit reversible function, there are N distinct input patterns different from their corresponding outputs, where N ≤ 2 n, and the other ( 2 n − N ) input patterns will be the same as their outputs. We show that this circuit can be synthesized by at most 2 n ⋅ N ‘ ( n − 1 ) ’-CNOT gates and 4 n 2 ⋅ N NOT gates. The time and space complexities of the algorithm are Ω ( n ⋅ 4 n ) and Ω ( n ⋅ 2 n ), respectively. The computational complexity of our synthesis algorithm is exponentially lower than that of breadth-first search based synthesis algorithms.