Abstract Quantum annealing (QA) offers a promising approach for solving constrained combinatorial optimization on near-term quantum devices. It encodes solutions into the ground states of the Ising problem Hamiltonians through penalty terms and penalty parameters to enforce constraints. We propose a variational determination framework to address the issue of penalty parameter selection through three progressively generalized methods: the Frozen method variationally adjusts parameters in a tunable Hamiltonian to prepare evolved states minimizing the energy of a target Hamiltonian with Frozen parameters; the Time-Transfer method applies optimized parameters to longer annealing times; and the Full-Transfer method extends this approach across both system sizes and annealing durations. The effectiveness of these methods stems from energy minimization steering the evolution toward the low-energy subspace. Evaluated on vertex cover problems over 40 randomly generated 12-vertex 3-regular graphs, the Frozen method improves the average single-run success probability from 0.27 ± 0.02 to 0.62 ± 0.03 at t a = 10 , and reduces the average number of runs required for 99.9% success probability by 3.8 times at t a = 2 (including optimization overhead). Crucially, both Time-Transfer method and Full-Transfer method achieve single-run fidelity improvements comparable to the Frozen method, while reducing the number of runs required for 99.9% success probability at t a = 2.5 by 6.63 times and 6.4 times, respectively. The speedup of the Time-Transfer method excludes initial optimization at t a = 2 , whereas Full-Transfer method provides end-to-end acceleration. Our variational framework establishes that optimization-informed short-time QA can match the performance of extended schedules, offering a practical approach for current quantum devices.
Abstract Quantum annealing (QA) offers a promising approach for solving constrained combinatorial optimization on near-term quantum devices. It encodes solutions into the ground states of the Ising problem Hamiltonians through penalty terms and penalty parameters to enforce constraints. We propose a variational determination framework to address the issue of penalty parameter selection through three progressively generalized methods: the Frozen method variationally adjusts parameters in a tunable Hamiltonian to prepare evolved states minimizing the energy of a target Hamiltonian with Frozen parameters; the Time-Transfer method applies optimized parameters to longer annealing times; and the Full-Transfer method extends this approach across both system sizes and annealing durations. The effectiveness of these methods stems from energy minimization steering the evolution toward the low-energy subspace. Evaluated on vertex cover problems over 40 randomly generated 12-vertex 3-regular graphs, the Frozen method improves the average single-run success probability from 0.27 ± 0.02 to 0.62 ± 0.03 at t a = 10 , and reduces the average number of runs required for 99.9% success probability by 3.8 times at t a = 2 (including optimization overhead). Crucially, both Time-Transfer method and Full-Transfer method achieve single-run fidelity improvements comparable to the Frozen method, while reducing the number of runs required for 99.9% success probability at t a = 2.5 by 6.63 times and 6.4 times, respectively. The speedup of the Time-Transfer method excludes initial optimization at t a = 2 , whereas Full-Transfer method provides end-to-end acceleration. Our variational framework establishes that optimization-informed short-time QA can match the performance of extended schedules, offering a practical approach for current quantum devices.
Quantum annealing (QA) is a promising quantum computing paradigm for solving optimization problems. However, the performance of QA is often limited by issues such as slow convergence rates and sensitivity to parameter settings. This paper presents a novel optimization method designed to address these limitations. The approach introduces refined parameters and an adaptive strategy to enhance the algorithm's convergence speed and solution accuracy. We explore the application of this optimized QA method to complex problems, demonstrating its potential for improved performance. The core of the optimization lies in modifying the annealing schedule and incorporating a dynamic adjustment of the magnetic field strength, denoted as H(t), where t represents time. The objective function to be minimized is typically represented as E[s], where s is the state vector of the quantum annealer. We introduce a variance reduction technique, denoted as σ(t), which is dynamically adjusted based on the error estimates of the current state. The overall optimization process can be summarized as: minsE[s]subject todtdS=−β(t)E[s]−γ(t)H(t)s where β(t) is the annealing rate and γ(t) is the magnetic field strength. The adaptive strategy involves updating β(t) and γ(t) based on the error in the current solution, aiming to reduce the variance σ(t) and improve the convergence. The theoretical analysis suggests that this approach can significantly reduce the computational cost and improve the solution quality compared to traditional QA methods. Furthermore, we investigate the impact of different parameter settings on the algorithm's performance, highlighting the importance of careful tuning for optimal results. The results demonstrate a notable improvement in solution quality and convergence speed across various benchmark problems.
Quantum annealing generally samples degenerate ground states with nonuniform probabilities. This unfair sampling depends on how the driver Hamiltonian couples these states near the end of annealing. For combinatorial optimization problems with a cardinality constraint, the penalty method and constrained quantum annealing (CQA) differ in these couplings. The transverse-field driver of the penalty method does not directly couple feasible ground states, whereas the fully connected XY driver of CQA couples pairs of them related by a single spin exchange. We investigate how this difference affects ground-state sampling, using closed-system simulations of random graph bipartitioning instances together with degenerate perturbation theory. For the instances studied, the conditional ground-state distribution of penalty-based quantum annealing approaches that of CQA at sufficiently large penalties and long annealing times. This convergence can be explained by the effective Hamiltonian of penalty-based quantum annealing, in which virtual single-spin flips to infeasible states generate a second-order interaction proportional to the CQA driver projected onto the feasible ground-state manifold, which is the leading term of the effective Hamiltonian of CQA. In the numerical simulations, the Jensen--Shannon divergence between the conditional ground-state distributions of penalty-based quantum annealing and CQA decreases approximately as the inverse square of the penalty-to-objective energy ratio, consistent with the perturbative analysis. This correspondence between the effective Hamiltonians extends to equal-weight fixed-magnetization constraints under the same perturbative conditions, providing a common mechanism for sampling bias in the two implementations.
I present a hybrid quantum-classical framework for constrained combinatorialoptimization based on fixed-schedule Trotterized Quantum Annealing (TQA). Theproposed approach combines Lagrangian-inspired penalty encoding, linearprogramming (LP)-guided problem decomposition, and static interaction pruning toimprove the sampling of high-quality feasible solutions while limiting quantum circuitcomplexity. Unlike conventional variational approaches that rely on iterative classical optimization ofcircuit parameters, my method employs a predetermined annealing schedule and penaltycoefficients determined during classical preprocessing. The constrained objective isencoded using a linear weight term and a quadratic penalty on deviations from theassigned capacity. LP relaxation guides the allocation of the global capacity betweenindependent problem groups, while static pruning reduces the number of pairwiseinteractions in the problem Hamiltonian. The resulting Trotterized evolution isimplemented without iterative optimization of quantum circuit angles. The framework is investigated on a 24-item knapsack problem, decomposed into twoindependent 12-variable subproblems and executed on quantum hardware. It builds onmy earlier experiments with ungrouped TQA on knapsack instances of 10 to 15 items, inwhich I used a sampling budget of 10 × 2^N shots. Because the fixed, coarse Trotterizedschedule spreads the probability over many configurations, the best solutions have smallindividual probabilities: with smaller budgets their position in the frequency ranking wasdominated by sampling noise and they could remain far down the list, whereas at 10 ×2^N shots they moved towards the front. In several runs on 15 items the optimalsolution was found within the top 1 % of the most frequently sampled configurations.These observations are empirical, drawn from a large number of runs rather than acontrolled scaling study. They suggest that the method may offer an effective way ofaccessing near-optimal solutions without relying on repeated variational parameteroptimization, although it requires a higher sampling budget in the experimentsconsidered. For the 24-item problem, a classical reconstruction procedure combinesindependently sampled group configurations to recover globally feasible solutions,including the exact optimum, even when the complete optimal bitstring is not observedin a single quantum measurement. These results motivate further investigation of fixed-schedule, penalty-based TQA as ahardware-oriented alternative to variational quantum optimization for constrained problems.In particular, the observed sampling behavior, feasibility-quality trade-off, andresource requirements provide a basis for systematic comparisons with CVaR-based andoptimizer-driven approaches.
Recent advances in quantum technologies have intensified the search for algo rithms that can use quantum resources effectively. Quantum annealing and hybrid quantum–classical variational algorithms are two prominent approaches in this set ting. Conventional quantum annealing follows a prescribed Hamiltonian interpo lation and may therefore be limited by small spectral gaps along that path. This Thesis investigates how algorithmic performance changes when three elements are varied: the annealing schedule (Chapter 2), the independent parameters of a digi tized evolution (Chapter 3), and the encoding of the problem (Chapter 4). For weighted MaxCut instances with anomalously small annealing gaps, opti mized smooth schedules outperform linear digitized annealing at equal circuit depth. Rather than restoring adiabaticity or enlarging the gap, the dynamics deliberately leaves the instantaneous ground state and later returns the population to the target state. Smoothness allows these digital solutions to retain their quality as continuous time controls and when transferred between related instances. The schedule restriction is then removed for a frustrated Ising ring whose anneal ing gap closes exponentially with system size. Optimizing all circuit angles inde pendently yields numerically exact ground-state preparation at the critical depth Pcr 1 =(N2−1)/4. This quadratic threshold is explained by the dimension and sym metries of the reachable free-fermion manifold, demonstrating that controllability, rather than the gap of a particular interpolation, determines the required number of digital controls. Finally, the same ring family is reformulated through the parity mapping. For the original frustrated ring, Parity-QAOA reaches the exact ground state using only single-qubit rotations, without applying the constraint unitary. The number of layers equals the number of distinct coupling values and does not grow with system size. To clarify the role of constraints, an equal-magnitude signed ring is also studied, for which the constraint unitary is essential for preparing the target ground state. Together, these results identify the shape, controllability, and encoding of a quan tum protocol as resources for overcoming limitations imposed by more restricted routes to ground-state preparation.
Quantum annealing (QA) is a method for solving combinatorial optimization problems. We can estimate the computational time for QA using what is referred to as the adiabatic condition derived from the adiabatic theorem. The adiabatic condition consists of two parts: an energy gap and a transition matrix. Most past studies have focused on the relationship between the energy gap and computational time. The success probability of QA is considered to decrease exponentially owing to the exponentially decreasing energy gap at the first-order phase-transition point. In this study, through a detailed analysis of the relationship between the energy gap, transition matrix, and computational cost during QA, we propose a general method for constructing counterintuitive models wherein QA with a constant annealing time fails despite a constant energy gap, based on polynomial energy. We assume that the energy of the total Hamiltonian is at most $\mathrm{\ensuremath{\Theta}}(L)$, where L is the number of qubits. In our formalism, we choose a known model that exhibits an exponentially small energy gap during QA, and modify the model by adding a specific penalty term to the Hamiltonian. In the modified model, the transition matrix in the adiabatic condition becomes exponentially large as the number of qubits increases, while the energy gap remains constant. Moreover, we achieve a quadratic speedup, for which the upper bound for improvement in the adiabatic condition is determined by the polynomial energy. For concrete examples, we consider the adiabatic Grover search and the ferromagnetic p-spin model. In these cases, with the addition of the penalty term, although the success probability of QA on the modified models becomes exponentially small despite a constant energy gap, we are able to achieve a success probability considerably higher than that of conventional QA. Moreover, in concrete examples, we numerically show the scaling of the computational cost is quadratically improved compared to the conventional QA. Our findings pave the way for a better understanding of QA performance.
We propose a post-processing variationally scheduled quantum algorithm (pVSQA) for solving constrained combinatorial optimization problems (COPs). COPs are typically transformed into ground-state search problems of the Ising model on a quantum annealer or gate-based quantum device. Variational methods are used to find an optimal schedule function that leads to high-quality solutions in a short amount of time. Post-processing techniques convert the output solutions of the quantum devices to satisfy the constraints of the COPs. pVSQA combines the variational methods and the post-processing technique. We obtain a sufficient condition for constrained COPs to apply pVSQA based on a greedy post-processing algorithm. We apply the proposed method to two constrained NP-hard COPs: the graph partitioning problem and the quadratic knapsack problem. pVSQA on a simulator shows that a small number of variational parameters is sufficient to achieve a (near-)optimal performance within a predetermined operation time. Then building upon the simulator results, we implement pVSQA on a quantum annealer and a gate-based quantum device. The experimental results demonstrate the effectiveness of our proposed method.