2022/11/03 by Hans Zantema, Zantema, Hans
Computer Science · #Complexity and Algorithms in Graphs #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Quantum Computing Algorithms and Architecture
paper · pdf · doi:10.48550/arxiv.2211.01776
openalex publication_date 2022/11/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Simon's problem is a standard example of a problem that is exponential in classical sense, while it admits a polynomial solution in quantum computing. It is about a function f for which it is given that a unique non-zero vector s exists for which f(x) = f(x ⊕ s) for all x, where ⊕ is the exclusive or operator. The goal is to find s. The exponential lower bound for the classical sense assumes that f only admits black box access. In this paper we investigate classical complexity when f is given by a standard representation like a circuit. We focus on finding the vector space of all vectors s for which f(x) = f(x ⊕ s) for all x, for any given f. Two main results are: (1) if f is given by any circuit, then checking whether this vector space contains a non-zero element is NP-hard, and (2) if f is given by any ordered BDD, then a basis of this vector space can be computed in polynomial time.