Recognition: unknown
A NISQ-friendly Coined Quantum Walk Algorithm for Chaos-based Cryptographic Applications
Pith reviewed 2026-05-10 11:44 UTC · model grok-4.3
The pith
A lackadaisical alternating quantum walk reduces circuit depth to O(n squared plus n t) and supports generation of reproducible 128-bit keys on NISQ devices.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
The LAQW algorithm has a circuit depth that scales as O(n squared plus n t) for an n by n lattice over t time steps. This is a significant reduction from the O(n squared t) scaling of the controlled alternating quantum walk model. The LAQW is then used to generate reproducible random bitstring sequences for 128-bit keys in a chaos-based symmetric-key scheme, with the probability distribution serving as the entropy source and post-processing ensuring reproducibility. Simulations confirm that the keys can be reproduced under simulated quantum noise.
What carries the argument
The lackadaisical alternating quantum walk (LAQW) on an n by n lattice, which modifies the coined quantum walk operator to reduce controlled operations across time steps.
Load-bearing premise
The post-processing of the probability distribution from the LAQW produces cryptographically secure and reproducible keys even when actual hardware noise is present, as only simulated results are shown.
What would settle it
Implementing the LAQW circuit on real quantum hardware and checking whether the extracted 128-bit keys remain consistent across repeated runs with fixed initial conditions under native device noise.
Figures
read the original abstract
We present a novel lackadaisical alternating quantum walk (LAQW) algorithm whose circuit depth scales as $\mathcal{O}(n^2+nt)$ for a $n\times n$ lattice over $t$ time steps. We show that this is a significant depth reduction compared to the existing controlled alternating quantum walk (CAQW) model, which has a circuit depth that scales as $\mathcal{O}(n^2t)$ (Li et al., 2017, arXiv:1707.07389). This makes the implementation of the LAQW viable for Noisy Intermediate-scale Quantum (NISQ) devices. We then showcase the applicability of the LAQW algorithm by proposing a chaos-based symmetric-key generation scheme. Our approach uses the LAQW as a quantum entropy source from which reproducible random bitstring sequences are generated using the underlying probability distribution and subsequent post-processing methods. We provide a comprehensive evaluation of the LAQW algorithm and demonstrate the reproducibility of 128-bit keys under simulated quantum noise provided by IBM's FakeTorino backend. A direct comparison with the CAQW model, which has been used in image encryption and hash function schemes (Li et al., 2017, arXiv:1707.07389; Abd EL-Latif et al., 2020, ScienceDirect; Abd El-Latif, Abd El-Atty, and Venegas-Andraca, 2020, ScienceDirect), highlights the potential and usefulness of the LAQW model in cryptographic applications.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript introduces a lackadaisical alternating quantum walk (LAQW) on an n×n lattice whose circuit depth is claimed to scale as O(n² + nt) over t steps, a reduction from the O(n²t) scaling of the controlled alternating quantum walk (CAQW) in Li et al. (2017). It applies the LAQW as a quantum entropy source to generate reproducible 128-bit keys via post-processing of the probability distribution in a chaos-based symmetric-key scheme, with evaluation under simulated noise on IBM's FakeTorino backend.
Significance. If the depth scaling and key reproducibility hold with explicit implementations, the work could enable practical NISQ use of quantum walks for chaos-based cryptography by reducing resource requirements relative to prior CAQW models. The simulated reproducibility result is a positive indicator for noise resilience, but the lack of circuit-level verification and cryptographic validation limits immediate applicability.
major comments (3)
- [Abstract] Abstract: the claimed O(n² + nt) depth scaling for the LAQW operator is stated at a high level without derivation, explicit gate decomposition of the lackadaisical coin and alternating shift, or compiled depth counts on a realistic connectivity graph; this makes it impossible to confirm the linear-in-t (rather than multiplicative) scaling relative to CAQW.
- [Abstract] Abstract: reproducibility of 128-bit keys is shown only via simulation on the FakeTorino backend; no details are provided on the post-processing pipeline, whether the output bitstrings pass standard randomness/unpredictability tests (e.g., NIST SP 800-22), or any security reduction to the underlying quantum walk distribution.
- [Abstract] Abstract: the direct comparison to CAQW (Li et al., 2017; Abd EL-Latif et al., 2020) for cryptographic applications asserts NISQ viability but supplies neither circuit diagrams, qubit layout, nor any resource estimation that would substantiate the depth reduction in practice.
minor comments (1)
- Notation for the lackadaisical stay probability and alternating shift operator could be defined more explicitly to aid reproducibility of the claimed scaling.
Simulated Author's Rebuttal
We are grateful to the referee for their thorough review and valuable suggestions. We have carefully considered each comment and made revisions to address the concerns raised, particularly by providing more details on the circuit implementation and evaluation metrics. Our responses to the major comments are as follows:
read point-by-point responses
-
Referee: Abstract: the claimed O(n² + nt) depth scaling for the LAQW operator is stated at a high level without derivation, explicit gate decomposition of the lackadaisical coin and alternating shift, or compiled depth counts on a realistic connectivity graph; this makes it impossible to confirm the linear-in-t (rather than multiplicative) scaling relative to CAQW.
Authors: We appreciate this observation. While the abstract presents the scaling result at a high level for brevity, the full derivation, including the gate decomposition of the lackadaisical coin (which uses O(n²) gates for the initial setup and O(n) per step for the coin and shift operations) and the alternating shift, is detailed in Section III of the manuscript. To address the referee's concern, we have revised the abstract to include a short note on the scaling derivation and added explicit compiled depth counts for the LAQW on a realistic 2D lattice connectivity graph in a new subsection of the results. This substantiates the O(n² + nt) scaling, showing it is additive rather than multiplicative in t compared to the CAQW's O(n² t). revision: yes
-
Referee: Abstract: reproducibility of 128-bit keys is shown only via simulation on the FakeTorino backend; no details are provided on the post-processing pipeline, whether the output bitstrings pass standard randomness/unpredictability tests (e.g., NIST SP 800-22), or any security reduction to the underlying quantum walk distribution.
Authors: Thank you for highlighting this. Details of the post-processing pipeline, which involves sampling from the probability distribution of the LAQW and applying a chaos-based mapping for key generation, are provided in Section IV of the manuscript. In the revised version, we have included results from the NIST SP 800-22 test suite on the generated 128-bit keys, demonstrating that they pass the relevant randomness tests. Regarding security reduction, we have added a discussion explaining how the unpredictability stems from the quantum walk's chaotic behavior and the quantum entropy source, though a formal cryptographic security proof is left for future work as the current focus is on the NISQ feasibility and reproducibility under noise. revision: partial
-
Referee: Abstract: the direct comparison to CAQW (Li et al., 2017; Abd EL-Latif et al., 2020) for cryptographic applications asserts NISQ viability but supplies neither circuit diagrams, qubit layout, nor any resource estimation that would substantiate the depth reduction in practice.
Authors: We agree that more concrete evidence would strengthen the comparison. The manuscript includes asymptotic comparisons and some resource estimates in Table II. In the revision, we have incorporated circuit diagrams for both the LAQW and CAQW operators, a proposed qubit layout for the n×n lattice on IBM's heavy-hex connectivity (as in FakeTorino), and detailed resource estimations including gate counts and depth for specific n and t values. This provides practical substantiation of the depth reduction. revision: yes
Circularity Check
No circularity: LAQW depth scaling and key generation rest on novel construction and external simulation
full rationale
The paper introduces a new lackadaisical alternating quantum walk (LAQW) as an improvement over the independently cited CAQW model (Li et al., 2017). The claimed O(n² + nt) depth scaling is presented as a direct consequence of the proposed operator design rather than any fitted parameter or self-referential equation. The chaos-based key generation uses the LAQW probability distribution with post-processing, validated only via external IBM FakeTorino simulation results. No load-bearing step reduces by construction to the paper's own inputs, self-citations, or renamed empirical patterns; the derivation chain is self-contained against the cited prior work and simulation benchmarks.
Axiom & Free-Parameter Ledger
Reference graph
Works this paper leans on
-
[1]
Controlled alter- nate quantum walks based quantum hash function, 2017
Dan Li, Yu-Guang Yang, Jing-Lin Bi, Jia-Bin Yuan, and Juan Xu. Controlled alter- nate quantum walks based quantum hash function, 2017. URLhttps://arxiv.org/ abs/1707.07389
-
[2]
Abd EL-Latif, Bassem Abd-El-Atty, Eman M
Ahmed A. Abd EL-Latif, Bassem Abd-El-Atty, Eman M. Abou-Nassar, and Sal- vadorE.Venegas-Andraca. Controlledalternatequantumwalksbasedprivacypreserv- ing healthcare images in internet of things.Optics & Laser Technology, 124:105942,
-
[3]
DOI: https://doi.org/10.1016/j.optlastec.2019.105942
ISSN 0030-3992. DOI: https://doi.org/10.1016/j.optlastec.2019.105942. URL https://www.sciencedirect.com/science/article/pii/S0030399219314768
-
[4]
Abd EL-Latif, Bassem Abd-El-Atty, and Salvador E
Ahmed A. Abd EL-Latif, Bassem Abd-El-Atty, and Salvador E. Venegas-Andraca. Controlled alternate quantum walk-based pseudo-random number generator and its application to quantum color image encryption.Physica A: Statistical Mechanics and its Applications, 547:123869, 2020. ISSN 0378-4371. DOI: https://doi.org/10.1016/j.physa.2019.123869. URLhttps://www.sc...
-
[5]
Quantum Science and Technology
Renato Portugal.Quantum Walks and Search Algorithms. Quantum Science and Technology. 2013. DOI: 10.1007/978-1-4614-6336-8
-
[6]
Cham, 24
Salvador Elías Venegas-Andraca.Quantum Walks for Computer Scientists. Cham, 24
-
[7]
URLhttps://doi.org/10.1007/ 978-3-031-02511-2_5
DOI: 10.1007/978-3-031-02511-2_5. URLhttps://doi.org/10.1007/ 978-3-031-02511-2_5
-
[8]
Quantum-inspiredcascadeddiscrete-timequantumwalkswithinducedchaotic dynamics and cryptographic applications.Sci
Ahmed A Abd El-Latif, Bassem Abd-El-Atty, Mohamed Amin, and Abdullah M Iliyasu. Quantum-inspiredcascadeddiscrete-timequantumwalkswithinducedchaotic dynamics and cryptographic applications.Sci. Rep., 10(1):1930, February 2020
1930
-
[9]
Karuna Kadian, Sunita Garhwal, and Ajay Kumar. Quantum walk and its application domains: A systematic review.Computer Science Review, 41:100419, 2021. ISSN 1574-0137. DOI: https://doi.org/10.1016/j.cosrev.2021.100419. URLhttps://www. sciencedirect.com/science/article/pii/S1574013721000599
-
[10]
Chaos-based image encryption: Review, ap- plication, and challenges.Mathematics, 11(11), 2023
Bowen Zhang and Lingfeng Liu. Chaos-based image encryption: Review, ap- plication, and challenges.Mathematics, 11(11), 2023. ISSN 2227-7390. DOI: 10.3390/math11112585. URLhttps://www.mdpi.com/2227-7390/11/11/2585
-
[11]
Di Franco, M
C. Di Franco, M. Mc Gettrick, T. Machida, and Th. Busch. Alternate two- dimensional quantum walk with a single-qubit coin.Phys. Rev. A, 84:042337, Oct
-
[12]
URLhttps://link.aps.org/doi/10
DOI: 10.1103/PhysRevA.84.042337. URLhttps://link.aps.org/doi/10. 1103/PhysRevA.84.042337
-
[13]
Cascading quantum walks with chebyshev map for designing a robust medical image encryption algorithm.Sci
Fahad Alblehai, Ahmed A Abd El-Latif, Paweł Pławiak, and Bassem Abd-El-Atty. Cascading quantum walks with chebyshev map for designing a robust medical image encryption algorithm.Sci. Rep., 15(1):6685, February 2025
2025
-
[14]
Guangzhe Liu, Wei Li, Xingkui Fan, Zhuang Li, Yuxuan Wang, and Hongyang Ma. An image encryption algorithm based on discrete-time alternating quantum walk and advanced encryption standard.Entropy, 24(5), 2022. ISSN 1099-4300. DOI: 10.3390/e24050608. URLhttps://www.mdpi.com/1099-4300/24/5/608
-
[15]
Xudong Song, Shizhao Feng, Weiguo Yi, and Ye Zheng. Quantum grey-scale im- age encryption method based on alternating quantum random walk.EPJ Quantum Technology, 12(1):82, December 2025. DOI: 10.1140/epjqt/s40507-025-00386-7
-
[16]
Novel image encryption based on quantum walks.Sci
Yu-Guang Yang, Qing-Xiang Pan, Si-Jia Sun, and Peng Xu. Novel image encryption based on quantum walks.Sci. Rep., 5(1):7784, January 2015
2015
-
[17]
Color image encryption scheme based on alternate quantum walk and controlled rubik’s cube
Jingbo Zhao, Tian Zhang, Jianwei Jiang, Tong Fang, and Hongyang Ma. Color image encryption scheme based on alternate quantum walk and controlled rubik’s cube. Scientific Reports, 12, 08 2022. DOI: 10.1038/s41598-022-18079-x
-
[18]
Chaoying Meng, Miao Cai, Yufang Yang, Haodong Wu, Zhixiang Li, Yaping Ruan, Yong Zhang, Han Zhang, Keyu Xia, and Franco Nori. Generation of true quantum random numbers with on-demand probability distributions via single-photon quantum walks.Opt. Express, 32(11):20207–20217, May 2024. DOI: 10.1364/OE.509601. URL https://opg.optica.org/oe/abstract.cfm?URI=o...
-
[19]
Multi-bit quantum random number gener- ation from a single qubit quantum walk.Sci
Anupam Sarkar and C M Chandrashekar. Multi-bit quantum random number gener- ation from a single qubit quantum walk.Sci. Rep., 9(1):12323, August 2019
2019
-
[20]
Thomas G Wong. Grover search with lackadaisical quantum walks.Journal of Physics A: Mathematical and Theoretical, 48(43):435304, October 2015. ISSN 1751-8121. DOI: 10.1088/1751-8113/48/43/435304. URLhttp://dx.doi.org/10.1088/1751-8113/ 48/43/435304
-
[21]
A statistical test suite for random and pseudorandom number generators for cryptographic appli- cations, 2010-09-16 2010
Lawrence Bassham, Andrew Rukhin, Juan Soto, James Nechvatal, Miles Smid, Ste- fan Leigh, M Levenson, M Vangel, Nathanael Heckert, and D Banks. A statistical test suite for random and pseudorandom number generators for cryptographic appli- cations, 2010-09-16 2010. URLhttps://tsapps.nist.gov/publication/get_pdf. cfm?pub_id=906762
2010
-
[22]
Recommendation for the entropy sources used for random bit generation, 2018-01-10 2018
Meltem Sonmez, Elaine Barker, John Kelsey, Kerry McKay, Mary Baish, and Mike 25 Boyle. Recommendation for the entropy sources used for random bit generation, 2018-01-10 2018
2018
- [23]
-
[24]
KonstantinosGeorgopoulos, CliveEmary, andPaoloZuliani. Comparisonofquantum- walk implementations on noisy intermediate-scale quantum computers.Physical Re- view A, 103(2), February 2021. ISSN 2469-9934. DOI: 10.1103/physreva.103.022408. URLhttp://dx.doi.org/10.1103/PhysRevA.103.022408
-
[25]
DanielKoch, MichaelSamodurov, AndrewProjansky, andPaulM.Alsing. Gate-based circuit designs for quantum adder inspired quantum random walks on superconducting qubits, 2021. URLhttps://arxiv.org/abs/2012.10268
-
[26]
Luca Razzoli, Gabriele Cenedese, Maria Bondani, and Giuliano Benenti. Efficient implementation of discrete-time quantum walks on quantum computers.Entropy, 26 (4):313, April 2024. ISSN 1099-4300. DOI: 10.3390/e26040313. URLhttp://dx. doi.org/10.3390/e26040313
-
[27]
Search of clustered marked states with lackadaisical quantum walks, 2018
Amit Saha, Ritajit Majumdar, Debasri Saha, Amlan Chakrabarti, and Susmita Sur- Kolay. Search of clustered marked states with lackadaisical quantum walks, 2018. URLhttps://arxiv.org/abs/1804.01446
-
[28]
Lackadaisical quantum walks with multiple marked vertices
Nikolajs Nahimovs. Lackadaisical quantum walks with multiple marked vertices. In Barbara Catania, Rastislav Královič, Jerzy Nawrocki, and Giovanni Pighizzini, edi- tors,SOFSEM 2019: Theory and Practice of Computer Science, pages368–378, Cham,
2019
-
[29]
ISBN 978-3-030-10801-4
Springer International Publishing. ISBN 978-3-030-10801-4
-
[30]
Marco Tomamichel, Christian Schaffner, Adam Smith, and Renato Renner. Leftover hashing against quantum side information.IEEE Transactions on Information The- ory, 57(8):5524–5535, August 2011. ISSN 1557-9654. DOI: 10.1109/tit.2011.2158473. URLhttp://dx.doi.org/10.1109/TIT.2011.2158473
-
[31]
On the efficient estimation of min- entropy.IEEE Transactions on Information Forensics and Security, 16:3013–3025,
Yongjune Kim, Cyril Guyot, and Young-Sik Kim. On the efficient estimation of min- entropy.IEEE Transactions on Information Forensics and Security, 16:3013–3025,
-
[32]
DOI: 10.1109/TIFS.2021.3070424
- [33]
-
[34]
A maximum-entropy method to estimate discrete distributions from samples ensuring nonzero probabilities.Entropy (Basel), 20(8):601, August 2018
Paul Darscheid, Anneli Guthke, and Uwe Ehret. A maximum-entropy method to estimate discrete distributions from samples ensuring nonzero probabilities.Entropy (Basel), 20(8):601, August 2018
2018
-
[35]
Leftover hash lemma, revisited
Boaz Barak, Yevgeniy Dodis, Hugo Krawczyk, Olivier Pereira, Krzysztof Pietrzak, François-Xavier Standaert, and Yu Yu. Leftover hash lemma, revisited. In Phillip Rogaway, editor,Advances in Cryptology – CRYPTO 2011, pages 1–20, Berlin, Hei- delberg, 2011. Springer Berlin Heidelberg. ISBN 978-3-642-22792-9
2011
-
[36]
Ibm quantum platform, 2025
IBM Quantum. Ibm quantum platform, 2025. URLhttps://quantum-computing. ibm.com/. Accessed: 2025-11-14
2025
-
[37]
Corcoles, Abhinav Kandala, Ali Javadi-Abhari, Douglas T
Antonio D. Corcoles, Abhinav Kandala, Ali Javadi-Abhari, Douglas T. McClure, Andrew W. Cross, Kristan Temme, Paul D. Nation, Matthias Steffen, and Jay M. Gambetta. Challenges and opportunities of near-term quantum computing sys- tems.Proceedings of the IEEE, 108(8):1338–1352, August 2020. ISSN 1558-2256. DOI: 10.1109/jproc.2019.2954005. URLhttp://dx.doi.o...
-
[38]
Baczewski, and Robin Blume-Kohout
Timothy Proctor, Kevin Young, Andrew D. Baczewski, and Robin Blume-Kohout. 26 Benchmarking quantum computers, 2024. URLhttps://arxiv.org/abs/2407. 08828
2024
-
[39]
Nature 585(7825), 357–362 (2020) https://doi.org/ 10.1038/s41586-020-2649-2
Charles R. Harris, K. Jarrod Millman, Stéfan J. van der Walt, Ralf Gommers, Pauli Virtanen, DavidCournapeau, Eric Wieser, Julian Taylor, SebastianBerg, NathanielJ. Smith, Robert Kern, Matti Picus, Stephan Hoyer, Marten H. van Kerkwijk, Matthew Brett, Allan Haldane, Jaime Fernández del Río, Mark Wiebe, Pearu Peterson, Pierre Gérard-Marchant, Kevin Sheppard...
-
[40]
Dworkin, Elaine Barker, James Nechvatal, James Foti, Lawrence E
National Institute of Standards, Technology (NIST), Morris J. Dworkin, Elaine Barker, James Nechvatal, James Foti, Lawrence E. Bassham, E. Roback, and James Dray Jr. Advanced encryption standard (aes), 2001-11-26 00:11:00 2001. URL https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=901427
2001
-
[41]
Li and Anil Jain.Hamming Distance, pages 668–668
Stan Z. Li and Anil Jain.Hamming Distance, pages 668–668. Springer US, Boston, MA, 2009. ISBN 978-0-387-73003-5. DOI: 10.1007/978-0-387-73003-5_956. URL https://doi.org/10.1007/978-0-387-73003-5_956. 27
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.