Quantum abstract detecting systems

Abstract

In this paper, we study Quantum Abstract Detecting Systems (QADS), that generalize some key characteristics of the operators used in Grover’s algorithm, a wide variety of quantum walks and the quantum abstract search algorithm. A QADS is an algorithm that constructs a quantum state and a quantum operator that help testing whether a circuit-implemented boolean function f is identically zero. We also identify some relatively weak properties of QADS that lead to the construction of algorithms for the detection problem (i.e. determining whether there is a marked element in a given set). Our results provide not only a common framework to all the aforementioned search methods, and their transformation into algorithms for the detection problem, but also allow the development of new similar methods. As an example, we construct a modification of Grover’s algorithm (from the tensor product of controlled QADS) that shows improved detection probability.