Presentation
Design of a Quantum Walk Circuit to Solve the Subset-Sum Problem
SessionQuantum Real Problem Solver
DescriptionSearch 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 additionally compare our solution against a Grover quantum search approach, showing a reduction of the T-depth cost compared to it. The proposed design provides a building block for the construction of efficient quantum search algorithms that can be modeled on Johnson graphs, filling the gap with the existing theoretical complexity analyses.
Event Type
Research Manuscript
TimeWednesday, June 2611:06am - 11:24am PDT
Location3004, 3rd Floor
Design
Quantum Computing