2018/10/29 by Joran van Apeldoorn, van Apeldoorn, Joran, Sander Gribling +1
Computer Science · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Physical sciences #Machine Learning and Algorithms #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph)
paper · pdf · doi:10.48550/arxiv.1810.12030
openalex publication_date 2018/10/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Simon's problem asks the following: determine if a function f: \0,1\n → \0,1\n is one-to-one or if there exists a unique s ∈ \0,1\n such that f(x) = f(x ⊕ s) for all x ∈ \0,1\n, given the promise that exactly one of the two holds. A classical algorithm that can solve this problem for every f requires 2Ω(n) queries to f. Simon showed that there is a quantum algorithm that can solve this promise problem for every f using only \mathcal O(n) quantum queries to f. A matching lower bound on the number of quantum queries was given by Koiran et al., even for functions f: \mathbbFpn → \mathbbFpn. We give a short proof that \mathcal O(n) quantum queries is optimal even when we are additionally promised that f is linear. This is somewhat surprising because for linear functions there even exists a classical n-query algorithm.