Quantum parity algorithms as oracle calls, and application in Grover Database search

This paper discusses the determination of the parity of a string of N binary digits, the well-known problem in classical as well as quantum information processing. It can be formulated as an oracle problem. It has been established that quantum algorithms require at least N /2 oracle calls. We present an algorithm that reaches this lower bound and is also optimal in terms of additional gate operations required.