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 T-count 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 modeled on Johnson graphs, filling the gap with the existing theoretical complexity analyses.
Design of a Quantum Walk Circuit to Solve the Subset-Sum Problem
G. Lancellotti;S. Perriello;A. Barenghi;G. Pelosi
2024-01-01
Abstract
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 T-count 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 modeled on Johnson graphs, filling the gap with the existing theoretical complexity analyses.File | Dimensione | Formato | |
---|---|---|---|
main_stripped_squeezed.pdf
Accesso riservato
:
Altro materiale allegato
Dimensione
638.68 kB
Formato
Adobe PDF
|
638.68 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.