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

IEEE Access

A Quantum Algorithm for Boolean Functions Processing

Fahad Aljuaydi, Samar AbdelAzim, Mohamed M. Darwish, Mohammed Zidan

Published Jan 1, 2024• 3 citations
Publisher

Abstract

Detecting junta variables is a critical issue in Boolean function analysis, circuit design optimization, and machine learning feature selection. In this paper, we investigate a novel quantum computation algorithm based on the Mz operator. The algorithm takes in an unknown oracle concealing a Boolean function with n variables and an unknown input state, which can be quantum or classical. The input state can be complete or incomplete quantum basis states, and it can be a weighted or uniform superposition of basis states. The proposed approach determines whether a given variable is a junta with a time cost of$O(2/\epsilon ^{2})$and a memory cost of$2n+6$. The algorithm is analyzed and experimentally implemented using the Qiskit simulator and IBM’s real quantum computer. Experimental results show that the proposed approach achieved a quantum supremacy ratio 6300% higher than that of the classical method when verifying junta variables for Boolean functions with 12 variables. The results suggest that the proposed quantum method can verify junta variables in scenarios beyond the capabilities of current classical or quantum methods.

DOI
10.1109/access.2024.3486333

Related papers

Estimating the Number of Junta Variables for Optimizing Boolean Functions in Quantum Memories

Abdulaziz Mutlaq Alotaibi, Samar AbdelAzim, Sattam Alharbi +1 more

Optimizing Boolean function components to have the minimum number of inputs in order to reduce the memory space required during these functions in computing devices is a significant demand. This paper proposes a quantum computation approach based on the degree-of-entanglement quantum computation model to estimate the number of junta variables of an unknown Boolean function presented through an oracle. The time complexity of the developed quantum approach is independent of the number of inputs and depends on an allowable assigned error ϵ. Thus, the time complexity of the developed algorithm is O(ϵ−2), compared to O(2n+1) in the traditional approach. Also, the memory space of the developed approach is linear, O(2n+4), in terms of the number of inputs compared to the exponential memory space O(2n+1) using the traditional approach. Therefore, the developed quantum approach has exponential supremacy in comparison to the traditional approach. The developed approach was implemented practically using both the Qiskit simulator and the IBM real quantum computer. The obtained results expose high statistical fidelities between the empirical and theoretical results.

Mathematics•Oct 25, 2025•0 citations

A Quantum Algorithm for Testing Junta Variables and Learning Boolean Functions via Entanglement Measure

Khaled El-Wazan, Ahmed Younes, Salah Badawi Doma

Given a black-box representing an unknown Boolean function $f$ of $n$ variables, in this paper we propose a fast quantum algorithm to test whether or not a certain variable in the function $f$ is a junta variable. The proposed algorithm creates entanglement between the variable under test and an auxiliary qubit, where the entanglement is measured using concurrence measure to decide if the variable is junta. The paper shows applications to the proposed algorithm in learning and categorization of Boolean functions.

arXiv:1710.10495•Oct 28, 2017•4 citations

A Quantum Algorithm for System Specifications Verification

Mohammed Zidan, Ahmed M. Eisa, Montasir Qasymeh +1 more

Verifying system specifications is a crucial requirement in science and technology, as it improves accuracy and efficiency in systems engineering. However, traditional computers are time-consuming and cannot efficiently check the consistency of system specifications for classical and quantum systems due to exponential complexity costs. Currently, there is no quantum approach available for verifying consistency in quantum systems. This paper introduces a novel quantum algorithm that utilizes the entanglement measure to efficiently check the consistency of unknown system specifications represented by m oracles. The proposed algorithm has a time complexity of O(m-2), which is independent of the input size n and depends only on a predetermined error margin, providing exponential speedup compared to the classical approach with a time complexity of O(m2n). Moreover, the proposed algorithm can handle weighted superposition input states, which are impossible for classical computers to handle. Thus, the algorithm has the potential to check the consistency of both quantum and classical system specifications. The proposed algorithm is realized experimentally using IBM’s Aer simulator with an input size of n=12. The experimental results closely aligned with the theoretical predictions, demonstrating the algorithm’s efficiency in checking the consistency of system specifications. Specifically, the proposed algorithm achieved a quantum supremacy ratio of 300% to 3100% compared to the classical algorithm, highlighting its significant advantage in terms of time complexity. Additionally, the simulation results confirmed the efficiency of the proposed algorithm in checking the consistency of the quantum system’s specifications.

IEEE Internet of Things Journal•Mar 29, 2024•10 citations

A Quantum Algorithm for Testing Juntas in Boolean Functions

Khaled El-Wazan, Ahmed Younes, Salah Badawi Doma

Given a Boolean function $f$ provided as a black-box with $n$ variables, this paper will propose a quantum algorithm for testing if a certain variable is junta or $ε$-far from being junta. The proposed algorithm constructs another black-box using two copies of the provided black-box. The constructed black-box is used with the partial diffusion operator in an amplitude amplification technique to test whether the variable being tested is junta or not, using $\mathcal{O}(\sqrt{2^n})$ queries to the constructed black-box. The proposed algorithm considers a Boolean function of general form, contrary to relevant algorithms proposed by others.

arXiv:1701.02143•Jan 9, 2017•6 citations

Efficient Non-Adaptive Quantum Algorithms for Tolerant Junta Testing

Zongbo Bao, Yuxuan Liu, Penghui Yao +2 more

We consider the problem of deciding whether an \(n\)-qubit unitary (or \(n\)-bit Boolean function) is \(\varepsilon_1\)-close to some \(k\)-junta or \(\varepsilon_2\)-far from every \(k\)-junta, where \(k\)-junta unitaries act non-trivially on at most \(k\) qubits and as the identity on the rest, and \(k\)-junta Boolean functions depend on at most \(k\) variables. For constant numbers \(\varepsilon_1, \varepsilon_2\) such that \(0 \lt \varepsilon_1 \lt \varepsilon_2 \lt 1\), we show the following.1.A non-adaptive \(O(k \log k)\)-query tolerant (\(\varepsilon_1, \varepsilon_2\))-tester for \(k\)-junta unitaries when \(2\sqrt2\varepsilon_1 \lt \varepsilon_2\).2.A non-adaptive tolerant (\(\varepsilon_1, \varepsilon_2\))-tester for \(k\)-junta Boolean functions with \(O(k \log k)\) quantum queries when \(4\varepsilon_1 \lt \varepsilon_2\).3.A \(2^{\widetilde{O}(k)}\)-query tolerant (\(\varepsilon_1, \varepsilon_2\))-tester for \(k\)-junta unitaries for any \(\varepsilon_1, \varepsilon_2\).The first algorithm provides an exponential improvement over the best-known quantum algorithms [CLL24, ADG25]. The second algorithm shows an exponential quantum advantage over any non-adaptive classical algorithm [CDL+24]. The third tester gives the first tolerant junta unitary testing result for an arbitrary gap.

arXiv:2508.17306•Society for Industrial and Applied Mathematics eBooks•Jan 1, 2026•5 citations

A Quantum Algorithm for Evaluating the Hamming Distance

Sohail Khan, Mohammad Nauman, Suleiman Ali Alsaif +2 more

We present a novel quantum algorithm to evaluate the hamming distance between two unknown oracles via measuring the degree of entanglement between two ancillary qubits. In particular, we use the power of the entanglement degree based quantum computing model that preserves at most the locality of interactions within the quantum model structure. This model uses one of two techniques to retrieve the solution of a quantum computing problem at hand. In the first technique, the solution of the problem is obtained based on whether there is an entanglement between the two ancillary qubits or not. In the second, the solution of the quantum computing problem is obtained as a function in the concurrence value, and the number of states that can be generated from the Boolean variables. The proposed algorithm receives two oracles, each oracle represents an unknown Boolean function, then it measures the hamming distance between these two oracles. The hamming distance is evaluated based on the second technique. It is shown that the proposed algorithm provides exponential speedup compared with the classical counterpart for Boolean functions that have large numbers of Boolean variables. The proposed algorithm is explained via a case study. Finally, employing recently developed experimental techniques, the proposed algorithm has been verified using IBM's quantum computer simulator.

Computers, materials & continua/Computers, materials & continua (Print)•Nov 3, 2021•17 citations
Detecting junta variables is a critical issue in Boolean function analysis, circuit design optimization, and machine learning feature selection. In this paper, we investigate a novel quantum computation algorithm based on the Mz operator. The algorithm takes in an unknown oracle concealing a Boolean function with n variables and an unknown input state, which can be quantum or classical. The input state can be complete or incomplete quantum basis states, and it can be a weighted or uniform superposition of basis states. The proposed approach determines whether a given variable is a junta with a time cost ofO(2/ϵ2)O(2/\epsilon ^{2})O(2/ϵ2)and a memory cost of2n+62n+62n+6. The algorithm is analyzed and experimentally implemented using the Qiskit simulator and IBM’s real quantum computer. Experimental results show that the proposed approach achieved a quantum supremacy ratio 6300% higher than that of the classical method when verifying junta variables for Boolean functions with 12 variables. The results suggest that the proposed quantum method can verify junta variables in scenarios beyond the capabilities of current classical or quantum methods.
Optimizing Boolean function components to have the minimum number of inputs in order to reduce the memory space required during these functions in computing devices is a significant demand. This paper proposes a quantum computation approach based on the degree-of-entanglement quantum computation model to estimate the number of junta variables of an unknown Boolean function presented through an oracle. The time complexity of the developed quantum approach is independent of the number of inputs and depends on an allowable assigned error ϵ. Thus, the time complexity of the developed algorithm is O(ϵ−2), compared to O(2n+1) in the traditional approach. Also, the memory space of the developed approach is linear, O(2n+4), in terms of the number of inputs compared to the exponential memory space O(2n+1) using the traditional approach. Therefore, the developed quantum approach has exponential supremacy in comparison to the traditional approach. The developed approach was implemented practically using both the Qiskit simulator and the IBM real quantum computer. The obtained results expose high statistical fidelities between the empirical and theoretical results.
Given a black-box representing an unknown Boolean function fff of nnn variables, in this paper we propose a fast quantum algorithm to test whether or not a certain variable in the function fff is a junta variable. The proposed algorithm creates entanglement between the variable under test and an auxiliary qubit, where the entanglement is measured using concurrence measure to decide if the variable is junta. The paper shows applications to the proposed algorithm in learning and categorization of Boolean functions.
Verifying system specifications is a crucial requirement in science and technology, as it improves accuracy and efficiency in systems engineering. However, traditional computers are time-consuming and cannot efficiently check the consistency of system specifications for classical and quantum systems due to exponential complexity costs. Currently, there is no quantum approach available for verifying consistency in quantum systems. This paper introduces a novel quantum algorithm that utilizes the entanglement measure to efficiently check the consistency of unknown system specifications represented by m oracles. The proposed algorithm has a time complexity of O(m-2), which is independent of the input size n and depends only on a predetermined error margin, providing exponential speedup compared to the classical approach with a time complexity of O(m2n). Moreover, the proposed algorithm can handle weighted superposition input states, which are impossible for classical computers to handle. Thus, the algorithm has the potential to check the consistency of both quantum and classical system specifications. The proposed algorithm is realized experimentally using IBM’s Aer simulator with an input size of n=12. The experimental results closely aligned with the theoretical predictions, demonstrating the algorithm’s efficiency in checking the consistency of system specifications. Specifically, the proposed algorithm achieved a quantum supremacy ratio of 300% to 3100% compared to the classical algorithm, highlighting its significant advantage in terms of time complexity. Additionally, the simulation results confirmed the efficiency of the proposed algorithm in checking the consistency of the quantum system’s specifications.
Given a Boolean function fff provided as a black-box with nnn variables, this paper will propose a quantum algorithm for testing if a certain variable is junta or εεε-far from being junta. The proposed algorithm constructs another black-box using two copies of the provided black-box. The constructed black-box is used with the partial diffusion operator in an amplitude amplification technique to test whether the variable being tested is junta or not, using O(2n)\mathcal{O}(\sqrt{2^n})O(2n​) queries to the constructed black-box. The proposed algorithm considers a Boolean function of general form, contrary to relevant algorithms proposed by others.
We consider the problem of deciding whether an nnn-qubit unitary (or nnn-bit Boolean function) is ε1\varepsilon_1ε1​-close to some kkk-junta or ε2\varepsilon_2ε2​-far from every kkk-junta, where kkk-junta unitaries act non-trivially on at most kkk qubits and as the identity on the rest, and kkk-junta Boolean functions depend on at most kkk variables. For constant numbers ε1,ε2\varepsilon_1, \varepsilon_2ε1​,ε2​ such that 0<ε1<ε2<10 \lt \varepsilon_1 \lt \varepsilon_2 \lt 10<ε1​<ε2​<1, we show the following.1.A non-adaptive O(klog⁡k)O(k \log k)O(klogk)-query tolerant (ε1,ε2\varepsilon_1, \varepsilon_2ε1​,ε2​)-tester for kkk-junta unitaries when 22ε1<ε22\sqrt2\varepsilon_1 \lt \varepsilon_222​ε1​<ε2​.2.A non-adaptive tolerant (ε1,ε2\varepsilon_1, \varepsilon_2ε1​,ε2​)-tester for kkk-junta Boolean functions with O(klog⁡k)O(k \log k)O(klogk) quantum queries when 4ε1<ε24\varepsilon_1 \lt \varepsilon_24ε1​<ε2​.3.A 2O~(k)2^{\widetilde{O}(k)}2O(k)-query tolerant (ε1,ε2\varepsilon_1, \varepsilon_2ε1​,ε2​)-tester for kkk-junta unitaries for any ε1,ε2\varepsilon_1, \varepsilon_2ε1​,ε2​.The first algorithm provides an exponential improvement over the best-known quantum algorithms [CLL24, ADG25]. The second algorithm shows an exponential quantum advantage over any non-adaptive classical algorithm [CDL+24]. The third tester gives the first tolerant junta unitary testing result for an arbitrary gap.
We present a novel quantum algorithm to evaluate the hamming distance between two unknown oracles via measuring the degree of entanglement between two ancillary qubits. In particular, we use the power of the entanglement degree based quantum computing model that preserves at most the locality of interactions within the quantum model structure. This model uses one of two techniques to retrieve the solution of a quantum computing problem at hand. In the first technique, the solution of the problem is obtained based on whether there is an entanglement between the two ancillary qubits or not. In the second, the solution of the quantum computing problem is obtained as a function in the concurrence value, and the number of states that can be generated from the Boolean variables. The proposed algorithm receives two oracles, each oracle represents an unknown Boolean function, then it measures the hamming distance between these two oracles. The hamming distance is evaluated based on the second technique. It is shown that the proposed algorithm provides exponential speedup compared with the classical counterpart for Boolean functions that have large numbers of Boolean variables. The proposed algorithm is explained via a case study. Finally, employing recently developed experimental techniques, the proposed algorithm has been verified using IBM's quantum computer simulator.