Wikipedia / Simon's problem
Wikipedia / Simon's problem
In computational complexity theory and quantum computing, Simon's problem is a computational problem that is proven to be solved exponentially faster on a quantum computer than on a classical (that is, traditional) computer. The quantum algorithm solving Simon's problem, usually called Simon's algorithm, served as 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.
The problem is set in the model of decision tree complexity or query complexity and was conceived by Daniel R. Simon in 1994. Simon exhibited a quantum algorithm that solves Simon's problem exponentially faster with exponentially fewer queries than the best probabilistic (or deterministic) classical algorithm. In particular, Simon's algorithm uses a linear number of queries and any classical probabilistic algorithm must use an exponential number of queries.
This problem yields an oracle separation between the complexity classes BPP (bounded-error classical query complexity) and BQP (bounded-error quantum query complexity). This is the same separation that the Bernstein–Vazirani algorithm achieves, and different from the separation provided by the Deutsch–Jozsa algorithm, which separates P and EQP. Unlike the Bernstein–Vazirani algorithm, Simon's algorithm's separation is exponential.
Because this problem assumes the existence of a highly-structured "black box" oracle to achieve its speedup, this problem has little practical value. However, without such an oracle, exponential speedups cannot easily be proven, since this would prove that P is different from PSPACE.
Problem description
as implemented by a black box or an oracle. This function is promised to be either a one-to-one differ in a fixed set of bits. I.e.,
denotes bitwise exclusive-or.
. Thus, Simon's problem may be restated in the following form:
(non-decision version).
Example
:.
as before.
In this example the function f.
Problem hardness
takes the same output, as per the birthday problem. Since, classically to find s inputs, Simon's problem seeks to find s using fewer queries than this classical method.
Simon's algorithm
The algorithm as a whole uses a subroutine to execute the following two steps:
times to get a list of linearly independent.
.
Quantum subroutine
The quantum circuit (see the picture) is the implementation of the quantum part of Simon's algorithm. The quantum subroutine of the algorithm makes use of the Hadamard transform denotes XOR.
. Then, we apply the Hadamard transform to the first register, which gives the state
to get the state
.
Apply another Hadamard transform to the first register. This will produce the state
. There are two cases for our measurement:
is one-to-one.
is two-to-one.
.
.
Classical post-processing
.
is one-to-one.
We can repeat Simon's algorithm a constant number of times to increase the probability of success arbitrarily, while still having the same time complexity.
Explicit examples of Simon's algorithm for few qubits
One qubit
. In this case evolving the input state through an Hadamard gate and the oracle results in the state (up to renormalization):
, and always results in the first register collapsing to the state (up to renormalization):
, with equal probability.
the number of performed measurements, and can thus be made exponentially small by increasing the statistics.
Two qubits
are thus found with equal probability.
with equal probabilities.
rule discussed in the general case.
we thus only need to distinguish between these four cases, collecting enough statistics to ensure that the probability of mistaking one outcome probability distribution for another is sufficiently small.
Complexity
queries. It is also known that Simon's algorithm is optimal in the sense that any queries.
Simon's algorithm Qiskit implementation
The quantum circuit shown here is from a simple example of how Simon's algorithm can be implemented in Python using Qiskit, an open-source quantum computing software development framework by IBM.