Inverse Problems, Constraint Satisfaction, Reversible Logic, Invertible Logic and Grover Quantum Oracles for Practical Problems

Published In

Science of Computer Programming

Document Type

Citation

Publication Date

6-1-2022

Abstract

It is well-known that the “Unsorted Database” quantum algorithm by Grover gives quadratic speedup to several practically important combinatorial and enumerative problems, such as: SAT, Graph Coloring, Maximum Cliques, Traveling Salesman and many others. Recently, quantum programming languages such as QISKIT, QSHARP or Quipper start to be used to design, verify and simulate practical quantum algorithms for important problems in Quantum Machine Learning or optimization. So far, however, no methodologies have been created to program Grover's Oracles for particular classes of problems. In contrast, such methodologies have been already created for classical Constraint Satisfaction Problems (CSP). Invertible Logic was recently introduced by Supriyo Datta and his team. The goal of this paper is to present results of our research towards creating a systematic methodology to solve search problems in Artificial Intelligence, Logic Design and Machine Learning by repeated applications of modified hardware oracles. These oracles can use: (1) classical Boolean logic, (2) quantum logic, or (3) invertible logic. Our methodology to design and exercise all types of general oracles is based on bottom-up synthesis and technology transformations. For CSP problems we apply unified blocks which use various data representations and encodings.

Rights

© 2022 Published by Elsevier B.V.

DOI

10.1016/j.scico.2022.102775

Persistent Identifier

https://archives.pdx.edu/ds/psu/37887

Share

COinS