A Quantum Algorithm for the Classification of Patterns of Boolean Functions

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.

References in corpus (16)

• Quantum cryptography: Public key distribution and coin tossing
• Quantum Algorithms Revisited
• Quantum Games and Quantum Strategies
• Quantum strategies
• Distributed Quantum Computing across an Optical Network Link
• Quantum learning robust to noise
• Lower Bounds on Quantum Query Complexity
• A quantum speedup in machine learning: Finding a N-bit Boolean function for a classification
• How many functions can be distinguished with k quantum queries?
• Quantum MAC: Genuine Entanglement Access Control via Many-Body Dicke States
• Entanglement Distribution in the Quantum Internet: Knowing when to Stop!
• Conditions that enable a player to surely win in sequential quantum games
• A two-party quantum parliament
• Quantum Volunteer's Dilemma
• A Multiparty Quantum Private Equality Comparison scheme relying on $|GH{Z}_3⟩$ states
• Testing Boolean Functions Properties

Cited by in corpus (1)

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