A Quantum Algorithm for the Classification of Patterns of Boolean Functions
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 e...
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2025-05-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/13/11/1750 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850160945735663616 |
|---|---|
| author | Theodore Andronikos Constantinos Bitsakos Konstantinos Nikas Georgios I. Goumas Nectarios Koziris |
| author_facet | Theodore Andronikos Constantinos Bitsakos Konstantinos Nikas Georgios I. Goumas Nectarios Koziris |
| author_sort | Theodore Andronikos |
| collection | DOAJ |
| description | 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, <i>n</i>, the hierarchy contains a class of <i>n</i>-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 <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mn>1.0</mn></mrow></semantics></math></inline-formula>. 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. |
| format | Article |
| id | doaj-art-02dc81df9e3847e6b54e73b4c19e9ee4 |
| institution | OA Journals |
| issn | 2227-7390 |
| language | English |
| publishDate | 2025-05-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Mathematics |
| spelling | doaj-art-02dc81df9e3847e6b54e73b4c19e9ee42025-08-20T02:23:00ZengMDPI AGMathematics2227-73902025-05-011311175010.3390/math13111750A Quantum Algorithm for the Classification of Patterns of Boolean FunctionsTheodore Andronikos0Constantinos Bitsakos1Konstantinos Nikas2Georgios I. Goumas3Nectarios Koziris4Department of Informatics, Ionian University, 7 Tsirigoti Square, 49100 Corfu, GreeceComputing Systems Laboratory, National Technical University of Athens, Heroon Polytechniou 9, 15780 Zografou, GreeceComputing Systems Laboratory, National Technical University of Athens, Heroon Polytechniou 9, 15780 Zografou, GreeceComputing Systems Laboratory, National Technical University of Athens, Heroon Polytechniou 9, 15780 Zografou, GreeceComputing Systems Laboratory, National Technical University of Athens, Heroon Polytechniou 9, 15780 Zografou, GreeceThis 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, <i>n</i>, the hierarchy contains a class of <i>n</i>-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 <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mn>1.0</mn></mrow></semantics></math></inline-formula>. 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.https://www.mdpi.com/2227-7390/13/11/1750quantum algorithmBoolean functionpatternoraclethe Deutsch–Jozsa algorithmclassification |
| spellingShingle | Theodore Andronikos Constantinos Bitsakos Konstantinos Nikas Georgios I. Goumas Nectarios Koziris A Quantum Algorithm for the Classification of Patterns of Boolean Functions Mathematics quantum algorithm Boolean function pattern oracle the Deutsch–Jozsa algorithm classification |
| title | A Quantum Algorithm for the Classification of Patterns of Boolean Functions |
| title_full | A Quantum Algorithm for the Classification of Patterns of Boolean Functions |
| title_fullStr | A Quantum Algorithm for the Classification of Patterns of Boolean Functions |
| title_full_unstemmed | A Quantum Algorithm for the Classification of Patterns of Boolean Functions |
| title_short | A Quantum Algorithm for the Classification of Patterns of Boolean Functions |
| title_sort | quantum algorithm for the classification of patterns of boolean functions |
| topic | quantum algorithm Boolean function pattern oracle the Deutsch–Jozsa algorithm classification |
| url | https://www.mdpi.com/2227-7390/13/11/1750 |
| work_keys_str_mv | AT theodoreandronikos aquantumalgorithmfortheclassificationofpatternsofbooleanfunctions AT constantinosbitsakos aquantumalgorithmfortheclassificationofpatternsofbooleanfunctions AT konstantinosnikas aquantumalgorithmfortheclassificationofpatternsofbooleanfunctions AT georgiosigoumas aquantumalgorithmfortheclassificationofpatternsofbooleanfunctions AT nectarioskoziris aquantumalgorithmfortheclassificationofpatternsofbooleanfunctions AT theodoreandronikos quantumalgorithmfortheclassificationofpatternsofbooleanfunctions AT constantinosbitsakos quantumalgorithmfortheclassificationofpatternsofbooleanfunctions AT konstantinosnikas quantumalgorithmfortheclassificationofpatternsofbooleanfunctions AT georgiosigoumas quantumalgorithmfortheclassificationofpatternsofbooleanfunctions AT nectarioskoziris quantumalgorithmfortheclassificationofpatternsofbooleanfunctions |