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 s.
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.
Consider the Hilbert space consisting of the tensor product of the Hilbert space of input strings, and output strings. Using Hadamard operations, we can prepare the initial state
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.
Read more about this topic: Simon's Algorithm
Famous quotes containing the words problem and/or description:
“Great speeches have always had great soundbites. The problem now is that the young technicians who put together speeches are paying attention only to the soundbite, not to the text as a whole, not realizing that all great soundbites happen by accident, which is to say, all great soundbites are yielded up inevitably, as part of the natural expression of the text. They are part of the tapestry, they aren’t a little flower somebody sewed on.”
—Peggy Noonan (b. 1950)
“It is possible—indeed possible even according to the old conception of logic—to give in advance a description of all ‘true’ logical propositions. Hence there can never be surprises in logic.”
—Ludwig Wittgenstein (1889–1951)