An exact quantum polynomial-time algorithm for Simon's problem

摘要: We investigate the power of quantum computers when they are required to return an answer that is guaranteed be correct after a time upper-bounded by polynomial in worst case. show natural generalization Simon's problem can solved this way, whereas previous algorithms expected sense only, without upper bounds on worst-case running time. This achieved generalizing both and Grover's combining them novel way. It follows there decision exact time, which would require exponential any classical bounded-error probabilistic computer if data supplied as black box.