A Quantum Algorithm for the Classification of Patterns of Boolean Functions

• URL: http://arxiv.org/abs/2503.11722v1
• Date: Fri, 14 Mar 2025 00:26:36 GMT
• Title: A Quantum Algorithm for the Classification of Patterns of Boolean Functions
• Authors: Theodore Andronikos, Constantinos Bitsakos, Konstantinos Nikas, Georgios I. Goumas, Nectarios Koziris,
• Abstract summary: This paper introduces a novel quantum algorithm that is able to classify a hierarchy of classes of imbalanced Boolean functions.<n>Our algorithm achieves classification in a straightforward manner as the final measurement reveals the unknown function with probability $1$.
• Score: 2.209328709671456
• License: http://creativecommons.org/licenses/by/4.0/
• 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 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$. 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.

Related papers

• Quantum Classification Outside the Promised Class [2.209328709671456]
  We investigate whether it is feasible to obtain insights when the input function deviates from the promised class. We use a recently introduced quantum algorithm that is designed to classify with probability $1.0$ using just a single oracular query. We show that, as long as the input function is close enough to the promised class, it is still possible to obtain useful information.
  arXiv  Detail & Related papers  (2025-04-26T11:50:58Z)
• Ehrenfeucht-Haussler Rank and Chain of Thought [51.33559894954108]
  We show that the rank of a function $f$ corresponds to the minimum number of Chain of Thought steps required by a single-layer transformer decoder.<n>We also analyze the problem of identifying the position of the $k$-th occurrence of 1 in a Boolean sequence, proving that it requires $k$ CoT steps.
  arXiv  Detail & Related papers  (2025-01-22T16:30:58Z)
• Achieving More with Less: A Tensor-Optimization-Powered Ensemble Method [53.170053108447455]
  Ensemble learning is a method that leverages weak learners to produce a strong learner. We design a smooth and convex objective function that leverages the concept of margin, making the strong learner more discriminative. We then compare our algorithm with random forests of ten times the size and other classical methods across numerous datasets.
  arXiv  Detail & Related papers  (2024-08-06T03:42:38Z)
• Look into the Mirror: Evolving Self-Dual Bent Boolean Functions [35.305121158674964]
  This paper experiments with evolutionary algorithms with the goal of evolving (anti-)self-dual bent Boolean functions. We successfully construct self-dual bent functions for each dimension. We also tried evolving secondary constructions for self-dual bent functions, but this direction provided no successful results.
  arXiv  Detail & Related papers  (2023-11-20T16:20:16Z)
• A New Angle: On Evolving Rotation Symmetric Boolean Functions [32.90791284928444]
  This paper uses several evolutionary algorithms to evolve rotation symmetric Boolean functions with different properties. Surprisingly, we find bitstring and floating point encodings work better than the tree encoding.
  arXiv  Detail & Related papers  (2023-11-20T16:16:45Z)
• Gradient-free optimization of highly smooth functions: improved analysis and a new algorithm [87.22224691317766]
  This work studies problems with zero-order noisy oracle information under the assumption that the objective function is highly smooth. We consider two kinds of zero-order projected gradient descent algorithms.
  arXiv  Detail & Related papers  (2023-06-03T17:05:13Z)
• Learning Two-Player Mixture Markov Games: Kernel Function Approximation and Correlated Equilibrium [157.0902680672422]
  We consider learning Nash equilibria in two-player zero-sum Markov Games with nonlinear function approximation. We propose a novel online learning algorithm to find a Nash equilibrium by minimizing the duality gap.
  arXiv  Detail & Related papers  (2022-08-10T14:21:54Z)
• Don't Explain Noise: Robust Counterfactuals for Randomized Ensembles [50.81061839052459]
  We formalize the generation of robust counterfactual explanations as a probabilistic problem. We show the link between the robustness of ensemble models and the robustness of base learners. Our method achieves high robustness with only a small increase in the distance from counterfactual explanations to their initial observations.
  arXiv  Detail & Related papers  (2022-05-27T17:28:54Z)
• Polynomial representation of general partial Boolean functions with a single quantum query [0.0]
  Early in 1992, Deutsch-Jozsa algorithm computed a symmetric partial Boolean function with a single quantum query. This paper proves and discovers three new results.
  arXiv  Detail & Related papers  (2021-12-23T08:45:06Z)
• Provably efficient, succinct, and precise explanations [17.176431214060063]
  We consider the problem of explaining the predictions of an arbitrary blackbox model $f$. We design an efficient algorithm with provable guarantees on the succinctness and precision of the explanations that it returns.
  arXiv  Detail & Related papers  (2021-11-01T17:35:10Z)
• Quantifying and Improving Transferability in Domain Generalization [53.16289325326505]
  Out-of-distribution generalization is one of the key challenges when transferring a model from the lab to the real world. We formally define transferability that one can quantify and compute in domain generalization. We propose a new algorithm for learning transferable features and test it over various benchmark datasets.
  arXiv  Detail & Related papers  (2021-06-07T14:04:32Z)
• A quantum algorithm to estimate the Gowers $U_2$ norm and linearity testing of Boolean functions [6.8072479152471566]
  We propose a quantum algorithm to estimate the Gowers $U$ norm of a Boolean function. We extend it into a second algorithm to distinguish between linear Boolean functions and Boolean functions that are $epsilon$-far from the set of linear Boolean functions.
  arXiv  Detail & Related papers  (2020-06-30T04:39:20Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.