An exact quantum polynomial-time algorithm for solving k-junta problem with one uncomplemented product
The author suggests exact quantum algorithms for solving a particular example of the \(k\)-junta problem. The proposed algorithm can be used to find dependent variables of a Boolean function \(f(x_0,\ldots,x_{n-1}) = x_{g_1}\cdots x_{g_k}\). After an introduction to related results, the paper uses a modification of methods developed in earlier works [\textit{C.-Y. Chen}, Quantum Inf. Process. 19, No. 7, Paper No. 213, 12 p. (2020; Zbl 07649751); Quantum Inf. Process. 20, No. 1, Paper No. 36, 22 p. (2021; Zbl 07654151)] for two and three dependent variables, respectively, to \(k \ge 4\). An analysis of the suggested algorithms both in the worst-case and in the average-case is finally provided.
- An exact quantum algorithm for testing 3-junta in Boolean functions with one uncomplemented product
- An exact quantum algorithm for the 2-junta problem
- A exact quantum learning algorithm for the 2-junta problem in constant time
- An exact quantum algorithm for testing Boolean functions with one uncomplemented product of two variables
- Quantum algorithms for learning symmetric juntas via the adversary bound
- An exact quantum algorithm for testing 3-junta in Boolean functions with one uncomplemented product
- An exact quantum algorithm for testing Boolean functions with one uncomplemented product of two variables
- Efficient quantum algorithms for (gapped) group testing and junta testing
- Learning functions of \(k\) relevant variables
- Learning juntas
- Quantum algorithms for learning and testing juntas
- Quantum algorithms for testing Boolean functions
- Quantum Complexity Theory
- Quantum learning of concentrated Boolean functions
- A exact quantum learning algorithm for the 2-junta problem in constant time
- An exact quantum algorithm for the 2-junta problem
- Quantum algorithms for learning symmetric juntas via the adversary bound
- Quantum algorithms for learning and testing juntas
- An exact quantum algorithm for testing Boolean functions with one uncomplemented product of two variables
- An exact quantum algorithm for testing 3-junta in Boolean functions with one uncomplemented product
- Efficient quantum algorithms for (gapped) group testing and junta testing
- An exact quantum logarithmic time algorithm for the 3-junta problem
This page was built for publication: An exact quantum polynomial-time algorithm for solving \(k\)-junta problem with one uncomplemented product
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2118738)
