Quantum Classification Outside the Promised Class
Theodore Andronikos, Constantinos Bitsakos, Konstantinos Nikas, Georgios I. Goumas, Nectarios Koziris · 2025
Read Quantum Classification Outside the Promised Class 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-2504-18898.txt.
Introduction
Andronikos leads a team asking what quantum classification can reveal when a function breaks its promise in a 2025 paper. Standard quantum classifiers give exact answers only when inputs meet strict conditions. Real inputs may drift from those conditions.
The study uses a recent algorithm that classifies a large family of lopsided Boolean functions with a single oracle query. A new notion of nearness between Boolean functions is defined first. When an input stays close enough to the promised family, the algorithm still yields useful clues about its behavior. The authors call this early evidence that off-promise inputs are not wasted. The result hints at more forgiving quantum algorithms. Theory, not hardware, is the setting.
Catalog record
| CREATOR | Theodore Andronikos, Constantinos Bitsakos, Konstantinos Nikas, Georgios I. Goumas, Nectarios Koziris |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 53 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-18898
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Quantum Classification Outside the Promised Class Theodore Andronikos, Constantinos Bitsakos, Konstantinos Nikas, Georgios I. Goumas, Nectarios Koziris Abstract This paper studies the important problem of quantum classification of Boolean functions from a entirely novel perspective. Typically, quantum classification algorithms allow us to classify functions with a probability of 1.0 1.0 , if we are promised that they meet specific unique properties. The primary objective of this study is to explore whether it is feasible to obtain any insights when the input function deviates from the promised class. For concreteness, we use a recently introduced quantum algorithm that is designed to classify with probability 1.0 1.0 using just a single oracular query a large class of imbalanced Boolean functions. Fist, we establish a completely new concept characterizing “nearness” between Boolean function. Utilizing this concept, we show that, as long as the input function is close enough to the promised class, it is still possible to obtain useful information about its behavioral pattern from the classification algorithm. In this regard, the current study is among the first to provide evidence that shows how useful it is to apply quantum classification algorithms to functions outside the promised class in order to get a glimpse of important information. Keywords: : Quantum algorithm, Boolean function, pattern, oracle, classification. \usephysicsmodule braket 1 Introduction In the realm of quantum computing, let us first recognize that there aren’t any quantum computers that are strong enough to upend the status quo at this time. However, given the astounding developments in recent years, this is probably going to change sooner rather than later. Over the past few months, the majority of the key players in this field have made remarkable strides. Following the success of the 127-qubit Eagle [ IBMEagle2021 ] and the 433-qubit Osprey [ IBMOsprey2022 ] , IBM has now introduced the 1,121-qubit Condor [ IBMCondor2023 ] and the newest and most powerful R2 Heron [ IBMHeron2024 ] . Google has recently showcased the capability of quantum computers to surpass the performance of the most advanced supercomputers available today, as referenced in [ GoogleWillow2024 , NatureGoogle2024 ] . Microsoft has unveiled the groundbreaking Majorana 1 quantum chip, as noted in [ Aasen2025 , Aghaee2025 , MicrosoftMajorana2025 ] that promises to be a game-changer. Regarding quantum annealers, D-Wave announced that they used a quantum processor to solve the first scientifically significant problem more quickly than they could have with a classical computer [ King2025 , NatureD-Wave2025 ] . At the same time, other research teams have reported significant breakthroughs. Although this report is far from exhaustive, we believe that some of the most significant recent advancements are as follows. The state-of-the-art Zuchongzhi 3.0 quantum processor, featuring 105 qubits, represents a significant technological achievement [ Gao2025 , APSNewsZuchongzhi3.0-2025 ] . Other significant developments include design concepts [ Cacciapuoti2024 , Illiano2024 ] and hardware [ Photonic2024 , NuQuantum2024 ] . Researchers recently demonstrated distributed quantum computing by successfully connecting two separate quantum processors using a photonic network interface, resulting in a single, fully integrated quantum computer [ Main2025 , OxfordNewsEvents2025 ] . We believe that distributed quantum computing is currently becoming a reality. This work examines the significant issue of quantum classification of Boolean functions from a completely new angle. It is generally possible to classify functions using quantum classification algorithms with a probability of 1.0 if we are promised that they satisfy certain special characteristics. This study’s main goal is to determine whether it is possible to gain any understanding when the input function deviates from the promised class. Staring from the ground-breaking Deutsch-Jozsa algorithm [ Deutsch1992 ] , numerous sophisticated works for quantum classification have appeared. The authors in [ Cleve1998 ] investigated a multidimensional variant of the Deutsch–Jozsa problem, which was subsequently elaborated upon in [ Chi2001 ] through the analysis of evenly distributed and balanced functions. Further advancements were made in [ Holmes2003 ] , where the Deutsch–Jozsa algorithm was adapted for balanced functions within finite Abelian subgroups. Another significant generalization was introduced in [ Ballhysa2004 ] . In [ Qiu2018 ] , researchers expanded the Deutsch–Jozsa problem and proposed an optimal algorithm. A more recent and innovative generalization of the Deutsch–Jozsa algorithm is presented in [ OssorioCastillo2023 ] . Additionally, practical applications of the Deutsch–Jozsa algorithm were explored in [ Qiu2020 ] and [ Zhengwei2021 ] . Notably, two significant contributions towards developing a distributed version of the Deutsch–Jozsa algorithm can be found in [ Tanasescu2019 ] and [ Li2025 ] . In a related context, the authors in [ Nagata2020 ] extended Deutsch’s algorithm to binary Boolean functions. It is also important to note that oracular algorithms designed for computing Boolean functions or for classification purposes are frequently discussed in the literature on Quantum Learning and Quantum Machine Learning, with notable studies including [ Bshouty1998 ] , [ Farhi1999 ] , [ Servedio2004 ] , [ Hunziker2009 ] , [ Yoo2014 ] , and [ Cross2015 ] . The vast majority of these works focus on the differentiation between constant and balanced functions, which are defined as functions where the number of elements in their domain that yield the value 0 is equal to those that yield the value 1 . In contrast to this trend, a very recent study [ Andronikos2025a ] focuses on imbalanced functions with an emphasis on classifying a large class of such functions exhibiting specific behavioral patterns with a novel quantum algorithm termed BFPQC for Boolean Function Pattern Quantum Classifier. Our algorithm is presented as a game with the well-known Alice and Bob as characters. Games’ entertaining elements are expected to help people comprehend the technical ideas more clearly. Since 1999 [ Meyer1999 , Eisert1999 ] , quantum games have become increasingly popular because quantum strategies frequently perform better than classical ones [ Andronikos2018 , Andronikos2021 , Andronikos2022a ] . This is best demonstrated by the well-known Prisoners’ Dilemma [ Eisert1999 ] , which is a good example that can be applied to a number of other abstract quantum games [ Giannakis2015a , Koh2024 ] . Although quantum games seem like fun, they have been used to solve serious problems like like Quantum Key Distribution, Quantum Secret Sharing, Quantum Private Comparison (see [ Bennett1984 , Ampatzis2021 , Ampatzis2022 , Ampatzis2023 , Andronikos2023 , Andronikos2023a , Andronikos2023b , Karananou2024 , Andronikos2024 , Andronikos2024a , Andronikos2024b , Andronikos2025 ] ). Many classical systems can be transformed into quantum versions, including political frameworks, as demonstrated in recent studies [ Andronikos2022 ] . When it comes to games that take place in unusual settings, it is important to note that games that feature biological systems have attracted a lot of attention [ Theocharopoulou2019 , Kastampolidou2020a , Kostadimas2021 ] . The fact that biosystems can produce biostrategies that might perform better than conventional strategies—even in the well-known Prisoners’ Dilemma game—is especially fascinating [ Kastampolidou2020 , Kastampolidou2021 , Papalitsas2021 , Kastampolidou2023 , Adam2023 ] . Contribution . Generally, by utilizing a quantum classification algorithm, we can classify functions that meet specific properties with a probability of 1.0 . In the literature, it is common to encounter a phrase indicating that we have been assured the classifiable functions possess these special properties, leading to the term “promise”