Qudit-based scalable quantum algorithm for solving the integer programming problem

• URL: http://arxiv.org/abs/2508.13906v1
• Date: Tue, 19 Aug 2025 15:06:49 GMT
• Title: Qudit-based scalable quantum algorithm for solving the integer programming problem
• Authors: Kapil Goswami, Peter Schmelcher, Rick Mukherjee,
• Abstract summary: programming (IP) is an NP-hard optimization problem that is widely used to represent a diverse set of real-world problems.<n>Most quantum algorithms for solving IP are highly resource inefficient because they encode integers into qubits.<n>In this work, a circuit-based scalable quantum algorithm is presented using multiple interacting qudits for which we show a quantum speed-up.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Integer programming (IP) is an NP-hard combinatorial optimization problem that is widely used to represent a diverse set of real-world problems spanning multiple fields, such as finance, engineering, logistics, and operations research. It is a hard problem to solve using classical algorithms, as its complexity increases exponentially with problem size. Most quantum algorithms for solving IP are highly resource inefficient because they encode integers into qubits. In [1], the issue of resource inefficiency was addressed by mapping integer variables to qudits. However, [1] has limited practical value due to a lack of scalability to multiple qudits to encode larger problems. In this work, by extending upon the ideas of [1], a circuit-based scalable quantum algorithm is presented using multiple interacting qudits for which we show a quantum speed-up. The quantum algorithm consists of a distillation function that efficiently separates the feasible from the infeasible regions, a phase-amplitude encoding for the cost function, and a quantum phase estimation coupled with a multi-controlled single-qubit rotation for optimization. We prove that the optimal solution has the maximum probability of being measured in our algorithm. The time complexity for the quantum algorithm is shown to be $O(d^{n/2} + m\cdot n^2\cdot \log{d} + n/\epsilon_{QPE})$ for a problem with the number of variables $n$ taking $d$ integer values, satisfying $m$ constraints with a precision of $\epsilon_{QPE}$. Compared to the classical time complexity of brute force $O(d^n)$ and the best classical exact algorithm $O((\log{n})^{3n})$, it incurs a reduction of $d^{n/2}$ in the time complexity in terms of $n$ for solving a general polynomial IP problem.

Related papers

• Pseudo-deterministic Quantum Algorithms [7.46931129146594]
  We show that for any total problem $R$, pseudo-deterministic quantum algorithms admit at most a quintic advantage over deterministic algorithms.<n>On the algorithmic side, we identify a class of quantum search problems that can be made pseudo-deterministic with small overhead.
  arXiv  Detail & Related papers  (2026-02-19T18:54:47Z)
• Limitation of Quantum Walk Approach to the Maximum Matching Problem [0.0]
  The Maximum Matching problem has a quantum query complexity lower bound of $Omega(n3/2)$ for graphs on $n$ vertices represented by an adjacency matrix.<n>The current best quantum algorithm has the query complexity $O(n7/4)$, which is an improvement over the trivial bound $O(n2)$.<n>We show that the quantum walk technique fails to produce a fast algorithm improving the known (or even the trivial) upper bound on the query complexity.
  arXiv  Detail & Related papers  (2025-10-30T08:29:44Z)
• Quantum and classical algorithms for SOCP based on the multiplicative weights update method [44.99833362998488]
  We give classical and quantum algorithms for approximately solving second-order cone programs (SOCPs)<n>Our approach follows the MW framework previously applied to semidefinite programs (SDPs)<n>We show that the additional structure of SOCPs can be exploited to give better runtime with SOCP-specific algorithms.
  arXiv  Detail & Related papers  (2025-07-18T17:55:58Z)
• Quantum Algorithm for the Fixed-Radius Neighbor Search [39.58317527488534]
  We propose a quantum algorithm for the Fixed RAdius Neighbor Search problem (FRANS) based on the fixed-point version of Grover's algorithm.<n>We derive an efficient circuit for solving the FRANS with linear query complexity with the number of particles $N$.<n>We assess the resilience of the model to the readout error, suggesting an error correction-free strategy to check the accuracy of the results.
  arXiv  Detail & Related papers  (2025-07-04T10:01:10Z)
• 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)
• Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
  We study the problem of estimating frequency response functions of systems of coupled, classical harmonic oscillators using a quantum computer.<n>Our proposed quantum algorithm operates in the standard $s-sparse, oracle-based query access model.<n>We show that a simple adaptation of our algorithm solves the random glued-trees problem in time.
  arXiv  Detail & Related papers  (2024-05-14T15:28:37Z)
• Quantum algorithms for Hopcroft's problem [45.45456673484445]
  We study quantum algorithms for Hopcroft's problem which is a fundamental problem in computational geometry. The classical complexity of this problem is well-studied, with the best known algorithm running in $O(n4/3)$ time. Our results are two different quantum algorithms with time complexity $widetilde O(n5/6)$.
  arXiv  Detail & Related papers  (2024-05-02T10:29:06Z)
• Integer Programming Using A Single Atom [0.0]
  We develop an algorithm that maps and solves an IP problem in its original form to any quantum system. The optimal solution is found within a few microseconds for IP problems with up to eight variables and four constraints.
  arXiv  Detail & Related papers  (2024-02-26T12:59:20Z)
• Randomized adiabatic quantum linear solver algorithm with optimal complexity scaling and detailed running costs [0.0]
  We develop a quantum linear solver algorithm based on adiabatic quantum computing.<n>The algorithm is improved to the optimal scaling $O(kappa/log$)$ - an exponential improvement in $epsilon$.<n>We introduce a cheaper randomized walk operator method replacing Hamiltonian simulation.
  arXiv  Detail & Related papers  (2023-05-19T00:07:32Z)
• 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)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits. Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit. We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
  arXiv  Detail & Related papers  (2022-06-30T03:15:23Z)
• Pauli String Partitioning Algorithm with the Ising Model for Simultaneous Measurement [0.0]
  We propose an efficient algorithm for partitioning Pauli strings into subgroups, which can be simultaneously measured in a single quantum circuit. Our partitioning algorithm drastically reduces the total number of measurements in a variational quantum eigensolver for a quantum chemistry.
  arXiv  Detail & Related papers  (2022-05-09T01:49:21Z)
• A quantum algorithm for computing the Carmichael function [0.0]
  Quantum computers can solve many number theory problems efficiently. This paper presents an algorithm that computes the Carmichael function for any integer $N$ with a probability as close to 1 as desired.
  arXiv  Detail & Related papers  (2021-11-03T19:30:27Z)
• Quantum mean value approximator for hard integer value problems [19.4417702222583]
  We show that an optimization can be improved substantially by using an approximation rather than the exact expectation. Together with efficient classical sampling algorithms, a quantum algorithm with minimal gate count can thus improve the efficiency of general integer-value problems.
  arXiv  Detail & Related papers  (2021-05-27T13:03:52Z)

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.