A NISQ-friendly Coined Quantum Walk Algorithm for Chaos-based Cryptographic Applications
Natalie Gibson, Niklas Keckman, Andrea Marchesin, Matti Raasakka, Ilkka Tittonen
Abstract
We present a novel lackadaisical alternating quantum walk (LAQW) algorithm whose circuit depth scales as for a lattice over 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 (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.
AI Impact Assessments
(3 models)Scientific Impact Assessment
1. Core Contribution
The paper introduces the Lackadaisical Alternating Quantum Walk (LAQW), a novel quantum walk variant that achieves circuit depth scaling of O(n² + nt) for an n×n lattice over t time steps, compared to O(n²t) for the existing Controlled Alternating Quantum Walk (CAQW). The key insight is elegant: by adding self-loops to each node of the cycle graph (requiring one additional coin qubit), the shift matrices become circulant, enabling QFT-based circuit optimization that was previously incompatible with the odd-sized cycle graphs required by AQW/CAQW models. The paper then builds a complete symmetric-key generation scheme on top of the LAQW, including post-processing (interval rounding, prime-modulus mapping) and entropy extraction via the Leftover Hash Lemma.
2. Methodological Rigor
Circuit analysis: The depth comparison is well-substantiated. The authors correctly identify that odd-sized cycle graphs (needed by AQW/CAQW to avoid predictable parity patterns) preclude QFT-based optimization because the resulting increment/decrement matrices are non-circulant. The LAQW resolves this by allowing even-sized cycles with self-loops, restoring circulant structure at the cost of one extra qubit. The ~88% depth reduction across t∈{8,...,20} on both GenericBackendV2 and FakeTorino backends is convincing.
Sensitivity analysis: The use of Hellinger distance over 1000 random parameter sets is reasonable but has limitations. The LAQW shows higher sensitivity to coin parameters (θ₀, θ₁, α) but lower sensitivity to time step changes and lower average distance between uncorrelated distributions (14.63% less). The authors acknowledge this trade-off honestly.
Cryptographic evaluation: The statistical testing is adequate but limited. Only a subset of NIST SP 800-22 tests is applied, and the bitstring lengths (5120 raw, 128 key) are short—acknowledged by the authors for the spectral test. The min-entropy estimation using Clopper-Pearson bounds is methodologically sound. However, the raw bitstring fails the Runs test (p=0.003), which is somewhat concerning even though the extracted key passes all tests.
Reproducibility testing: The demonstration of key reproducibility (normalized Hamming distance of 0.0003 across 100 trials, including under FakeTorino noise) is a strength, though the sample size and key length are modest.
Notable weaknesses in rigor: The interval rounding parameters (α=0.005, β=0.010, threshold 0.03S) appear chosen heuristically without theoretical justification. The weighted bit extraction scheme using α_r as a weighting factor is also ad hoc. The claim of "chaos" in the quantum walk is used informally—no formal Lyapunov exponents or rigorous chaos metrics are computed.
3. Potential Impact
The practical impact is moderate but targeted. The ~88% circuit depth reduction genuinely addresses a real barrier to running quantum walk-based cryptographic primitives on near-term hardware. However, the authors themselves note that even the LAQW circuits remain too deep for current hardware capabilities. The cryptographic application is a proof-of-concept rather than a production-ready scheme—no formal security proof is provided, and the key length (128 bits) from a 5120-bit raw string with extensive post-processing raises questions about efficiency.
The work could influence the quantum walk community by providing a practical template for QFT-compatible walk designs on even-sized lattices. The observation that self-loops restore circulant structure is a useful technical insight that may find applications beyond cryptography (e.g., spatial search, graph algorithms).
4. Timeliness & Relevance
The paper addresses the well-recognized gap between theoretical quantum walk algorithms and their practical implementation on NISQ devices. As quantum hardware improves toward the hundreds-of-qubits regime with moderate coherence times, reducing circuit depth from O(n²t) to O(n²+nt) becomes increasingly relevant. The focus on reproducibility under realistic noise (FakeTorino) is timely and practical. However, the cryptographic application feels somewhat forced—the community already has well-established methods for key generation, and the advantage of quantum walk-based approaches over simpler quantum random number generators is not convincingly argued.
5. Strengths & Limitations
Strengths:
Limitations:
Additional Observations
The paper is well-written and clearly structured. The figures effectively communicate the circuit comparisons and Hamming distance distributions. The work sits at an intersection of quantum computing, cryptography, and chaos theory, but doesn't achieve deep results in any single area. The contribution is primarily algorithmic (the LAQW circuit) rather than cryptographic—the key generation scheme is illustrative rather than foundational.
Generated Apr 17, 2026
Comparison History (43)
Paper 2 offers a significant, quantifiable algorithmic improvement (circuit depth reduction) that makes quantum walks viable for current NISQ devices. Its direct application to chaos-based cryptography provides immediate, highly relevant real-world utility in cybersecurity. While Paper 1 offers valuable fundamental insights into quantum thermodynamics, Paper 2's timeliness, practical implementation on simulated IBM backends, and clear technological applications give it a higher potential for broad and immediate scientific impact.
Paper 1 offers a practical, depth-reduced quantum algorithm tailored for near-term (NISQ) devices, directly addressing current hardware limitations. Its concrete real-world application in cryptography, validated through simulated noisy backends, ensures immediate and tangible utility. While Paper 2 provides profound theoretical insights into quantum thermodynamics, Paper 1's combination of algorithmic innovation, practical applicability, and high timeliness gives it a higher potential for broad and immediate scientific impact.
Paper 1 presents a novel quantum walk algorithm with significant circuit depth reduction enabling NISQ implementation, combined with a practical cryptographic application. It addresses the critical challenge of making quantum algorithms viable on near-term hardware, has broader applicability (cryptography, image encryption, hash functions), and demonstrates practical reproducibility under realistic noise models. Paper 2 offers a technically rigorous but incremental improvement to fidelity estimation via semidefinite programming, with narrower scope and more limited real-world applicability. Paper 1's dual contribution (algorithmic improvement + application) gives it broader impact potential.
Paper 1 offers a more methodologically rigorous and broadly relevant contribution: it replaces a surrogate objective with an exact minimax (worst-case variance) formulation, reduces it to an SDP, and provides implementable algorithms with demonstrated variance gains over a known baseline (OASIS). This advances a core quantum verification/characterization primitive with potential impact across quantum computing/communication experiments. Paper 2 is timely and application-oriented, but its cryptographic scheme relies on NISQ-generated “entropy” and simulated backends, with less clear security grounding and narrower likely uptake beyond niche quantum-walk-based crypto.
Paper 2 introduces a fundamentally new theoretical measure (Gaussian asymmetry) that addresses analytical limitations in the well-established field of entanglement asymmetry. It connects to multiple active research areas (Mpemba effect, symmetry restoration, quasiparticle picture) and provides exact analytical techniques applicable to free-fermionic systems. Its broader theoretical applicability across quantum many-body physics and its methodological elegance give it wider impact potential. Paper 1, while technically sound, addresses a more niche intersection of quantum walks and cryptography with NISQ-era constraints that may become obsolete.
Paper 1 likely has higher impact due to a clear algorithmic innovation (reducing quantum-walk circuit depth from O(n^2 t) to O(n^2+nt)) directly targeting NISQ feasibility, plus a concrete cryptographic application and simulation under realistic noise. This combination improves practicality and timeliness for near-term quantum computing and may influence quantum algorithm design and applied security. Paper 2 is conceptually interesting at the interface of QED and quantum information, but it is theoretical, tree-level, and its near-term applicability and cross-field uptake may be narrower.
Paper 2 offers higher potential impact due to its significant reduction in quantum circuit depth, addressing a critical bottleneck for Noisy Intermediate-Scale Quantum (NISQ) devices. While Paper 1 provides a robust hardware advancement for quantum optics, Paper 2's algorithmic improvement directly accelerates near-term quantum cryptographic applications. The transition from multiplicative to additive depth scaling, combined with practical demonstrations of symmetric-key generation under simulated noise, ensures broad, immediate relevance across both quantum computing and cybersecurity fields.
Paper 2 offers a significant practical breakthrough by reducing the circuit depth of quantum walk algorithms, making them viable for current Noisy Intermediate-Scale Quantum (NISQ) devices. While Paper 1 provides valuable fundamental physics insights into multi-photon entanglement, Paper 2 demonstrates more immediate real-world utility by directly applying its optimized algorithm to chaos-based cryptography and symmetric-key generation. The timely focus on overcoming near-term quantum hardware limitations combined with concrete cybersecurity applications gives Paper 2 a broader and more translatable scientific impact.
Paper 2 addresses a fundamental question about quantum resource scaling for simulating long-range interacting systems, which is broadly relevant to quantum simulation and many-body physics. Its introduction of logarithmic negativity as a criterion beyond energy fidelity for VQE is a methodologically significant contribution. The systematic analysis of how interaction range governs circuit depth requirements across different phases provides practical guidance for quantum simulation. Paper 1, while presenting a useful NISQ-friendly quantum walk algorithm for cryptography, addresses a more niche application area with narrower impact across the broader physics and quantum computing communities.
Paper 2 addresses a fundamental theoretical gap in photonic quantum advantage experiments—developing a systematic framework for linear cross-entropy benchmarking (LXEB) and anticoncentration in Boson Sampling variants. This has broad impact across quantum computing theory, quantum advantage verification, and representation theory. It provides foundational tools applicable to multiple experimental platforms and resolves open questions about the saturated regime. Paper 1, while practically useful for NISQ cryptography, is more incremental—optimizing circuit depth for quantum walks and applying them to key generation—with narrower scope and less theoretical depth.
Paper 2 proposes a framework to identify macroscopic quantum anomalies in neural tissue, bridging quantum physics, NMR, and neuroscience. If validated, demonstrating classically inexplicable quantum effects in the brain would cause a paradigm shift in biology and physics. Paper 1 offers a solid algorithmic improvement for NISQ devices and cryptographic applications, but its impact is more incremental and confined to quantum computing and cryptography compared to the potentially revolutionary implications of Paper 2.
Paper 1 has higher likely scientific impact: it addresses a fundamental, timely problem in quantum certification—quantifying basis-independent invariants and entanglement with randomized measurements—and establishes a rigorous minimal-setting bound plus a hierarchy of measurement difficulty, with extensions beyond two qubits. This has broad relevance across quantum information, verification, and near-term experiments. Paper 2 offers an engineering-style depth improvement for a specific quantum-walk model and a crypto key-generation application that relies on simulated noise; real-world cryptographic impact is uncertain and narrower, with less fundamental cross-field significance.
Paper 1 addresses a fundamental theoretical question about the true boundary of quantum advantage in decoded quantum interferometry, proving that existing bounds systematically underestimate quantum advantage. The Master Theorem provides a strictly tighter bound valid over arbitrary finite fields, with concrete numerical evidence of a significant hidden advantage region. This has broad implications for quantum algorithm theory and computational complexity. Paper 2 presents a practical circuit-depth improvement for quantum walks applied to cryptography, which is useful but more incremental and narrowly focused on NISQ-era implementation of a specific application.
Paper 2 combines quantum computing, quantum walks, and cryptography in a practically motivated way that addresses the timely NISQ-era constraint. Its novel LAQW algorithm with reduced circuit depth has immediate applicability to near-term quantum devices and cryptographic key generation, bridging multiple active research communities. Paper 1, while rigorous and elegant, extends an existing perturbation theory framework in a relatively incremental manner within established quantum mechanics methodology, with narrower potential impact beyond atomic/molecular physics.
Paper 2 has higher likely scientific impact: it resolves a fundamental question connecting cloning and learning sample complexities for stabilizer states with tight Θ(n) bounds, using novel representation-theoretic techniques and linking to sample amplification in classical learning theory. This is methodologically rigorous and broadly relevant across quantum foundations, quantum learning theory, and cryptography, making it timely for theory and applications in quantum information. Paper 1 is useful and NISQ-motivated, but its impact is narrower (a specific walk variant and a key-generation scheme) and more incremental relative to existing quantum-walk cryptographic proposals.
Paper 2 likely has higher impact: it tackles a timely, practical limitation (finite-precision inputs) on deployed optimization hardware (coherent Ising machines) with a generalizable algorithmic idea (block coordinate descent decomposition) and demonstrates results on real hardware with competitive benchmarks and runtime benefits. The approach can transfer to other structured QUBOs and near-term analog/quantum-inspired optimizers, broadening impact. Paper 1 offers an interesting NISQ-depth reduction for a specific quantum walk and a crypto key-generation use case, but its real-world cryptographic relevance and security rigor are less clear and narrower.
Paper 2 offers a clear, practical advancement for Noisy Intermediate-scale Quantum (NISQ) devices by significantly reducing circuit depth for quantum walk algorithms. Its direct application to chaos-based cryptography, along with empirical validation using noise simulations, provides immediate utility and broadens its impact across quantum computing and cybersecurity. In contrast, Paper 1, while rigorously exploring a novel mathematical approach to quantifying quantum magic, remains highly theoretical and specialized, lacking the near-term real-world applicability that drives higher immediate scientific and technological impact.
Paper 1 is more likely to have higher scientific impact: it introduces a novel geometric/determinantal framework tightly connected to established two-qubit gate theory (Weyl chamber, operator Schmidt), yields rigorous, broadly useful quantitative bounds (e.g., fidelity limit to local gates), and provides interpretable coordinates for nonlocal complexity—relevant across quantum information, gate synthesis, and quantum control. Paper 2 is timely and application-oriented for NISQ, but the cryptographic scheme relies on simulated noise and “quantum entropy” claims that may face rigor/security scrutiny and narrower cross-field uptake.
Paper 1 resolves a fundamental problem in quantum circuit complexity by providing the first QAC^0 construction of super-constant weight Dicke states and tight bounds for arbitrary symmetric states. This foundational theoretical breakthrough has broad, lasting implications for quantum state preparation and hardware implementation. Paper 2 offers a useful algorithmic depth reduction, but its application to chaos-based cryptography serves a much narrower, niche audience.
Paper 1 offers a highly timely and practical contribution by introducing a NISQ-friendly algorithm that significantly reduces circuit depth. Its direct application to chaos-based cryptography provides clear, near-term real-world utility. While Paper 2 presents a strong theoretical advancement in fundamental quantum physics, Paper 1 bridges quantum algorithm design with immediate cybersecurity applications, promising broader and more immediate scientific and technological impact.