⚛️ quantum physics

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

This paper presents an end-to-end, non-variational quantum implementation of the Closest String problem using the NV-QWOA algorithm, featuring a new parameter prescription that avoids instance-specific optimization while consistently amplifying optimal solutions with analytically estimated resource requirements.

Original authors: Benjamin Rossdeutscher, Jingbo Wang

Published 2026-10-27

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Benjamin Rossdeutscher, Jingbo Wang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the vast landscape of modern computing, there exists a class of puzzles so complex that even the most powerful supercomputers struggle to solve them exactly. These are combinatorial optimization problems, where the goal is to find the single best arrangement among a staggering number of possibilities. Imagine trying to find the perfect key in a room filled with billions of locks; as the number of locks grows, the time required to check every single one grows so fast that it quickly becomes impossible. One such puzzle is the "Closest String" problem. It asks a simple question: given a collection of different strings of characters, can you find a new string that is as similar as possible to all of them at once? This is not just a theoretical game. Scientists use this logic to reconstruct damaged messages in communications, identify common structures in protein molecules for drug discovery, and track mutated viruses during disease outbreaks. Because the number of possible answers explodes as the problem gets bigger, finding the true best answer is considered one of the hardest tasks in computer science.

Recently, researchers at the University of Western Australia have taken a significant step toward solving this problem using the unique power of quantum computers. Instead of checking answers one by one like a classical computer, their new method uses the strange rules of quantum mechanics to explore many possibilities at once. They applied a specific technique called the Non-Variational Quantum Walk Optimization Algorithm, or NV-QWOA, to the Closest String problem. This approach is distinct because it does not rely on a slow, trial-and-error process to tune its settings. Instead, the researchers designed a fixed set of instructions that automatically guide the quantum computer toward the best solution. By simulating this process on a classical computer, they demonstrated that their method can successfully amplify the probability of finding the correct answer, turning a nearly impossible search into a manageable one for small to medium-sized problems.

The core of their work involves building a digital blueprint, or circuit, that a quantum computer can follow. This circuit acts as a factory for processing information. First, it creates a superposition, a state where the computer holds every possible answer simultaneously. Then, it begins a rigorous evaluation process. The system compares this cloud of potential answers against the original collection of reference strings. It calculates the "distance" between each potential answer and the references, measuring how many characters would need to be changed to make them match. The goal is to find the answer that requires the fewest changes across the board. The researchers had to design a clever way to do this math within the quantum realm, using special gates to count differences and determine the maximum distance without losing the delicate quantum information.

A major hurdle in these types of quantum algorithms is deciding how to adjust the internal settings to get the best result. Many existing methods require a classical computer to constantly tweak these settings based on the results of previous runs, a process that can be slow and inefficient. The researchers in this study introduced a new, fixed rule for one of these critical settings. They discovered that by setting this value based simply on the size of the problem, they could avoid the need for any trial-and-error tuning. This change prevented a common error where the quantum phases, which guide the search, would wrap around and cancel each other out. By keeping these phases distinct and properly scaled, the algorithm could more effectively push the probability of finding the correct answer higher.

To test their idea, the team ran simulations on a classical computer that mimicked the behavior of a quantum machine. They created dozens of different problem scenarios, ranging from simple strings of three characters to more complex ones with six characters. In every case, they started with a state where all possible answers were equally likely. As the algorithm ran through its steps, it began to favor the best solutions. After thirty rounds of processing, the simulations showed that the probability of measuring the perfect answer jumped to over eighty percent. In many instances, the chance of finding the best answer was even higher, reaching ninety percent. The system consistently pushed the correct solutions to the top while suppressing the incorrect ones, proving that the method works as intended for the sizes they tested.

The researchers also carefully counted the resources their method would require if run on real quantum hardware. They found that the number of quantum bits, or qubits, needed grows in a manageable way as the problem gets larger. Specifically, the number of qubits scales linearly with the number of reference strings and the length of the strings, but only logarithmically with the size of the character set used. This means that even as the problem becomes more complex, the hardware requirements do not explode uncontrollably. The depth of the circuit, which represents the time it takes to run the calculation, also follows a predictable pattern. These findings provide a clear map for future experiments, showing exactly what kind of machine would be needed to tackle these problems in the real world.

While the current results are based on simulations, the implications for the future are clear. The study confirms that the Closest String problem, which is notoriously difficult for classical computers, can be approached effectively with quantum methods. The team's work provides a complete, step-by-step guide for how to build the necessary quantum circuits and how to set their parameters without needing constant human intervention. Although the simulations were limited to small problem sizes, the success of the algorithm in these tests suggests it could scale up to handle the complex data sets found in genetics and communications. The researchers note that their method could potentially be extended to solve related problems, such as finding common substrings within longer sequences, opening the door for broader applications in science and technology.

This research represents a concrete move from theory to practice in the field of quantum optimization. By demonstrating a working circuit design and a reliable method for setting its parameters, the authors have provided a foundation for future hardware experiments. Their work shows that with the right approach, quantum computers can navigate the vast search spaces of combinatorial problems, concentrating their power on the most promising answers. As quantum hardware continues to improve, the techniques developed in this study will likely serve as a blueprint for solving some of the most challenging optimization puzzles that currently limit our ability to analyze complex biological and digital systems.

Technical Summary: Quantum Solutions to the Closest String Problem with Non-Variational QWOA

1. Problem Definition

The Closest String Problem (CSP) is a combinatorial optimization problem classified as NP-Hard. Given a set of $m$ reference strings, each of length $n$ over an alphabet of size $k$ , the objective is to find a solution string $s$ of length $n$ that minimizes the maximum Hamming distance to any string in the reference set. The cost function is defined as:
$f(s) = \max_{i=1,2,...,m} d_H(s, s_i)$
where $d_H$ is the Hamming distance.

Classically, solving this problem exactly is computationally prohibitive for large $n$ . An exhaustive search scales as $O(k^n)$ , and calculating the cost matrix for a single candidate requires $O(mn)$ comparisons, leading to a total classical complexity of $O(k^n mn)$ . While parameterized classical algorithms exist, they still exhibit exponential scaling with respect to the maximum Hamming distance $d$ . The CSP has significant applications in bioinformatics (e.g., identifying common structures in protein molecules or mutated viral strains), communications (reconstructing signals from damaged copies), and code correction.

2. Methodology: Non-Variational QWOA (NV-QWOA)

The authors propose an end-to-end quantum implementation of the CSP using the Non-Variational Quantum Walk Optimization Algorithm (NV-QWOA). Unlike Variational Quantum Algorithms (VQAs) like QAOA, which rely on classical optimization loops to tune parameters, NV-QWOA utilizes a fixed set of hyperparameters determined by problem structure, avoiding the barren plateau issues and classical overhead associated with variational methods.

Algorithmic Steps

The algorithm operates on a quantum circuit through $p$ iterations, each consisting of three main components:

Cost Evaluation (Phase Separation):
- The algorithm calculates the Hamming distance between a superposition of candidate solution strings and all $m$ reference strings.
- It determines the maximum Hamming distance for each candidate (the cost) using a deterministic quantum circuit architecture involving Quantum Fourier Addition (QFA) and a quantum state comparator.
- A phase shift proportional to the cost is applied to the solution register. The authors introduce a revised prescription for the phase-separation parameter $\gamma$ , defined deterministically as $\gamma = \frac{\pi}{2(n+1)}$ . This avoids the need for instance-specific optimization and mitigates phase wrapping modulo $2\pi$ that can weaken the correlation between cost and phase.
Mixing (Quantum Walk):
- A Continuous Time Quantum Walk (CTQW) is performed over a mixing graph. For the CSP, this graph is a Hamming graph, where nodes represent solution strings and edges connect strings differing by a Hamming distance of 1.
- This mixing unitary redistributes amplitude between neighboring states, amplifying those with favorable (low) phases.
Iteration:
- Steps 1 and 2 are repeated $p$ times. The algorithm amplifies the probability of measuring optimal or near-optimal solutions while suppressing non-optimal states.

Circuit Implementation Details

Gate-Level Encoding: The implementation uses Qiskit to translate the problem into one- and two-qubit gates.
Registers: The circuit utilizes seven quantum registers: a solution register, a reference register, a character register (for $k>2$ ), a QFT register, a winner register, a winner slot register, and a phase target register.
Uncomputation: Ancilla registers used for cost calculation are uncomputed (disentangled) via Hermitian conjugate operations to prevent interference with the mixing step.
Optimization: The authors optimized the Hamming distance calculation by integrating an efficient OR-gate implementation with QFA, reducing the need for additional ancilla qubits.

3. Key Contributions

Explicit Gate-Level Implementation: The paper provides a complete, automated workflow to convert arbitrary CSP instances into quantum circuits, including the encoding of reference strings, cost evaluation, and the NV-QWOA ansatz.
Deterministic Phase Scaling: A new, problem-size-dependent prescription for the parameter $\gamma$ is introduced. This removes the need for heuristic estimation or classical optimization of $\gamma$ , ensuring the algorithm remains truly non-variational.
Resource Complexity Analysis:
- Qubit Complexity: $O(nm \log k)$ .
- Circuit Depth: $O(pm \log^2 n + pn \log n)$ for fixed alphabet sizes.
- These estimates represent a favorable scaling trajectory compared to the exponential classical search space.
Efficient Max-Function Circuit: The authors designed specific circuit architectures (using CCNOT and CSwap gates) to deterministically find the maximum Hamming distance across the reference set, a non-trivial task in quantum circuits due to the non-quadratic nature of the max function.

4. Results

The authors validated the approach using classical state-vector simulations via Qiskit-Aer.

Simulation Parameters: Experiments were conducted for string lengths $n \in \{3, 4, 5, 6\}$ , with $m=2$ reference strings and a binary alphabet ( $k=2$ ). This corresponds to circuits ranging from 15 to 26 qubits.
Performance:
- After $p=30$ iterations, the algorithm consistently amplified the optimal solution set (subshell 0).
- The probability of measuring an optimal solution reached 80–90% across all tested instances.
- Subshell 1 (near-optimal solutions) retained 10–20% probability, while all other subshells converged to near-zero probability.
- The deterministic $\gamma$ prescription proved effective without requiring cost-standard-deviation scaling, which was found to be slightly detrimental at smaller scales.
Observation: The results demonstrate that NV-QWOA can effectively concentrate measurement probability on high-quality candidates starting from a uniform superposition, even without classical parameter tuning.

5. Significance and Claims

The paper claims to provide a foundational framework for solving the Closest String Problem on quantum hardware. Its significance lies in:

Demonstrating Applicability: It verifies that NV-QWOA, previously tested on problems like MaxCut and k-means, is applicable to the NP-Hard CSP.
Hardware Readiness: By providing an explicit gate-level implementation and resource estimates, the work lays the groundwork for future experiments on fault-tolerant quantum computers.
Benchmarking Potential: The authors position this work as a basis for benchmarking quantum algorithms against classical solvers. They explicitly state that establishing a full "end-to-end quantum speedup" requires further analysis of iteration scaling ( $p$ ), measurement repetitions, and classical overheads, which are not fully resolved in this study.
Future Extensions: The authors note that the framework could potentially be extended to the Closest Substring Problem (where the solution is a substring of length $n$ within longer reference strings of length $L$ ), though this was not investigated in the current work.

The paper maintains a modest tone, acknowledging that while the algorithm shows strong amplification in simulation, the transition to practical quantum advantage requires further investigation into scaling laws and hardware constraints.