A concept of controlling Grover diffusion operator: a new approach to solve arbitrary Boolean-based problems

Abstract

Abstract A controlled-diffusion operator for Boolean oracles is designed as a new approach for Grover’s algorithm to search for solutions for arbitrary logical structures of such oracles, since the Grover diffusion operator is not able to find correct solutions for some logical structures of Boolean oracles. We also show that the Phase oracles do not work sometimes correctly using the Grover diffusion operator. Our proposed controlled-diffusion operator relies on the states of output qubit, as the reflection of Boolean decisions from a Boolean oracle without relying on the phase kickback. We prove that on many examples of Boolean and Phase oracles the Grover diffusion operator is not working correctly. The oracles in these examples are constructed using different structures of POS, SOP, ESOP, CSP-SAT, and XOR-SAT. Our mathematical models and experiments prove that the proposed controlled-diffusion operator successfully searches for all solutions for all Boolean oracles regardless of their different logical structures.

Keywords

• Grover’s algorithm
• Grover diffusion operator
• Controlled-diffusion operator
• Boolean oracle
• Phase oracle
• Logical structures