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

Automation and Remote Control

Classification of Boolean functions by the invariants of their matrix representation

A. B. Lapshin

Published Jul 1, 2006• 1 citation
Publisher

Abstract

A variant of matrix representation for Boolean functions is designed such that these functions can be classified by matrix invariants. By way of example, the Deutsch problem is solved to illustrate the advantages of this classification.
DOI
10.1134/s0005117906070095

Related papers

Construction of a class of quantum Boolean functions based on the Hadamard matrix

Jiao Du, Shanqi Pang, Qiaoyan Wen +1 more

Acta Mathematicae Applicatae Sinica English Series•Oct 1, 2015•1 citation

A quantum algorithm based on entanglement measure for classifying Boolean multivariate function into novel hidden classes

Mohammed Zidan, Abdel‐Haleem Abdel‐Aty, Duc Manh Nguyen +4 more

In this paper, we propose a novel algorithm that solves a generalized version of the Deutsch-Jozsa problem. The proposed algorithm has the potential to classify an oracle U F , that represents an unknown Boolean function on n Boolean variables, to one of 2 n different classes instead of only two classes which are constant and balanced classes in the case of Deutsch-Jozsa algorithm. The proposed algorithm is based on the use of entanglement measure to explore 2 n - 2 additional classes compared to the standard Deutsch-Jozsa algorithm. In addition, the comparison between the proposed quantum algorithm and the classical one is investigated in details. The comparison shows that the proposed algorithm is faster when the number of Boolean variables exceed 14 variables.

Results in Physics•Aug 9, 2019•58 citations

On Molecular Bonding Logic and Matrix Representation of Constant and Balanced Boolean Functions

Eugene S. Kryachko

Representing a bonding manifold of a molecule or molecular cluster by a graph given by a set of vertices associated with atoms and a set of edges imitating bonds, the bonding edge encoding formalism is defined on n-tuples qubits in terms of the NOT logic gate acting on the "non-bonded" string. This formalism is illustrated by the simplest diatomic and triatomic molecules whose adjacency matrices generate different quadratic Boolean functions, among which the balanced function appears. In this regard, we review the Deutsch–Jozsa quantum algorithm, well-known in quantum computing, that discriminates between the balanced and constant Boolean functions. A novel matrix representation of the constant-balancedquantum oracle within this algorithm is elaborated. The proposed approach is generalized to distinguish between constant and evenly balanced Boolean functions.

Ukrainian Journal of Physics•Feb 9, 2022•1 citation

On the Classification of Finite Boolean Functions up to Fairness

Nikolaos Makriyannis

Lecture notes in computer science•Jan 1, 2014•25 citations

Computability of Matrix Functions and Compiling of Matrix Problems on Quantum Computers

Holger Boche, Adalbert Fono, Gitta Kutyniok

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2026•0 citations

Quantum Classification Outside the Promised Class

Theodore Andronikos, Constantinos Bitsakos, Konstantinos Nikas +2 more

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.

arXiv:2504.18898•Computers•Jun 10, 2025•2 citations
In this paper, we propose a novel algorithm that solves a generalized version of the Deutsch-Jozsa problem. The proposed algorithm has the potential to classify an oracle U F , that represents an unknown Boolean function on n Boolean variables, to one of 2 n different classes instead of only two classes which are constant and balanced classes in the case of Deutsch-Jozsa algorithm. The proposed algorithm is based on the use of entanglement measure to explore 2 n - 2 additional classes compared to the standard Deutsch-Jozsa algorithm. In addition, the comparison between the proposed quantum algorithm and the classical one is investigated in details. The comparison shows that the proposed algorithm is faster when the number of Boolean variables exceed 14 variables.
Representing a bonding manifold of a molecule or molecular cluster by a graph given by a set of vertices associated with atoms and a set of edges imitating bonds, the bonding edge encoding formalism is defined on n-tuples qubits in terms of the NOT logic gate acting on the "non-bonded" string. This formalism is illustrated by the simplest diatomic and triatomic molecules whose adjacency matrices generate different quadratic Boolean functions, among which the balanced function appears. In this regard, we review the Deutsch–Jozsa quantum algorithm, well-known in quantum computing, that discriminates between the balanced and constant Boolean functions. A novel matrix representation of the constant-balancedquantum oracle within this algorithm is elaborated. The proposed approach is generalized to distinguish between constant and evenly balanced Boolean functions.
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.