A Quantum Algorithm for the Classification of Patterns of Boolean Functions

Theodore Andronikos, Constantinos Bitsakos, Konstantinos Nikas, Georgios I. Goumas, Nectarios Koziris · 2025

Read A Quantum Algorithm for the Classification of Patterns of Boolean Functions by Theodore Andronikos, Constantinos Bitsakos, Konstantinos Nikas, Georgios I. Goumas, Nectarios Koziris (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-11722.txt.

Introduction

Theodore Andronikos and co-authors give a quantum algorithm that sorts Boolean functions by pattern in a 2025 paper. Imbalanced functions return zero and one at unequal rates. Classes in their hierarchy group functions by that imbalance ratio. Telling classes apart is the task.

Their algorithm reads the class off one final measurement with certainty. It queries the oracle just once, which makes it optimal of its kind. The design method is laid out step by step in the paper. The authors hope it extends to other function families with distinct behavior patterns. The work adds a clean, exact case to the quantum algorithm shelf, where most wins are matters of degree.

Catalog record

CREATORTheodore Andronikos, Constantinos Bitsakos, Konstantinos Nikas, Georgios I. Goumas, Nectarios Koziris
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE22 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-11722

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A Quantum Algorithm for the Classification of Patterns of Boolean Functions Theodore Andronikos, Constantinos Bitsakos, Konstantinos Nikas, Georgios I. Goumas, Nectarios Koziris 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 0 is not equal to the proportion of elements that take the value 1 1 . For every positive integer n n , the hierarchy contains a class of Boolean functions defined based on 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 probability 1 1 . Let us also note that the proposed algorithm is an optimal oracular algorithm because it can classify the aforementioned functions with 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. 1 Introduction The endeavor to construct quantum computers that surpass the capabilities of classical computers poses a significant challenge in our era. It is important to acknowledge that this goal has not yet been realized. However, substantial progress is evident, as illustrated by IBM’s advancements with the 127-qubit Eagle [ IBMEagle2021 ] , the 433-qubit Osprey [ IBMOsprey2022 ] , the 1,121-qubit Condor [ IBMCondor2023 ] , and the latest and most powerful R2 Heron [ IBMHeron2024 ] . These developments suggest a swift movement towards the practical application of quantum technology. All these suggest that quantum technology has reached a level of maturity that warrants careful consideration in the development and implementation of algorithms targeting difficult problems. The imperative to enhance the scale of quantum computers represents the most significant obstacle to their potential application in industrial-scale problems. It has become evident that advancing quantum computers beyond the Noisy Intermediate-Scale Quantum (NISQ) level will necessitate scientific breakthroughs and the resolution of various technological hurdles. In our assessment, the most promising strategy to address the scaling dilemma currently lies in the advancement of distributed quantum computing systems. In the realm of classical computing, the concept of interlinking smaller processors to distribute computational tasks emerged as a solution to scaling difficulties. This principle is believed to be equally relevant to quantum computing, where the scaling challenge encourages the exploration of connecting smaller quantum computers. A distributed quantum computing system would comprise a network of quantum nodes, each possessing a specific number of qubits for processing and the capability to transmit both classical and quantum information. Nevertheless, the inherent differences between quantum and classical computing introduce unique challenges, not present in classical networks, in the design of networked quantum computers. Fortunately, recently there have been significant technological advancements in hardware [ Photonic2024 , NuQuantum2024 ] and design concepts [ Cacciapuoti2024 , Illiano2024 ] . In fact, very recently researchers demonstrated distributed quantum computing by employing a photonic network interface to effectively connect two distinct quantum processors, thus, creating a unified and fully integrated quantum computer [ Main2025 , OxfordNewsEvents2025 ] . It is our firm belief that we are entering the era of distributed quantum computing. In this work, we introduce a new quantum algorithm that classifies classes of Boolean functions that are characterized by a specific patterns that demonstrate imbalance. The fundamental characteristic of these 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 . We refer to this algorithm as the Boolean Function Pattern Quantum Classifier, or BFPQC for short. We have drawn inspiration mainly from the many sophisticated works studying various extensions of the Deutsch-Jozsa algorithm. Already in [ Cleve1998 ] , the authors examined a multidimensional version of the Deutsch–Jozsa problem. This was further expanded in [ Chi2001 ] by considering evenly distributed and evenly balanced functions. Subsequently, in [ Holmes2003 ] the Deutsch–Jozsa algorithm was extended for balanced functions in finite Abelian subgroups. Another generalization appeared in [ Ballhysa2004 ] . Later, the researchers in [ Qiu2018 ] generalized the Deutsch–Jozsa problem and gave an optimal algorithm. A more recent clever generalization of the Deutsch–Jozsa algorithm can be found in [ OssorioCastillo2023 ] . Useful applications of the Deutsch–Jozsa algorithm were also obtained in [ Qiu2020 ] and in [ Zhengwei2021 ] . Two particularly interesting works towards establishing a distributed version of the Deutsch–Jozsa algorithm were [ Tanasescu2019 ] and [ Li2025 ] . In a related development, the authors in [ Nagata2020 ] extended Deutsch’s algorithm for binary Boolean functions. We should also mention that oracular algorithm geared towards computing Boolean functions or achieving classification are often encountered in the literature on Quantum Learning and Quantum Machine Learning. Some noteworthy studies in these areas include [ Bshouty1998 , Farhi1999 , Servedio2004 , Hunziker2009 , Yoo2014 , Cross2015 ] . The fundamental characteristic of the Deutsch-Jozsa algorithm and its subsequent extensions is the distinction among constant and balanced functions, i.e., functions that the number of elements in their domain that take the value 0 is equal to the number of elements that take the value 1 . Here, to differentiate from this trend, we study imbalanced functions focusing on classifying specific patterns. We present our algorithm in the form of game, featuring the familiar characters of Alice and Bob. It is anticipated that the entertaining aspect of games will facilitate a clearer understanding of the technical concepts presented. Since their introduction in 1999 [ Meyer1999 , Eisert1999 ] , quantum games have gained considerable popularity, as quantum strategies often outperform classical ones [ Andronikos2018 , Andronikos2021 , Andronikos2022a ] . A notable illustration of this is the well-known Prisoners’ Dilemma [ Eisert1999 ] , which serves as a prime example and is applicable to various other abstract quantum games [ Giannakis2015a , Koh2024 ] . Furthermore, many classical systems can be transformed into quantum versions, including political frameworks, as demonstrated in recent studies [ Andronikos2022 ] . Especially cryptographic protocols like Quantum Key Distribution, Quantum Secret Sharing, Quantum Private Comparison, etc. are very often presented as interactions among signature players, including famous figures such as Alice, Bob, Charlie, Eve (see the recent works [ Ampatzis2021 , Ampatzis2022 , Ampatzis2023 , Andronikos2023 , Andronikos2023a , Andronikos2023b , Karananou2024 , Andronikos2024 , Andronikos2024a , Andronikos2024b , Andronikos2025 ] . In discussing games set within unconventional environments, it is noteworthy that games involving biological systems have garnered considerable interest [ Theocharopoulou2019 , Kastampolidou2020a , Kostadimas2021 ] . It is particularly intriguing to note that biosystems can lead to biostrategies that may outperform traditional strategies, even in the renowned Prisoners’ Dilemma game [ Kastampolidou2020 , Kastampolidou2021 , Papalitsas2021 , Kastampolidou2023 , Adam2023 ] . Contribution . Numerous sophisticated studies have

Read the complete text