Adversary Lower Bound for the Orthogonal Array Problem

2013/04/03 by Robert Špalek, Robert Spalek, Spalek, Robert · 1 citation
Computer Science · Physics and Astronomy · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Physical sciences #Machine Learning and Algorithms #Optimization and Search Problems #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph) #cs.CC #quant-ph

paper · pdf · doi:10.48550/arxiv.1304.0845

13 pages

arxiv created 2013/04/03 · openalex publication_date 2013/04/03 · arxiv updated 2013/04/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Citations

• A Time-Efficient Quantum Walk for 3-Distinctness Using Nested Updates
• Quantum Algorithm for k-distinctness with Prior Knowledge on the Input
• Strengths and Weaknesses of Quantum Computing
• Bounds for Small-Error and Zero-Error Quantum Algorithms

Cited by

• Adversary Lower Bound for Element Distinctness with Small Range

Related

• Adversary Lower Bound for the k-sum Problem
• Adversary Lower Bounds for the Collision and the Set Equality Problems
• Adversary Lower Bound for Element Distinctness with Small Range
• A new quantum lower bound method, with an application to strong direct product theorem for quantum search
• Quantum lower bounds by quantum arguments