Design of a Quantum Walk Circuit to Solve the Subset-Sum Problem

Search algorithms based on quantum walks have emerged as a promising approach to solve computational problems across various domains, including combinatorial optimization, and cryptography. Stating a generic search problem in terms of a (quantum) search over a graph makes the efficiency of the algorithmic method depend on the structure of the graph itself. In this work, we propose a complete implementation of a quantum walk search on Johnson graphs, speeding up the solution of the subset-sum problem. We provide a detailed design of each sub-circuit, quantifying their cost in terms of gate number, depth, and width. We compare our solution against a Grover quantum search, showing a reduction of the Tcount and T-depth for practically solvable problems. The proposed design provides a building block for the construction of efficient quantum search algorithms that can be modelled on Johnson graphs, filling the gap with the existing theoretical complexity analyses.

• Theory of computation → Design and analysis of algorithms; • Mathematics of computing → Graph algorithms; • Computer systems organization → Quantum computing.