Adversary Lower Bound for the Orthogonal Array Problem
arXiv:1304.0845
Abstract
We prove a quantum query lower bound Ω(n^{(d+1)/(d+2)}) for the problem of deciding whether an input string of size n contains a k-tuple which belongs to a fixed orthogonal array on k factors of strength d<=k-1 and index 1, provided that the alphabet size is sufficiently large. Our lower bound is tight when d=k-1. The orthogonal array problem includes the following problems as special cases: k-sum problem with d=k-1, k-distinctness problem with d=1, k-pattern problem with d=0, (d-1)-degree problem with 1<=d<=k-1, unordered search with d=0 and k=1, and graph collision with d=0 and k=2.
13 pages
References in corpus (10)
- Quantum Mechanics helps in searching for a needle in a haystack
- Strengths and Weaknesses of Quantum Computing
- Negative weights make adversaries stronger
- Quantum query complexity of state conversion
- Learning-Graph-Based Quantum Algorithm for k-distinctness
- Bounds for Small-Error and Zero-Error Quantum Algorithms
- Quantum Algorithm for k-distinctness with Prior Knowledge on the Input
- Quantum Walks and Electric Networks
- A Time-Efficient Quantum Walk for 3-Distinctness Using Nested Updates
- On the Power of Non-Adaptive Learning Graphs