Efficient Quantum Algorithms for (Gapped) Group Testing and Junta Testing

DOI10.1137/1.9781611974331.ch65zbMath1410.68132arXiv1507.03126OpenAlexW2949645943MaRDI QIDQ4575644

Aleksandrs Belovs, Andris Ambainis, Oded Regev, Ronald de Wolf

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1507.03126

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Quantum algorithms and complexity in the theory of computing (68Q12)

Related Items (9)

A fast Fourier transform for the Johnson graph ⋮ 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 ⋮ An exact quantum algorithm for testing 3-junta in Boolean functions with one uncomplemented product ⋮ An exact quantum algorithm for the 2-junta problem ⋮ Quantum Algorithms for Classical Probability Distributions ⋮ Harmonicity and invariance on slices of the Boolean cube ⋮ Quantum cryptographic property testing of multi-output Boolean functions ⋮ An exact quantum polynomial-time algorithm for solving \(k\)-junta problem with one uncomplemented product

This page was built for publication: Efficient Quantum Algorithms for (Gapped) Group Testing and Junta Testing