Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2610.33532

Designing Quantum Solutions to the Closest String Problem with the Non-Variational QWOA

Benjamin Rossdeutscher, Jingbo Wang

On Aqora:Jingbo WangJingbo Wang
quant-phSubmitted Oct 24, 2026• Announced Oct 27, 2026• 0 citations
arXivHTMLPDF

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.

Little sign of AI-generated textIncrementalSmall numerics onlyMissing comparisonPossible error

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

Related papers

Non-Variational Quantum Combinatorial Optimisation

Tavis Bennett, Lyle Noakes, Jingbo B. Wang

This paper introduces a non-variational quantum algorithm designed to solve a wide range of combinatorial optimisation problems, including constrained and non-binary problems. The algorithm leverages an engineered interference process achieved through repeated application of two unitaries; one inducing phase-shifts dependent on objective function values, and the other mixing phase-shifted probability amplitudes via a continuous-time quantum walk (CTQW) on a problem-specific graph. The algorithm's versatility is demonstrated through its application to various problems, namely those for which solutions are characterised by either a vector of binary variables, a vector of non-binary integer variables, or permutations (a vector of integer variables without repetition). An efficient quantum circuit implementation of the CTQW for each of these problem types is also discussed. A penalty function approach for constrained problems is also introduced, including a method for optimising the penalty function. The algorithm's performance is demonstrated through numerical simulation for randomly generated instances of the following problems (and problem sizes): weighted maxcut (18 vertices), maximum independent set (18 vertices), k-means clustering (12 datapoints, 3 clusters), capacitated facility location (12 customers, 3 facility locations), and the quadratic assignment problem (9 locations). For each problem instance, the algorithm finds a globally optimal solution with a small number of iterations.

arXiv:2404.03167•IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 15, 2024•10 citations

Analysis of the Non-variational Quantum Walk-based Optimisation Algorithm

Tavis Bennett, Lyle Noakes, Jingbo B. Wang

This paper introduces in detail a non-variational quantum algorithm designed to solve a wide range of combinatorial optimisation problems, including constrained problems and problems with non-binary variables. The algorithm returns optimal and near-optimal solutions from repeated preparation and measurement of an amplified state. The amplified state is prepared via repeated application of two unitaries; one which phase-shifts solution states dependent on objective function values, and the other which mixes phase-shifted probability amplitudes via a continuous-time quantum walk (CTQW) on a problem-specific mixing graph. The general interference process responsible for amplifying optimal solutions is derived in part from statistical analysis of objective function values as distributed over the mixing graph. The algorithm's versatility is demonstrated through its application to various problems: weighted maxcut, k-means clustering, quadratic assignment, maximum independent set and capacitated facility location. In all cases, efficient circuit implementations of the CTQWs are discussed. A penalty function approach for constrained problems is also introduced, including a method for optimising the penalty function. For each of the considered problems, the algorithm's performance is simulated for a randomly generated problem instance, and in each case, the amplified state produces a globally optimal solution within a small number of iterations.

arXiv:2408.06368•Jul 29, 2024•4 citations

Quantum optimisation applied to the Quadratic Assignment Problem

Andrew Freeland, Jingbo Wang

This paper investigates the performance of the emerging non-variational Quantum Walk-based Optimisation Algorithm (NV-QWOA) for solving small instances of the Quadratic Assignment Problem (QAP). NV-QWOA is benchmarked against classical heuristics, the MaxMin Ant System (MMAS) and Greedy Local Search (GLS), as well as the Grover quantum search algorithm, which serves as a quantum baseline. Performance is evaluated using two metrics: the number of objective function evaluations and the number of algorithm iterations required to consistently reach optimal or near optimal solutions across QAP instances with 5 to 10 facilities. The motivation for this study stems from limitations of both classical exact methods and current quantum algorithms. Variational Quantum Algorithms (VQAs), such as QAOA and VQE, while widely studied, suffer from costly parameter tuning and barren plateaus that hinder convergence. By adopting a non-variational approach, this work explores a potentially more efficient and scalable quantum strategy for combinatorial optimisation. The results provide a direct comparative analysis between classical and quantum frameworks, characterising the average case performance of NV-QWOA. Our findings highlight the practical utility of quantum walks for complex combinatorial problems and establish a foundation for future quantum optimisation algorithms.

quant-pharXiv:2601.01104•Jan 6, 2026•0 citations

Scaling quantum approximate optimization on near-term hardware

Phillip C. Lotshaw, Thien Nguyen, Anthony Santana +5 more

The quantum approximate optimization algorithm (QAOA) is an approach for near-term quantum computers to potentially demonstrate computational advantage in solving combinatorial optimization problems. However, the viability of the QAOA depends on how its performance and resource requirements scale with problem size and complexity for realistic hardware implementations. Here, we quantify scaling of the expected resource requirements by synthesizing optimized circuits for hardware architectures with varying levels of connectivity. Assuming noisy gate operations, we estimate the number of measurements needed to sample the output of the idealized QAOA circuit with high probability. We show the number of measurements, and hence total time to solution, grows exponentially in problem size and problem graph degree as well as depth of the QAOA ansatz, gate infidelities, and inverse hardware graph degree. These problems may be alleviated by increasing hardware connectivity or by recently proposed modifications to the QAOA that achieve higher performance with fewer circuit layers.

arXiv:2201.02247•Scientific Reports•Jul 20, 2022•46 citations

Towards large-scale quantum optimization solvers with few qubits

Marco Sciorilli, Lucas Borges, Taylor L. Patti +4 more

Quantum computers hold the promise of more efficient combinatorial optimization solvers, which could be game-changing for a broad range of applications. However, a bottleneck for materializing such advantages is that, in order to challenge classical algorithms in practice, mainstream approaches require a number of qubits prohibitively large for near-term hardware. Here we introduce a variational solver for MaxCut problems over $$m={{\mathcal{O}}}({n}^{k})$$ binary variables using only n qubits, with tunable k > 1. The number of parameters and circuit depth display mild linear and sublinear scalings in m, respectively. Moreover, we analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature. Altogether, this leads to high quantum-solver performances. For instance, for m = 7000, numerical simulations produce solutions competitive in quality with state-of-the-art classical solvers. In turn, for m = 2000, experiments with n = 17 trapped-ion qubits feature MaxCut approximation ratios estimated to be beyond the hardness threshold 0.941. Our findings offer an interesting heuristics for quantum-inspired solvers as well as a promising route towards solving commercially-relevant problems on near-term quantum devices. Combinatorial optimization problems might be solvable more efficiently with quantum computing, but near-term quantum optimization solvers are limited in qubit size. Here, the authors propose and demonstrate a variational quantum algorithm that polynomially reduces the qubit overhead for applications like MaxCut.

arXiv:2401.09421•Nature Communications•Jan 8, 2025•72 citations

Performant near-term quantum combinatorial optimization

Titus Morris, Kaushik, Ananth, Martin Roetteler +1 more

Combinatorial optimization is a promising application for near-term quantum computers, however, identifying performant algorithms suited to noisy quantum hardware remains as an important goal to potentially realizing quantum computational advantages. To address this we present a variational quantum algorithm for solving combinatorial optimization problems with linear-depth circuits. Our algorithm uses an ansatz composed of Hamiltonian generators designed to control each term in the target combinatorial function, along with parameter updates following a modified version of quantum imaginary time evolution. We evaluate this ansatz in numerical simulations that target solutions to the MAXCUT problem. The state evolution is shown to closely mimic imaginary time evolution, and its optimal-solution convergence is further improved using adaptive transformations of the classical Hamiltonian spectrum. With these innovations, the algorithm consistently converges to optimal solutions, with interesting highly-entangled dynamics along the way. We further demonstrate the success of this approach by performing optimization of a truncated version of our ansatz with up to 32 qubits in a trapped-ion quantum computer, using measurements from the quantum computer to train the ansatz and prepare optimal solutions with high fidelity in the majority of cases we consider. The success of these large-scale quantum circuit optimizations, in the presence of realistic hardware constraints and without error mitigation, mark significant progress on the path towards solving combinatorial problems using quantum computers. We conclude our performant and resource-minimal approach is a promising candidate for potential quantum computational advantages.

arXiv:2404.16135•Apr 24, 2024•21 citations
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 O(nmlog⁡k)\mathcal{O}(nm\log k)O(nmlogk) and a circuit depth of O(pmlog⁡2n+pnlog⁡n)\mathcal{O}(pm\log^2 n + pn\log n)O(pmlog2n+pnlogn), where nnn is the string length, mmm is the number of reference strings, kkk is the alphabet size, and ppp 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π2π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.
The paper studies a gate-based implementation of the Closest String problem: given mmm reference strings of length nnn over an alphabet of size kkk, 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 O(nmlog⁡k)\mathcal{O}(nm\log k)O(nmlogk) qubits and, for fixed alphabet size, depth O(pmlog⁡2n+pnlog⁡n)\mathcal{O}(pm\log^2 n+pn\log n)O(pmlog2n+pnlogn) for ppp iterations. A revised deterministic phase parameter, γ=π/[2(n+1)]\gamma=\pi/[2(n+1)]γ=π/[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,6n=3,4,5,6n=3,4,5,6. With 1,024 measurement shots per circuit, 30 iterations produce approximately 808080–90%90\%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.
This paper introduces a non-variational quantum algorithm designed to solve a wide range of combinatorial optimisation problems, including constrained and non-binary problems. The algorithm leverages an engineered interference process achieved through repeated application of two unitaries; one inducing phase-shifts dependent on objective function values, and the other mixing phase-shifted probability amplitudes via a continuous-time quantum walk (CTQW) on a problem-specific graph. The algorithm's versatility is demonstrated through its application to various problems, namely those for which solutions are characterised by either a vector of binary variables, a vector of non-binary integer variables, or permutations (a vector of integer variables without repetition). An efficient quantum circuit implementation of the CTQW for each of these problem types is also discussed. A penalty function approach for constrained problems is also introduced, including a method for optimising the penalty function. The algorithm's performance is demonstrated through numerical simulation for randomly generated instances of the following problems (and problem sizes): weighted maxcut (18 vertices), maximum independent set (18 vertices), k-means clustering (12 datapoints, 3 clusters), capacitated facility location (12 customers, 3 facility locations), and the quadratic assignment problem (9 locations). For each problem instance, the algorithm finds a globally optimal solution with a small number of iterations.
This paper introduces in detail a non-variational quantum algorithm designed to solve a wide range of combinatorial optimisation problems, including constrained problems and problems with non-binary variables. The algorithm returns optimal and near-optimal solutions from repeated preparation and measurement of an amplified state. The amplified state is prepared via repeated application of two unitaries; one which phase-shifts solution states dependent on objective function values, and the other which mixes phase-shifted probability amplitudes via a continuous-time quantum walk (CTQW) on a problem-specific mixing graph. The general interference process responsible for amplifying optimal solutions is derived in part from statistical analysis of objective function values as distributed over the mixing graph. The algorithm's versatility is demonstrated through its application to various problems: weighted maxcut, k-means clustering, quadratic assignment, maximum independent set and capacitated facility location. In all cases, efficient circuit implementations of the CTQWs are discussed. A penalty function approach for constrained problems is also introduced, including a method for optimising the penalty function. For each of the considered problems, the algorithm's performance is simulated for a randomly generated problem instance, and in each case, the amplified state produces a globally optimal solution within a small number of iterations.
This paper investigates the performance of the emerging non-variational Quantum Walk-based Optimisation Algorithm (NV-QWOA) for solving small instances of the Quadratic Assignment Problem (QAP). NV-QWOA is benchmarked against classical heuristics, the MaxMin Ant System (MMAS) and Greedy Local Search (GLS), as well as the Grover quantum search algorithm, which serves as a quantum baseline. Performance is evaluated using two metrics: the number of objective function evaluations and the number of algorithm iterations required to consistently reach optimal or near optimal solutions across QAP instances with 5 to 10 facilities. The motivation for this study stems from limitations of both classical exact methods and current quantum algorithms. Variational Quantum Algorithms (VQAs), such as QAOA and VQE, while widely studied, suffer from costly parameter tuning and barren plateaus that hinder convergence. By adopting a non-variational approach, this work explores a potentially more efficient and scalable quantum strategy for combinatorial optimisation. The results provide a direct comparative analysis between classical and quantum frameworks, characterising the average case performance of NV-QWOA. Our findings highlight the practical utility of quantum walks for complex combinatorial problems and establish a foundation for future quantum optimisation algorithms.
The quantum approximate optimization algorithm (QAOA) is an approach for near-term quantum computers to potentially demonstrate computational advantage in solving combinatorial optimization problems. However, the viability of the QAOA depends on how its performance and resource requirements scale with problem size and complexity for realistic hardware implementations. Here, we quantify scaling of the expected resource requirements by synthesizing optimized circuits for hardware architectures with varying levels of connectivity. Assuming noisy gate operations, we estimate the number of measurements needed to sample the output of the idealized QAOA circuit with high probability. We show the number of measurements, and hence total time to solution, grows exponentially in problem size and problem graph degree as well as depth of the QAOA ansatz, gate infidelities, and inverse hardware graph degree. These problems may be alleviated by increasing hardware connectivity or by recently proposed modifications to the QAOA that achieve higher performance with fewer circuit layers.
Quantum computers hold the promise of more efficient combinatorial optimization solvers, which could be game-changing for a broad range of applications. However, a bottleneck for materializing such advantages is that, in order to challenge classical algorithms in practice, mainstream approaches require a number of qubits prohibitively large for near-term hardware. Here we introduce a variational solver for MaxCut problems over m=O(nk)m={{\mathcal{O}}}({n}^{k})m=O(nk) binary variables using only n qubits, with tunable k > 1. The number of parameters and circuit depth display mild linear and sublinear scalings in m, respectively. Moreover, we analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature. Altogether, this leads to high quantum-solver performances. For instance, for m = 7000, numerical simulations produce solutions competitive in quality with state-of-the-art classical solvers. In turn, for m = 2000, experiments with n = 17 trapped-ion qubits feature MaxCut approximation ratios estimated to be beyond the hardness threshold 0.941. Our findings offer an interesting heuristics for quantum-inspired solvers as well as a promising route towards solving commercially-relevant problems on near-term quantum devices. Combinatorial optimization problems might be solvable more efficiently with quantum computing, but near-term quantum optimization solvers are limited in qubit size. Here, the authors propose and demonstrate a variational quantum algorithm that polynomially reduces the qubit overhead for applications like MaxCut.
Combinatorial optimization is a promising application for near-term quantum computers, however, identifying performant algorithms suited to noisy quantum hardware remains as an important goal to potentially realizing quantum computational advantages. To address this we present a variational quantum algorithm for solving combinatorial optimization problems with linear-depth circuits. Our algorithm uses an ansatz composed of Hamiltonian generators designed to control each term in the target combinatorial function, along with parameter updates following a modified version of quantum imaginary time evolution. We evaluate this ansatz in numerical simulations that target solutions to the MAXCUT problem. The state evolution is shown to closely mimic imaginary time evolution, and its optimal-solution convergence is further improved using adaptive transformations of the classical Hamiltonian spectrum. With these innovations, the algorithm consistently converges to optimal solutions, with interesting highly-entangled dynamics along the way. We further demonstrate the success of this approach by performing optimization of a truncated version of our ansatz with up to 32 qubits in a trapped-ion quantum computer, using measurements from the quantum computer to train the ansatz and prepare optimal solutions with high fidelity in the majority of cases we consider. The success of these large-scale quantum circuit optimizations, in the presence of realistic hardware constraints and without error mitigation, mark significant progress on the path towards solving combinatorial problems using quantum computers. We conclude our performant and resource-minimal approach is a promising candidate for potential quantum computational advantages.