Simon's problem
In the computational complexity theory and quantum computing, Simon's problem is a computational problem that can be solved exponentially faster on a quantum computer than on a classical computer. Although the problem itself is of little practical value, it can be proved that a quantum algorithm can solve this problem exponentially faster than any known classical algorithm.
The problem is set in 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 computation time than the best classical probabilistic algorithm.
This problem yields an oracle separation between the complexity classes BPP and BQP, unlike the separation provided by the Deutsch–Jozsa algorithm, which separates P and EQP.
Simon's algorithm was also the inspiration for Shor's algorithm. Both problems are special cases of the Abelian hidden subgroup problem, which is now known to have efficient quantum algorithms.
Problem description
Given a function , promised to satisfy the property that, for some nonzero and all,So, in other words, is a function such that, for all where is unknown.
The problem is to find.
Example
For example, if, then the following function is an example of a function that satisfies the required and just mentioned property:| 000 | 101 |
| 001 | 010 |
| 010 | 000 |
| 011 | 110 |
| 100 | 000 |
| 101 | 110 |
| 110 | 101 |
| 111 | 010 |
In this case, . It can easily be verified that every output of occurs twice, and the two input strings corresponding to any one given output have bitwise XOR equal to. For example, the input strings and are both mapped to the same output string. If we XOR and we obtain, that is
In this example the function is indeed a two-to-one function.
Problem hardness
Intuitively, this is a very hard problem to solve in a "classical" way, even if one uses randomness and accepts a small probability of error. The intuition behind the hardness is reasonably simple: if you want to solve the problem classically, you need to find two different inputs and for which. There is not necessarily any structure in the function that would help us to find two such inputs: more specifically, we can discover something about only when, for two different inputs, we obtain the same output. In any case, we would need to guess different inputs before being likely to find a pair on which takes the same output, as per the birthday problem.
Overview of Simon's algorithm
Idea
The high-level idea behind Simon's algorithm is to "probe" a quantum circuit "enough times" to find n-bit strings, that issuch that the following equations are satisfied
where is the modulo-2 dot product; that is,, and, for and for.
So, this linear system contains linear equations in unknowns, and the goal is to solve it to obtain, and is fixed for a given function. There is not always a solution.
Simon's quantum circuit
The quantum circuit is the implementation of the quantum part of Simon's algorithm.A quantum state of all zeros is first prepared. Half of this state is then transformed using a Hadamard transform. The result is then fed into an oracle, which knows how to compute. Where acts on the two registers as. After that, part of the output produced by the oracle is transformed using another Hadamard transform. Finally, a measurement on the overall resulting quantum state is performed. It is during this measurement that we retrieve the n-bit strings,, mentioned in the previous sub-section.
Simon's algorithm can be thought of as an iterative algorithm followed by a classical algorithm to find the solution to a linear system of equations.
Simon's algorithm
In this section, each part of Simon's algorithm is explained. It may be useful to look at the picture of Simon's quantum circuit above while reading each of the following sub-sections.Input
Simon's algorithm starts with the input, where is the quantum state with zeros.Example
So, for example, if, then the initial input isFirst Hadamard transformation
After that, the input is transformed using a Hadamard transform. Specifically, the Hadamard transform is applied to the first qubits, that is, to the "partial" state, so that the composite state after this operation iswhere denotes any n-bit string. The term can be factored out of the summation because it does not depend on , and.
Example
Suppose , then the input is and the Hadamard transform isIf we now apply to the first, i.e. to the state
we obtain
To obtain the final composite quantum state, we can now tensor product with, that is
Oracle
We then call the oracle or black-box to compute the function on the transformed input, to obtain the stateSecond Hadamard transformation
We then apply the Hadamard transform to the states of the first qubits of the state, to obtainwhere can either be or, depending on, where, for. So, for example, if and, then, which is an even number. Thus, in this case,, and is always a non-negative number.
Intuition behind this inverse Hadamard transformation that is applied here can be found on
Let's now rewrite
as follows
This manipulation will be convenient to understand the explanations in the next sections. The order of the summations has been reversed.
Measurement
After having performed all previously described operations, at the end of the circuit, a measurement is performed.There are now two possible cases we need to consider separately
- or
- , where.
First case
Let's keep in mind that the quantum state before the measurement is
Now, the probability that the measurement results in each string is
This follows from
because the two vectors only differ in the ordering of their entries, given that is one-to-one.
The value of the right-hand side, that is
is more easily seen to be.
Thus, when, the outcome is simply a uniformly distributed -bit string.
Second case
Let's now analyze the case , where. In this case, is a two-to-one function, that is, there are two inputs that map to the same output of.The analysis performed in the first case is still valid for this second case, that is, the probability to measure any given string can still be represented as
However, in this second case, we still need to figure out what this value of is. Let's see why in the following explanations.
Let, the image of. Let , then for every, there is one , such that ; moreover, we also have, which is equivalent to .
Hence, we have
Given that, then we can rewrite the coefficient as follows
Given that, then we can further write the expression above as
So, can further be written as
Odd number
Now, if is an odd number, then. In that case,Consequently, we have
Given that, then we never have this case, that is, no string is seen in this case.
Even number
If, instead, is an even number, then. In that case,So, we have
Is the case of constructive interference,
So, in summary, for this second case, we have the following probabilities
Classical post-processing
When we run the circuit above, there are two cases:- in the case where, the measurement results in each string with probability
- in the case , the probability to obtain each string is given by
Is this enough information to determine ? The answer is "yes", provided that the process is repeated several times. Specifically, if the above process is run times, we get strings, such that
This is a system of linear equations in unknowns, and the goal is to solve it to
obtain. Note that each of the that we obtain after each measurement is, of course, the result of a measurement, so it is known.
We only get a unique non-zero solution if we are "lucky" and are linearly independent. The probability that are linearly independent is at least
If we have linear independence, we can solve the system to get a candidate solution and test that. If, we know that, and the problem has been solved. If, it must be that . Either way, once we have linear independence, we can solve the problem.