arXiv:2610.33532
Designing Quantum Solutions to the Closest String Problem with the Non-Variational QWOA
Benjamin Rossdeutscher, Jingbo Wang
Abstract
Quantum computing offers promising approaches to combinatorial optimization problems whose search spaces grow exponentially with problem size. The Closest String problem belongs to this category, which seeks a string that minimizes the maximum Hamming distance to any string in a given collection of reference strings. In this work, we present an end-to-end quantum implementation of the Closest String problem using the Non-Variational Quantum Walk Optimization Algorithm (NV-QWOA), evaluating its resource requirements and solution amplification capabilities. Our automated workflow converts arbitrary problem instances into quantum circuits expressed in one- or two-qubit gates that encode candidate solutions, evaluate the objective function, and apply NV-QWOA optimisation to increase the measurement probabilities of high-quality solutions. Analytical resource estimates yield a qubit complexity of $\mathcal{O}(nm\log k)$ and a circuit depth of $\mathcal{O}(pm\log^2 n + pn\log n)$, where $n$ is the string length, $m$ is the number of reference strings, $k$ is the alphabet size, and $p$ is the number of NV-QWOA iterations. We introduce a revised prescription for the phase-separation parameter, $γ$, that depends on problem size but requires no instance-specific optimization. This prescription mitigates excessive phase wrapping modulo $2π$, which can weaken the relationship between objective values and the phases guiding the optimization dynamics. Across all simulated problem sizes, the algorithm consistently amplifies optimal and near-optimal candidates. This work provides an explicit gate-level implementation, an improved phase-scaling method, and a foundation for hardware experiments and benchmarking against classical algorithms.
AI Summary
The paper studies a gate-based implementation of the Closest String problem: given $m$ reference strings of length $n$ over an alphabet of size $k$, find a string minimizing its maximum Hamming distance to the references. It applies the non-variational quantum walk optimization algorithm (NV-QWOA), alternating cost-dependent phase separation with continuous-time quantum walks on the Hamming graph of candidate strings. The circuit combines reversible character comparisons, Fourier-based Hamming-distance addition, a comparator-based maximum calculation, phase application, and uncomputation. Analytical resource counts give $\mathcal{O}(nm\log k)$ qubits and, for fixed alphabet size, depth $\mathcal{O}(pm\log^2 n+pn\log n)$ for $p$ iterations. A revised deterministic phase parameter, $\gamma=\pi/[2(n+1)]$, replaces standard-deviation-based scaling to bound the cost-dependent phase range and avoid phase wrapping, without instance-specific optimization of $\gamma$. Evidence for solution amplification comes from ideal Qiskit state-vector simulations of 30 generated instances per size, using binary alphabets, two reference strings, and lengths $n=3,4,5,6$. With 1,024 measurement shots per circuit, 30 iterations produce approximately $80$–$90\%$ total probability of sampling an optimal string. The reported experiments therefore cover small instances rather than the full parameter range of the construction. The paper states that establishing end-to-end quantum advantage requires determining how iteration counts and measurement repetitions scale, including preprocessing and hyperparameter-tuning overheads, and benchmarking against state-of-the-art classical solvers at matched solution quality and success probability. Extension to Closest Substring is proposed but not implemented.
Central claim may not hold: The abstract's alphabet-independent circuit-depth bound is not established for one- and two-qubit gates because the derivation counts multi-controlled gates as primitive layers, while its final qualified bound assumes fixed alphabet size. For non-power-of-two alphabet sizes, the specified Hadamard initialization populates invalid symbol encodings, with no supplied valid-subspace preparation or explanation of compatible mixer behavior. The amplification evidence concerns only tiny binary instances with two references, a class solvable exactly by splitting differing positions to attain optimal maximum distance ceil(d_H(s1,s2)/2). The reported simulation qubit counts conflict with the final resource formula at n=4 and do not explain the conclusion's claim of simulations up to 28 qubits. The phase prescription prevents wrapping, but its claimed maximal phase separation and its stated degeneracy-based reason for choosing n+1 rather than n are mathematically incorrect.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 19 pages, 7 figures