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:1710.10495

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

Khaled El-Wazan, Ahmed Younes, Salah Badawi Doma

Published Oct 28, 2017• 4 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.1710.10495

Related papers

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

Measuring Hamming Distance between Boolean Functions via Entanglement Measure

Khaled El-Wazan

In this paper, we present a fast quantum algorithm to measure the Hamming distance between two or more Boolean functions provided as black-boxes. The proposed algorithm constructs a new black-box with a certain property which is utilized to solve this problem. The introduced algorithm converts measuring the Hamming distance between Boolean functions to measuring entanglement between qubits, using concurrence entanglement measure.

arXiv:1903.04762•Mar 12, 2019•1 citation

A Quantum Algorithm for Boolean Functions Processing

Fahad Aljuaydi, Samar AbdelAzim, Mohamed M. Darwish +1 more

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.

IEEE Access•Jan 1, 2024•3 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

Tolerant Quantum Junta Testing

Zhaoyang Chen, Lvzhou Li, Jingquan Luo

Junta testing for Boolean functions has sparked a long line of work over recent decades in theoretical computer science, and recently has also been studied for unitary operators in quantum computing. Tolerant junta testing is more general and challenging than the standard version. While optimal tolerant junta testers have been obtained for Boolean functions, there has been no knowledge about tolerant junta testers for unitary operators, which was thus left as an open problem in [Chen, Nadimpalli, and Yuen, SODA2023]. In this paper, we settle this problem by presenting the first algorithm to decide whether a unitary is $ε_1$-close to some quantum $k$-junta or is $ε_2$-far from any quantum $k$-junta, where an $n$-qubit unitary $U$ is called a quantum $k$-junta if it only non-trivially acts on just $k$ of the $n$ qubits. More specifically, we present a tolerant tester with $ε_1 = \frac{\sqrtρ}{8} ε$, $ε_2 = ε$, and $ρ\in (0,1)$, and the query complexity is $O\left(\frac{k \log k}{ε^2 ρ(1-ρ)^k}\right)$, which demonstrates a trade-off between the amount of tolerance and the query complexity. Note that our algorithm is non-adaptive which is preferred over its adaptive counterparts, due to its simpler as well as highly parallelizable nature. At the same time, our algorithm does not need access to $U^\dagger$, whereas this is usually required in the literature.

arXiv:2411.02244•Nov 4, 2024•8 citations

Quantum algorithms for testing and learning Boolean functions

Dominik Floess, Erika Andersson, Mark S. Hillery

We discuss quantum algorithms based on the Bernstein–Vazirani algorithm for finding which input variables a Boolean function depends on. There are 2 n possible linear Boolean functions of n input variables; given a linear Boolean function, the Bernstein–Vazirani quantum algorithm can deterministically identify which one of these Boolean functions we are given using just one single function query. We show how the same quantum algorithm can also be used to learn which input variables any other type of Boolean function} depends on. The success probability of learning that the function depends on a particular input variable depends on} the form of the Boolean function that is tested, but does not depend on the total number of input variables. We also outline a procedure based on another quantum algorithm, the Grover search, to amplify further the success probability. Finally, we discuss quantum algorithms for learning the exact form of certain quadratic and cubic Boolean functions.

Mathematical Structures in Computer Science•Feb 28, 2013•8 citations
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.
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.
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.
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.
Junta testing for Boolean functions has sparked a long line of work over recent decades in theoretical computer science, and recently has also been studied for unitary operators in quantum computing. Tolerant junta testing is more general and challenging than the standard version. While optimal tolerant junta testers have been obtained for Boolean functions, there has been no knowledge about tolerant junta testers for unitary operators, which was thus left as an open problem in [Chen, Nadimpalli, and Yuen, SODA2023]. In this paper, we settle this problem by presenting the first algorithm to decide whether a unitary is ε1ε_1ε1​-close to some quantum kkk-junta or is ε2ε_2ε2​-far from any quantum kkk-junta, where an nnn-qubit unitary UUU is called a quantum kkk-junta if it only non-trivially acts on just kkk of the nnn qubits. More specifically, we present a tolerant tester with ε1=ρ8εε_1 = \frac{\sqrtρ}{8} εε1​=8ρ​​ε, ε2=εε_2 = εε2​=ε, and ρ∈(0,1)ρ\in (0,1)ρ∈(0,1), and the query complexity is O(klog⁡kε2ρ(1−ρ)k)O\left(\frac{k \log k}{ε^2 ρ(1-ρ)^k}\right)O(ε2ρ(1−ρ)kklogk​), which demonstrates a trade-off between the amount of tolerance and the query complexity. Note that our algorithm is non-adaptive which is preferred over its adaptive counterparts, due to its simpler as well as highly parallelizable nature. At the same time, our algorithm does not need access to U†U^\daggerU†, whereas this is usually required in the literature.
We discuss quantum algorithms based on the Bernstein–Vazirani algorithm for finding which input variables a Boolean function depends on. There are 2 n possible linear Boolean functions of n input variables; given a linear Boolean function, the Bernstein–Vazirani quantum algorithm can deterministically identify which one of these Boolean functions we are given using just one single function query. We show how the same quantum algorithm can also be used to learn which input variables any other type of Boolean function} depends on. The success probability of learning that the function depends on a particular input variable depends on} the form of the Boolean function that is tested, but does not depend on the total number of input variables. We also outline a procedure based on another quantum algorithm, the Grover search, to amplify further the success probability. Finally, we discuss quantum algorithms for learning the exact form of certain quadratic and cubic Boolean functions.