Parameterized quantum algorithms for closest string problems

• URL: http://arxiv.org/abs/2510.15529v1
• Date: Fri, 17 Oct 2025 11:01:15 GMT
• Title: Parameterized quantum algorithms for closest string problems
• Authors: Josh Cudby, Sergii Strelchuk,
• Abstract summary: We present three quantum algorithms for the Closest String Problem (CSP) and the related Closest Substring Problem (CSSP)<n>Each algorithm demonstrates improved performance over classical counterparts in specific settings.<n>We also derive a conditional lower bound for the CSP with binary alphabets, showing that our first algorithm is tight in its dominant scaling factor.
• Score: 0.42970700836450487
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Parameterized complexity enables the practical solution of generally intractable NP-hard problems when certain parameters are small, making it particularly useful in real-world applications. The study of string problems in this framework has been particularly fruitful, yielding many state-of-the-art classical algorithms that run efficiently in certain parameter regimes contrary to their worst- or average-case performance. Motivated by the dramatic increase in genomic data and its growing computational demands, we initiate the study of the quantum parameterized complexity of the Closest String Problem (CSP) and the related Closest Substring Problem (CSSP). We present three quantum algorithms for the CSP and one for the CSSP. Each algorithm demonstrates improved performance over classical counterparts in specific parameter regimes, highlighting the promise of quantum approaches in structured combinatorial settings. We also derive a conditional lower bound for the CSP with binary alphabets, showing that our first algorithm is tight in its dominant scaling factor.

Related papers

• Quantum Algorithms for Network Signal Coordination [0.7734726150561088]
  The Network Signal Coordination (NSC) problem is one such problem known to be complete.<n>We implement Grover's search to solve the NSC problem to provide speedup.<n>We demonstrate its implementation through simulation and on an actual quantum computer.
  arXiv  Detail & Related papers  (2026-03-05T03:14:52Z)
• Quantum optimisation applied to the Quadratic Assignment Problem [4.483208369550461]
  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)<n>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.<n>Our findings highlight the practical utility of quantum walks for complex quantum problems and establish a foundation for future quantum optimisation algorithms.
  arXiv  Detail & Related papers  (2026-01-03T07:50:03Z)
• A quantum speedup algorithm for TSP based on quantum dynamic programming with very few qubits [0.0]
  We propose a quantum algorithm to generate the uniform superposition state of all N-length Hamiltonian cycles as an initial state within gate complexity.<n>Compared to some algorithms that theoretically have lower query complexities but lack practical implementation solutions, our algorithm has feasible circuit implementation.
  arXiv  Detail & Related papers  (2025-02-12T23:58:25Z)
• Quantum evolutionary algorithm for TSP combinatorial optimisation problem [0.0]
  This paper implements a new way of solving a problem called the traveling salesman problem (TSP) using quantum genetic algorithm (QGA) We compared how well this new approach works to the traditional method known as a classical genetic algorithm (CGA)
  arXiv  Detail & Related papers  (2024-09-20T08:27:42Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• Out of the Loop: Structural Approximation of Optimisation Landscapes and non-Iterative Quantum Optimisation [1.4691887238367354]
  We introduce means of efficiently approximating the QAOA optimisation landscape from solution space structures.<n>We derive a new algorithmic of unit-depth QAOA for two-level Hamiltonians.<n>Our approach is based on proving a long-standing conjecture regarding quantum-independent structures in QAOA.
  arXiv  Detail & Related papers  (2024-08-12T21:02:58Z)
• Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
  We propose a quantum computing-based algorithm to solve the single image super-resolution (SISR) problem. The proposed AQC-based algorithm is demonstrated to achieve improved speed-up over a classical analog while maintaining comparable SISR accuracy.
  arXiv  Detail & Related papers  (2023-04-18T11:57:15Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• Polynomial unconstrained binary optimisation inspired by optical simulation [52.11703556419582]
  We propose an algorithm inspired by optical coherent Ising machines to solve the problem of unconstrained binary optimization. We benchmark the proposed algorithm against existing PUBO algorithms, and observe its superior performance. The application of our algorithm to protein folding and quantum chemistry problems sheds light on the shortcomings of approxing the electronic structure problem by a PUBO problem.
  arXiv  Detail & Related papers  (2021-06-24T16:39:31Z)
• Adaptive pruning-based optimization of parameterized quantum circuits [62.997667081978825]
  Variisy hybrid quantum-classical algorithms are powerful tools to maximize the use of Noisy Intermediate Scale Quantum devices. We propose a strategy for such ansatze used in variational quantum algorithms, which we call "Efficient Circuit Training" (PECT) Instead of optimizing all of the ansatz parameters at once, PECT launches a sequence of variational algorithms.
  arXiv  Detail & Related papers  (2020-10-01T18:14:11Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  We show that it is possible to greatly reduce the number of qubits needed for the Traveling Salesman Problem. We also propose encoding schemes which smoothly interpolate between the qubit-efficient and the circuit depth-efficient models.
  arXiv  Detail & Related papers  (2020-09-15T18:17:27Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.