1307.6538 (Itay Hen)

Period Finding with Adiabatic Quantum Computation    [PDF]

Itay Hen

We outline a quantum-adiabatic algorithm to solve Simon's problem, in which one has to determine the `period', or xor-mask, of a given black-box function. We show that the proposed algorithm is exponentially faster than its classical counterpart and has the same complexity as the corresponding circuit-based algorithm. Together with other related studies, this result supports a conjecture that the complexity of adiabatic quantum computation is equivalent to the circuit-based computational model in a stronger sense than the well-known, proven polynomial equivalence between the two paradigms. We also briefly discuss the implications of the algorithm for the existence of an optimal-complexity adiabatic version of Shor's period finding algorithm and its experimental implementation.

View original: http://arxiv.org/abs/1307.6538