Designing Quantum Solutions to the Closest String Problem with the Non-Variational QWOA
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 𝒪(nmlog k) and a circuit depth of 𝒪(pmlog2 n + pnlog 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.
Related
- Fractional and quantum Latin squares: real solutions of quantum 36 officers problem
- Quantum Variational Approaches to the Maximum Independent Set Problem at Utility Scale
- Non-variational scalar field cosmology: Exact Bianchi I solutions for near-minimal scalar fields
- Exact solutions of the nuclear shell-model secular problem: Discrete Non-Orthogonal Shell Model within a Variation After Projection approach
- Inverse Feshbach's problem: Solvability and solutions
BibTeX
@misc{rossdeutscher2026designing,
title = {{Designing Quantum Solutions to the Closest String Problem with the Non-Variational QWOA}},
author = {Benjamin Rossdeutscher and Jingbo Wang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.33532},
eprint = {2610.33532},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.33532},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Designing Quantum Solutions to the Closest String Problem with the Non-Variational QWOA
AU - Benjamin Rossdeutscher
AU - Jingbo Wang
PY - 2026
DA - 2026/10/24
PB - arXiv
DO - 10.48550/arxiv.2610.33532
UR - https://arxiv.org/abs/2610.33532
AB - 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 𝒪(nmlog k) and a circuit depth of 𝒪(pmlog^2 n + pnlog 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.
ER -