2015/07/14 by Kaspars Balodis, Balodis, Kaspars, Jānis Iraids +1 · 1 citation
Computer Science · Physics and Astronomy · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Cryptography and Data Security #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph) #cs.CC #quant-ph
paper · pdf · doi:10.48550/arxiv.1507.03885
arxiv created 2015/07/14 · openalex publication_date 2015/07/14 · arxiv updated 2015/07/15 · openalex created_date 2022/10/03 · openalex updated_date 2026/07/28
We show that an improvement to the best known quantum lower bound for GRAPH-COLLISION problem implies an improvement to the best known lower bound for TRIANGLE problem in the quantum query complexity model. In GRAPH-COLLISION we are given free access to a graph (V,E) and access to a function f:V→ \0,1\ as a black box. We are asked to determine if there exist (u,v) ∈ E, such that f(u)=f(v)=1. In TRIANGLE we have a black box access to an adjacency matrix of a graph and we have to determine if the graph contains a triangle. For both of these problems the known lower bounds are trivial (Ω(√(n)) and Ω(n), respectively) and there is no known matching upper bound.