Resource-Scalable Fully Quantum Metropolis–Hastings for Integer Linear Programming Gabriel Escrig, Roberto Campos, M. A. Martín-Delgado Abstract Integer linear programming (ILP) remains computationally challenging due to its NP-complete nature despite its central role in scheduling, logistics, and design optimization. We introduce a fully quantum Metropolis–Hastings algorithm for ILP that implements a coherent random walk over the discrete feasible region using only reversible quantum circuits, without quantum-RAM assumptions or classical pre/post-processing. Each walk step is a unitary update that prepares coherent candidate moves, evaluates the objective and constraints reversibly—including a constraint-satisfaction counter to enforce feasibility—and encodes Metropolis acceptance amplitudes via a low-overhead linearized rule. At the logical level, the construction uses 𝒪 ⁡ ( n ​ log 2 ​ N ) \mathcal{O}(n\log_{2}N) qubits to represent n n integer variables over the interval [ − N , N − 1 ] [-N,\,N-1] , and the Toffoli-equivalent cost per Metropolis step grows linearly with the total logical qubit count. Using explicit ripple-carry adder constructions, we support linear objectives and mixed equality/inequality constraints. Numerical circuit-level simulations on a broad ensemble of randomly generated instances validate the predicted linear resource scaling and exhibit progressive thermalization toward low-cost feasible solutions under the annealing schedule. Overall, the method provides a coherent, resource-characterized baseline for fully quantum constraint programming and a foundation for incorporating additional quantum speedups in combinatorial optimization. I Introduction Figure 1: Heat map of the probability distribution obtained after applying the Randomized Quantum Metropolis algorithm (see Sec. III ) for 20 steps. Color intensity encodes the probability of measuring the quantum state \ket{x_{1},x_{2}} , where each grid cell corresponds to a discrete point in the feasible region defined by the constraint x_{1}+x_{2}\geq 0 . The optimization function is given by f(x_{1},x_{2})=-2x_{1}-x_{2} , and the distribution reflects the thermalized process. The problem is solved for 2 qubits of discretization per variable, leaving the possible search space as the square [-2,1]\times[-2,1] . Integer linear programming sits at the heart of operations research, underpinning critical applications in scheduling, logistics, and design. Defined by the optimization of a linear objective function subject to linear constraints over integer variables, ILP provides a modeling framework broad enough to cover a vast range of industrial problems 6 ; 36 . While the Simplex algorithm remains the de‑facto standard for continuous relaxations 21 , the integrality constraints render the general problem NP-complete 29 . Consequently, modern commercial solvers rely on sophisticated branch‑and‑bound or branch‑and‑cut frameworks, augmented by primal heuristics, to certify optimality 16 ; 22 ; 28 . In contexts where diverse high-quality solutions are preferred over a single optimal proof—such as generating warm starts for exact solvers—Metropolis–Hastings (MH) sampling serves as a powerful primitive 12 . As a lightweight Markov-chain Monte Carlo method, MH enables the exploration of large discrete state spaces and admits efficient parallelization 3 . However, classical ILP solvers face three inherent barriers: combinatorial explosion of the search space, scalability bottlenecks related to constraint evaluation, and reliance on structural heuristics that may not generalize. From a complexity‑theoretic standpoint, ILP’s NP‑completeness precludes universal polynomial‑time algorithms—classical or quantum. While quantum speed‑ups have been reported for semidefinite programming, they typically rely on sparsity and quantum‑RAM (QRAM) data‑access assumptions 19 ; 5 ; 1 ; 9 , conditions that do not carry over to the combinatorial landscape of ILP. Similarly, variational approaches like QAOA or adiabatic annealing offer approximate mappings but have yet to demonstrate systematic performance gains on large, constrained instances without extensive classical feedback loops 2 ; 31 . In this work, we depart from hybrid or oracle-based paradigms by proposing a fully quantum Metropolis–Hastings algorithm for ILP. Every arithmetic subroutine—cost evaluation, constraint counting, and acceptance-probability computation—is implemented as a reversible quantum circuit, avoiding any classical pre- or post-processing. In contrast to previous approaches relying on QRAM or preloaded data, our method performs all calculations on-the-fly , enabling coherent updates and transitions directly within the quantum circuit. Furthermore, the algorithm is designed with an all-to-all connectivity topology, allowing direct transitions between arbitrary states. This approach facilitates global exploration of the optimization landscape, thereby significantly mitigating the risk of the search process stagnating in local minima. The resulting unitary walk explores the feasible polytope coherently, biasing the quantum state amplitude toward high-quality integer solutions. In addition to preserving the massive parallelism of the Metropolis–Hastings framework, this construction opens the door to genuinely quantum enhancements such as amplitude amplification and coherent thermalization, which are unavailable in hybrid or semi-classical samplers. A central contribution of this work is the explicit characterization of the logical resource requirements. We derive two key scaling results: First, the spatial complexity scales as \mathcal{O}(n\log_{2}N) , where n is the number of variables and N the discretization size. This reflects an efficient logarithmic encoding where auxiliary overheads scale linearly with n . Second, the logical depth of the Metropolis step, measured in Toffoli-equivalent gates, scales linearly as \mathcal{O}(k) with the total qubit count k . This linear scaling captures the dominant cost of reversible arithmetic and establishes that, while the classical search space grows exponentially, the quantum circuit resources remain polynomial and predictable. While the method achieves full quantum coherence and predictable scaling, it remains subject to the practical overhead associated with reversible arithmetic and multi-controlled operations, which dominate the Toffoli-equivalent cost. Moreover, the number of annealing steps required to reach thermal equilibrium depends on the specific instance and temperature schedule, introducing a heuristic component typical of annealing-based approaches. It is important to note that the efficiency analysis presented in this work refers strictly to the logical circuit complexity, assuming access to a fully fault-tolerant quantum computer. Physical-level overheads related to error correction and qubit connectivity are therefore not included in the reported scaling estimates. Nevertheless, these characteristics are intrinsic to the algorithm’s design and do not compromise its asymptotic efficiency or scalability. The remainder of this paper is organized as follows. Section II formalizes the ILP problem and establishes the notation used throughout the paper. Section III provides a high-level overview of the proposed quantum Metropolis–Hastings algorithm. Section IV describes the quantum encoding of linear constraints and their circuit implementation. Section V details the construction of the full quantum Metropolis–Hastings operator, including proposal, conditional rotation, transition, and reflection subroutines. Finally, Section VI presents the numerical simulations that validate the scaling analysis and performance of the method, and Section VII summarizes our findings and outlines directions for future research. Figure 2: One iteration of the quantum Metropolis walk. Registers (top to bottom) hold the current position S , its cost F , a candidate position S^{\prime} , its cost F^{\prime} , the constraint counter R and a coin qubit C . The red shaded region encloses the walk operator W=R\,P^{\dagger}\,F\,P . II Linear Optimization Problems Linear programming (LP) is the canonical framework for optimizing a linear objective over a polyhedral feasible region described by linear equality and inequality constraints. Integer linear programming strengthens LP by imposing integrality on some or all decision variables, thereby capturing inherently discrete decisions at the cost of a substantial increase in computational difficulty. II.1 Canonical definition Let \mathbf{x}=(x_{1},\dots,x_{n})^{\mathsf{T}}\in\mathbb{R}^{n} be the decision vector and let \Theta\subseteq\mathbb{R}^{n} denote the state space, i.e., the set of all values \mathbf{x} is allowed to take. A linear optimization problem in canonical form is \displaystyle\underset{\mathbf{x}\in\Theta}{\text{minimize}}\quad \displaystyle f(\mathbf{x})\;=\;c_{0}+c_{1}x_{1}+\dots+c_{n}x_{n}, (1) subject to \displaystyle g_{i}(\mathbf{x})\;\geq\;0,\quad i=0,\dots,m-1, \displaystyle h_{j}(\mathbf{x})\;=\;0,\quad j=0,\dots,p-1. Throughout this work, we consider f , each g_{i} , and each h_{j} to be linear functions defined by integer coefficients and constants. Specifically, we assume c_{l}\in\mathbb{Z} for all l , and that the linear constraints are similarly parameterized by integers. This restriction aligns with the fixed-point arithmetic inherent to the quantum adder constructions utilized in our algorithm. The inequalities g_{i}(\mathbf{x})\geq 0 are called inequality constraints, whereas the equalities h_{j}(\mathbf{x})=0 are equality constraints; we take m\geq 0 and p\geq 0 . The feasible region is \Omega\;=\;\bigl\{\mathbf{x}\in\Theta:g_{i}(\mathbf{x})\geq 0\;\forall i,\;h_{j}(\mathbf{x})=0\;\forall j\bigr\}\subseteq\Theta. (2) By construction, the feasible region \Omega is a convex polytope, obtained as the intersection of half-spaces and hyperplanes defined by the linear constraints. An optimal solution is a point \mathbf{x}^{\star}\in\Omega that minimizes (or, in the equivalent maximization form, maximizes) f(\mathbf{x}) on \Omega . Because \max f(\mathbf{x})=-\min[-f(\mathbf{x})] , every minimization problem can be converted into a maximization problem. Likewise, a “ \leq ” constraint can be turned into a “ \geq ” constraint by simply multiplying by -1 . Finally, in integer linear programming, the additional integrality constraint \mathbf{x}\in\mathbb{Z}^{n} is imposed. This represents the central challenge addressed in this work. In the following sections, we show how such problems can be tackled within a fully quantum framework based on quantum walks. III Algorithm overview The quantum Metropolis-Hastings algorithm acts as a unitary embedding of the classical Metropolis–Hastings sampler. While the general framework allows for sampling from arbitrary probability distributions, for optimization purposes we configure the algorithm to produce quantum superpositions whose measurement statistics converge to the Boltzmann distribution \pi_{\beta}(\mathbf{x})\propto e^{-\beta f(\mathbf{x})} . By repeatedly applying a reversible proposal–acceptance block, the algorithm explores the feasible region \Omega while amplifying the amplitudes of maximal reward solutions. Once the walk has mixed, a measurement yields—with high probability—a state that minimizes the linear objective f(\mathbf{x}) in ( 1 ), as can be seen in Figure 1 . In our construction, the reversible proposal–acceptance block is implemented using the framework of coined quantum walks, following the quantum simulated annealing (QSA) algorithm introduced in 30 , which ensures convergence to the Boltzmann distribution, but is slightly modified with the randomization technique, resulting in an original scheme to address the ILP problem. A discrete-time quantum walk is obtained by repeatedly applying a unitary step operator, denoted by W , where each application of W corresponds to one step of the walk 24 . The operator W must be constructed so as to respect the adjacency structure of the underlying graph. In our setting, each vertex corresponds to an assignment \mathbf{x} of the n decision variables, encoded in the system register S as \ket{\mathbf{x}}_{S}\;=\;\ket{x_{1}}\otimes\ket{x_{2}}\otimes\cdots\otimes\ket{x_{n}}. (3) To represent transitions between vertices, the system space is extended with an auxiliary proposal space. In general graphs the number of neighbors may depend on the vertex, so it is more precise to view this space as having dimension at least the maximum degree of the graph (or, equivalently, to choose a register large enough to index all candidate moves allowed by the proposal rule). We denote this auxiliary register by S^{\prime} , and we interpret it as encoding a proposed neighboring configuration \ket{\mathbf{x}^{\prime}}_{S^{\prime}} . In addition, we introduce a coin register C consisting of a single qubit, which coherently encodes the transition amplitude associated with the move from the current state \ket{\mathbf{x}}_{S} to the proposed state \ket{\mathbf{x}^{\prime}}_{S^{\prime}} . Furthermore, two function registers F and F^{\prime} are used to store the objective-function values evaluated at the current and proposed configurations, respectively, i.e., f(\mathbf{x}) and f(\mathbf{x}^{\prime}) as defined in Eq. ( 1 ). Finally, a constraint-counter register R records how many of the problem constraints are satisfied by a candidate configuration, and is used to ensure that only feasible transitions contribute to the walk dynamics. The underlying transition graph is taken to be fully connected: from any configuration \ket{\mathbf{x}}_{S} the proposal register can coherently encode any candidate configuration \ket{\mathbf{x}^{\prime}}_{S^{\prime}} . Feasibility is not enforced by removing edges from the graph, but by the walk dynamics itself. In particular, the constraint-evaluation circuit and the acceptance filter suppress (or null) amplitudes associated with moves that would violate the problem constraints, so that transitions between feasible and infeasible configurations carry zero effective weight. Thus, while the proposal mechanism remains complete at the level of connectivity, the implemented quantum evolution restricts the walk to the feasible region by construction. The MH acceptance rule is implemented coherently via the coin register. Given a proposed transition from \mathbf{x} to \mathbf{x}^{\prime} , we define the acceptance probability A(\mathbf{x},\mathbf{x}^{\prime})\;:=\;\min\!\left\{1,\,\exp\!\big(-\beta\,[f(\mathbf{x}^{\prime})-f(\mathbf{x})]\big)\right\}, (4) where \beta represents an annealing schedule. This is the Boltzmann distribution, which we want to sample in order to search for the minimum or maximum values of the objective function. Any function that highlights the maximal values can be used, since the algorithm will attempt to sample it and thus increase the probability of finding these optimal values. In our coined-walk construction, an acceptance subroutine encodes \sqrt{A(\mathbf{x},\mathbf{x}^{\prime})} as an amplitude on the coin qubit. We now outline the one-step quantum walk operator W at a heuristic level, deferring the explicit circuit construction to Section V and the formal proofs of unitarity and spectral properties to Appendix A . One step of the quantum Metropolis walk is implemented by the unitary W\;=\;R\,P^{\dagger}\,F\,P. (5) The structure and ordering of these constituent operators of the walk W mirrors the standard Metropolis–Hastings update rule. First, the preparation stage P generates a coherent candidate move in S^{\prime} and encodes its acceptance amplitude in the coin and auxiliary registers (including feasibility information). Second, the conditional shift F applies the proposed update, conditioned jointly on feasibility and on the acceptance register. Third, P^{\dagger} uncomputes the auxiliary information, restoring the ancilla registers to their initial states and ensuring reversibility. Finally, the reflection R applies a phase flip about the designated reference subspace, yielding the spectral structure required by the Szegedy-type quantization (in particular, a unique eigenvalue 1 associated with the target stationary state and a nonzero spectral gap). Appendix A proves that W is unitary and that its induced measurement statistics reproduce the Metropolis–Hastings acceptance rule. Figure 2 illustrates one full iteration of the operator W . Operationally: (1) Initialization. Prepare a uniform superposition and compute the cost function as the initial input state, \ket{\psi^{(0)}}=\frac{1}{\sqrt{\Theta}}\sum_{\mathbf{x}\in\Theta}\ket{\mathbf{x}}_{S}\ket{f(\mathbf{x})}_{F}, (6) with auxiliary registers set to \ket{0} . (2) Set temperature. Set the maximum number of annealing steps Q and the maximum number of repetitions per temperature step T . Fix the inverse temperature schedule \{\beta_{1},\beta_{2},\ldots,\beta_{Q}\} , typically ranging from \beta_{1}\approx 0 to a sufficiently large \beta_{Q} . Initialize counter k\!\leftarrow\!1 . (3) Randomized quantum walk. Draw a random integer t\in\{1,\,T\}, (7) and apply the corresponding block \ket{\psi^{(k+1)}}=(W_{k+1})^{t}\ket{\psi^{(k)}}, (8) where W_{k}=RP_{k}^{\dagger}FP_{k} . Here P_{k} encodes the thermalization step defined by \beta_{k} . The operation (W_{k})^{t} performs a randomized quantum walk whose length is controlled by the random variable t , enhancing mixing within the feasible subspace. (4) Partial measurement and update. Perform a partial measurement on the coin qubit \mathcal{H}_{C} and the movement register \mathcal{H}_{S^{\prime}} and discard the result. Increment the temperature step counter k\!\leftarrow\!k+1 . If k0 . This condition ensures that the sequence of projections and evolutions effectively drags the system toward the low-cost states of f(\mathbf{x}) with high probability. At high temperatures (small \beta ), nearly all transitions are accepted except those violating feasibility constraints, allowing a broad exploration of the search space. As the temperature decreases, the acceptance probability becomes increasingly selective, and in the low-temperature limit, only transitions that reduce the objective function value are accepted. This gradual cooling emulates the classical simulated-annealing process, but here it occurs coherently within a reversible quantum framework. Unlike the classical Metropolis–Hastings procedure, where convergence relies on the empirical estimation of a mixing time T_{\mathrm{mix}} 15 , the quantum approach relies on spectral filtering via quantum phase estimation. The walk operator W_{k} possesses a unique eigenstate with eigenvalue 1 (corresponding to eigenphase \theta=0 ) while all other eigenvalues are separated by a finite spectral gap \Delta (see Appendix A ). Consequently, the computational cost is determined by the requirement to resolve this gap. Specifically, distinguishing the target eigenstate requires a phase estimation precision of 2^{-q}\lesssim\Delta , which implies \mathcal{O}(1/\Delta) applications of W_{k} 20 ; 7 . Provided this precision is met, the QPE subroutine projects the state \ket{\psi^{(k)}} onto the desired Gibbs distribution with high probability, effectively filtering out the excited states that correspond to the classical mixing transient. After Q annealing steps, with sufficient spectral resolution, the final state \ket{\psi^{(Q)}} approximates the quantum Gibbs state associated with the Boltzmann weights \pi_{\beta_{Q}}(\mathbf{x})\propto e^{-\beta_{Q}f(\mathbf{x})} . A projective measurement on the system register S then samples configurations \mathbf{x} according to this low-temperature thermal distribution, yielding solutions whose energies lie within \epsilon of the global optimum. In the original QSA formulation 30 , the total number of required quantum walk steps to accurately sample the thermal distribution scales as \mathcal{N}_{\mathrm{QSA}}=\mathcal{O}\!\left[\left(\frac{E_{M}}{\gamma}\right)^{2}\frac{\log^{2}(d/\epsilon)\,\log d}{\epsilon\sqrt{\delta}}\right], (12) where E_{M} is the bound on the energy function range, d represents the dimension of the state space, and \epsilon is the desired precision. Crucially, \delta denotes the spectral gap of the classical transition matrix. Due to the quadratic speedup property of Szegedy-type quantum walks 32 ; 23 , the spectral gap of the unitary operator W_{k} —denoted previously as \Delta —scales as \Delta\sim\sqrt{\delta} . This relationship dictates the phase estimation precision required to distinguish the ground state, leading to the 1/\sqrt{\delta} factor in the complexity, in contrast to the 1/\delta scaling of classical mixing times. However, in the optimization setting considered here, the requirements are relaxed compared to exact sampling. Since our goal is to amplify the probability of the optimal configuration rather than to strictly sample the full Gibbs distribution, the number of annealing steps need not saturate the theoretical bound derived for sampling. In practice, the process acts as a heuristic filter: the sequential application of W_{k} operators, combined with the partial measurement scheme 27 , progressively concentrates probability amplitude into the lowest-energy subspace. Unlike Grover-type amplitude amplification, where precise timing is critical to avoid over-rotation 17 ; 13 , this annealing approach is robust: extending the schedule typically improves—or at least preserves—the success probability, rather than oscillating away from the solution. Therefore, while the theoretical upper bound in 30 remains the rigorous limit for exact Gibbs sampling, in the optimization-oriented version of QSA implemented here, convergence to near-optimal solutions is observed empirically to scale more favorably. We find that a polynomial or polylogarithmic number of temperature steps often suffices to reach the feasible ground state. In this sense, the annealing schedule serves as a tunable heuristic: slower cooling (smaller \Delta\beta ) reliably enhances the fidelity of the final state with respect to the global minimum. Figure 3: Quantum circuit implementing two’s-complement negation of an n -qubit register ( n=3 shown). The circuit comprises two stages: (i) bit-wise NOT operations (left-hand X gates) that flip all qubits, and (ii) a cascade of multi-controlled NOT gates (shaded region) that increments the result by one, together realizing the two’s-complement negation -x=\overline{x}+1 . IV Quantization of the Restrictions Figure 4: Synthesis of the unitary U_{f} for the two-variable linear form f(x_{1},x_{2})=c_{0}-c_{1}x_{1}+c_{2}x_{2} with c_{i}>0 . Register F is first loaded with the constant term c_{0} (red box). Orange block: subtraction of c_{1}x_{1} . The value qubits of x_{1} and the global carry-in are flipped with X gates, the sign bit is fan-out via CNOTs to sign-extend x_{1} up to the number of qubits of register F , and the CDKM full adder is applied c_{1} times, yielding c_{0}-c_{1}x_{1} . Blue block: addition of c_{2}x_{2} . Because c_{2} is positive, only sign extension is required before invoking the adder c_{2} times. Upon completion the accumulator holds c_{0}-c_{1}x_{1}+c_{2}x_{2} and all ancillas (carry and extension lines) are returned to \ket{0} , ensuring that U_{f} is reversible. By definition, linear programming restricts both the objective function and every constraint to linear forms; evaluating any of them on a quantum register therefore boils down to computing weighted sums of integer variables. Addition is thus the core arithmetic primitive, and the literature offers several depth and qubit efficient reversible adders to implement it 33 ; 34 . Building on these primitives, the remainder of this section assembles the higher‑level unitary operators required by our algorithm. IV.1 Encoding As we are going to work with integers, we have to represent both positive and negative numbers. In order to represent negative numbers, we will use the binary encoding two’s complement. In this way, the subtraction can be performed according to: a-b=a+\bar{b}+1, (13) where \bar{x} is the negation of x bit by bit, and is nothing more than the consecutive application of X gates. Increasing the unit can be done simply with multi-controlled gates. This simple circuit is shown in Figure 3 . IV.2 Quantum Circuits for Linear Functions Multiplication by a classical integer coefficient is implemented as a sequence of conditional additions; hence the only primitive we need is a reversible adder. We adopt the Cuccaro–Draper–Kutin–Moulton ripple‑carry design (CDKM) 8 because of its qubit‑optimal footprint; any other reversible adder can be substituted without altering the logic that follows. The CDKM adder natively performs \ket{a}\ket{b}\!\mapsto\!\ket{a}\ket{a+b\bmod 2^{m}}, (14) on two equally sized m qubit registers. To incorporate subtraction with the CDKM adder we negate the second operand in two steps. First apply X gates to all m qubits of b (bit‑wise NOT). Then, invoke the fixed‑adder version of CDKM with the carry‑in initialized to \ket{1} . This adds the required +1 and yields a+\overline{b}+1=a-b . Figure 5: Explicit circuit for the operator V of the one-step operator W . For every candidate vector \mathbf{x^{\prime}} in S^{\prime} the unitary first computes the constraint values in the workspace register F^{\prime} and then updates the counter register R . Controls on the equality blocks H_{j} act on all qubits of F^{\prime} , whereas the inequality blocks G_{i} need only the sign qubit. The final state of R encodes the number of satisfied constraints, being m{+}p for feasible points. The NOT+carry‑in trick avoids an extra adder since the CDKM fixed adder always works with one carry in qubit. All CDKM inputs must have the same width. If variable x_{i} is stored in k qubits but the accumulator uses m>k qubits, we sign‑extend x_{i} by copying its sign bit into the m-k highest positions; this is done with CNOTs controlled by the sign qubit. All ancillas are uncomputed locally, so the transformation remains unitary. Let us introduce the reversible operations associated to the integer linear optimization problem by means of the following unitary operators: \displaystyle\begin{split}U_{g_{i}}\ket{\mathbf{x}}_{S^{\prime}}\ket{0}_{F^{\prime}}&:=\ket{\mathbf{x}}_{S^{\prime}}\ket{g_{i}(\mathbf{x})}_{F^{\prime}},\\ U_{h_{j}}\ket{\mathbf{x}}_{S^{\prime}}\ket{0}_{F^{\prime}}&:=\ket{\mathbf{x}}_{S^{\prime}}\ket{h_{j}(\mathbf{x})}_{F^{\prime}},\\ U_{f}\ket{\mathbf{x}}_{S^{\prime}}\ket{0}_{F^{\prime}}&:=\ket{\mathbf{x}}_{S^{\prime}}\ket{f(\mathbf{x})}_{F^{\prime}}.\\ \end{split} (15) These operators compute the functions ( 1 ) in quantum states. Let us see explicitly the construction for f(x) in ( 1 ), being a general scheme for any linear function. This process is shown in Figure 4 . First we initialize the circuit with the independent term c_{0} with gates X so we get the state \ket{\mathbf{x}}_{S^{\prime}}\ket{c_{0}}_{F^{\prime}} . The next step is to add the variable x_{1} . To do this, we need to take into account the sign of the coefficient. If the coefficient is positive, we perform the sign extension and apply c_{1} times the CDKM adder. On the other hand, if the coefficient is negative, we negate the x_{1} register with X gates, set the carry in to \ket{1} and perform the sign extension. We then apply |c_{1}| times the adder and descompute the sign extension and the X gates. In this way we reach the state: \ket{\mathbf{x}}_{S^{\prime}}\ket{c_{0}}_{F^{\prime}}\mapsto\ket{\mathbf{x}}_{S^{\prime}}\ket{c_{0}+c_{1}x_{1}}_{F^{\prime}}. (16) Repeating this process for each of the n variables x_{i} , each with its own coefficient c_{i} , we finally arrive at the state \ket{\mathbf{x}}_{S^{\prime}}\ket{f(\mathbf{x})}_{F^{\prime}} . Each adder gate uses \mathcal{O}(m) Toffoli gates for an m -bit adder 8 , which is applied to n variables x_{i} , each with its coefficient c_{i} , giving a total of \mathcal{O}(m\sum_{i}|c_{i}|) Toffoli gates. Although these arithmetic elements do not accelerate individual operations versus classical logic, the advantage will lie in their coherent evaluation over a superposition of all \mathbf{x}\in\Theta , essential for the quantum Metropolis walk developed in Sec. V . IV.3 Quantum Circuits for Constraint Implementation We now design a reversible routine that, for every candidate point \mathbf{x} held in the candidate state register S^{\prime} , evaluates all p equality constraints h_{j} and all m inequality constraints g_{i} and stores the result in a dedicated counter register R . The role of R is purely to count how many of the (m+p) constraints are satisfied by \mathbf{x} ; it needs \lceil\log_{2}(m+p)\rceil qubits. The purpose of this routine is to perform the following operation: \ket{\mathbf{x}}_{S^{\prime}}\ket{0}_{R}\;\longmapsto\;\begin{cases}\ket{\mathbf{x}}_{S^{\prime}}\,\ket{m+p}_{R},&\mathbf{x}\in\Omega,\\[4.0pt] \ket{\mathbf{x}}_{S^{\prime}}\,\ket{r}_{R},&\mathbf{x}\notin\Omega,\\ \end{cases} (17) where \Omega is the feasible region and r\leq m+p is the number of constraints met by the infeasible point \mathbf{x} . The registers involved are S^{\prime} – candidate state register, \ket{\mathbf{x}}_{S^{\prime}} ; F^{\prime} – workspace register used to compute each g_{i}(\mathbf{x}) or h_{j}(\mathbf{x}) via the unitary operators U_{g_{i}},U_{h_{j}} and the cost function of Eq. ( 15 ); R – counter register described above. This explicit construction will be explained in more detail in the following section in order to arrive at ( 17 ). All the following developments can be found in Figure 5 . IV.4 Equality constraints To study the equality constraints, the first step is to apply the first constraint, as follows: U_{h_{0}}\ket{\mathbf{x}}_{S^{\prime}}\ket{0}_{F^{\prime}}\ket{0}_{R}=\ket{\mathbf{x}}_{S^{\prime}}\ket{h_{0}(\mathbf{x})}_{F^{\prime}}\ket{0}_{R}. (18) As the condition h_{0} is an equality condition, it will be fulfilled if the F^{\prime} register is \ket{0}_{F^{\prime}} . Consequently, we increment the R register by 1 (resulting in \ket{0\dots 01}_{R} ) if the constraint is met; otherwise, the register remains in \ket{0}_{R} . For increasing the unit the Add 1 circuit of the Figure 3 can be used. For this we define the operator A_{\text{eq}} , which acts as follows: \displaystyle\small A_{\text{eq}} \displaystyle\ket{\mathbf{x}}_{S^{\prime}}\ket{h_{0}(\mathbf{x})}_{F^{\prime}}\ket{0}_{R}:= \displaystyle=\begin{cases}\ket{\mathbf{x}}_{S^{\prime}}\ket{h_{0}(\mathbf{x})}_{F^{\prime}}\ket{0...01}_{R}&\text{if }\ket{h_{0}(\mathbf{x})}_{F^{\prime}}=\ket{0}_{F^{\prime}},\\ \ket{\mathbf{x}}_{S^{\prime}}\ket{h_{0}(\mathbf{x})}_{F^{\prime}}\ket{0...00}_{R}&\text{if }\ket{h_{0}(\mathbf{x})}_{F^{\prime}}\neq\ket{0}_{F^{\prime}}.\end{cases} (19) And this comparison between \ket{h_{0}(\mathbf{x})}_{F^{\prime}} and \ket{0}_{F^{\prime}} is as simple as applying X on every qubit of F^{\prime} , then applying Multi Controlled Add 1 gate of Figure 3 controlled by all the qubits of the F^{\prime} , and finally uncompute the transformation applying X on every qubit of F^{\prime} . This controlled operation is sometimes referred to as Anti-controlled gate, being represented as an empty circle in the Figure 5 . Before applying the next constraint, we must uncompute U_{h_{0}} to reset the F^{\prime} register to \ket{0}_{F^{\prime}} . This step enables us to store the value of the next function in the same register, optimizing qubit usage. This is simply applying U_{h_{0}}^{\dagger} : U_{h_{0}}^{\dagger}\ket{\mathbf{x}}_{S^{\prime}}\ket{h_{0}(\mathbf{x})}_{F^{\prime}}\ket{r}_{R}=\ket{\mathbf{x}}_{S^{\prime}}\ket{0}_{F^{\prime}}\ket{r}_{R} (20) For the next constraint, we apply the exact same procedure as described above. Specifically: U_{h_{1}}\ket{\mathbf{x}}_{S^{\prime}}\ket{0}_{F^{\prime}}\ket{r}_{R}=\ket{\mathbf{x}}_{S^{\prime}}\ket{h_{1}(\mathbf{x})}_{F^{\prime}}\ket{r}_{R}. (21) Following the same logic, the constraint is satisfied if the F^{\prime} register remains in the state \ket{0}_{F^{\prime}} : \displaystyle\small A_{\text{eq}} \displaystyle\ket{\mathbf{x}}_{S^{\prime}}\ket{h_{1}(\mathbf{x})}_{F^{\prime}}\ket{r}_{R}= \displaystyle=\begin{cases}\ket{\mathbf{x}}_{S^{\prime}}\ket{h_{1}(\mathbf{x})}_{F^{\prime}}\ket{r+1}_{R}&\text{if }\ket{h_{1}(\mathbf{x})}_{F^{\prime}}=\ket{0}_{F^{\prime}},\\ \ket{\mathbf{x}}_{S^{\prime}}\ket{h_{1}(\mathbf{x})}_{F^{\prime}}\ket{r}_{R}&\text{if }\ket{h_{1}(\mathbf{x})}_{F^{\prime}}\neq\ket{0}_{F^{\prime}}.\end{cases} (22) Finally, we uncompute by applying U_{h_{1}}^{\dagger} to reset the F^{\prime} register to \ket{0}_{F^{\prime}} , thereby allowing for the evaluation of subsequent constraints: U_{h_{1}}^{\dagger}\ket{\mathbf{x}}_{S^{\prime}}\ket{h_{1}(\mathbf{x})}_{F^{\prime}}\ket{r}_{R}=\ket{\mathbf{x}}_{S^{\prime}}\ket{0}_{F^{\prime}}\ket{r}_{R}. (23) Figure 6: Explicit circuit construction of the operator B in Eq. ( 40 ). The Metropolis acceptance amplitude is encoded into the coin register by applying controlled R_{y} rotations conditioned qubit-by-qubit on the discretized energy-difference register \Delta f stored in F^{\prime} . For each annealing step k , the rotation angles \{\theta^{(k)}_{j}\} are determined by the inverse temperature \beta_{k} through the prescribed approximation scheme. This qubit-wise construction avoids implementing an explicit exponential subroutine while enabling a \beta -dependent thermalization of the acceptance rule. We define the composite operator for the j -th constraint, denoted as H_{j} , by: H_{j}:=U_{h_{j}}^{\dagger}A_{\text{eq}}U_{h_{j}}. (24) We provide explicit constructions for each H_{j} , which implement the following transformation: H_{j}\ket{\mathbf{x}}_{S^{\prime}}\ket{0}_{F^{\prime}}\ket{r}_{R}=\begin{cases}\ket{\mathbf{x}}_{S^{\prime}}\ket{0}_{F^{\prime}}\ket{r+1}_{R}&\text{if }\mathbf{x}\in\Omega_{j},\\ \ket{\mathbf{x}}_{S^{\prime}}\ket{0}_{F^{\prime}}\ket{r}_{R}&\text{if }\mathbf{x}\notin\Omega_{j}.\end{cases} (25) Here, \Omega_{j} denotes the feasible region defined by the j -th equality constraint. This approach yields a clear modular scheme, the architecture of which is illustrated in Figure 5 . IV.5 Inequality constraints Having established the scheme for equality constraints, we now address the construction of the operators for inequality constraints, denoted by g_{i} . We define an operator G_{i} , analogous to H_{j} in Eq. ( 25 ), such that: G_{i}\ket{\mathbf{x}}_{S^{\prime}}\ket{0}_{F^{\prime}}\ket{r}_{R}:=\begin{cases}\ket{\mathbf{x}}_{S^{\prime}}\ket{0}_{F^{\prime}}\ket{r+1}_{R}&\text{if }\mathbf{x}\in\Omega_{i},\\ \ket{\mathbf{x}}_{S^{\prime}}\ket{0}_{F^{\prime}}\ket{r}_{R}&\text{if }\mathbf{x}\notin\Omega_{i},\end{cases} (26) where \Omega_{i} corresponds to the feasible region satisfied by the i -th inequality constraint. The construction of this operator is straightforward. First, we compute the constraint function: U_{g_{0}}\ket{\mathbf{x}}_{S^{\prime}}\ket{0}_{F^{\prime}}\ket{r}_{R}=\ket{\mathbf{x}}_{S^{\prime}}\ket{g_{0}(\mathbf{x})}_{F^{\prime}}\ket{r}_{R}. (27) Since g_{i} represents a greater-than or equal to constraint ( \geq 0 ), it is satisfied if the value in the F^{\prime} register is non-negative. In the two’s complement representation, the most significant bit (MSB) acts as the sign bit: a state represents a non-negative value if and only if the MSB is \ket{0} . Consequently, the condition corresponds to the F^{\prime} register being in a state of the form \ket{0\dots}_{F^{\prime}} . Thus, we increment the ancilla register R (mapping \ket{r}_{R}\to\ket{r+1}_{R} ) if the constraint is met, leaving it unchanged otherwise. This conditional increment is performed using the same Add 1 circuit shown in Figure 3 . We define the conditional operator A_{\text{ineq}} as follows: \displaystyle A_{\text{ineq}}\ket{\mathbf{x}}_{S^{\prime}}\ket{g_{0}(\mathbf{x})}_{F^{\prime}}\ket{r}_{R}:= \displaystyle=\begin{cases}\ket{\mathbf{x}}_{S^{\prime}}\ket{g_{0}(\mathbf{x})}_{F^{\prime}}\ket{r+1}_{R}&\text{if }\ket{g_{0}(\mathbf{x})}_{F^{\prime}}=\ket{0...}_{F^{\prime}},\\ \ket{\mathbf{x}}_{S^{\prime}}\ket{g_{0}(\mathbf{x})}_{F^{\prime}}\ket{r}_{R}&\text{if }\ket{g_{0}(\mathbf{x})}_{F^{\prime}}\neq\ket{0...}_{F^{\prime}}.\end{cases} (28) Verifying this condition is computationally less expensive than checking for equality, as it requires querying only the first qubit (MSB) of the F^{\prime} register. Implementation-wise, since the standard control activates on \ket{1} but we require activation on \ket{0} (positive sign), we apply an X gate to the MSB, perform the controlled Add 1 , and then apply X again to restore the state. This is equivalent to an open-controlled (zero-controlled) operation. Finally, we uncompute U_{g_{i}} to reset the F^{\prime} register. The complete construction for any inequality constraint G_{i} is given by: G_{i}:=U_{g_{i}}^{\dagger}A_{\text{ineq}}U_{g_{i}}. (29) The full constraint-checking subroutine, corresponding to Eq. ( 17 ), is composed as follows: \small G_{m-1}\cdots G_{1}G_{0}H_{p-1}\cdots H_{1}H_{0}=\prod_{i=0}^{m-1}G_{m-1-i}\prod_{j=0}^{p-1}H_{p-1-j}, (30) ensuring that the counter ancilla reaches the state \ket{m+p}_{R} if and only if all constraints are fulfilled. From an implementation standpoint, it is worth emphasizing that the equality–checking subroutine H_{j} generally incurs a higher logical cost than its inequality counterpart G_{i} . In particular, testing equality requires a full multi-qubit comparison with \ket{0}_{F^{\prime}} , which translates into multi-controlled increments on the counter register R and therefore leads to a quadratic Toffoli overhead in the bit width of F^{\prime} . By contrast, inequality constraints of the form g_{i}(\mathbf{x})\geq 0 reduce to a sign test in two’s-complement representation and can be implemented by querying only the most significant bit, yielding a linear logical cost. This asymmetry suggests a more resource-efficient formulation in which equality constraints are recast as pairs of inequalities. The following statement formalizes this observation. Theorem 1 (Resource-efficient equality elimination) . Consider an ILP instance in canonical form ( 1 ) with m\geq 0 inequality constraints g_{i}(\mathbf{x})\geq 0 and p\geq 0 equality constraints h_{j}(\mathbf{x})=0 , and let \Omega denote its feasible region. Under the constraint-encoding scheme of Section IV , there exists an equivalent formulation of the same problem with m^{\prime}\;=\;m+2p, (31) pure inequality constraints only, obtained by replacing each equality constraint h_{j}(\mathbf{x})=0 with the pair h_{j}(\mathbf{x})\geq 0,\qquad-h_{j}(\mathbf{x})\geq 0. (32) This reformulation preserves the feasible region \Omega exactly and admits a global constraint-checking operator of the form Eq. ( 30 ) that can be synthesized exclusively from G_{i} -type inequality subroutines, thereby yielding a strictly lower asymptotic Toffoli overhead than any implementation that employs both G_{i} - and H_{j} -type blocks. Proof. Let h:\Theta\rightarrow\mathbb{Z} be an integer-valued constraint function. For any \mathbf{x}\in\Theta , h(\mathbf{x})=0\;\Longrightarrow\;h(\mathbf{x})\geq 0\;\wedge\;h(\mathbf{x})\leq 0, (33) which is immediate. Conversely, if h(\mathbf{x})\geq 0 and h(\mathbf{x})\leq 0 hold simultaneously, the only integer satisfying both inequalities is h(\mathbf{x})=0 . Hence, h(\mathbf{x})=0\;\Longleftrightarrow\;\bigl(h(\mathbf{x})\geq 0\bigr)\;\wedge\;\bigl(h(\mathbf{x})\leq 0\bigr), (34) and, using h(\mathbf{x})\leq 0\iff-h(\mathbf{x})\geq 0 , h(\mathbf{x})=0\;\Longleftrightarrow\;\bigl(h(\mathbf{x})\geq 0\bigr)\;\wedge\;\bigl(-h(\mathbf{x})\geq 0\bigr). (35) Register Description Qubits S System register encoding \Theta n\log_{2}N S^{\prime} Possible movements n\log_{2}N F Function evaluation of \ket{\textbf{x}}_{S} \mathcal{O}(\log_{2}(N\sum_{k}|c_{k}|)) F^{\prime} Function evaluation of \ket{\textbf{x}^{\prime}}_{S^{\prime}} \mathcal{O}(\log_{2}(N\sum_{k}|c_{k})) R Constraints counter \lceil\log_{2}{(m^{\prime})}\rceil C Coin 1 Table 1: Summary of the quantum registers used in the algorithm, including their logical meaning and the corresponding number of qubits, except for a constant number of ancillas needed for the adders. Each variable x_{i} searches the interval x_{i}\in[-N,N-1] for i=1,\ldots,n . There are m inequailty and p equality constraints, with m^{\prime}=m+2p . Applying this equivalence to each equality constraint h_{j}(\mathbf{x})=0 shows that replacing it by the pair h_{j}(\mathbf{x})\geq 0 and -h_{j}(\mathbf{x})\geq 0 does not alter the set of feasible points, and therefore the feasible region \Omega is preserved exactly. The reformulated instance thus contains m^{\prime}=m+2p pure inequality constraints. From an implementation perspective, Section IV shows that the equality-checking subroutine H_{j} requires a full multi-qubit comparison of the workspace register F^{\prime} with \ket{0}_{F^{\prime}} , realized through multi-controlled increments on the counter register R . This leads to a quadratic Toffoli overhead in the bit width of F^{\prime} . By contrast, each inequality constraint g_{i}(\mathbf{x})\geq 0 is implemented by a G_{i} -type block that reduces to a sign test in two’s-complement representation, querying only the most significant bit of F^{\prime} , and therefore incurs a linear Toffoli cost in the same bit width. Replacing every equality block H_{j} with two inequality blocks of type G_{i} thus transforms each quadratic-cost subroutine into two linear-cost ones. At the level of the global constraint-checking operator Eq. ( 30 ), this modification strictly reduces the leading asymptotic Toffoli overhead while leaving all other circuit components unchanged. Consequently, the overall constraint-checking stage exhibits a strictly lower asymptotic cost, while the feasible region \Omega remains identical. ∎ V Quantum Metropolis Approach With the constraint-evaluation subroutines in place (Section IV ), we now move from the high-level description of the algorithm to its explicit circuit-level realization. As introduced in Section III , the one-step update operator is the unitary W in Eq. ( 5 ), acting on the joint register space \{S,S^{\prime},F,F^{\prime},R,C\} (see Section III and Table 1 ), and repeated applications of this step induce a discrete-time quantum walk whose measurement statistics reproduce Metropolis–Hastings acceptance filtering. In this section, we present the concrete construction of the walk, refining the architecture proposed in 4 ; 10 ; 11 to support explicit constraint handling. We specify each constituent subroutine—proposal generation, acceptance-amplitude encoding, conditional state transition, and reflection—and discuss the logical resources required to implement them as reversible quantum circuits. Figure 2 provides a schematic overview of one full application of the step operator and its register flow. Operationally: a ) Preparation ( P=B\,V ). · Proposal ( V ). Generates a superposition of candidate states \mathbf{x}^{\prime}\in\Theta in the move register S^{\prime} and evaluates \bigl(f(\mathbf{x}^{\prime}),\,r\bigr) into (F^{\prime},R) , with r counting satisfied constraints. · Balance ( B ). Controlled on the system and function registers (S,F) and (S^{\prime},F^{\prime}) , encodes the acceptance amplitude \sqrt{A(\mathbf{x},\mathbf{x}^{\prime})} onto the coin C via conditional rotations, where A=\min\{1,e^{-\beta\Delta f}\} . b ) Shift ( F ). Performs a conditional swap (S,F)\leftrightarrow(S^{\prime},F^{\prime}) , triggered only if the coin register C is in \ket{1}_{C} and the constraint counter R is in \ket{m^{\prime}}_{R} . This effectively accepts the proposed move if and only if it is feasible and statistically accepted. c ) Reflection ( R ). Applies the phase flip given by the reflection 2\ket{0}\!\bra{0}_{S^{\prime}}\!\otimes\!\ket{0}\!\bra{0}_{C}-I . We now examine each operator individually to show how it is implemented. V.0.1 Candidate Generation (Proposal) The first stage of the Quantum Walk involves the application of the proposal operator V . This operator is responsible for generating a superposition of all potential candidates and evaluating their feasibility and cost. The constituent operations are schematically illustrated in Figure 5 . The process begins by creating a uniform superposition over the entire search space (representing all representable integers with d qubits): H^{\otimes d}\ket{0}_{S^{\prime}}=\frac{1}{\sqrt{2^{d}}}\sum_{k=-2^{d-1}}^{2^{d-1}-1}\ket{k}_{S^{\prime}}. (36) Since not all generated states correspond to feasible solutions (i.e., some may violate constraints), we subsequently apply the constraint-counting subroutine defined in Section IV , Eq. ( 30 ). This procedure, illustrated in Figure 4 , increments the register R for each constraint satisfied by the state. Finally, we compute the objective function value, yielding the state: V\ket{0}_{S^{\prime}}\ket{0}_{F^{\prime}}\ket{0}_{R}=\frac{1}{\sqrt{|\Theta|}}\sum_{\mathbf{x}\in\Theta}\ket{\mathbf{x}}_{S^{\prime}}\ket{f(\mathbf{x})}_{F^{\prime}}\ket{r(\mathbf{x})}_{R}, (37) where r(\mathbf{x}) denotes the number of constraints satisfied by the candidate \mathbf{x} . Given that this operator relies primarily on arithmetic addition circuits, the gate complexity—specifically the Toffoli count—is expected to scale linearly with the number of constraints 8 . V.0.2 Conditional Rotations Once the superposition of candidate moves has been generated by V , the acceptance probabilities are encoded into the coin register via the operator B , which is shown schematically in Figure 6 . The first step involves subtracting the function value of the current state S from that of the candidate state S^{\prime} : \displaystyle\small\ket{\mathbf{x}}_{S}\ket{f(\mathbf{x})}_{F} \displaystyle\ket{\mathbf{x}^{\prime}}_{S^{\prime}}\ket{f(\mathbf{x}^{\prime})}_{F^{\prime}}\mapsto \displaystyle\ket{\mathbf{x}}_{S}\ket{f(\mathbf{x})}_{F}\ket{\mathbf{x}^{\prime}}_{S^{\prime}}\ket{f(\mathbf{x}^{\prime})-f(\mathbf{x})}_{F^{\prime}}, (38) performing the subtraction using the same arithmetic logic described in Section IV for negative coefficients. The purpose of this step is to encode the acceptance probability as a quantum amplitude: \displaystyle\small\ket{\mathbf{x}}_{S} \displaystyle\ket{\mathbf{x}^{\prime}}_{S^{\prime}}\ket{0}_{C}\mapsto \displaystyle\ket{\mathbf{x}}_{S}\ket{\mathbf{x}^{\prime}}_{S^{\prime}}[\sqrt{1-A(\mathbf{x},\mathbf{x}^{\prime})}\ket{0}_{C}+\sqrt{A(\mathbf{x},\mathbf{x}^{\prime})}\ket{1}_{C}]. (39) Here, the acceptance probability is encoded in the probability amplitude of the state \ket{1}_{C} , while the rejection probability corresponds to the amplitude of \ket{0}_{C} . Formally, this implements the rotation transformation: \small R(\vartheta)=\left(\begin{matrix}\sqrt{1-A(\mathbf{x},\mathbf{x}^{\prime})}&-\sqrt{A(\mathbf{x},\mathbf{x}^{\prime})}\\ \sqrt{A(\mathbf{x},\mathbf{x}^{\prime})}&\sqrt{1-A(\mathbf{x},\mathbf{x}^{\prime})}\end{matrix}\right), (40) defined by the rotation angle: \vartheta=\arcsin\left(\sqrt{A(\mathbf{x},\mathbf{x}^{\prime})}\right)=\arcsin\left(e^{-\frac{\beta}{2}[f(\mathbf{x}^{\prime})-f(\mathbf{x})]}\right). (41) To implement the conditional rotation shown in Fig. 6 , there is no need to compute the full exponential operator. Exponentiation constitutes a costly arithmetic operation in quantum circuits and can be avoided here, since it is not required for the optimization process (see Appendix A , Theorem 1 ). This avoids the heavy overhead of exponentiation and instead performs a qubit-wise interpolation between the binary-encoded components of the register F^{\prime} . The Metropolis acceptance probability, defined in Eq. ( 4 ), satisfies p_{\mathrm{acc}}=1 whenever the energy difference is non-positive ( \Delta f\leq 0 ). Consequently, the non-trivial exponential decay need only be computed when the energy increases, i.e., for \Delta f>0 . The register F^{\prime} encodes the cost function difference \Delta f=f(\mathbf{x}^{\prime})-f(\mathbf{x}) using two’s complement binary representation: Figure 7: Toffoli-equivalent gate count versus total qubit count across 1000 randomly generated problem instances with n=3 variables, fixed inverse temperature \beta=1 , and varying numbers of linear inequality constraints m^{\prime} . Each color and marker shape corresponds to a distinct constraint count. The dashed lines show linear regression fits, confirming the predicted \mathcal{O}(k) scaling with the total number of qubits k . The systematic increase in slope with m^{\prime} reflects the additional Toffoli overhead introduced by constraint-processing logic. y_{\mathrm{bin}}=b_{k-1}b_{k-2}\cdots b_{1}b_{0}, (42) where b_{i}\in\{0,1\} denotes the i -th bit, and b_{k-1} acts as the sign bit. In this encoding, b_{k-1}=1 indicates \Delta f<0 , while b_{k-1}=0 implies \Delta f\geq 0 . Accordingly, the circuit logic is designed such that the exponential update branch is activated only when the sign bit is in the state \ket{0} (representing positive energy differences), as illustrated in Fig. 6 . To approximate the target rotation induced by the term e^{-\frac{\beta}{2}\Delta f} , we construct a linear mapping from the binary-encoded values in F^{\prime} to the rotation angles of the coin register. Instead of evaluating the nonlinear exponential, we define a linear interpolation that reproduces its behaviour over the discretized domain of \Delta f . Specifically, for \Delta f>0 , we adopt the linear model: e^{\frac{\beta}{2}\Delta f}\;\approx\;\lambda_{0}b_{0}+\lambda_{1}b_{1}+\cdots+\lambda_{k-2}b_{k-2}, (43) where b_{i}\in\{0,1\} are the data qubits of F^{\prime} , and \{\lambda_{i}\} are real coefficients derived from an optimized linear fit. Crucially, these coefficients are constrained to guarantee monotonicity, a property sufficient to preserve the algorithm’s thermalization behavior. Theorem 1 in Appendix A provides the formal proof of validity. Note that this fit depends solely on the register size and the annealing schedule \beta_{k} , making it independent of the specific instance values or the functional form of the objective f(\mathbf{x}) . It is worth emphasizing that the purpose of this linearization is not to reproduce the exponential function with high numerical precision, but rather to preserve the correct thermal ordering of states according to their relative energies. In the Metropolis acceptance rule, the exponential factor e^{-\beta\Delta f/2} acts as a weighting term that suppresses transitions toward higher-energy configurations. Therefore, the algorithm only requires a monotonic mapping between \Delta f and the rotation amplitudes in Eq. ( 40 ) to ensure that \Delta f_{1}>\Delta f_{2}\Rightarrow A(\mathbf{x}_{1},\mathbf{x}^{\prime}_{1})0.99 ), confirming the predicted \mathcal{O}(nd) scaling dominated by the system and proposal registers S and S^{\prime} . The fitted slope also incorporates additive contributions from the auxiliary registers (F,F^{\prime},R,C) , illustrating a predictable and nearly affine growth of the total qubit requirement with the encoded problem size. In this work, the following Toffoli-equivalent cost model is adopted 25 ; 26 ; 14 . Each multi-controlled X gate (MCX) with n_{c} control qubits contributes C_{\mathrm{MCX}}=2n_{c}-3, (47) Toffoli-equivalents. Controlled unitaries (CU) follow a similar scaling, as their non-Clifford cost increases linearly with the number of control qubits 26 : C_{\mathrm{CU}}=2n_{c}-2. (48) Controlled-SWAP gates are automatically decomposed into MCX operations during synthesis; consequently, their resource footprint is captured directly via the total MCX count and depth. By definition, a standard Toffoli (CCX) gate corresponds to exactly one Toffoli-equivalent. Regarding single-qubit rotations, the cumulative contribution of T and T^{\dagger} gates is estimated based on a standard distillation overhead of one Toffoli-equivalent per seven T -type gates: C_{T}=\frac{N_{T}+N_{T^{\dagger}}}{7}, (49) where N_{T} and N_{T^{\dagger}} denote the total counts of T and T^{\dagger} gates, respectively. All remaining Clifford gates, including CNOT and Hadamard are considered to have negligible Toffoli cost. Each multi-controlled operation is thus mapped to its Toffoli-equivalent contribution, capturing the dominant non-Clifford component of the total circuit depth and logical resource requirements. This counting scheme provides a unified and hardware-agnostic measure of logical complexity, independent of the specific gate decomposition or hardware connectivity. To apply this cost model, the full algorithm is implemented using the Qiskit framework 18 . We utilize standard synthesis routines to decompose the high-level circuit components into the specific fundamental operations defined above—including MCX gates, single-qubit T/T^{\dagger} rotations, and Clifford primitives. This breakdown allows for a direct mapping between the synthesized circuit topology and the Toffoli-equivalent metrics, enabling a precise and deterministic calculation of the total resource overhead. We consider families of integer linear programs of the form in Eq. ( 1 ), with n\in[1,9] variables and m^{\prime}\in[1,7] linear constraints. Coefficients c_{i} and constraint entries g_{i},h_{j} are randomly sampled from bounded integer intervals, transforming the equality constraints into two inequality constraints, and each variable is represented using d -qubit two’s-complement encoding. For each instance, we record the total number of qubits required and the equivalent Toffoli count. Among the possible annealing steps, we focus specifically on the first iteration of the quantum Metropolis operator W , which captures the fundamental cost and scaling characteristics of the algorithm under identical thermalization conditions, with a fixed inverse temperature \beta=1 . A more detailed study of the effect of the annealing schedule and the number of iterations on convergence and accuracy is presented in Sec. VI.2 . VI.1.2 Simulation results Figure 10: Histogram of the measured probability distribution obtained after applying the Randomized Quantum Metropolis algorithm for two variables and three discretization qubits per variable. Each bar represents the probability of measuring a specific computational basis state \ket{x_{1},x_{2}} , corresponding to a discrete point in the feasible region defined by the constraint -x_{1}+x_{2}\geq 0 . The optimization objective is f(x_{1},x_{2})=-2x_{1}-2x_{2} , and the resulting distribution illustrates the progressive thermalization process toward the global minimum. With three qubits per variable, the search domain spans the square [-4,3]\times[-4,3] . Figure 7 illustrates the scaling of the Toffoli-equivalent gate count as a function of the total qubit register size. These results, derived from 1000 random instances per configuration at \beta=1 , reveal a strictly linear relationship between logical depth and circuit width across all regimes. Crucially, while the scaling remains linear, the slope of the regression fit steepens systematically with the number of linear constraints m^{\prime} . This behavior directly reflects the resource overhead associated with the constraint-checking logic—specifically, the multi-controlled operations required by the conditional update operator F (as detailed in Sec. V.0.3 ). Consequently, the data confirms that increasing the constraint density contributes additively to the logical cost coefficient, without altering the fundamental linear scaling of the one step operator W . Complementing this analysis, Fig. 8 isolates the effect of the number of variables by fixing the constraint count and varying the problem dimensionality. In this regime, the Toffoli-equivalent count continues to exhibit a linear dependence on the total number of qubits, with a slope that remains essentially invariant across different values of n . Increasing the number of variables results in a vertical upward shift of the regression lines—indicating a larger baseline circuit cost—but does not alter the asymptotic scaling rate. This behavior indicates that the number of variables affects the offset of the resource count, while the dominant scaling is governed by the total qubit budget rather than by n alone. Figure 9 addresses the spatial complexity of the construction by plotting the total number of qubits as a function of the product between the number of variables n and the number of discretization qubits d used to encode each variable in two’s-complement form. The data exhibit a linear dependence, confirming that the total qubit requirement scales proportionally with the effective encoded problem size nd=n\log_{2}N , where N denotes the size of the discretized domain per variable. Minor deviations from ideal linearity arise from secondary structural contributions, such as ancillary registers used for constraint evaluation and the bit-width required to store intermediate arithmetic results in the F^{\prime} register. These effects introduce only mild dispersion and do not modify the underlying linear trend, in agreement with the analytical register estimates summarized in Table 1 and Eq. ( 46 ). Taken together, Figs. 7 , 8 , and 9 establish that both the logical depth (measured in Toffoli-equivalent gates) and the spatial complexity (measured in total qubits) of the quantum Metropolis operator W scale linearly with the encoded problem size. While the classical search space grows exponentially with the discretization precision as [-2^{d-1},\,2^{d-1}-1] , the required quantum resources scale only as \mathcal{O}(nd) . This separation between exponential classical complexity and polynomial quantum resource growth highlights a key advantage of the proposed formulation: it enables coherent exploration of an exponentially large feasible region while maintaining predictable and scalable circuit complexity. Error bars are omitted from the reported figures, as the objective of the analysis is to reveal asymptotic scaling behavior rather than statistical variability. The quantities plotted correspond to deterministic circuit constructions, and the observed trends directly reflect algorithmic complexity bounds rather than stochastic fluctuations. VI.2 Precision and convergence analysis In this section we move beyond the analysis of individual operators and simulate the complete algorithm described in Sec. III . The annealing schedule implemented in our simulations starts from a fully “hot” configuration at \beta=0 and gradually cools toward \beta\rightarrow\infty . This is achieved by combining a linear increase of \beta in the early stages ( 0\leq\beta\leq 1 ) with an exponential decay of the acceptance amplitude. Each thermal block consists of a randomly selected number of internal repetitions, T\in[1,3] , corresponding effectively to q=2 qubits of randomization depth in the quantum walk. Intuitively, when consecutive \beta values are closer—i.e., when the temperature decreases more smoothly—the system requires fewer randomization steps to maintain detailed balance between successive Gibbs-like states. However, this also implies that more distinct \beta_{k} stages (larger Q ) must be executed to reach the same final temperature. Conversely, a faster cooling schedule reduces the total number of annealing stages but requires more mixing per stage to achieve comparable convergence. The chosen schedule thus represents a practical heuristic trade-off between coherence, convergence stability, and total circuit depth, tuned to each problem’s energy landscape and constraint configuration. Figure 1 illustrates the evolution of the probability distribution throughout the annealing process for a representative instance of the integer linear program. The depicted case corresponds to an instance with two optimization variables, each encoded on two qubits in two’s-complement form, defining a discrete search space of [-2,1]\times[-2,1] . In subsequent experiments shown Fig. 10 , we increase the discretization to three qubits per variable, expanding the hypercubic search domain to [-4,3]\times[-4,3] and thereby raising the maximum qubits of the qiskit simulators. The algorithm employs a \beta -scheduling scheme that gradually increases the inverse temperature, effectively performing a quantum analogue of simulated annealing. As \beta grows, the distribution concentrates progressively around configurations with lower energy values, until it converges with high probability to the global or local minimum of the cost landscape. This thermalization process is fully coherent and reversible, while partial measurements at selected steps remove entanglement with ancillary registers, effectively purging computational “garbage” and preserving only the physically relevant amplitudes. A distinctive feature of this quantum Metropolis formulation is that, unlike amplitude-amplification schemes such as Grover’s algorithm, the probability of measuring the optimal state does not exhibit oscillatory behavior as a function of the number of iterations. In practice, the repeated application of distinct operators W_{k} , each corresponding to a progressively lower effective temperature, combined with the partial measurements of the coin and movement registers, leads to a steady concentration of probability around low-energy configurations. While a strict proof of monotonicity is beyond the present scope, the numerical simulations consistently show a non-oscillatory, cumulative increase in the occupation probability of near-optimal states. This behavior can be interpreted as a consequence of measurement-induced state purification together with the \beta -dependent cooling schedule, which together suppress transitions that would otherwise repopulate higher-energy configurations. Hence, even though the optimal number of W_{k} applications cannot be fixed a priori—since it depends on the specific cost landscape and annealing path—the observed convergence remains stable and qualitatively monotonic across all tested instances. The key advantage is that, in the quantum case, the process exhibits a quadratic gain in convergence rate with respect to classical random-walk mixing 30 , while retaining the same qualitative monotonic behavior of probability concentration. In summary, the results shown in Fig. 1 and Fig. 10 demonstrate how the proposed quantum Metropolis dynamics progressively amplifies the occupation probability of the optimal solution as annealing proceeds, evidencing both the correctness of the \beta -dependent construction and the robustness of the partial measurement mechanism in maintaining a physically consistent thermal evolution. VII Conclusions This work introduces the first fully quantum Metropolis–Hastings algorithm for integer linear programming, implemented entirely as reversible quantum circuits without quantum-RAM assumptions or classical pre/post-processing. This represents a genuine advance in quantum constraint programming: all arithmetic—objective evaluation, constraint verification, acceptance filtering—occurs coherently within the quantum circuit, enabling simultaneous evaluation of candidate solutions across the entire feasible polytope in superposition. This capability is fundamentally unavailable in hybrid approaches (e.g., quantum oracles with classical search) or variational methods (QAOA, VQE) that require repeated quantum–classical feedback loops. A central contribution of this study is the explicit resource characterization: one step of the algorithm requires \mathcal{O}(n\log_{2}N) logical qubits and \mathcal{O}(k) Toffoli-equivalent gates, where n is the number of variables, N the search interval, and k the total qubit count. This linear scaling with problem dimension—despite the exponential size of the classical search space—is rigorously derived and validated numerically across more than 1500 instances (see Figs. 7 , 8 , and 9 ). Crucially, while the total time to convergence depends on the spectral gap—reflecting the NP-hard nature of the problem—the implementation cost per step is guaranteed to remain polynomial. Unlike classical branch-and-bound methods where worst-case memory and branching costs can become intractable, our framework offers predictable, linear scaling of the quantum hardware resources required to execute the Metropolis operator. Beyond finding the global optimum, the algorithm naturally generates a structured ranking of near-optimal solutions weighted by their Boltzmann probability. This capability is particularly valuable in practical applications such as scheduling, resource allocation, and design optimization, where high-quality feasible solutions are often preferred over exhaustive optimization. This behavior distinguishes our approach from both classical heuristics and quantum approximate solvers, which typically target a single best solution. Numerical simulations confirm convergence toward the global minimum with high probability (see Fig. 1 and Fig. 10 ) and validate the predicted linear resource scaling (Figs. 7 – 9 ). The algorithm’s robustness stems from its fully reversible construction and the thermalizing dynamics of the quantum Metropolis walk, which progressively concentrate probability amplitude on low-cost feasible configurations without the oscillation risks inherent in amplitude amplification schemes. Critically, this work addresses the theory–practice gap in quantum optimization by providing a framework whose resource requirements are characterized at the logical level and whose implementation is amenable to systematic error correction. While the method assumes access to fault-tolerant quantum computers, this transparent resource accounting enables principled technology roadmapping: practitioners can estimate physical qubit overheads based on realistic error rates and plan deployment timelines accordingly. Future directions include: (i) integration of problem-specific proposal mechanisms to exploit structure in integer linear programming instances, (ii) extension to non-linear and mixed-integer nonlinear programming, and (iii) experimental validation on near-term quantum processors using error mitigation techniques. Overall, the proposed framework opens a clear pathway toward practical quantum advantage in combinatorial optimization as quantum hardware matures. VIII