Design of a Quantum Walk Circuit to Solve the Subset-Sum Problem
Authors: 
Giacomo Lancellotti, Simone Perriello, Alessandro Barenghi, Gerardo PelosiAuthors Info & Claims
Article No.: 298, Pages 1 - 6
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 modelled on Johnson graphs, filling the gap with the existing theoretical complexity analyses.
References
[1]
Romas Aleliunas, Richard M. Karp, Richard J. Lipton, László Lovász, and Charles Rackoff. 1979. Random walks, universal traversal sequences, and the complexity of maze problems. In 20th Annual Symposium on Foundations of Computer Science, San Juan, Puerto Rico, 29-31 October 1979. IEEE Computer Society.
[2]
Andris Ambainis. 2004. Quantum walk algorithm for element distinctness. In 45th Symposium on Foundations of Computer Science (FOCS 2004), 17-19 October 2004, Rome, Italy, Proceedings. IEEE Computer Society.
[3]
Andreas Bärtschi and Stephan J. Eidenbenz. 2019. Deterministic preparation of dicke states. In Fundamentals of Computation Theory - 22nd International Symposium, FCT 2019, Copenhagen, Denmark, August 12-14, 2019, Proceedings (LNCS). Leszek Antoni Gasieniec, Jesper Jansson, and Christos Levcopoulos, (Eds.) Vol. 11651. Springer.
[4]
Daniel J. Bernstein, Stacey Jeffery, Tanja Lange, and Alexander Meurer. 2013. Quantum algorithms for the subset-sum problem. In Post-Quantum Cryptography - 5th International Workshop, PQCrypto 2013, Limoges, France, June 4-7, 2013. Proceedings (LNCS). Philippe Gaborit, (Ed.) Vol. 7932. Springer.
[5]
Xavier Bonnetain, Rémi Bricout, André Schrottenloher, and Yixin Shen. 2020. Improved classical and quantum algorithms for subset-sum. In Advances in Cryptology - ASIACRYPT 2020 - 26th International Conference on the Theory and Application of Cryptology and Information Security, Daejeon, South Korea, December 7-11, 2020, Proceedings, Part II (LNCS). Shiho Moriai and Huaxiong Wang, (Eds.) Vol. 12492. Springer.
[6]
P. Oscar Boykin, Tal Mor, Matthew Pulver, Vwani P. Roychowdhury, and Farrokh Vatan. 2000. A new universal and fault-tolerant quantum basis. Inf. Process. Lett., 75.
[7]
M. R. Garey and David S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman.
[8]
Vlad Gheorghiu, Michele Mosca, and Priyanka Mukhopadhyay. 2022. T-count and t-depth of any multi-qubit unitary. npj Quantum Information, 8.
[9]
Lov K. Grover. 1996. A fast quantum mechanical algorithm for database search. In Proceedings of the Twenty-Eighth Annual {ACM} Symposium on the Theory of Computing, Philadelphia, Pennsylvania, USA, May 22-24, 1996. Gary L. Miller, (Ed.) ACM.
[10]
Alexander Helm and Alexander May. 2018. Subset sum quantumly in 1.17n. In 13th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2018, July 16-18, 2018, Sydney, Australia (LIPIcs). Stacey Jeffery, (Ed.) Vol. 111. Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
[11]
Peter Høyer, Michele Mosca, and Ronald de Wolf. 2003. Quantum search on bounded-error inputs. In Automata, Languages and Programming, 30th International Colloquium, ICALP 2003, Eindhoven, The Netherlands, June 30 - July 4, 2003. Proceedings (LNCS). Jos C. M. Baeten, Jan Karel Lenstra, Joachim Parrow, and Gerhard J. Woeginger, (Eds.) Vol. 2719. Springer.
[12]
Samuel Jaques and John M. Schanck. 2019. Quantum cryptanalysis in the RAM model: claw-finding attacks on SIKE. In Advances in Cryptology - CRYPTO 2019 - 39th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2019, Proceedings, Part I (LNCS). Alexandra Boldyreva and Daniele Micciancio, (Eds.) Vol. 11692. Springer.
[13]
Ghazal Kachigar and Jean-Pierre Tillich. 2017. Quantum information set decoding algorithms. In Post-Quantum Cryptography - 8th International Workshop, PQCrypto 2017, Utrecht, The Netherlands, June 26-28, 2017, Proceedings (LNCS). Tanja Lange and Tsuyoshi Takagi, (Eds.) Vol. 10346. Springer.
[14]
Vadim Lyubashevsky, Adriana Palacio, and Gil Segev. 2010. Public-key cryptographic primitives provably as secure as subset sum. In Theory of Cryptography, 7th Theory of Cryptography Conference, TCC 2010, Zurich, Switzerland, February 9-11, 2010. Proceedings (LNCS). Daniele Micciancio, (Ed.) Vol. 5978. Springer.
[15]
Frédéric Magniez, Ashwin Nayak, Jérémie Roland, and Miklos Santha. 2011. Search via quantum walk. SIAM J. Comput., 40.
[16]
Michael A Nielsen and Isaac L Chuang. 2010. Quantum Computation and Quantum Information. Cambridge University Press.
[17]
J. R. Norris. 1997. Markov Chains. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press.
[18]
Simone Perriello, Alessandro Barenghi, and Gerardo Pelosi. 2021. A complete quantum circuit to solve the information set decoding problem. In IEEE International Conference on Quantum Computing and Engineering, QCE 2021, Broomfield, CO, USA, October 17-22, 2021. Hausi A. Müller, Greg Byrd, Candace Culhane, and Travis Humble, (Eds.) IEEE.
[19]
Simone Perriello, Alessandro Barenghi, and Gerardo Pelosi. 2023. Improving the efficiency of quantum circuits for information set decoding. ACM Transactions on Quantum Computing.
[20]
Neil Shenvi, Julia Kempe, and K. Birgitta Whaley. 2003. Quantum random-walk search algorithm. Phys. Rev. A, 67, 11 pages, 5.
[21]
Mario Szegedy. 2004. Quantum speed-up of markov chain based algorithms. In 45th Symposium on Foundations of Computer Science (FOCS 2004), 17-19 October 2004, Rome, Italy, Proceedings. IEEE Computer Society.
[22]
Yasuhiro Takahashi, Seiichiro Tani, and Noboru Kunihiro. 2010. Quantum addition circuits and unbounded fan-out. Quantum Inf. & Comp., 10.
[23]
Seiichiro Tani. 2009. Claw finding algorithms using quantum walk. Theoretical Compututer Science, 410.
Index Terms
- Design of a Quantum Walk Circuit to Solve the Subset-Sum Problem
Recommendations
Improved Classical and Quantum Algorithms for Subset-Sum
Advances in Cryptology – ASIACRYPT 2020AbstractWe present new classical and quantum algorithms for solving random subset-sum instances. First, we improve over the Becker-Coron-Joux algorithm (EUROCRYPT 2011) from down to , using more general representations with values in
Quantum gates via continuous time quantum walks in multiqubit systems with non-local auxiliary states: Quantum gates via continuous time quantum walks in multiqubit systems with non-local auxiliary states
Non-local higher-energy auxiliary states have been successfully used to entangle pairs of qubits in different quantum computing systems. Typically a longer-span nonlocal state or sequential application of few-qubit entangling gates are needed to produce ...
Quantum walk on distinguishable non-interacting many-particles and indistinguishable two-particle
We present an investigation of many-particle quantum walks in systems of non-interacting distinguishable particles. Along with a redistribution of the many-particle density profile we show that the collective evolution of the many-particle system ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
This work is licensed under a Creative Commons Attribution International 4.0 License.
Sponsors
In-Cooperation
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 07 November 2024
Check for updates
Author Tags
Qualifiers
- Research-article
Conference
DAC '24
Sponsor:
Acceptance Rates
Overall Acceptance Rate 1,770 of 5,499 submissions, 32%
Upcoming Conference
DAC '25
- Sponsor:
- sigda
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 39Total Downloads
- Downloads (Last 12 months)39
- Downloads (Last 6 weeks)39
Reflects downloads up to 18 Nov 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in