Simon's problem

(Redirected from Simon's algorithm)

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.[1] 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.[2] 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).[3] 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.[4] However, without such an oracle, exponential speedups cannot easily be proven, since this would prove that P is different from PSPACE.

Problem description

edit

Given a function (implemented by a black box or oracle)   with the promise that, for some unknown  , for all  ,

  if and only if  ,

where   denotes bitwise XOR. The goal is to identify   by making as few queries to   as possible. Note that

  if and only if  

Furthermore, for some   and   in  ,   is unique (not equal to  ) if and only if  . This means that   is two-to-one when  , and one-to-one when  . It is also the case that   implies  , meaning that which shows how   is periodic.

The associated decision problem formulation of Simon's problem is to distinguish when   (  is one-to-one), and when   (  is two-to-one).

Example

edit

The following function is an example of a function that satisfies the required property for  :

   
000 101
001 010
010 000
011 110
100 000
101 110
110 101
111 010

In this case,   (i.e. the solution). 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 (by  ) to the same output string  . That is,   and  . Applying XOR to 010 and 100 obtains 110, that is  

  can also be verified using input strings 001 and 111 that are both mapped (by f) to the same output string 010. Applying XOR to 001 and 111 obtains 110, that is  . This gives the same solution   as before.

In this example the function f is indeed a two-to-one function where  .

Problem hardness

edit

Intuitively, this is a 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   (or what it does) 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. Since, classically to find s with a 100% certainty it would require checking   inputs, Simon's problem seeks to find s using fewer queries than this classical method.

Simon's algorithm

edit
 
Quantum circuit representing/implementing Simon's algorithm

The algorithm as a whole uses a subroutine to execute the following two steps:

  1. Run the quantum subroutine an expected   times to get a list of linearly independent bitstrings  .
  2. Each   satisfies  , so we can solve the system of equations this produces to get  .

Quantum subroutine

edit

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 where  , where   denotes XOR.

First, the algorithm starts with two registers, initialized to  . Then, we apply the Hadamard transform to the first register, which gives the state

 

Query the oracle   to get the state

 .

Apply another Hadamard transform to the first register. This will produce the state

 

Finally, we measure the first register (the algorithm also works if the second register is measured before the first, but this is unnecessary). The probability of measuring a state   is This is due to the fact that taking the magnitude of this vector and squaring it sums up all the probabilities of all the possible measurements of the second register that must have the first register as  . There are two cases for our measurement:

  1.   and   is one-to-one.
  2.   and   is two-to-one.

For the first case,  since in this case,   is one-to-one, implying that the range of   is  , meaning that the summation is over every basis vector. For the second case, note that there exist two strings,   and  , such that  , where  . Thus,  Furthermore, since  ,  , and so This expression is now easy to evaluate. Recall that we are measuring  . When  , then this expression will evaluate to  , and when  , then this expression will be  .

Thus, both when   and when  , our measured   satisfies  .

Classical post-processing

edit

We run the quantum part of the algorithm until we have a linearly independent list of bitstrings  , and each   satisfies  . Thus, we can efficiently solve this system of equations classically to find  .

The probability that   are linearly independent is at least Once we solve the system of equations, and produce a solution  , we can test if  . If this is true, then we know  , since  . If it is the case that  , then that means that  , and   since   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

edit

One qubit

edit

Consider the simplest instance of the algorithm, with  . In this case evolving the input state through an Hadamard gate and the oracle results in the state (up to renormalization):

 

If  , that is,  , then measuring the second register always gives the outcome  , and always results in the first register collapsing to the state (up to renormalization):

 

Thus applying an Hadamard and measuring the first register always gives the outcome  . On the other hand, if   is one-to-one, that is,  , then measuring the first register after the second Hadamard can result in both   and  , with equal probability.

We recover   from the measurement outcomes by looking at whether we measured always  , in which case  , or we measured both   and   with equal probability, in which case we infer that  . This scheme will fail if   but we nonetheless always found the outcome  , but the probability of this event is   with   the number of performed measurements, and can thus be made exponentially small by increasing the statistics.

Two qubits

edit

Consider now the case with  . The initial part of the algorithm results in the state (up to renormalization): If  , meaning   is injective, then finding   on the second register always collapses the first register to  , for all  . In other words, applying Hadamard gates and measuring the first register the four outcomes   are thus found with equal probability.

Suppose on the other hand  , for example,  . Then measuring   on the second register collapses the first register to the state  . And more generally, measuring   gives   on the first register. Applying Hadamard gates and measuring on the first register can thus result in the outcomes   and   with equal probabilities.

Similar reasoning applies to the other cases: if   then the possible outcomes are   and  , while if   the possible outcomes are   and  , compatibly with the   rule discussed in the general case.

To recover   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

edit

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.[5][6]

See also

edit

References

edit
  1. ^ Shor, Peter W. (1999-01-01). "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer". SIAM Review. 41 (2): 303–332. arXiv:quant-ph/9508027. doi:10.1137/S0036144598347011. ISSN 0036-1445.
  2. ^ Simon, Daniel R. (1997-10-01). "On the Power of Quantum Computation". SIAM Journal on Computing. 26 (5): 1474–1483. doi:10.1137/S0097539796298637. ISSN 0097-5397.
  3. ^ Preskill, John (1998). Lecture Notes for Physics 229: Quantum Information and Computation. pp. 273–275.
  4. ^ Aaronson, Scott (2018). Introduction to Quantum Information Science Lecture Notes (PDF). pp. 144–151.
  5. ^ 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
  6. ^ 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:quant-ph/0501060, Bibcode:2005quant.ph..1060K, retrieved 2011-06-06