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.
Giacomo Lancellotti
Ph.D. Student
I am a PhD Researcher at the Department of Electronics, Information, and Bioengineering (DEIB) at Politecnico di Milano, part of the quantum computing research group. In my free time, I enjoy playing board games, traveling, and exploring personal finance and startups.
Alessandro Barenghi
Associate Professor
Alessandro Barenghi holds an M.Sc. (2007) and Ph.D. (2011) from Politecnico di Milano. His research focuses on computer, embedded, and network security, particularly applied cryptography. He also works on formal languages and compilers, specifically techniques for parallel parsing using operator precedence grammars.
Gerardo Pelosi
Associate Professor
Gerardo Pelosi received the Laurea degree in Telecommunications Engineering in 2003 and the Ph.D. degree in Computer Engineering and Information Technology in 2007 from Politecnico di Milano. His research fields cover (1) the area of information security and privacy including access control models, models for encrypted data management in relational databases, and secure data outsourcing; (2) the area of applied cryptography including side-channel cryptanalysis, system-level attacks, and efficient hardware and software design of cryptographic algorithms; other research interests are in designing security support into computer architectures and the logic synthesis of combinatorial circuits.