In computational complexity theory and quantum computing, Simon's problem is a computational problem conceived to showcase the efficiency increase a quantum algorithm could have over a classic one. Although the problem itself is of little practical value, it is interesting because it provides an exponential speedup over any classical algorithm (in a black box model).
The problem deals with the model of decision tree complexity or query complexity and was conceived by Daniel Simon in 1994. Simon exhibited a quantum algorithm, usually called Simon's algorithm, that solves the problem exponentially faster than any deterministic or probabilistic classical algorithm, requiring exponentially less computational power than the best classical probabilistic algorithm.
Problem description and algorithm
The input to the problem is a function (implemented by a black box) , promised to satisfy the property that for some we have for all , if and only if or . Note that the case of is allowed, and corresponds to being a permutation. The problem then is to find .
The set of n-bit strings is a vector space under bitwise XOR. Given the promise, the preimage of f is either empty, or forms cosets with n-1 dimensions. Using quantum algorithms, we can, with arbitrarily high probability determine the basis vectors spanning this n-1 subspace since s is a vector orthogonal to all of the basis vectors.
and then call the oracle to transform this state to
Hadamard transforms convert this state to
We perform a simultaneous measurement of both registers. If , we have destructive interference. So, only the subspace is picked out. Given enough samples of y, we can figure out the n-1 basis vectors, and compute s.
Simon's algorithm requires queries to the black box, whereas a classical algorithm would need at least queries. It is also known that Simon's algorithm is optimal in the sense that any quantum algorithm to solve this problem requires queries.
- Arora, Sanjeev and Barak, Boaz. Computational Complexity: A Modern Approach. Cambridge University Press.
- Simon, D.R. (1995), "On the power of quantum computation", Foundations of Computer Science, 1996 Proceedings., 35th Annual Symposium on: 116–123, retrieved 2011-06-06
- Koiran, P.; Nesme, V.; Portier, N. (2007), "The quantum query complexity of the abelian hidden subgroup problem", Theoretical Computer Science, 380 (1-2): 115–126, doi:10.1016/j.tcs.2007.02.057, retrieved 2011-06-06
- Koiran, P.; Nesme, V.; Portier, N. (2005), "A quantum lower bound for the query complexity of Simon's Problem", Proc. ICALP, 3580: 1287–1298, arXiv:, retrieved 2011-06-06