论文标题
西蒙问题在古典意义上的复杂性
Complexity of Simon's problem in classical sense
论文作者
论文摘要
西蒙的问题是一个在经典意义上是指数级的问题的标准示例，而它在量子计算中接受多项式解决方案。它是一个函数$ f $，允许它存在一个唯一的非零矢量$ s $，其中$ f（x）= f（x \ oplus s）$对于所有$ x $，其中$ \ oplus $是独家或运营商。目标是找到$ S $。经典意义的指数下限假设$ f $仅允许黑匣子访问。在本文中，当$ F $像电路这样的标准表示形式给出$ F $时，我们研究了经典的复杂性。我们专注于为所有给定的$ f $ $ f（x）= f（x）= f（x \ oplus s）$找到所有向量的矢量空间。两个主要结果是：（1）如果任何电路给出了$ f $，则检查该向量空间是否包含非零元素为NP-HARD，并且（2）如果任何有序的BDD给出$ f $，则可以在多项式时间内计算此矢量空间的基础。
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 \oplus s)$ for all $x$, where $\oplus$ 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 \oplus 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.
