Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2504.18898 · Computers

Quantum Classification Outside the Promised Class

Theodore Andronikos, Constantinos Bitsakos, Konstantinos Nikas, Georgios Goumas, Nectarios Koziris

Published Jun 10, 2025• 2 citations
arXivHTMLPDF

Abstract

This paper studies the important problem of quantum classification of Boolean functions from an entirely novel perspective. Typically, quantum classification algorithms allow us to classify functions with a probability of 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 a large class of imbalanced Boolean functions with probability 1.0 using just a single oracular query. First, we establish a completely new concept characterizing “nearness” between Boolean functions. Utilizing this concept, we show that, as long as the unknown 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.

DOI
10.3390/computers14060228

Related papers

A Quantum Algorithm for the Classification of Patterns of Boolean Functions

Theodore Andronikos, Constantinos Bitsakos, Konstantinos Nikas +2 more

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.

arXiv:2503.11722•Mathematics•May 25, 2025•3 citations

Probabilistic Links Between Quantum Classification of Patterns of Boolean Functions and Hamming Distance

Theodore Andronikos, Constantinos Bitsakos, Konstantinos Nikas +2 more

This article investigates the probabilistic relationship between quantum classification of Boolean functions and their Hamming distance. By integrating concepts from quantum computing, information theory, and combinatorics, we explore how Hamming distance serves as a metric for analyzing deviations in function classification. Our extensive experimental results confirm that the Hamming distance is a pivotal metric for validating nearest neighbors in the process of classifying random functions. One of the significant conclusions we arrived is that the successful classification probability decreases monotonically with the Hamming distance. However, key exceptions were found in specific classes, revealing intra-class heterogeneity. We have established that these deviations are not random but are systemic and predictable. Furthermore, we were able to quantify these irregularities, turning potential errors into manageable phenomena. The most important novelty of this work is the demarcation, for the first time to the best of our knowledge, of precise Hamming distance intervals for the classification probability. These intervals bound the possible values the probability can assume, and provide a new foundational tool for probabilistic assessment in quantum classification. Practitioners can now endorse classification results with high certainty or dismiss them with confidence. This framework can significantly enhance any quantum classification algorithm’s reliability and decision-making capability.

arXiv:2510.12736•Stats•Jan 1, 2026•2 citations

Image Classification via Quantum Machine Learning

Héctor Iván García Hernández, Raymundo Torres Ruiz, Guo-Hua Sun

Quantum Computing and especially Quantum Machine Learning, in a short period of time, has gained a lot of interest through research groups around the world. This can be seen in the increasing number of proposed models for pattern classification applying quantum principles to a certain degree. Despise the increasing volume of models, there is a void in testing these models on real datasets and not only on synthetic ones. The objective of this work is to classify patterns with binary attributes using a quantum classifier. Specially, we show results of a complete quantum classifier applied to image datasets. The experiments show favorable output while dealing with balanced classification problems as well as with imbalanced classes where the minority class is the most relevant. This is promising in medical areas, where usually the important class is also the minority class.

arXiv:2011.02831•Nov 3, 2020•10 citations

Properties and application of nondeterministic quantum query algorithms

Alina Dubrovska

Many quantum algorithms can be analyzed in a query model to compute Boolean functions where input is given by a black box. As in the classical version of decision trees, different kinds of quantum query algorithms are possible: exact, with bounded error and even nondeterministic. In this paper, we study the latter class of algorithms. We introduce a new notion in addition to already studied nondeterministic algorithms and introduce dual nondeterministic quantum query algorithms. We examine properties of such algorithms and prove relations with exact and nondeterministic quantum query algorithm complexity. As a result and as an example of the application of discovered properties, we demonstrate a gap of n vs. 2 between classical deterministic and dual nondeterministic quantum query complexity for a specific Boolean function. Finally, we show an approach how to construct examples where quantum nondeterministic complexity of an algorithm is O(1), however classical deterministic algorithm for the same function would require O(n) queries.

arXiv:quant-ph/0606248•Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•Apr 27, 2007•3 citations

A Fast Quantum Algorithm for the Affine Boolean Function Identification

Ahmed Younes

Bernstein-Vazirani algorithm (the one-query algorithm) can identify a completely specified linear Boolean function using a single query to the oracle with certainty. The first aim of the paper is to show that if the provided Boolean function is affine, then one more query to the oracle (the two-query algorithm) is required to identify the affinity of the function with certainty. The second aim of the paper is to show that if the provided Boolean function is incompletely defined, then the one-query and the two-query algorithms can be used as bounded-error quantum polynomial algorithms to identify certain classes of incompletely defined linear and affine Boolean functions respectively with probability of success at least $2/3$.

arXiv:1407.6402•Jul 23, 2014•1 citation

Characterization of exact one-query quantum algorithms (ii): for partial functions

Zekun Ye, Lvzhou Li

The query model (or black-box model) has attracted much attention from the communities of both classical and quantum computing. Usually, quantum advantages are revealed by presenting a quantum algorithm that has a better query complexity than its classical counterpart. For example, the well-known quantum algorithms including Deutsch-Jozsa algorithm, Simon algorithm and Grover algorithm all show a considerable advantage of quantum computing from the viewpoint of query complexity. Recently we have considered in (Phys. Rev. A. {\bf 101}, 02232 (2020)) the problem: what functions can be computed by an exact one-query quantum algorithm? This problem has been addressed for total Boolean functions but still open for partial Boolean functions. Thus, in this paper we continue to characterize the computational power of exact one-query quantum algorithms for partial Boolean functions by giving several necessary and sufficient conditions. By these conditions, we construct some new functions that can be computed exactly by one-query quantum algorithms but have essential difference from the already known ones. Note that before our work, the known functions that can be computed by exact one-query quantum algorithms are all symmetric functions, whereas the ones constructed in this papers are generally asymmetric.

arXiv:2008.11998•Aug 27, 2020•1 citation
This paper studies the important problem of quantum classification of Boolean functions from an entirely novel perspective. Typically, quantum classification algorithms allow us to classify functions with a probability of 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 a large class of imbalanced Boolean functions with probability 1.0 using just a single oracular query. First, we establish a completely new concept characterizing “nearness” between Boolean functions. Utilizing this concept, we show that, as long as the unknown 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.
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.
This article investigates the probabilistic relationship between quantum classification of Boolean functions and their Hamming distance. By integrating concepts from quantum computing, information theory, and combinatorics, we explore how Hamming distance serves as a metric for analyzing deviations in function classification. Our extensive experimental results confirm that the Hamming distance is a pivotal metric for validating nearest neighbors in the process of classifying random functions. One of the significant conclusions we arrived is that the successful classification probability decreases monotonically with the Hamming distance. However, key exceptions were found in specific classes, revealing intra-class heterogeneity. We have established that these deviations are not random but are systemic and predictable. Furthermore, we were able to quantify these irregularities, turning potential errors into manageable phenomena. The most important novelty of this work is the demarcation, for the first time to the best of our knowledge, of precise Hamming distance intervals for the classification probability. These intervals bound the possible values the probability can assume, and provide a new foundational tool for probabilistic assessment in quantum classification. Practitioners can now endorse classification results with high certainty or dismiss them with confidence. This framework can significantly enhance any quantum classification algorithm’s reliability and decision-making capability.
Quantum Computing and especially Quantum Machine Learning, in a short period of time, has gained a lot of interest through research groups around the world. This can be seen in the increasing number of proposed models for pattern classification applying quantum principles to a certain degree. Despise the increasing volume of models, there is a void in testing these models on real datasets and not only on synthetic ones. The objective of this work is to classify patterns with binary attributes using a quantum classifier. Specially, we show results of a complete quantum classifier applied to image datasets. The experiments show favorable output while dealing with balanced classification problems as well as with imbalanced classes where the minority class is the most relevant. This is promising in medical areas, where usually the important class is also the minority class.
Many quantum algorithms can be analyzed in a query model to compute Boolean functions where input is given by a black box. As in the classical version of decision trees, different kinds of quantum query algorithms are possible: exact, with bounded error and even nondeterministic. In this paper, we study the latter class of algorithms. We introduce a new notion in addition to already studied nondeterministic algorithms and introduce dual nondeterministic quantum query algorithms. We examine properties of such algorithms and prove relations with exact and nondeterministic quantum query algorithm complexity. As a result and as an example of the application of discovered properties, we demonstrate a gap of n vs. 2 between classical deterministic and dual nondeterministic quantum query complexity for a specific Boolean function. Finally, we show an approach how to construct examples where quantum nondeterministic complexity of an algorithm is O(1), however classical deterministic algorithm for the same function would require O(n) queries.
Bernstein-Vazirani algorithm (the one-query algorithm) can identify a completely specified linear Boolean function using a single query to the oracle with certainty. The first aim of the paper is to show that if the provided Boolean function is affine, then one more query to the oracle (the two-query algorithm) is required to identify the affinity of the function with certainty. The second aim of the paper is to show that if the provided Boolean function is incompletely defined, then the one-query and the two-query algorithms can be used as bounded-error quantum polynomial algorithms to identify certain classes of incompletely defined linear and affine Boolean functions respectively with probability of success at least 2/32/32/3.
The query model (or black-box model) has attracted much attention from the communities of both classical and quantum computing. Usually, quantum advantages are revealed by presenting a quantum algorithm that has a better query complexity than its classical counterpart. For example, the well-known quantum algorithms including Deutsch-Jozsa algorithm, Simon algorithm and Grover algorithm all show a considerable advantage of quantum computing from the viewpoint of query complexity. Recently we have considered in (Phys. Rev. A. {\bf 101}, 02232 (2020)) the problem: what functions can be computed by an exact one-query quantum algorithm? This problem has been addressed for total Boolean functions but still open for partial Boolean functions. Thus, in this paper we continue to characterize the computational power of exact one-query quantum algorithms for partial Boolean functions by giving several necessary and sufficient conditions. By these conditions, we construct some new functions that can be computed exactly by one-query quantum algorithms but have essential difference from the already known ones. Note that before our work, the known functions that can be computed by exact one-query quantum algorithms are all symmetric functions, whereas the ones constructed in this papers are generally asymmetric.