Quantum Approximate Walk Algorithm
Ziqing Guo, Jan Balewski, Wenshuo Hu, Alex Khan, Ziwen Pan · 2025
Read Quantum Approximate Walk Algorithm by Ziqing Guo, Jan Balewski, Wenshuo Hu, Alex Khan, Ziwen Pan (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-07676.txt.
Introduction
Ziqing Guo, Jan Balewski, and Wenshuo Hu present a quantum algorithm for learning patterns hidden in classical data. Trigonometric encodings map data into quantum circuits, but variational training by blind gradient search offers no guarantees about what the measured outputs mean. Existing methods stall on that gap.
Their quantum oracle stays traceable to the classical data, with circuit depth growing only linearly in qubit count. Approximate result patterns become learnable with structure intact. The Quantum Approximate Walk Algorithm aims to keep the link between data and quantum outcome auditable. Such traceability matters if quantum learning is to be trusted on real datasets rather than demos.
Catalog record
| CREATOR | Ziqing Guo, Jan Balewski, Wenshuo Hu, Alex Khan, Ziwen Pan |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 61 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-07676
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Quantum Approximate Walk Algorithm Ziqing Guo, Jan Balewski, Wenshuo Hu, Alex Khan, Ziwen Pan Abstract The encoding of classical to quantum data mapping through trigonometric functions within arithmetic-based quantum computation algorithms leads to the exploitation of multivariate distributions. The studied variational quantum gate learning mechanism, which relies on agnostic gradient optimization, does not offer algorithmic guarantees for the correlation of results beyond the measured bitstring outputs. Consequently, existing methodologies are inapplicable to this problem. In this study, we present a classical data-traceable quantum oracle characterized by a circuit depth that increases linearly with the number of qubits. This configuration facilitates the learning of approximate result patterns through a shallow quantum circuit (SQC) layout. Moreover, our approach demonstrates that the classical preprocessing of mid-quantum measurement data enhances the interpretability of quantum approximate optimization algorithm (QAOA) outputs without requiring full quantum state tomography. By establishing an inferable mapping between the classical input and quantum circuit outcomes, we obtained experimental results on the state-of-the-art IBM Pittsburgh hardware, which yielded polynomial-time verification of the solution quality. This hybrid framework bridges the gap between near-term quantum capabilities and practical optimization requirements, offering a pathway toward reliable quantum-classical algorithms for industrial applications. I Introduction The quantum information theory underlies contemporary noisy intermediate-scale quantum (NISQ) computation and its inherent parallelism 43 . Key practical algorithms include the Quantum Approximate Optimization Algorithm (QAOA) for combinatorial optimization 17 , Harrow–Hassidim–Lloyd (HHL) algorithm for linear systems 21 , Shor’s factoring algorithm 50 , and Grover’s unstructured search procedure 18 . Their power is derived from exploring exponentially large solution spaces in time, independent of the problem size, while requiring only polynomially many qubits 51 . Quantum approximation is particularly relevant to large-scale tasks such as portfolio optimization 33 ; within a high-dimensional parameter landscape it attains near-optimal results with a finite set of bounded parameterized quantum gates of limited circuit depth, thereby necessitating a specific number of qubits 34 . This approximation algorithm falls within the domain of quantum circuit learning (QCL). From a practical standpoint, emerging learning models such as variational quantum algorithms (VQAs) 35 , quantum walks (QWs) 11 ; 46 , and quantum Boltzmann machines (QBMs) 3 address general optimization tasks 16 ; 13 ; 44 ; 24 by minimizing the cost objective using gradients obtained from quantum measurements. Current QCL frameworks approximate high-dimensional functions by encoding classical data into quantum kernels 4 ; however, their efficacy diminishes as the complexity of the unitary operations and sampling iterations increases. In particular, performance depends on internal correlations and sampling biases extracted from the measured outputs and circuit configurations, which can mask the true optimum. Nevertheless, quantum circuit solvers can be confined to the SQC regime 7 , which remains challenging to simulate classically, but can be solved on two-dimensional grid quantum computers 8 . Although qubit resources are restricted to discrete quantum computation, pioneering studies 5 ; 6 ; 2 have demonstrated that classical-to-quantum encodings exploit quantum parallelism attainable on near-term, error-prone quantum processing units (QPUs) 48 ; 31 ; 29 . Figure 1: Quantum Approximate Walk Algorithm ( QAWA ) architecture: mid-circuit measurements applied to the QAOA ansatz yields outcomes that feed an \mathrm{R}_{y} encoding layer with sign negation; the unitary block C(\theta) generates a walkable state that, via one ancilla qubit, controls the weighted-summation learning layer conditioned on the measurement results. The top register \ket{\psi_{a}} functions as an activation multiplier that globally modulates the learning procedure, and the training loop employs a classical optimizer. To improve approximation accuracy, several methodological advances have been explored, including heuristic parameter initialization for the QAOA ansatz 45 ; 37 ; 23 ; 20 , fixed-ramp scaling of variational parameters 36 , generative quantum adversarial networks (QGANs) 55 ; 40 ; 56 , gradient–measurement trade-off strategies 12 , and deterministic quantum walks 42 . These techniques yield favorable scaling and implicitly leverage the approximated QCL structure shaped by underlying physical and classical data; however, definitive links between measured outcomes and their sampling distributions remain elusive. For concreteness, 49 demonstrates that problem energy spectra modulate bitstring probabilities; similarly, 25 connects graph symmetry and density to algorithmic success rates. What can be demonstrated to derive the outcome correlation structure from a quantum approximation algorithm? Alternatively, how can the approximation be evaluated? Most importantly, why do approximation algorithms yield specific correlation patterns? Although the success ratio directly reflects the algorithm performance, a more detailed examination of each bitstring dependence is warranted. A native quantum arithmetic protocol (Ehands) 4 incorporates block data encoding 9 for multiplication, weighted summation, sign negation, and parity flip, which are independent of the fully entangled VQA learning ansatz 10 . This particular design enables the estimation of observables based on real classical input; thus, by integrating the results derived from the quantum approximation ansatz, tunable classical-to-quantum encoded data can manifest a result correlation. Consequently, building upon our previous work 19 on the vectorized quantum learning scheme, we introduce a novel quantum approximate walk algorithm ( QAWA ) that provides an asymptotic solution to substantiate the quantum approximation results, even when the quantum circuit is composed and transpiled on QPUs with limited capabilities. By eliminating the conventional quantum state transition scheme (known as state hopping or walking), our approach effectively captures each probabilistically distributed outcome derived from classical definitive data by circumventing the approximation results that depend on discrete-time state evolution. Consequently, we inquire whether a quantum oracle exists that can authenticate the evolution of state vectors. This study revealed that the answer is YES. Initially, we formulated a quadratic unconstrained binary optimization (QUBO) portfolio optimization problem to quantum approximate ansatz associated with mid-circuit measurements, as shown in Fig. 1 . The quantum walk inspired weighted summation learning layer exhibits a linear correlation between the circuit depth and the increase in the number of qubits. The primary contribution of the quantum oracle can be summarized as follows: Theorem 1 . Given a set of bitstrings output \mathcal{S}=\{\mathbf{x}^{(1)},\ldots,\mathbf{x}^{(N)}\} obtained from the sampling of the approximation algorithm with mid-circuit measurement, the correlation structure satisfies \mathbb{E}[Y|\mathcal{S}]=\lim_{N\to\infty}\frac{1}{N}\sum_{j=1}^{N}a\left(\sum_{i=1}^{n}w_{i}x_{i}^{(j)}\right), (1) where w is the weight, x is the encoded classical input, a is the activation encoding: \mathbb{R}\to\mathbb{R} , and Y represents the correlation observable for the approximate optimization output. U_{selu} U_{\text{sum}} \ket{\psi_{selu}} \ket{\phi} R_{z}^{{\nicefrac{{\pi}}{{2}}}} R_{z}^{{\nicefrac{{\pi}}{{2}}}} X X R_{z}(\frac{\pi}{2}) R_{z}(\frac{\pi}{2}) R_{y}^{{\nicefrac{{\alpha}}{{2}}}} R_{y}^{{\nicefrac{{\alpha}}{{2}}}} X X R_{y}^{{\nicefrac{{\alpha}}{{2}}}} R_{y}^{{\nicefrac{{\alpha}}{{2}}}} U_{\text{sum}} U_{\text{sum}} R_{z}(\frac{\pi}{2}) R_{z}(\frac{\pi}{2}) A \psi_{c} Circuit 1:: The architecture of quantum circuit for activation encoding and walkable weighted sum learning. The remainder of this paper is organized as follows. Section II delineates the problem formulation and introduces the proposed algorithm. To the best of our knowledge, 27 was the first to establish unitary learning in the SQC domain. Inspired by this work, we present a scaling protocol that restricts the oracle to an SQC setting for future fault-tolerant quantum computers (FTQC). Section III details the experimental implementation of the algorithm on QPUs, while Section X describes the principal methodologies that substantiate our claims. A comprehensive state-vector analysis of the main algorithm is provided in Appendix A , and Appendix B provides a polynomial-time verification of the solution in comparison with conventional quantum state tomography. Additional experiments supporting the primary results are presented in Appendix C and Appendix D . II Overview