A Quantum Algorithm for the Classification of Patterns of Boolean Functions

Theodore Andronikos (), Constantinos Bitsakos, Konstantinos Nikas, Georgios I. Goumas and Nectarios Koziris
Additional contact information
Theodore Andronikos: Department of Informatics, Ionian University, 7 Tsirigoti Square, 49100 Corfu, Greece
Constantinos Bitsakos: Computing Systems Laboratory, National Technical University of Athens, Heroon Polytechniou 9, 15780 Zografou, Greece
Konstantinos Nikas: Computing Systems Laboratory, National Technical University of Athens, Heroon Polytechniou 9, 15780 Zografou, Greece
Georgios I. Goumas: Computing Systems Laboratory, National Technical University of Athens, Heroon Polytechniou 9, 15780 Zografou, Greece
Nectarios Koziris: Computing Systems Laboratory, National Technical University of Athens, Heroon Polytechniou 9, 15780 Zografou, Greece

Mathematics, 2025, vol. 13, issue 11, 1-23

Abstract: This paper introduces a novel quantum algorithm that is able to classify a hierarchy of classes of imbalanced Boolean functions. The fundamental characteristic of imbalanced Boolean functions is that the proportion of elements in their domain that take the value 0 is not equal to the proportion of elements that take the value 1. For every positive integer, n , the hierarchy contains a class of n -ary Boolean functions defined according to their behavioral pattern. The common trait of all the functions belonging to the same class is that they possess the same imbalance ratio. Our algorithm achieves classification in a straightforward manner as the final measurement reveals the unknown function with a probability of 1.0 . Let us also note that the proposed algorithm is an optimal oracular algorithm because it can classify the aforementioned functions with just a single query to the oracle. At the same time, we explain in detail the methodology we followed to design this algorithm in the hope that it will prove general and fruitful, given that it can be easily modified and extended to address other classes of imbalanced Boolean functions that exhibit different behavioral patterns.

Keywords: quantum algorithm; Boolean function; pattern; oracle; the Deutsch–Jozsa algorithm; classification (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2025
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/13/11/1750/pdf (application/pdf)
https://www.mdpi.com/2227-7390/13/11/1750/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:13:y:2025:i:11:p:1750-:d:1663960

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().