research-article

Open access

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

Authors:

Giacomo Lancellotti,

Simone Perriello,

Alessandro Barenghi,

Gerardo PelosiAuthors Info & Claims

DAC '24: Proceedings of the 61st ACM/IEEE Design Automation Conference

Article No.: 298, Pages 1 - 6

https://doi.org/10.1145/3649329.3657337

Published: 07 November 2024 Publication History

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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[10]

Alexander Helm and Alexander May. 2018. Subset sum quantumly in 1.17ⁿ. 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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Cited By

Perriello SBarenghi APelosi G(2024)A Quantum Circuit to Execute a Key-Recovery Attack Against the DES and 3DES Block Ciphers2024 IEEE International Conference on Quantum Computing and Engineering (QCE)10.1109/QCE60285.2024.00011(1-12)Online publication date: 15-Sep-2024
https://doi.org/10.1109/QCE60285.2024.00011
Barenghi APelosi G(2024)Post Quantum Cryptography Research Lines in the Italian Center for Security and Rights in CyberspaceEmbedded Computer Systems: Architectures, Modeling, and Simulation10.1007/978-3-031-78380-7_16(191-202)Online publication date: 30-Jun-2024
https://dl.acm.org/doi/10.1007/978-3-031-78380-7_16

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 2020
Abstract
We present new classical and quantum algorithms for solving random subset-sum instances. First, we improve over the Becker-Coron-Joux algorithm (EUROCRYPT 2011) from $\tilde{O} (2^{0.291 n})$ down to $\tilde{O} (2^{0.283 n})$ , using more general representations with values in ${- ...$ $\overset{}{} (^{})$
$\overset{}{} (^{})$ $\overset{}{} (^{})$ $\overset{}{} (^{})$
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

cover image ACM Conferences

DAC '24: Proceedings of the 61st ACM/IEEE Design Automation Conference

June 2024

2159 pages

ISBN:9798400706011

DOI:10.1145/3649329

Chair:
Vivek De

This work is licensed under a Creative Commons Attribution International 4.0 License.

Sponsors

SIGDA: ACM Special Interest Group on Design Automation
IEEE-CEDA

In-Cooperation

SIGBED: ACM Special Interest Group on Embedded Systems

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:

SIGDA

DAC '24: 61st ACM/IEEE Design Automation Conference

June 23 - 27, 2024

CA, San Francisco, USA

Acceptance Rates

Overall Acceptance Rate 1,770 of 5,499 submissions, 32%

Upcoming Conference

DAC '25

Sponsor:
sigda

62nd ACM/IEEE Design Automation Conference

June 22 - 26, 2025

San Francisco , CA , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
160
Total Downloads

Downloads (Last 12 months)160
Downloads (Last 6 weeks)76

Reflects downloads up to 03 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Perriello SBarenghi APelosi G(2024)A Quantum Circuit to Execute a Key-Recovery Attack Against the DES and 3DES Block Ciphers2024 IEEE International Conference on Quantum Computing and Engineering (QCE)10.1109/QCE60285.2024.00011(1-12)Online publication date: 15-Sep-2024
https://doi.org/10.1109/QCE60285.2024.00011
Barenghi APelosi G(2024)Post Quantum Cryptography Research Lines in the Italian Center for Security and Rights in CyberspaceEmbedded Computer Systems: Architectures, Modeling, and Simulation10.1007/978-3-031-78380-7_16(191-202)Online publication date: 30-Jun-2024
https://dl.acm.org/doi/10.1007/978-3-031-78380-7_16

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Figures

Tables

Media

View Table of Conten