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

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.

References in corpus (11)

• Quantum Mechanics helps in searching for a needle in a haystack
• Entanglement of a Pair of Quantum Bits
• Entanglement detection
• Scalable multi-particle entanglement of trapped ions
• Experimental entanglement of six photons in graph states
• Grover's quantum searching algorithm is optimal
• A Survey of Quantum Property Testing
• Quantum Searching via Entanglement and Partial Diffusion
• Entanglement quantification made easy: Polynomial measures invariant under convex decomposition
• A Quantum Algorithm for Testing Juntas in Boolean Functions
• Constant-Time Quantum Algorithm For The Unstructured Search Problem

Cited by in corpus (1)

• Measuring Hamming Distance between Boolean Functions via Entanglement Measure