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.
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)and a memory cost of2n+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 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.
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 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.
In this paper, we study the following variant of the junta learning problem. We are given oracle access to a Boolean function f on n variables that only depends on k variables, and, when restricted to them, equals some predefined function h. The task is to identify the variables the function depends on. When h is the XOR or the OR function, this gives a restricted variant of the Bernstein-Vazirani or the combinatorial group testing problem, respectively. We analyse the general case using the adversary bound, and give an alternative formulation for the quantum query complexity of this problem. We construct optimal quantum query algorithms for the cases when h is the OR function (complexity is Θ(k)) or the exact-half function (complexity is Θ(k1/4)). The first algorithm resolves an open problem from arXiv:1210.1148. For the case when h is the majority function, we prove an upper bound of O(k1/4). All these algorithms can be made exact. We obtain a quartic improvement when compared to the randomised complexity (if h is the exact-half or the majority function), and a quadratic one when compared to the non-adaptive quantum complexity (for all functions considered in the paper).
We consider the problem of deciding whether an n-qubit unitary (or n-bit Boolean function) is ε1-close to some k-junta or ε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 ε1,ε2 such that 0<ε1<ε2<1, we show the following.1.A non-adaptive O(klogk)-query tolerant (ε1,ε2)-tester for k-junta unitaries when 22ε1<ε2.2.A non-adaptive tolerant (ε1,ε2)-tester for k-junta Boolean functions with O(klogk) quantum queries when 4ε1<ε2.3.A 2O(k)-query tolerant (ε1,ε2)-tester for k-junta unitaries for any ε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.
In this paper, we study the following variant of the junta learning problem. We are given oracle access to a Boolean function f on n variables that only depends on k variables, and, when restricted to them, equals some predefined function h. The task is to identify the variables the function depends on. This is a generalisation of the Bernstein-Vazirani problem [1] (when h is the XOR function) and the combinatorial group testing problem [2] (when h is the OR function). We analyse the general case using the adversary bound, and give an alternative formulation for the quantum query complexity of this problem. We construct optimal quantum query algorithms for the cases when h is the OR function (complexity is square root of k) or the exact-half function (complexity is the fourth power root of k). The first algorithm resolves an open problem from. For the case when h is the majority function, we prove an upper bound of the fourth power root of k. We obtain a quartic improvement when compared to the randomised complexity (if h is the exact-half or the majority function), and a quadratic one when compared to the non-adaptive quantum complexity (for all functions considered in the paper).