Circuit implementation and analysis of a quantum-walk based search complement algorithm

Area of Science:

• Quantum Computing
• Quantum Algorithms
• Graph Theory

Background:

• The Shenvi, Kempe, and Whaley (SKW) algorithm is a quantum walk-based search method.
• Quantum walks offer a powerful framework for search and optimization problems.

Purpose of the Study:

• To modify the SKW algorithm to exhibit a 'search complement' behavior, reducing target state probabilities.
• To extend the algorithm for multi-node targeting, enhancing its utility for quantum optimization.

Main Methods:

• Modification of the SKW algorithm's evolution operator using a graph shift operator and a perturbed Hadamard coin operator.
• Application of a multigraph and matrix approach to analyze the quantum walk dynamics.
• Experimental execution on the IBM quantum processor ibmq_manila.

Main Results:

• The modified algorithm successfully reduces the probability of measuring target states, demonstrating the 'search complement' effect.
• The algorithm was extended to target multiple nodes simultaneously.
• Experimental results on ibmq_manila showed a statistical distance of [Formula: see text] when reducing the probability of one state out of four.

Conclusions:

• The developed 'search complement' quantum walk algorithm offers a novel approach to manipulating state probabilities.
• The algorithm's multi-node targeting capability makes it a promising initialization routine for the Quantum Approximate Optimization Algorithm (QAOA) in solving restricted Quadratic Unconstrained Binary Optimization (QUBO) problems.