Feedback-based quantum optimization and its classical counterpart: quantum advantage and the power of classical algorithms Preprint: APS/123-QED

Tomohiro Hattori, Takuya Hatomura · 2026

Read Feedback-based quantum optimization and its classical counterpart: quantum advantage and the power of classical algorithms Preprint: APS/123-QED by Tomohiro Hattori, Takuya Hatomura (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-13082.txt.

Introduction

Hattori and Hatomura build the non-quantum twin of feedback-based quantum optimisation, using the quantum-classical correspondence of spin systems to probe possible quantum advantage. They pit the FALQON quantum algorithm and its variant against their non-quantum twins. They then test quantum and non-quantum methods on small cases and non-quantum methods on large ones. Quantum methods win on solution quality while non-quantum methods converge faster, and one non-quantum method scales notably for higher-order binary optimisation problems.

Catalog record

CREATORTomohiro Hattori, Takuya Hatomura
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE46453
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.13082

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Feedback-based quantum optimization and its classical counterpart: quantum advantage and the power of classical algorithms Preprint: APS/123-QED Tomohiro Hattori, Takuya Hatomura Abstract Feedback-based quantum optimization is a quantum approach to combinatorial optimization. In this paper, we introduce the classical counterpart of feedback-based quantum optimization by using the quantum-classical correspondence of spin systems to discuss the possibility of quantum advantage. It also enables us to develop higher-order theory of a previously proposed classical approach to feedback-based quantum optimization. First, we compare the feedback-based algorithm for quantum optimization (FALQON) and its variant with their classical counterparts. Then, we perform benchmark tests of various quantum and classical algorithms with small-scale instances, and of classical algorithms with large-scale instances. Main findings are that (i) quantum algorithms can be advantageous to classical algorithms in terms of the quality of solutions, while classical algorithms tend to show faster convergence than quantum ones, and (ii) one of the classical algorithms discussed in this paper shows significant scalability for higher-order unconstrained binary optimization problems. These findings highlight the importance of quantumness and the usefulness of classical approaches. I Introduction Combinatorial optimization is ubiquitous, with numerous applications across fields such as logistics 69 ; 22 ; 64 , materials science 71 ; 67 and finance 20 ; 84 . The importance and applications of solving combinatorial optimization problems have been broadened. However, in computational complexity theory, most combinatorial optimization problems are classified as NP-hard, which indicates that there are no polynomial algorithms 21 . In other words, exactly solving combinatorial optimization problems requires exponential computational cost with respect to the number of variables. Combinatorial optimization problems can be formulated as quadratic unconstrained binary optimization (QUBO) forms, or equivalently, as the ground-state search in Ising spin-glass models 56 . Various physical systems have been studied as platforms for solving combinatorial optimization because of the latter formulation, and a wide range of solvers has been developed, including quantum annealers 44 and quantum-inspired machines 82 ; 37 ; 18 ; 25 . Numerous approaches have also been proposed under the QUBO (Ising) framework. These include black-box optimization methods 51 ; 41 ; 38 ; 60 ; 63 ; 16 ; 78 ; 62 , large-scale combinatorial optimization 48 ; 47 ; 39 ; 4 ; 49 ; 30 ; 31 ; 35 , and constrained combinatorial optimization 33 ; 32 ; 53 ; 54 ; 34 ; 46 . Higher-order unconstrained binary optimization (HUBO) is higher-order formulation of QUBO and also has many applications 61 ; 13 ; 66 ; 73 ; 45 . To solve HUBO problems using QUBO solvers, higher-order interactions must be reduced to quadratic forms 7 ; 40 ; 52 ; 17 ; 19 . However, the proposed approaches typically require the introduction of auxiliary variables, leading to an increase in problem size and consequently to a degradation in performance. Therefore, directly handling HUBO formulation is considered more efficient 36 . The feedback-based algorithm for quantum optimization (FALQON) 57 ; 58 is one of the quantum algorithms for combinatorial optimization. A key idea of FALQON is the use of the Lyapunov control theory 15 for reducing a cost function, and a main feature is the unnecessity of classical optimization unlike variational quantum algorithms 9 . There are many studies based on FALQON, such as performance improvement 8 ; 70 ; 3 ; 59 ; 11 ; 76 , constrained combinatorial optimization 2 , noise mitigation techniques 1 , and the ground-state preparation 55 ; 79 . One of the drawbacks is the substantial computational cost for iterative feedback due to the quantum version of Lyapunov control. A quantum iteration-free method using machine learning was proposed 68 , but practical realization still costs heavily. The counterdiabaticity-assisted classical algorithm for optimization (CACAO) is a specific case of FALQON that can be treated as a classical algorithm without substantial computational overhead 29 . This algorithm is derived from FALQON with the idea of local counterdiabatic driving 72 ; 14 ; 27 ; 81 ; 77 ; 6 ; 65 ; 28 , which has the potential to improve quantum algorithms 83 ; 80 ; 10 ; 59 ; 11 . CACAO exhibits faster convergence to low-energy states than FALQON, whereas it does not always converge to lower-energy states than FALQON. Although it is related to FALQON, it is not exactly the classical counterpart of FALQON. In this paper, we introduce the classical counterpart of feedback-based quantum optimization by using the quantum-classical correspondence of spin systems and the canonical equations of motion for classical spins. This theory enables us to construct the exact classical counterparts of feedback-based quantum optimization algorithms and to discuss the possibility of quantum advantage. To be specific, we consider the classical counterparts of FALQON (CC-FALQON) and inhomogeneous FALQON (CC-iFALQON), where inhomogeneous FALQON (iFALQON) is a FALQON-like algorithm inspired by inhomogeneous driving for quantum annealing 74 ; 75 , and compare the performance of these algorithms. Moreover, this theory also enables us to develop the higher-order theory of CACAO (HOT-CACAO). In particular, we consider the introduction of the second-order counterdiabatic term to CACAO, which we simply call HOT-CACAO in this paper, and also introduce HOT-CACAO+, which includes all the terms we discuss in this paper. We perform benchmark tests of these algorithms with large instances of HUBO. This paper is organized as follows. In Sec. II , we explain the feedback-based quantum optimization algorithms (FALQON and iFALQON). In Sec. III , we introduce the classical counterparts of the feedback-based quantum optimization algorithms (CC-FALQON and CC-iFALQON), and extend the classical algorithm (CACAO) to the higher-order classical algorithms (HOT-CACAO and HOT-CACAO+). In Sec. IV , we perform benchmark tests of the quantum and classical algorithms. Further discussion is provided in Sec. V . We conclude the paper in Sec. VI . II Quantum algorithms First, we explain the general idea of feedback-based quantum optimization, and then introduce the concrete algorithms. Finally, we mention the way of implementation. Throughout the paper, the Pauli matrices of N quantum spins are expressed as \{\hat{X}_{i},\hat{Y}_{i},\hat{Z}_{i}\}_{i=1}^{N} . II.1 Feedback-based quantum optimization In this section, we give a brief summary of feedback-based quantum optimization that uses the Lyapunov control theory proposed in Refs. 58 ; 57 . We consider real-time quantum dynamics \mathrm{i}\frac{\partial}{\partial t}|\Psi(t)\rangle=\hat{H}(t)|\Psi(t)\rangle, (1) with the Hamiltonian in the following form: \hat{H}(t)=\beta_{0}(t)\hat{H}_{\mathrm{P}}+\sum_{k}\beta_{k}(t)\hat{V}_{k}. (2) Here, \hat{H}_{\mathrm{P}} is the problem Hamiltonian consisting of the Pauli-Z operators and \{\hat{V}_{k}\}_{k\neq 0} are driving terms that do not commute with the problem Hamiltonian. When the parameters \{\beta_{k}(t)\}_{k\neq 0} are given by \beta_{k}(t)=\mathrm{i}\langle\Psi(t)|[\hat{H}_{\mathrm{P}},\hat{V}_{k}]|\Psi(t)\rangle, (3) the cost function \displaystyle E_{\mathrm{P}}(t)=\bra{\Psi(t)}\hat{H}_{\mathrm{P}}\ket{\Psi(t)}, (4) decreases with time evolution because (d/dt)E_{\mathrm{P}}(t)\leq 0 always holds. Note that \beta_{0}(t) is an arbitrary function. Owing to the state-dependence of the parameters ( 3 ), this optimization must be performed in an iterative way, and thus it is called feedback-based quantum optimization. II.2 Algorithms We list the quantum algorithms discussed in this paper. II.2.1 FALQON In the original proposal of FALQON 58 ; 57 , the following Hamiltonian \hat{H}(t)=\hat{H}_{\mathrm{P}}+\beta^{X}(t)\sum_{i=1}^{N}\hat{X}_{i}, (5) was considered. The single parameter \beta^{X}(t) is given by \beta^{X}(t)=\mathrm{i}\langle\Psi(t)|\left[\hat{H}_{\mathrm{P}},\sum_{i=1}^{N}\hat{X}_{i}\right]|\Psi(t)\rangle, (6) which guarantees the reduction of the cost function ( 4 ). II.2.2 iFALQON As summarized above and mentioned in Refs. 58 , we can introduce multiple parameters. For example, we

Read the complete text