Meeting 8.1: Simon's problem and factoring
From Eric Samperton
…Read more Less…
Simon's problem is a somewhat contrived oracle problem that provides an oracle separation of BQP and BPP, which should be interpreted as evidence (but not proof) that BQP and BPP are distinct. Simon's problem and Deutsch's problem are both examples of the hidden subgroup problem, which has other more important and realistic problems as special cases, and often has efficient quantum algorithms. In particular, order-finding in the group of units of a finite cyclic ring Z/nZ, which can be used to factor composite integers. Order-finding can then be solved in BQP using the phase estimation protocol.